Hi,

ich möchte eine Wegfindung im 2D raum implementieren
Ich habe folgendes:
-eine zum Teil sehr große Karte
-objekte, die durch ihre begrenzungslinien gegeben sind (nicht unbedingt geschlossene figuren, da z.b. auch ein Haus nur durch die 4 wände als je eine linie gegeben ist, und eine linie eine lücke (die tür) hat; sprich: das haus KÖNNTE betreten werden (was in meinem fall aber nicht sinnvoll wäre). zumindest kann ich also nicht davon ausgehen, dass alle figruen geschlossen sind)
-gebiete, die abgegrenzt sind. also wieder linien, die einfach sagen: hier beginnt eine schlucht, über die geht es nicht drüber

kurz: ich habe linien, die nicht berührt oder übertreten werden dürfen
einige objecte sind klein (bäume, laternen) andre sind groß, wie das terrain.

was mich sehr intressiert hat war das hier: http://wiki.delphigl.com/index.php/Tuto ... thfinding2

klingt, wie für mein problem geschaffen. nur dass meine linien nicht an den achsen ausgerichtet sind, sonder auch schräg verlaufen können.

da start und ziel sich bei jeder wegsuche ändern, kann ich nicht alles von vornherein berechnen.
meine idee bisher war: alle linien zu speichern und die punkte als graph schon im vornherein zu berechnen.
dann start und ziel jeweils als zusätzliche punkt mit einzufügen und über den graph dann die wegsuche zu starten.
da es aber sehr viele objecte sind, kann das schon sehr lange dauern. auch müsste ich beim erstellen, eine verbindung von jedem punkt mit jedem prüfen.
auch sehr aufwendig.

wie kann ich das ganze implementieren? vl erst mal alle kleinen objecte raus lassen und dann im fertigen pfad nur noch die kleinen objecte umgehen?
könnte zum problem werden, wenn mehrere kleine einen durchgang versperren...

Du könntest den Tutorialansatz "wrappen".

Mach BoundingBoxen um deine Objekte. Oder füge "Objektinternes-Routing" hinzu. D.h. wenn dein Algorithmus an den grenzen eines Objektes ankommt, dann sagt er dem Objekt in welche Richtung er weiter will, und das Objekt antwortet mit einer Route. So kannst du eventuelle kompliziert geformete Objekte dezentral behandeln.

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Ich würde einen Ansatz mit einem Wegpunktenetz (Graph) wählen. Du erstellst im voraus manuell ein Netzwerk von Wegpunkten. Jeder Wegpunkt ist mit anderen Wegpunkten in seiner Umgebung verbunden. Für jeden zulässigen Punkt in deiner Welt muss gelten das der gerade Weg zum nächsten Wegpunkt (also Luftlinie) frei von jeglichen Hindernissen ist. Um die Anzahl der Wegpunkte zu reduzieren kannst du den Punkten z.B. einen erlaubten Radius geben.

Grundsätzliches Vorgehen:
1. Suche den zu Start (bzw. Ziel) am nächsten gelegenen Wegpunkt StartWP (bzw. ZielWP). Dafür benutzt man natürlich eine geeignete Baumstruktur (z.B. QuadTree, R-Tree), ein GridFile o.ä, damit man nicht alle Punkte anschauen muss.
2. Auf dem Netzwerk der Wegpunkte kannst du einen der diversen Standardalgorithmen für Graphen anwenden. Beispielsweise Dijkstra oder A-Star.
3. Der Pfad ist nun also: Start -> StartWP -> ....Wegpunktnetz.... -> ZielWP -> Ziel

Hier wäre man schon fertig. Den Pfad kann man noch etwas optimieren, indem man versucht den Radius der einzelnen Wegpunkte auszunutzen. Siehe Bild im Anhang. Wenn nichts im Weg ist wird abgekürzt.

Je mehr Wegpunkte desto besser wird natürlich der resultierende Pfad. Um das Wegpunktnetz zu erzeugen kann man sich einen einfachen Editor schreiben. Z.B. man fliegt mit der Kamera durch die Gegend und immer wenn man Leertaste drückt wird ein Wegpunkt erzeugt der automatisch mit allen anderen Wegpunkten in einer gewissen Entfernung verbunden wird wenn nichts im Weg ist.

_________________
Yeah!

ein manuelles erstellen der karte kommt aufgrund der komplexität und größe leider nicht in frage.
es muss vollautomatisch aus den o.g. daten gehen.

bisher habe ich schon nen A* implementiert, der aus einer karte mit quadratischen felder den kürzesten weg findet. (jedes quadrat ist begehbar oder nicht markiert) ich kenne mich mit diesem (und auch mit dijkstra) also aus

das problem ist tatsächlich das erstellen der karte.

für das tutorial brauche ich verbindungen von jedem eckpunkt zu jedem anderen (möglichen)
da ich schon auf einem teilstück ca 200 eckpunkte habe und von den teilstücken mehrere hundert existieren, könnte das zum problem werden.
einziger vorteil: es muss nur beim laden einmal gemacht werden.

deinen ansatz mit den boundingbox verstehe ich nicht ganz.

ich sehe als großes problem eine U-förmige sackgasse. start liegt im U und ziel auf der runden seite des Us direkt gegenüber. außerdem besteht das U aus mehreren objecten

wie kann da ein object "wissen", wie es weiter gehn soll? es kennt ja die anderen objecte nicht

Ich habe mal was ähnliches gemacht. Dabei bin ich erst Luftlinie "gegangen" wenn ein Hinderniss kam habe ich über einfaches ausprobieren denn kürzesten punkt gesucht der wieder auf die Luftlinie fürt, es ist war nicht optimal aber funktioniert sehr gut.

_________________
You even trying ...

Website: http://rise-of-light.de/

Jedes Teils vom U ist ein eigenes Objekt?
Dann hat auch jedes Teilstück eine Bounding Box.
Die Ecken der Boundingbox sind dann Quasi potentielle "Navigationspunkte". Die Wissen dann, welche Navigationspunkte in der Nähe liegen und welche nicht.

Es gibt aber ein viel interessanteres Problem zu lösen.

Ich hab da mal vor Jahren drüber nachgedacht und meinem Prof ne Mail geschickt. Er meinte nur, dass das interessant sei, aber er im Moment keine Zeit hätte darüber nachzudenken.

Und zwar geht es um Durchgänge. Wie findest du heraus ob du durch einen Durchgang durchpasst oder net?

Das ist net ganz einfach.

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Du kannst auch einfach Wegpunkte in einem Abstand von X Einheiten über die Karte verstreuen. Zusätzlich Wegpunkte mit geringem Abstand auf beiden Seiten jeder Kante. Wegpunkte die sich innerhalb eines Objektes befinden werden entfernt.
Dann verbindest du alle Wegpunkte mit den Nachbarwegpunkten im Umkreis von 2*X Einheiten, wenn sich kein Objekt im Weg befindet. Von Hand machen gibt natürlich bessere Ergebnisse, aber vielleicht kannst du ja auch nach justieren oder sowas.

_________________
Yeah!

2 schwierigkeiten: von Hand geht nicht, da zu komplex/groß
und ich weiß nicht was "innerhalb eines objectes" ist

ich habe ja nur einzelne linien die nicht mal zwingenderweise eine geschlossene figur darstellen.
also z.b.: ein rechteck mit "anbauten" und einem durchgang in der mitte als "haus mit flur"
ok kann man noch abstrahieren und als BB auffassen-->nur äußere linien zählen und den durchgang gibts nicht mehr...schwer aber vl machbar
schlimmer sowas: ein object ist ein marktplatz: in der mitte ein brunnen (8-eck) und 4 säulen drum rum...
dazwischen kann/muss man durchlaufen....

ich könnte aber tatsächlich wegpunkte erstellen, und benachbarte verbinden, wenn es keine linie gibt, die diese verbindung kreuzt UND der wegpunkt selbst keine linie beinhaltet
dann sind u.U. zwar wegpunkte innerhalb von objecten, haben aber keine verbindung zur außenwelt-->nicht von belang


@Flash: um durchgänge kümmere ich mich später...ist mir derzeit zu aufwending...gibt vl dann ne möglichkeit
wichtiger ist erstmal die hauptroutine

hast du etwas code oder pseudocode, damit ich deine idee verstehen kann?

Naja die Wegfindungsidee ist so:

Basisidee:

- Erstelle um alle Objekte Boundingboxen. (Bzw. Boundingvolumes anderer Art)
- Jeder Eckpunkt des Boundingvolumes ist ein Navigationspunkt.
- Verbinde die Navigationspunkte die innerhalb einer gewissen entfernung zueinander liegen und erreichbar sind. (Suche Alle Punkte in Umgebung. Schieße einen Strahl zu jedem Nachbar und Prüfe ob du Kanten kreuzt.)
- Start und Ziel sind ebenfalls Navipunkte und sie werden dynamisch ebenfalls ins Netz integriert wie die anderen Navipunkte. (Aber nur wenn in allernächster Umgebung nicht schon ein Punkt ist.)

Auf die Art u. Weise wird dein Netz in den Hauptgebieten mit der Zeit auch dichter. Eventuell

Diese "Subobjekt Navigation" macht hier eigentlich keinen Sinn. Es gibt keinen Fall, wo der obige Algorithmus nicht geht (jedenfalls auf den ersten blick).

Wenn jetzt aber noch einheiten dazukommen sieht das anders aus. Einheiten bewegen sich Ständig und sollen sich auch umlaufen. Hier wäre es günstig, wenn du die Einheit(ansammlungen) zuerstmal nur als 1 Objekt betrachtest das von der Navigation nicht beachtet wird (tust du das nicht, dann kann ich mir vorstellen, dass Einheiten "eiern" wenn andere Einheiten ihren Weg kreuzen).
Stellst du fest, dass deine Einheiten im nächsten Schritt kollidieren, dann fragst du erst die BB der Einheiten ab und versuchst durch zu manövrieren.

_________________
Blog: kevin-fleischer.de und fbaingermany.com

einheiten dürften vernachläsigbar sein,. ich glaube, die haben gar keine collisionsbox

das problem ist z.b. die stadt: die hat drumrum eine mauer aus ein paar mauerstücken, und teile der mauer haben einen durchgang(als tor)
das ist aber kein extraobject sondern in die mauer integriert. (ist halt ein portal, sprich: mauer ist auch drüber)
nur die linien hören halt an der position auf.

wie kann man dann in der stadt navigieren, wenn doch durch die mauer, die stadt als ein object aufgefasst wird?

Wenn du von einem Objekt weißt das es geschlossen ist, kannst du leicht raus finden ob du innen oder außen bist. Wenn das nicht bekannt ist, ist nicht so wichtig, nur eine Optimierung, weil du dann weniger Wegpunkte hättest.

Ich muss das ganze Verfahren noch mal korrigieren, weil es schwierig ist sicherzustellen, dass der nächste Wegpunkt auch immer wirklich erreichbar ist.

Verfahren: Wegpunkte verteilen (Vorberechnung)

• Verteile Wegpunkte entlang beider Seiten im Abstand X einer jeden Linie. Siehe Bild 1. Wegpunkte die zu nahe an anderen Linien liegen werden entfernt. Im Bild sind das die roten Punkte. Dazu muss für jeden Wegpunkt der Abstand zur nächsten Linie berechnet werden. Da es sich hier nur um einen Vorberechnungsschritt geht, das ganze also nur einmal gemacht werden muss, ist Performance nicht so wichtig. Trotzdem kann man sich natürlich eine Baumstruktur o.ä. konstruieren.
• Verteile nun in einem gleichmäßigen Raster Wegpunkte mit Abstand Y über die gesamte Karte, siehe Bild 2. Dabei werden wieder Wegpunkte entfernt, wenn sie zu nahe an einer Linie liegen sollten. Zusätzlich kann man Wegpunkte entfernen, wenn sie zu nahe an einem anderen Wegpunkt liegen.
• Spätestens jetzt muss eine Baumstruktur aufgebaut werden die effiziente Abfragen der Nachbarn eines Punktes erlaubt. Außerdem wird eine Struktur benötigt die effizient testen kann ob eine Linie eine andere Linie schneidet. (Man kann natürlich auch beides mit einer Datenstruktur lösen)
• Alle Wegpunkte werden mit allen Nachbarn im Abstand von 1,5*Y verbunden, wenn keine Linie im Weg ist, siehe Bild 3. Es kann sein, dass im Bild einige Linien fehlen...

Verfahren: Wegfindung

• Statt nun nur den nächsten Wegpunkt zu suchen betrachten wir alle Wegpunkte im Radius von 1,5*Y. Für jeden Wegpunkt checken wir, ob es eine Luftlinien-Verbindung von unserem Punk gibt. (Vor allem hier brauchen wir die zuvor erstellte Datenstruktur.)
• Du hast nun eine Menge von Wegpunkten im Start-Bereich und eine Menge von Wegpunkten im Zielbereich. Jetzt wähle je einen Wegpunkt aus jeder Menge aus und berechne mit Dijkstra (etc.) einen Pfad über das Wegenetz. Wenn die Qualität besser sein soll, kann man diese Berechnung auch mehrfach machen, also beispielsweise zufällig mehrere Paare probieren.

_________________
Yeah!

Ich versteh dein Problem mit der Mauer nicht.

Machen wir mal einen komplizierten Fall: Die Mauer ist Kreisrund mit einem Tor.

Dann erstellst du ein zusammengesetztes Bounding Volume bestehend aus mehreren Kästen. Also Quasi ein Ring aus Schachteln.

Das Tor bekommt eine extra BB.

Die Eckpunkte des Schachtelrings sind Wegpunkte. Allerdings Wegpunkte die entweder innen oder außen liegen. Eine Verbindung zwischen diesen beiden Gruppen gibt es nicht.

Die Eckpunkte des Tors sind zwar aus außen oder innen, allerdings sagst du denen einfach, dass sie miteinander verbunden sind. Also dass man von einem Tor-Außen-Knoten zu einem Tor-Innen-Knoten kommen kann.
Und schon bist du drinnen.

Wenn du die gesamte Stadt als ein Objekt machst, dann ist das ungünstig aber nicht unmöglich.
Dann gehst du hierarchisch vor. Als erstes den Weg bis zur Stadt-BB finden und dann sagt dir die Stadt, wie die Navigation innerhalb der BB funktioniert.

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Ich kenne das Problem aus der kognitiven Robotik.
Falls das Objekt kreisförmig ist, ist das Problem einfach zu lösen.
Man muß nur die Bounding-Boxes um den Radius des Objektes vergrössern, so wie auf dem Bild unten...




Viele Grüße
dj3hut1

ich habe von einem object nur die linien gegeben. weiß also nicht ob es geschlossen ist.
könnte man u.u. herausfinden, indem man in den punkten der linien nach kreisen sucht (also algebraische kreise)

die idee von Coolcat klingt sehr gut.
wie sollte so eine struktur aussehen? bzw besonders die zum testen, ob eine linie schneidet?
ich würde derzeit ein array der punkte erstellen, wo nur die koordinaten gespeichert werden.
in einem weiteren array, würde ich zu jedem punkt (durch den index in den arrays "verbunden"), die erreichbaren nachbarn(wieder nur die indizes) speichern. problem dabei: durch den ungerichteten graphen, hätte ich jede verbindung 2 mal
vorteil: ist schneller als ein array "of verbindungen" mit jeweils 2 einträgen für start und zielpunkt

im anhang mal eine "stadt"-skizze. ich habe die linien absichtlich etwas versetzt, damit man erkennt, dass es viele sind (die gehören nichtmal zu einem object)
es gibt mehrere mauerstücken.
wie z.b.: mauertyp1,mauertyp2,mauertyp1gedreht...

Zum Testen ob ein Weg eine deiner Linien schneidet, ist eine Baumstruktur für die Linien sinnvoll. Man kann einen R-Baum nehmen, der ist wahrscheinlich besser, aber ein QuadTree ist einfacher zu implementieren. Der Unterschied ist das sich der R-Baum der Struktur der Daten besser anpasst, was die Sache ziemlich kompliziert macht. Ich weiß nur noch das wir damals einige Stunden gebraucht haben um den R-Baum vollständig zu verstehen, was aber auch daran lag das die Erklärung vom Prof voller Fehler war....also nehmen wir den QuadTree:

Grundsätzliches QuadTree-Konzept ist hoffentlich klar, also du beginnst mit einem quadratischen Wurzelnknoten. Diesen Knoten unterteilst du rekursiv in kleinere Knoten. Dabei wird immer auf beiden Achsen genau in der Mitte geteilt. Von jeder Linie berechnest du eine Axis-Aligned-Bounding-Box (AABB), was einfach nur ein Minimum und ein Maximum der beiden Punkte der Linie bezüglich jeder Koordinate ist. Eine Linie wird einem Knoten zugeordnet, wenn sich die AABB der Linie innerhalb des Knotens befindet oder ihn zumindest berührt. Dabei kann es vorkommen, dass sich eine Linie in mehreren Knoten befindet. (das ist der Nachteil ggü. dem R-Baum)
Sind einem Knoten mehr als 5 Linien zugeordnet, wird dieser Knoten rekursiv weiter unterteilt. Das geht solange bis du eine maximale Tiefe erreicht hast oder eben weniger als 5 Linien im Knoten sind.
=> Die Linien sind also den Blättern zugeordnet. Die übergeordneten Knoten enthalten also keine Linien. Es macht wahrscheinlich Sinn statt der richtigen Linie in den Knoten nur eine ID zu speichern. Das erleichtert den Duplikat-Test (siehe unten)

Wenn du nun wissen willst ob dein gegebener Weg (=Linie) eine andere Linie schneidet, fragst du deinen Baum:
Du berechnest die AABB deiner Linie und suchst im Baum sämtliche Knoten die deine AABB berühren. So erhältst du eine Liste aller Linien die für eine Kollision in Frage kommen. Eine Linie kann mehreren Knoten zugeordnet sein, wir könnten also Linien mehrfach in der Liste haben. Sofern wir ID-Nummern verwenden, brauchen wir einfach nur die Liste nach dieser ID sortieren. In der sortierten Liste lassen sich Duplikate leicht finden.
Die resultierende Liste müssen wir nun durchgehen und testen ob sie sich mit unserer Linie schneiden.

Mit dem selben Baum kann man auch Punktanfragen durchführen. Wir berechnen auch hier die Menge aller Knoten die unseren angefragten Punkt berühren. Wieder erhalten wir eine Liste mit Linien, wieder werden Duplikate entfernt. Die resultierende Liste gehen wir wieder durch und berechnen den Abstand unseres Punktes zu jeder Linie. Wir nehmen den kleinsten Abstand.



Um das Wegpunktenetz zu speichern würde ich so vorgehen:

Darüber benötigst du wieder einen QuadTree für Wegpunkte, damit du effizient die nächst liegenden Wegpunkte berechnen kannst.

_________________
Yeah!