Ich schreibe gerade ein 2D-Spiel in Javascript mit dem HTML5 <Canvas> Element. Es kommt sehr gut voran, aber ich habe ein Problem bekommen.Was ist ein guter 2D-Gitter-basierter Pfadfindungsalgorithmus?
Das Level-Design für mein Spiel ist ein Gitter (so Kosten Weg von einer Zelle nach Norden bewegen/Süd/Ost/West-Zelle 1) mit verschiedenen Hindernissen verschiedene Orte im Netz – viel wie ein Labyrinth zu besetzen, aber mit viel mehr Spielraum. Jede einzelne Stufe liegt in der Größenordnung von 400 Zellen.
Ich versuche, einen Feind zu implementieren, der den Spieler aufspürt, egal wo er ist, aber ich habe Probleme, einen der verschiedenen Pfadfindungsalgorithmen zu übersetzen, um meiner Situation zu entsprechen. Die meisten, denen ich begegnet bin (wie A * und Dijkstra) scheinen am besten für 3D- oder viel kompliziertere 2D-Situationen geeignet zu sein. Ich habe mich gefragt, ob es möglich ist, diese Algorithmen dramatisch zu vereinfachen, um sie besser für meine Zwecke zu nutzen, oder wenn etwas wie die Tiefensuche zuerst eine effizientere Alternative wäre, wenn man die Ebenengröße berücksichtigt.
Sie werden es nicht besser machen als A *, ohne ihm irgendwelche Vorkenntnisse über die möglichen Pfade zu geben (wie das Teilen Ihrer Karte in Segmente mit bekannter Konnektivität). Tiefe zuerst wäre viel (viel viel viel) langsamer als Breite zuerst. – Dave
Dies ist nicht wirklich was Stackoverflow/Stack Exchange geht; Stellen Sie eine Frage mit einer eindeutigen Antwort, keine Einkaufsfrage. Verwenden Sie auf jeden Fall, was die Leute vorschlagen, aber kommen Sie zurück, wenn Sie einen Programmierfehler haben. – Amelia
@Dave: Nun, Sie können einfach [finden Sie besser als plain-ol 'A \ *] (http://programmers.stackexchange.com/questions/197894) wenn auf ein Gitter beschränkt ist; aber JPS + A \ * ist komplizierter als nur A \ * und normalerweise nicht notwendig. –