Lineare Wegfindung
- Die grundlegendste Methode der Wegfindung besteht darin, eine gerade Linie zwischen Monster und Spieler zu ziehen und das Monster in diese Richtung zu bewegen.
- Trifft das Monster auf eine Wand, bleibt es stehen, aber dieses Problem lässt sich mit der Wall-Sliding-Technik lösen, bei der es an der Wand entlanggleitet.
- Wall Sliding ist nicht nur für die Wegfindung, sondern auch für die Spielerbewegung effektiv, und viele Spiele verwenden diese Technik.
Dijkstra-Algorithmus
- Ein Algorithmus, den man in der Schule lernt und der den kürzesten Pfad vom Startknoten zu allen anderen Knoten findet.
- Man kann abbrechen, sobald der Zielknoten gefunden ist, aber es gibt keine Möglichkeit, den Algorithmus in eine bestimmte Richtung zu lenken.
- In Spielen ändert sich das Ziel eines Monsters ständig mit der Bewegung des Spielers, daher ist der Dijkstra-Algorithmus ineffizient.
A*-Suchalgorithmus
- Er verwendet die Entfernung vom Startknoten zum Ziel als Gewichtung und versucht dadurch zunächst den direkten Weg.
- Wird dieser durch eine Wand blockiert, untersucht er benachbarte Knoten und versucht, die Wand zu umgehen; bereits besuchte Knoten werden nicht erneut besucht, sodass schließlich ein Weg um die Wand herum gefunden wird.
A*-Algorithmus-Tricks
- Implizite Graph-Datenstruktur: Anstatt Knoten und eine Adjazenzmatrix oder Adjazenzliste zu verwenden, werden Pixelkoordinaten als Knoten genutzt und benachbarte Knoten dynamisch erzeugt, um den Speicherverbrauch zu senken.
- Geometrische Heuristiken: Durch die Verwendung von Tiles als Knoten wird die Suchgeschwindigkeit erhöht, und durch das Festlegen einer festen Iterationstiefe kann ein sinnvoller Fortschritt erzielt werden, ohne den Algorithmus vollständig auszuführen.
GN⁺-Meinung:
- Das Wichtigste an diesem Artikel ist, dass er verschiedene Tricks zur effizienten Implementierung des A*-Algorithmus vorstellt.
- Der A*-Algorithmus ist in der Spieleentwicklung, insbesondere auf Plattformen mit begrenzten Ressourcen, sehr nützlich zur Lösung von Wegfindungsproblemen.
- Indem gezeigt wird, wie sich die Komplexität des Algorithmus verringern und der Speicherverbrauch optimieren lässt, hilft der Artikel Einsteigerinnen und Einsteigern im Software Engineering, Wegfindungsalgorithmen besser zu verstehen und anzuwenden.
Noch keine Kommentare.