Bewegungsalgorithmus Implementierungsfrage

[stKev]

Hallo,

vor geraumer Zeit hatte ich mich mit dem A* Algorithmus beschäftigt und ihn auch erfolgreich implementieren können. Meine Klasse Pathfinder gibt mittels der Methode aStar(Node startKnoten, Node zielKnoten) eine List<Node> zurück. Diese beinhaltet den shortestPath.

Wie wäre es besser?
Soll meine Ebene, auf der die Npc sich bewegen, einen Pathfinder haben, den alle Npcs fragen können oder soll jeder Npc einen eigenen Pathfinder besitzen?

Bin mir nicht ganz sicher wie rechen intensiv das wird für eine zunehmende Npc Anzahl sowie die Spielerfigur.

Wieviel Npcs könnten von dem einen Pathfinder Objekt berechnet werden?

Kann mir da jemand einen Rat geben?

 

[Firephoenix]

Das ist abhängig von deiner Implementierung.
In der Regel kann man A* statisch implementieren, so dass es garnicht mehr nötig ist konkrete Instanzen zu erzeugen. Dadurch wird der Pathfinder parallelisierbar und es genügt einen Pathfinder für das gesamte Spiel zu verwenden.

Allerdings kann auch das beschränkt sein, wenn Entities z.B. unterschiedliche Heuristiken oder Bewertungsfunktionen für die Geländeschwierigkeit verwenden.

Eine (vermutlich recht gängige) Taktik ist es z.B. einen Pathfinder einzurichten, der in einem seperaten Thread(pool) eine bestimmte Anzahl Pfade oder eine bestimmte Anzahl Millisekunden pro Tick verbrauchen darf, weitere Pfade landen in einer Warteschlange. Dadurch lässt sich recht einfach der Rechenaufwand und der Speicherverbrauch beschränken.
Benötigt ein Entitiy einen Pfad, fragt es beim Pathfinder an und wartet. Ist dann irgendwann der Pfad berechnet, setzt das Entitiy mit dem Pfad fort.

Gruß

 

[Spacerat]

Zugegeben, ich kenn' mich nicht wirklich damit aus, aber befasse mich gerade auch mit Pfaden, welche jedoch bereits fest liegen (Bezier's). So ein Pathfinder liefert ja Anlaufpunkte (lässt sich unschwer aus dem Text entnehmen), dazu könnte man also in jeder Hinsicht schon mal einen Algo verwenden, der schon mal grob die Vorarbeit leistet (maw, einen Bezier zurückliefert). NPC spezifische Feinheiten müssten sich doch dann per De-Casteljau-Algorithmus ? Wikipedia berechnen lassen. Nur so 'ne Idee.

 

[Helgon]

Genau wie Firephoenix sagt!
Wo kommen auf einmal Bezier Curven bei nem A* her?

 

[Spacerat]

Wie gesagt, nur so 'ne Idee. Die Wegpunkte stellen die Kurve dar (Bezier n-ten Grades) und wenn mans feiner braucht, interpoliert man zwischen denen. So kann A* statisch bleiben und die Feinheiten auf Threads verteilt werden.

 

[stKev]

Danke euch!

Ich werde wohl die Variante mit einem Pathfinder Objekt und einer Warteschlange probieren.

In der Regel kann man A* statisch implementieren, so dass es garnicht mehr nötig ist konkrete Instanzen zu erzeugen. Dadurch wird der Pathfinder parallelisierbar und es genügt einen Pathfinder für das gesamte Spiel zu verwenden.

Ich muss gestehen seit dem Übergang zur OOP verwende ich gar keine statischen Elemente mehr.
Würde mich interessieren, in welchem Zusammenhang es für die Implementierung des A* (statisch) Vorteile birgt?

Du sagtest "parallelisierbar" meinst du damit "synchronized"?

Mit wem sollte die static synchronized List<Node> aStar(...) den synchronisiert werden?

Es müsste doch nur für alle Entities, die eine Bewegung durchführen wollen, diese Methode aufgerufen werden.

Würde mich freuen, wenn du mich da ein wenig erleuchten magst! :idea:

--------------------------------------------------------------------------------------

Wo wäre der Unterschied zu einem Objekt mit der aStar() Methode, das auf der ganzen Ebene bekannt ist oder einer Klasse mit einer statischen Methode aStar()?

Klar das Objekt liegt im Heap, die static Methode im Stack. Die static Methode könnt ich via import überall verwenden. Aber da könnt ich doch auch sagen ebene.getPathfinder().aStar().

Man sieht schon, wohl eher so ne ganz allgemeine Frage zum Nutzen bzw. zur Verwendung von static in OOP. Finde es derzeit eher unschön static zu verwenden. Aber ich bin auch ein "Newbie".

 

[Helgon]

Statisch weil alle Objekte die nen weg finden wollen drauf zu greifen - der pathfinder muss ja auch immer wissen wo alle anderen sich bewegenden objekte sind.
Und er meint parallel und nicht synchronisiert. das heißt, jede "such mir den weg" anfrage ist ein eigener thread.

 

[stKev]

Da sind wir quasi genau bei meiner Frage.

Wieso ein eigenen Thread erzeugen der die Methode für ein Entitie durchrechnet.
Klar, wenn n Entities die Methode gleichzeitig aufrufen wollen.

Aber, bei meinen Überlegung kam mir der Gedanken, das es doch irgendwo das Gleiche ist.
Ob jedes Entitie nun ein Pathfinder hat oder aber ich jedesmal ein Thread anlege.

Unterscheidet sich doch in der Anzahl erzeugter Objekte nicht? ???:L

der pathfinder muss ja auch immer wissen wo alle anderen sich bewegenden objekte sind

Ein Node soll besetzt oder nicht besetzt sein. Da alle Nodes auf der Ebene liegen und jeder Pathfinder mit dieser arbeitet, wäre es allen bekannt. Aber vermutlich lasse ich das, stört sicher nur den reibungslosen Durchfluss (siehe unten).

-----------------------------------------------------------------------------------------------

Vllt einmal kurz etwas zum geplanten Projekt es soll ein MazeTD werden. Also Gegner suchen ein Weg durch das Towerlabyrinth. Noch ein Helden dabei, der via Maus gesteuert für Abwechslung sorgt.
Dazu natürlich noch die Tower die plaziert werden auf der Ebene...

 

[Helgon]

Wenn der Thread die möglichen Wege ausprobiert erzeugt er kein neues "Pathfinder" Objekt. Der Thread verwendet nur die im Pathfinder vorhandenen Informationen.

 

[duzhdsLHD]

Genau wie Firephoenix sagt!
Wo kommen auf einmal Bezier Curven bei nem A* her?

Wenn du keine direkte Linie zum Ziel hast entstehen oft kantige Bewegungsmuster. Und um diese zu glätten kann man Bezierkurven einsetzen. IMHO reicht es aber meistens z.B. ein Catmull Rom-Spline zu verwenden.

 

[Helgon]

Diese Catmull Rom-Splines sehen ja echt interessant aus. Hab jetzt nur an 2D gedacht bei A*. Hab noch nie Pathfinding oder AI in nem 3D Spiel implementiert, deswegen darüber nie weiter Gedanken gemacht. Funktioniert der A* da auch? Nimmt man da dann auch einfach die Vertices als Felder oder wie läuft das da?

 

[Spacerat]

:lol: Könnt ihr mal sehen, auf was für Ideen ihr durch "unqualifizierte" Kommentare kommt.

 

[ThreadPool]

Diese Catmull Rom-Splines sehen ja echt interessant aus. Hab jetzt nur an 2D gedacht bei A*. Hab noch nie Pathfinding oder AI in nem 3D Spiel implementiert, deswegen darüber nie weiter Gedanken gemacht. Funktioniert der A* da auch? Nimmt man da dann auch einfach die Vertices als Felder oder wie läuft das da?

Ja das läuft nicht wesentlich anders. Oft wird in einem Vorverarbeitungsschritt die Welt irgendwie partitioniert und dann ein Graph der begehbaren Wege erstellt. Aber aus der Thematik bin ich schon länger raus, 3D-Pathfinding sollte bei Google aber recht aktuelles liefern. Der A* selbst ist ein allgemeiner Problemlösungsalgorithmus. Du kannst ihn für all das verwenden wenn es gilt von einem bestimmten Ausgangszustand einen definierten Zielzustand zu erreichen. Ein prominentes Beispiel abseits der Wegfindung wären ein Schiebepuzzle oder das Wasserkrugproblem.

 

[Helgon]

Ah ja klar, Graphen machen da wohl am meisten Sinn