Hallo,

Ich habe gestern ein A* Pathfinding Konzept in 3D-Gamestudio erarbeitet. Grundsätzlich funktioniert alles sehr gut und vollkommen ohne probleme. Ich habe nur 2-3 Fragen.. Vielleicht findet sich ja jemand der Interesse hat - und wenn nur über eine Frage - zu diskutieren

1) Wenn ein Player von A nach B laufen soll muss ich natürlich erstmal überprüfen, welcher Waypoint von Player A/B am nähsten ist. Das Problem: In komplexen Levels kann es tatsächlich sein, dass der nähste Waypoint nicht der nähste ERREICHBARE Waypoint ist (z.B. könnte dieser hinter einer Wand oder hinder einem magischen Schild oder was weiß ich liegen..). Wie geht ihr damit um?

2) Wenn waypoints nicht sehr engmasching im Level verteilt sind (spart natürlich fps und nerven), dann kann es teils zu unlogischen Bewegungen kommen. Beispiel:



Der weg den der Spieler hier gehen würde wäre: y->w2->w3->z.
Viel menschlicher wäre aber wenn der Spieler direkt an der Wand entlang gehen würde und nicht erst den unglaublich unrealistischen weg von y zu w2 bewältigen müsste.

Es wäre möglich dauerhaft während des laufens zu tracen ob bereits einer der folgenden Waypoints erreichbar ist. Das wäre aber erstens langsam und zweitens würde es immer noch beschissen aussehen, weil die erste Richtung des Players nunmal richtung w2 ist...

Dann bleiben nur noch mehr Waypoints ==> wiedr sehr langsam.
Wie löst ihr dieses Problem?



3) Crowd Managment: Hat sich damit schon mal jemand auseinander gesetzt? Die Bewegung von vielen Entities aufeinmal (z.B. in einem Strategie-Spiel)? Es wäre ja vollkommen bescheuert hier jedes Entitiy einzeln zu berechnen.

Irgendwelche Erfahrungen vorhanden?

4 (und letztens)) Einheiten Kollision. Wenn jemand schon mal hier ein A* Pathfinding Script erarbeitet hat wird er auch sicher schon auf das Problem gestoßen sein, dass bewegliche Einheiten auf den Weg kollidieren können. Wie seid ihr mit diesem Problem umgegangen?

Vielen Dank im vorhinein,
mit freundlichen Grüßen,
TechMuc

Please, could you translate it in to English?

There are already several A* dll's for 3dGS, as far as I know.
I also can't help without english text.

Just use more waypoints to solve the w3->w2 problem. Another way is to save regions instead of waypoints and connect them. That way you can even find out in which area your player is.

1. Ich glaub da musst du c_trace verwenden oder wie be IntenseX die conntections zwischen den waypoints vorspeichern damit du weiß von welchem waypoint man zu welchem kann.

2.Mehr waypoints würde ich auch sagen.

3.Hab noch eine Erfahrung damit aber du könntest immer gruppen machen und in jeder gruppe gibt es einen leader. Das ist die Entity die alles berechnet als den path und die anderen sind dann immer an der leader position +- x/y...

4.Da musst du ein dynamic obstacle avoidance script schreiben. Schau dir dazu auch mal IntenseX Pathfinding an. Da werden Repulsing vectors genutzt

Es ist vor allem wichtig zu wissen, das nicht nur eine
Methode ALLES erledigen sollte.

Das A* (oder ähnliches) Pathfinding sollte als "Grober" Wegweiser für die Entity fungieren.
Es ist wie beim Autofahren: die Stadtkarte zeigt dir den Weg, nicht aber jeden Bordstein und jedes andere Auto.

Also:

Schritt 1:
bestimmen von ereeichbaren Pathfinding Nodes (trace benutzen),
nimm die Node, die am nächsten ist, und möglichst auf gleicher Höhe ist.
(das gleiche für das Ziel zum bestimmen der End-Node)

Schritt 2:
A* (oder ähnliche Methode) bestimmt die Folge der Nodes
die abzulaufen sind (Stadplan)

Schritt 3:
Eine dynamische Player-Bewegungsroutine läuft nun den Weg ab
(übrigens eine der Schwachstellen bei Intense X)

Die Playerbewegung ist eine der wichtigsten funktionen:
sie sollte:
durch Traces versuchen, die Entity immer in einem bestimmten
Abstand zum Untergrund und den Seiten zu halten
(wie eine Art "Hovercraft")
Dadurch verringert Du dramatisch Kollisionen mit Kanten
und! anderen Entities.
So gibst Du der Entity einen entgegengesetzen Push zu Tracerichtung wenn ein Hinderniss zu nahe kommt.
Die Hauptkraft bewegt den Spieler in die berechnete Richtung zum
Zielpunkt oder Der A* Zielnode.

Durch dieses Verfahren wird auch automatisch anderen Spielen
ausgewichen.

Ich benutze 3 (lange) Traces nach vorne, einen nach unten und zwei zur Seite, um mich immer in einem Mindestabstand zum Boden und den Wänden zu halten.


Ansonsten:
Durch Einführen einer gewissen Beschleunigung und Trägheit
bewegt sich die Entity auch Menschlicher (weniger Zackiege Bewegung)

Viele Pathfinding Nodes machen die Wege eleganter, erhöhen aber auch den Rechenaufwand und Erstellungsaufwand, UND!
die Enity versucht zu genau an einen bestimmten Punkt zu gelangen, der Wohlmöglich von einer anderen Entity besetzt ist.
Die Entity sollte nur versuchen in die Nähe der Node zu gelangen.

Soviel zum Grundkonzept

Moin,

dann werde ich mal versuchen mit meinem Halbwissen zu helfen ...

1.) Es muss immer geprüft werden, ob die Erreichbarkeit gegeben ist (entweder mittels eines c_trace oder einem ähnlichen Ansatz), da die reine Navigation zu einem Wegpunkt letztendlich noch keine Navigation zu einem bestimmten Koordinatenpunkt darstellt.

2.) Grundsätzlich wirst Du nicht um mehr Waypoints herumkommen ... A* (oder auch andere Algorithmen) sind allesamt von einem hinreichend "feinen" Grid abhängig. Um Wände herum werden immer Waypoints an den Ecken (weit genug von der Wand entfernt) notwendig sein. In engen Korridoren kann man Waypoints "in der Mitte" platzieren.

Die Anzahl der Waypoints sollte kein Speed-Problem darstellt ... das hängt natürlich von einer Reihe von Faktoren ab (z.B. ob es noch externe Einschränkungen gibt wie "Bot muss Punkt B innerhalb von 5 Sekunden erreichen können"). Aber wenn es nicht ein Monsterlevel ist, dann wird der eigentlich Planungsprozess (also die Routenbestimmung) sehr schnell sein ...

3.) Welchen Ansatz verfolgst Du mit Crowd Management ? Wenn jedes Mitglied der Gruppe z.B. den Player einzeln wahrnehmen (und angreifen) soll, dann kommt man um Berechnungen pro Entity nicht herum ... also ist das nicht unbedingt "bescheuert" sondern durchaus auch notwendig. Hier sind dann nur effiziente Algorithmen gefragt und ein intelligentes Design (z.B. nur Bots zu aktivieren die 100m oder näher am Player sind ...)

4.) Die Lösung hierfür ist die Nutzung von "Repulsion Vectors". Wenn zwei Entities aufeinanderprallen, dann wird der resultierende Abprallvektor bestimmt und die Entity bewegt sich ein Stück in die Richtung bevor sie den alten Weg wieder einschlägt.

Aber bevor Du das Rad komplett neu erfindest ... schau Dir doch einfach mal IntensePathfinding (entweder hier im Forum oder www.intense-i.com) an ... nicht nur hat Aris einen A*-Algorithmus implementiert, er hat auch einen entsprechenden Graph Generator, Repulsion Vectors etc. verarbeitet. Das Pathfinding ist kostenlos (ich selbst hab mir allerdings "IntenseX Copper" gekauft, da es auch noch AI für Bots/NPCs beinhaltet).

Gruß,
Andreas

Vielen Dank für eure Hilfe, Ich les mir das jetzt mal alles genau durch und gehe dann morgen genau darauf ein

Vielen Dank Nochmal,
TechMuc

PS: Danke für die Links zu Intense-X. Mir geht es allerdings gar nicht zwangsweise darum Pathfinding neu zu erfinden. Ich habe micht schlichtweg noch nie an AI-Programmierung versucht und da ich Programmieren liebe muss ichs einfach mal selber probieren

Kann ich gut nachvollziehen ... wenn Du den A* dann fertig hast, kannst Du Dich ja mal am CD* versuchen ... ist noch eine Stufe "fortgeschrittener"

Und wenn Du es richtig fortgeschritten mache willst, dann verzichtest Du komplett auf Waypoints und gibst dem NPC eine "heightmap" (greyscale) als Karte mit und er findet sich dann allein zurecht (hier haben Anthony Stentz und Martial Hebert viel Vorarbeit geleistet) ... mal gucken, ob die heutigen PCs & 3DGS so etwas bewältigen könnten

Aber mal im Ernst ... das Ganze hängt ja auch davon ab wie viele NPCs Du gleichzeitig aktiviert hast ... viele der aus der Forschung publizierten Experimente/Studien gehen immer nur von einem Vehicle aus, welches sich in unbekanntem Terrain zurechtfinden soll.

Auf jeden Fall wünsche ich Dir viel Spaß und Erfolg !

Gruß,
Andreas