Wegfindung, aber welcher Algorithmus?

[T.Jay03]

Ich habe vor mir einen kleinen Wegfinder zusammen zu basteln.

Die Frage die sich für mich stellt: Welcher Algorithmus ist für meine Anforderungen am besten geeignet?

Ich habe genau 4 Anforderungen.

1. Er muss schnell sein,

2. dynamisch änderbar,

3. er soll nicht Zick-Zack laufen (ohne Glättung! nicht nur horizontal, vertikal und diagonal)

4. und nicht zu letzt er soll ein Kompromiss aus kürzester Weg und dem Weg der am "breitesten ist. D.h. es soll möglicht für ein große Gruppe von Objekten möglich sein, diesen Weg zu passieren. Wenn der gefundene Weg sehr eng ist, da es keinen breiteren gibt, soll dieser auch gefunden werden, jedoch nur als "Notnagel".

Ich hoffe es gibt schlaue Köpfe die mir einen Algorithmus empfehlen können.

Ich habe schon folgende Verfahren ausprobiert:
1. Einteilung des Feldes in ein Gitter und diese als Verbindungspunkte Verbinden
= langsam, dynamisch, Zick-Zack Wege, minimale Entfernung zu Hindernissen

2. Sichbarkeitspunkte als Verbindungspunkte
= schnell(aber sehr komplex!?), nicht dynamisch, perfekt kürzeste Weg, minimale Entfernung zu Hindernissen

3. Quad Trees als Verbindungspunkte
(arbeite gerade daran)
= schnell, dynamisch, leichte (aber akzeptable) Zick-Zack Wege, Entfernung zu Hindernissen maximal, wenn man eine Heuristik verwendet, die den Weg künstlich länger macht, je kleiner das zu betrachtende Feld ist

Ich weiß noch nicht, ob ich nur die Verbindung von Nachbarknoten erlaube, oder das mit dem Sichtbarkeitsalgorithmus verbinde und Verbindungen zu jeden sichtbaren Punkt erlaube (denke aber das fällt aufgrund der extremen Komplexität weg)

Ich kenne noch weitere, mit den ich mich jedoch noch nicht weiter mit befasst habe.

1. Polygone als Verbindungspunkte

**2. Einteilung in Räume und dann mit Raumteilungspunkte als Verbindungspunkte
**(denke sehr nahe dem Quad Tree Algorithmus)

Also ich freue mich über Antworten!

Liebe Grüße

[thordk]

ganz pragmatischer ansatz.

zunächst lege ich eine minimale distanz fest, die sich fortbewegt werden kann. dann richte vom startpunkt aus meinen richtungsvektor aufs ziel. der nächste zu erreichende knoten liegt auf dem rand eines kreises, dessen radius der minimalen distanz entspricht und zunächst der schnittpunkt mit dem richtungsvektor ist. ein knoten wird teurer, je näher die schnittpunkte der tangente an diesem punkt mit umliegenden objekten liegen. den richtungsvektor zu rotieren ist teuer, da ich geradlinige bewegungen bevorzuge. also suche ich auf dem rand des kreises ein lokales minimum, vom "startknoten" ausgehend.

der algorithmus liefert vielleicht nicht immer den optimalen weg, aber ich denke eine implementation wird recht zügig nen weg finden. zudem ist er durch die heuristiken gut anpassbar und es ist ihm völlig wurst, wie die karte beschaffen ist. schwachpunkt ist natürlich, dass er auch mal ungünstig in ne ecke laufen kann und dadurch extreme wendungen vollführen muss.

da ich mir den aber grad innerhalb von ca. 30 sekunden ausgedacht habe, verspreche ich keinen erfolg

[DDR-RAM]

A*
Den Algorithmus gibs in allen möglich Varianten. Dein Problem lässt sich damit auch lösen.

MfG
DDR-RAM

[thordk]

A* arbeitet topografisch. für ne beliebige map musst du deshalb erstmal überlegen, wie du da knoten definierst.

[Jester]

Sichtbarkeit der Verbindungspunkte dürfte das Verfahren sein, das die besten Resultate liefert. Den Abstand zum Rand kannste durch Versehen der Hindernisse mit einem Rand modellieren (das haste sicher schon). Du kannst sogar mehrere verschiedene Versionen des gleichen Hindernisses aufnehmen und Kanten, die zu Knoten hinführen, die in einige Ränder bereits hineinragen stärker gewichten. Damit kannste dann steuern wie kurz dein weg bzw. wie nah Du an Dein Objekt kommst.

Hauptproblem bei dieser Variante ist dann die Dynamik. Ob das noch effizient lösbar ist, hängt auch stark von der Situation ab. Haben Deine Hindernisse eine spezielle Form oder Lage?