spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

A* D*

3D-Wegfindung? Wenn du an sowas denkst wie in Shootern, zb FarCry - das ist alles auf 2D-Basis. Stell dir vor du betrachtest das ganze Geschehen von oben, oft reicht das vollkommen aus.

Eine 2D-Wegfindung hab ich mal mithilfe einer kleinen Polygonklasse geschriben: Ein Polygon bestimmt die Positionen auf denen sich der Spieler befinden darf. Wenn der direkte Weg versperrt ist, sollte die Wegfindung auf dem kuerzesten Weg zum Ziel finden (am Rand des Polys) Jetzt braucht das Polygon alle Moeglichen Funktionen zur Abfrage, wie zb: Liegt der Punkt im Polygon? Schneidet eine Linie das Polygon? usw..

Dann sah die Wegfindung in etwa wie folgt aus:
1. Versuche von der Spielerposition zum Ziel zu laufen -> wenns klappt wunderbar
2. Wenn nicht: Sortiere die Eckpunkte des Polys abfallend von der Entfernung des Ziels (Stack)
3. Nimm dir einen Punkt aus dem Stack, fuege ihn einer Liste (Queue) an, und versuche zu diesem Punkt zu laufen.
4. Wenns nicht klappt, weiter bei 3.
5. In der Queue liegen die Punkte des Pfades

Da das ganze nur ein paar 2D-Koordinaten waren, war performance keine grosse Sache.. vielleicht ist dein Ansatz ja ganz ok.. wie sieht der denn aus?

Für A* nimm als Googlebegriff "astar finding" und von da aus müsstest Du Dich weiterhangeln können.

Wie gesagt, normalerweise läuft das in 2D.

Aber was, wenn der Level nicht nur eine Art Landschaft ist, sondern wirklich in alle 3 Dimensionen ungefähr gleich stark verteilt ist?
Dann wird man mit dem klassischen A* sicher nicht weit kommen. Das ist doch eher für Tile-basierte 2D-Maps geeignet.
Ich würde die 3D-Welt mit "AI-Waypoints" durchziehen und diese als Knoten in einem Graphen betrachten. Wenn du nun von A nach B willst:
- von A aus den nächsten Knoten suchen (= A')
- von B aus den nächsten Knoten suchen (= B')
- den kürzesten Weg vom Knoten A' zu B' im Graphen suchen

Im Graphen werden natürlich nur solche Knoten verbunden, zwischen denen auch physisch ein Weg existieren kann. So ungefähr könnte es ablaufen.

Jetzt könnte man jeder Verbindung zwischen zwei Knoten noch einen Kostenfaktor zuweisen und die Wegkosten zusätzlich zur zurückzulegenden Distanz als Kriterium zu nehmen.

David, diese AI-Waypoints kann man hervorragend mit dem A*-Algorithmus bearbeiten. Es ist lediglich pro Knoten eine Liste mit Verbindungen zu Nachbarknoten sowie eine heuristische Schätzdistanz zu anderen Knoten notwendig.
Der A*-Algorithmus ist keinesfalls an irgendwelche Dimensionen gebunden. Der Algorithmus selbst benutzt ja nur eine gewisse Methode zur Generierung von Nachbarknoten zu einem gegebenen Knoten sowie eine Heuristik, um die Entfernung zu jenen Knoten zu ermitteln. Wie diese Generierung und die Schätzung aufgebaut sind, ist dem Algorithmus wumpe: Das können dann Tile-basierte 2D-Landschaften sein (was sehr trivial ist), oder aber auch einzelne Punkte verteilt in einem multidimensionalen Raum.

Dynamic A*