du forderst ja, dass die figur zu jedem zeitpunkt kontakt mit der oberfläche des levels hat. daraus folgt, dass dein problem 2 dimensionaler natur ist (du suchst ja einen weg auf der oberfläche des levels).
A* selbst ist nur ein algorithmus, der versucht den kürzesten weg zwischen 2 punkten in einem graphen zu finden; nichts weiter. er hat also erstmal nichts mit der geometrie eines levels zu tun. die einzigen vorraussetzungen damit A* funktioniert sind, dass es
- kantengewichte und
- eine heuristik zum abschätzen des abstandes zwischen zwei knoten im graphen gibt.
das ist alles und beides ist bei deinem problem vorhanden (du kannst ja z.b. den abstand zwischen 2 punkten berechnen).
was der graph darstellt ist dem algorithmus egal.
das problem liegt also nicht am algorithmus, sondern an der konstruktion des graphen (finden der geeigneten kantengewichte (<- wegkosten) und heuristik) zu einem problem.
ich könnte mir vorstellen, dass man erstmal alle flächen die der spieler nicht betreten kann (z.b. anhand des normalvektors) eliminiert. aus den verbleibenden flächen erstellt man sich eine datenstruktur (z.b. einen baum) die darstellt wie die flächen zusammenhängen und die hoch die kosten sind sie zu beschreiten.
bewegte objekte sind in der tat ein problem. man muss hier sicher einmal den zeitpunkt der suche mit in betracht ziehen. dann kann man z.b. abschätzen ob ein objekt sich an einem punkt befindet, zum zeitpunkt da man diesen erreichen würde, etc. vielleicht kann man auch mit wahrscheinlichkeiten was machen (suche den weg mit der kleinsten/größten wahrscheinlichkeit mit einem objekt zusammenzustoßen)...
nur so ein paar gedanken.
EDIT: ich seh grad, ich hab das mit den bewegten objekten zuerst falsch verstanden (nicht genau gelesen
). ich lass es trozdem stehen, vielleicht ist es ja was brauchbares
Zitat von »"Firefly"«
erstell einfach ne 2dmap auf die du a* anwendest...
02.05.2024, 14:12
Zum Seitenanfang
