Welche Heuristiken werden in NavMeshes verwendet?

Welche Heuristiken verwenden Programmierer bei der A * -Pfadfindung für NavMeshes?

NavMesh = Navigationsnetz, eine Art der Pfadfindung, bei der Netze anstelle von Wegpunkten verwendet werden.

path-finding Shawn Mclean
quelle

Bitte klären Sie Ihre Frage. Ich weiß nicht, was Sie meinen, wenn Sie "NavMeshes" sagen (groß geschrieben, als wäre es ein Produktname ™). Fragen Sie nach alternativen Algorithmen zu A *, die ungefährere Pfade erzeugen, jedoch in kürzerer Zeit?

Ricket

@ Ticket ai-blog.net/archives/000152.html

Shawn Mclean

Gotcha, danke! Ich habe von ihnen gehört, aber nie etwas mit ihnen gemacht, also habe ich den komprimierten Namen nicht erkannt :)

Ricket

Antworten:

Treffen Sie Ihre Wahl:

http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

In diesem Link wird eine Vielzahl von Heuristiken beschrieben, entweder aus Gründen der Geschwindigkeit oder der Genauigkeit. Es gibt immer einen Kompromiss, daher würde ich davon ausgehen, dass Entwickler die genaueste Heuristik verwenden, die die Leistung ihres Spiels nur minimal beeinträchtigt.

Ray Dey
quelle

Diese sind für Gitterkarten. Ich gehe davon aus, dass Navigationsnetze eine andere Heuristik verwenden würden, um von einer Poly zur anderen zu wechseln. Wahrscheinlich eine Form der Geometrieheuristik, um das nächstbeste Poly basierend auf der Größe der Kante oder etwas auszuwählen.

Shawn Mclean

Einverstanden, aber Heuristiken werden verwendet, um den kürzesten Weg zum endgültigen absoluten Ziel zu schätzen und die Kosten für die nächste Poly zu decken. Sie sollten die Entfernung als "zulässige Heuristik" unterschätzen. Ein Navigationsnetz ist immer noch ein Diagramm, genau wie eine Gitterkarte ein Diagramm ist. Ich denke, die meisten dieser Heuristiken sind anwendbar. Es liegt am Entwickler, zu sehen, welche am besten anwendbar sind.

Ray Dey

Eine sehr, sehr grobe (aber sehr schnelle) Heuristik ist: (Manhattan Entfernung)

vec1 = start vector
vec2 = end vector

heuristic = abs(vec2.x - vec1.x) + abs(vec2.y - vec1.y))

Dies vermeidet jegliche quadratische Wurzelbildung, die kostspielig sein könnte (pythagoreische Entfernung).

Die kommunistische Ente
quelle

Manhattan Entfernung, nein?

Ray Dey

Ich dachte es wäre und bearbeitete es dann heraus, da ich dachte, es wäre vielleicht nicht so gewesen.

Die kommunistische Ente

Sie können auch die quadratische Länge verwenden (pythagoreische Entfernung ohne Quadratwurzel). Es ist schnell und höchstwahrscheinlich eine bessere Heuristik als die Entfernung von Manhattan (es sei denn, Ihr Charakter kann sich nur horizontal und vertikal bewegen)

bummzack

@bummzack: Bitte lesen Sie den Abschnitt "Euklidische Distanz, Quadrat" auf Amits heuristischer Seite. Die quadratische Entfernung ist keine zulässige Heuristik und führt zu einer suboptimalen Pfadbildung.

Quadratische Entfernungen sind für kurze Entfernungen zu klein (A * verschwendet Zeit) und für lange Entfernungen zu groß (A * findet schlechtere Wege). Es gibt gute Gründe, die heuristischen Entfernungen zu überschätzen, aber das Vermeiden von sqrt gehört nicht dazu. Verwenden Sie entweder eine schnelle sqrt-Näherung oder einen diagonalen Abstand. Wenn Ihr Navigationsdiagramm explizit ist, berechnen Sie den euklidischen / pythagoreischen Abstand einmal und speichern Sie ihn mit der Kante zwischen den Knoten.

Amitp