Suche: Heuristik um den nächsten Rohstoff zu finden

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.

Im Prinzip kannst du das direkt in deinem A* einbauen. Du musst lediglich den approx_value anders berechnen.

Code:

---

approx_distance = (1.0/0.0) # = infinity
for rohstoffquelle in rohstoffquellen
  distance = luftlinie(current_node, rohstoffquelle)
  approx_distance = distance if approx_distance > distance
end
approx_value = approx_distance * MINIMALE_WEGKOSTEN

---

Und die Abbruchsbedingung prüft jetzt nicht mehr, ob du auf dem Zielfeld angekommen bist, sondern ob du auf irgendeiner Rohstoffquelle angekommen bist.

Ansonsten ist das zu 100% derselbe Algorithmus wie dein Pathfinding.

Ob eine zusätzliche Heuristik notwendig ist, hängt wohl von der Anzahl der Rohstoffquellen ab.

Es funktioniert einwandtfrei derzeit. Vielen Dank.

Allerdings dachte ich mir, dass es vielleicht dennoch sinnvoll wäre einige Knoten kategorisch auszuschließen. Vielleicht könnte ich die Anzahl der zu überprüfenden Knoten halbieren? Also, dass nur die erste Hälfte aller Rohstoffquellen via Pathfinding betrachtet wird?
Denn die gesamte Liste ist bereits nach ihrem Abstand (Luftlinie) zum Abgabepunkt sortiert.
Ich bin ein wenig traumatisiert was die Performance angeht denke ich, ich versuche wirklich das Maximum herauszukitzeln, da ich noch einiges vorhabe in das Projekt einzubauen.