Cornix
06.06.2011, 11:54
Guten Tag, ich habe ein neues Problem.
Es geht erneut um Performance des Pathfindings, aber diesmal um eine andere Facette.
Etwas Hintergrund:
In meinem Spiel gibt es eine Schaar von Arbeitern welche Resourcen sammeln sollen welche wiederum an verschiedenen Stellen auf der Karte in verschiedener Menge vorhanden sind.
Diese Arbeiter sollen selbstständig, wenn ein Gebiet abgesammelt ist, ein neues Sammelgebiet finden und ihre Arbeit dort fortsetzen.
Der Abladepunkt ist konstant, er ist durchgehend durch das gesamte Spiel gleich und ändert niemals seine Position.
Die einzelnen Resourcenvorkommen verschwinden falls sie abgesammelt wurden, es können jedoch im Laufe des Spiels auch neue entstehen.
Der wichtigste Punkt ist jedoch dieser, dass das gesamte Gelände sich ebenfalls verändern kann und wahrscheinlich auch wird. Was anfangs ein Fluss war oder sogar ein Meer kann sich nach längerem Spielverlauf in eine Wüste verwandeln. Die Wegkosten von dem Abladepunkt zum Rohstoff sind daher sehr variabel und könnten sich jederzeit verändern.
Eine einfache Lösung wäre es natürlich jedes Mal durch die gesamte Anzahl von Rohstoffquellen zu iterieren und die Wegkosten zu berechnen um damit die nächstliegenste Quelle zu finden. Doch ich denke bei mehreren Arbeitern könnte dies durchaus eine ganze Menge von Performance kosten.
Daher dachte ich mir, dass es vielleicht sehr viel besser wäre eine Heuristik zu verwenden welche schätzt welche Rohstoffquelle derzeit die beste ist.
Ich dachte mir, ich könnte die Rohstoffquellen bereits nach Luftlinie sortieren (nicht nach tatsächlichen Wegkosten) und dann anhand dessen schätzen wo als nächstes gesammelt werden sollte. Denn immerhin kann ich mir sicher sein, dass eine Rohstoffquelle am anderen Ende der Karte größere Wegkosten versprechen wird als eine Rohstoffquelle welche vielleicht in unwegsamen Gelände liegt jedoch dafür nah am Abladepunkt ist.
Außerdem wird der Spieler sehr wahrscheinlich versuchen das Gelände zugunsten seiner Arbeiter zu formen um möglichst einen schnellen geradlinigen Weg zur nächsten Quelle zu garantieren. Daher denke ich würde eine Heuristik wahrscheinlich in den meisten Fällen sehr gute Ergebnisse für wenig Arbeit liefern.
Ich bräuchte nun nur leider etwas Hilfe hierbei da ich, um ehrlich zu sein, niemals soetwas und sogar etwas ähnliches getan habe.
Nocheinmal was ich habe:
Ein Array mit allen Rohstoffquellen nach ihrer Entfernung (Luftlinie) zum Abladepunkt sortiert.
Die zuletzt gesammelte Rohstoffquelle eines Arbeiters (Der Arbeiter soll eine neue Quelle suchen falls die zuletztgesammelte Quelle erschöpft ist)
Die Möglichkeit zu prüfen ob ein Weg von einem Punkt zum anderen besteht und wenn ja wie groß seine Wegkosten wären.
Vielen Dank für die Hilfe.
Es geht erneut um Performance des Pathfindings, aber diesmal um eine andere Facette.
Etwas Hintergrund:
In meinem Spiel gibt es eine Schaar von Arbeitern welche Resourcen sammeln sollen welche wiederum an verschiedenen Stellen auf der Karte in verschiedener Menge vorhanden sind.
Diese Arbeiter sollen selbstständig, wenn ein Gebiet abgesammelt ist, ein neues Sammelgebiet finden und ihre Arbeit dort fortsetzen.
Der Abladepunkt ist konstant, er ist durchgehend durch das gesamte Spiel gleich und ändert niemals seine Position.
Die einzelnen Resourcenvorkommen verschwinden falls sie abgesammelt wurden, es können jedoch im Laufe des Spiels auch neue entstehen.
Der wichtigste Punkt ist jedoch dieser, dass das gesamte Gelände sich ebenfalls verändern kann und wahrscheinlich auch wird. Was anfangs ein Fluss war oder sogar ein Meer kann sich nach längerem Spielverlauf in eine Wüste verwandeln. Die Wegkosten von dem Abladepunkt zum Rohstoff sind daher sehr variabel und könnten sich jederzeit verändern.
Eine einfache Lösung wäre es natürlich jedes Mal durch die gesamte Anzahl von Rohstoffquellen zu iterieren und die Wegkosten zu berechnen um damit die nächstliegenste Quelle zu finden. Doch ich denke bei mehreren Arbeitern könnte dies durchaus eine ganze Menge von Performance kosten.
Daher dachte ich mir, dass es vielleicht sehr viel besser wäre eine Heuristik zu verwenden welche schätzt welche Rohstoffquelle derzeit die beste ist.
Ich dachte mir, ich könnte die Rohstoffquellen bereits nach Luftlinie sortieren (nicht nach tatsächlichen Wegkosten) und dann anhand dessen schätzen wo als nächstes gesammelt werden sollte. Denn immerhin kann ich mir sicher sein, dass eine Rohstoffquelle am anderen Ende der Karte größere Wegkosten versprechen wird als eine Rohstoffquelle welche vielleicht in unwegsamen Gelände liegt jedoch dafür nah am Abladepunkt ist.
Außerdem wird der Spieler sehr wahrscheinlich versuchen das Gelände zugunsten seiner Arbeiter zu formen um möglichst einen schnellen geradlinigen Weg zur nächsten Quelle zu garantieren. Daher denke ich würde eine Heuristik wahrscheinlich in den meisten Fällen sehr gute Ergebnisse für wenig Arbeit liefern.
Ich bräuchte nun nur leider etwas Hilfe hierbei da ich, um ehrlich zu sein, niemals soetwas und sogar etwas ähnliches getan habe.
Nocheinmal was ich habe:
Ein Array mit allen Rohstoffquellen nach ihrer Entfernung (Luftlinie) zum Abladepunkt sortiert.
Die zuletzt gesammelte Rohstoffquelle eines Arbeiters (Der Arbeiter soll eine neue Quelle suchen falls die zuletztgesammelte Quelle erschöpft ist)
Die Möglichkeit zu prüfen ob ein Weg von einem Punkt zum anderen besteht und wenn ja wie groß seine Wegkosten wären.
Vielen Dank für die Hilfe.