spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Achso, dann hatte ich Dich missverstanden. Wie gesagt: A* ist eine gängige Priorisierungsheuristik, die auch in diesem Fall gute Dienste leisten dürfte, aber natürlich auch bei komplexen Umgebungen degenerieren kann. Es dürfte bei der Fahrzeugsteuerung aber umso kniffliger sein, Totpunkte und schon besuchte Zustände zu erkennen. Sonst verrennt sich die Heuristik z.B. in einer Sackgasse in die ziel-naheste Ecke und betrachtet dort bis in alle Ewigkeit Kleinstmanöver hin und her.

Zitat von »Schrompf«

Sonst verrennt sich die Heuristik z.B. in einer Sackgasse in die ziel-naheste Ecke und betrachtet dort bis in alle Ewigkeit Kleinstmanöver hin und her.

Nein, das tut sie nicht. A* betrachtet immer den Knoten, bei dem die Summe aus bisherigem Weg + geschaetzter Restweg minimal ist. Das heisst nach einer endlichen Zahl von "Kleinstmanöver" ist der dort bisher zurueckgelegte Weg trotzdem so lang, das der Algorithmus dann bei einem naeher zum Start gelegenen Knoten abbiegt.

Würde es nicht auch einfach reichen mit Navigation Meshes zu arbeiten? Dann guckst du bei jeder Bewegung, dass du auf dem Navigation Mesh bleibst. Das kommt natürlich immer ein wenig auf die Umgebung selbst an, sollte damit aber doch eigentlich recht gut machbar sein.

Was genau wuerde das gegenueber seinem Grid helfen? Er koennte ja deiner Logik zu Folge auch einfach bei jeder Bewegung schauen, dass er auf den begehbaren Gridfeldern bleibt.

Gridfelder sind aber meistens kleiner als einzelne Polygone vom Navmesh. Man müsste also nicht nur das aktuelle Polygon checken sondern die umliegenden auch. Da ich bei einem Navigationmesh je nach Bauart der Karte eher wenige Große Polygone besitze dürfte hier die Komplexität geringer sein. Einfach weil eine Wendeaktion bei einem Grid vermutlich über viel mehr Polygone verlaufen würde. Wie gesagt hängt von der Umgebung ab und ob es viel bringt bin ich mir nicht sicher.

Welche "Komplexitaet" meinst du denn jetzt? Ich kann mir keine Definition von Komplexitaet vorstellen, wo ein Navmesh "einfacher" als ein Grid sein soll.

Mir geht es darum, dass es einfacher ist zu prüfen ob der Spieler bei einer Aktion (Laufen, Kurve gehen, Fahrzeug wenden, ...) in wenigen Polygonen oder in vielen bleibt. Einfach weil ich behaupte, dass man bei einem NavMesh die Polygone so verteilen kann (wenn es die Welt denn zulässt), dass man mit wenigen Großen Polygonen auskommt. Ich bleibe also bei so einer Aktion wahrscheinlicher in meinem großen Polygon und es reicht hiermit auf Kollision zu prüfen. Bei einem Raster passiert es schneller, dass ich während so einer Aktion mehrere Felder passiere. So muss ich mit recht vielen Feldern testen. Wie ich bereits gesagt habe bin ich mir über den Vorteil den man dadurch erhalten kann selbst noch nicht ganz bewusst, ich glaube jedoch dass es einen Performancevorteil geben sollte (bei geeigneter Weltgeometrie).

Zitat von »Schorsch«

Mir geht es darum, dass es einfacher ist zu prüfen ob der Spieler bei einer Aktion (Laufen, Kurve gehen, Fahrzeug wenden, ...) in wenigen Polygonen oder in vielen bleibt.

Was genau meinst du da mit "einfacher ist zu prüfen"?

Ach TGGC das wird mir hier zu blöd. Ich bin mir ziemlich sicher dass du weißt was ich meine. Ich habe behauptet dass es weniger komplex ist, was in meinem Fall bedeuten soll, dass es einfacher zu berechnen sein würde. Jetzt kommt es natürlich auf die Polygone vom Navmesh an und wie komplex (Anzahl Vertizes) sie sind. Um das mögliche Missverständnis gleich aus dem Weg zu räumen, einfacher zu berechnen bedeutet nicht weniger Codezeilen oder was weiß ich, sondern schneller und somit einfacher für einen Computer zu berechnen. Wie gesagt war das einfach eine fixe Behauptung. Im Endeffekt macht es vermutlich doch eher einen untergeordneten Unterschied weshalb wir hier eigentlich auch nicht weiter drauf rum reiten müssen. Dem TE wirds vermutlich am Ende nicht helfen.