Dijkstra und A * sind alle nett und beliebt, aber welche Art von Algorithmus wurde in Warcraft 1 zur Pfadfindung verwendet?
Ich erinnere mich, dass der Feind in schalenartigen Höhlen gefangen sein könnte, was bedeutet, dass es (höchstwahrscheinlich) keine vollständigen Berechnungen von "Anfang bis Ende" gab. Wenn ich mich richtig erinnere, könnte der Algorithmus ungefähr so aussehen:
A) Bewegen Sie sich in Richtung Feind, bis Sie Erfolg haben oder eine Wand treffen
B) Wenn Sie von einer Mauer blockiert werden, folgen Sie der Mauer, bis Sie sich dem Feind nähern können, ohne blockiert zu werden, und führen Sie dann A) aus
Aber ich würde gerne wissen, ob jemand weiß :-)
[Bearbeiten] Wie Byte56 erklärt, suche ich nach einem Algo mit niedriger CPU- / Mem- / Mem-Bandbreite und wollte wissen, ob Warcraft einige besondere Geheimnisse zu liefern hat (ich habe diese Art der Wegfindung anderswo noch nie gesehen). Ich hoffe, dass dies der Fall ist mehr Übereinstimmung mit den Stapelaustauschregeln.
quelle
A, sondern wie Sie es tun könnenA. Sie werden bestimmt bessere Antworten bekommen und es wäre kein Thema (wie diese Frage ist).Antworten:
Eigentlich stellte sich heraus, dass dies eine interessantere Frage war, als ich dachte.
Video
Ich habe die "Rechtsregel" für die Pfadfindung vergessen, aber es scheint, dass das Spiel sie verwendet.
Angenommen, Sie sind in einem Keller verloren und es ist dunkel. Der einfachste Weg, einen Ausgang zu finden (falls es einen gibt!), Besteht darin, die Hand auf die nächste Wand zu legen und "der Wand zu folgen", alle Kurven zu verfolgen und durch die Spalten zu gehen, bis Sie einen Ausgang finden. Das einzige Mal, wenn dies nicht funktioniert, ist, wenn Sie zufällig eine Stange ("Insel") im Keller greifen, dann werden Sie für immer um diese Stange herumgehen.
Ich denke, das Spiel verwendet eine Variation dieser "Follow the Wall" -Regel, bis die Einheit eine Linie zum Zielpunkt findet.
quelle
Ich glaube nicht, "wie hat das X-Spiel Y erreicht?" ist technisch im Umfang dieses Stapels, aber ich werde eine Vermutung wagen, warum einige Pfadfindungsalgorithmen in einer Schüssel stecken bleiben: Sie laufen so etwas wie A *, aber nur bis zu einer bestimmten Tiefe. Dies begrenzt den Zeitaufwand für die Pfadfindung, garantiert jedoch keine umfassende Suche [was gut sein könnte, Starcraft hatte das Problem, dass Dragoner auf die andere Seite der Karte wandern und versuchen, einen Pfad zu finden].
Im oberen Szenario ist der Suchradius des obersten Orks zu klein. Der "beste" sichtbare Punkt ist mit A markiert, der "beste" schiffbare Punkt befindet sich auf der näheren Seite der Wand gegenüber von A.
Im unteren Szenario ist Punkt A jetzt navigierbar, aber Punkt B sollte der "beste" navigierbare Punkt sein, und dies wäre der Weg, den ein eingeschränktes A * einschlagen würde.
quelle