Bester Algorithmus für Pfadsuche in einer Tower Defense

Question

A habe gelesen über A * sowie D * und ähnliche, und ich bin nicht in der Lage, zwischen ihnen zu wählen. Was ist der beste Suchalgorithmus, wenn es um viele Suchen geht (50 Suchen pro Tick) und mit vielen verschiedenen Möglichkeiten?

Answer 1

Zwischen den beiden würde ich D * wählen. D * nimmt insbesondere einen besten Weg ein, aber wenn Hindernisse auftraten, wird neu berechnet. Das bedeutet, dass jeder Kriechgang eine eigene Sicht auf den Ausgangspfad haben kann, die aktualisiert wird, wenn der Kriechkörper auf Hindernisse trifft.

Solche Annahmen auf dem besten Weg mit Anpassungen im Verhalten ist etwas realistischer, als ob Sie oder ich den Weg gingen, würden wir Hindernisse nicht vermeiden, bevor Sie über sie wissen. Es berücksichtigt auch die Neuberechnung des Pfades, falls jemand (die Spieler) einen neuen Turm baut. Wenn Sie die Erweiterung der offenen Knoten gut ausbalancieren, können Sie sogar auf beiden Seiten eines Turms herumkriechen, der zentral auf dem besten Weg liegt.

Wenn Sie jedoch wirklich Spaß machen wollen, nehmen Sie einen lernbasierten Ansatz zur besten Pfadfindung. Viel interessanter als andere Lösungen. Um ein Beispiel zu sehen, schauen Sie sich etwas an wie antbuster. Vielleicht so interessant, dass es nicht ganz in das Standard Tower Defense Game Genre passt.

Answer 2

Q-Learning kann eine gute Wahl dafür sein. Q-Learning versucht, ein Raster von Penatlies/Gewinnen aufzuzeigen, die eine lokale Entscheidung in einer endlichen Welt ermutigen würden.