Wegberechnung im 2D-Raum

[spyboot]

Hi Leute,

Ich beschäftige mich jetzt schon einige Zeit damit wie mann eine Wegberechnung im 2D-Raum realisieren kann,
Es gibt eine Methode

boolean istfrei(int x,int y)

um zu prüfen ob die Koordinate frei ist

zum Testen gibt es ein Feld von 400x400 Pixeln mit 3 Hindernissen:

Das ganze sollte auf einem 3GHz Rechner nicht länger als 200 Tausendstelsekunden dauern wobei nicht der Kürzeste sondern wenigstens ein einigermaßen direkter Weg ermittelt werden muss.
Das ganze muss in einer Point2D Array gespeichert werden und die einzelnen Punkte müssen ohne Hindernisse anzusteuern sein. Es kann Pro schritt immer nur die x oder die y Koordnate geändert werden.

 

[spyboot]

Was ich noch vergessen hatte: Die Welt ist in alee Richtungen unendlich Das heist:

-Es können Punkte und Hindernisse im Minusbreich liegen
-Und deshalb hab ich das Problem dass ich die anderen Algorithmen nicht verwenden kann.

 

[Marco13]

"Die" anderen Algorithmen? Welche auch immer du meinst: Es sollte eigentlich kein Problem sein, die Hindernisse für die Wegeberechnung mal kurz in den Positiven Quadranten zu schieben - wenn es daran hängt. Ansonsten wäre es SEHR vorteilhaft, wenn man alle Eckpunkte aller Hinternisse kennen würde. Wennman wirklich nur "istFrei(x,y" kennt, ist das ein bißchen problematisch, weil man ja bei jedem "Pixel" damit rechnen muss, in ein winziges "Sackgässchen" zu laufen... Mit einer A*-Suche (A-Star-Search, Wikipedia ctc.) könnte man das vielleicht trotzdem noch in <200ms schaffen, aber kein Vergleich zu den effizienteren Möglichkeiten, wenn man genauere Informationen über die Umgebung hätte....

 

[spyboot]

Ok wenn mann jetzt eine Array der Klasse "Rect" hätte mit:
Rect.getX();Rect.getY();Rect.getWidth();Rect.getHeight();
bzw.
Rect.x;Rect.y usw.

Wie könnte mann es dann so machen dass es auch mit einer Situation wie zb dem obigen beispiel funktioniert?

 

[Marco13]

Da gibt's dann verschiedene Ansätze. Ein paar Stichworte wären "Visibility Graph", "Tangent Graph", "Voronoi Regions".... Mit sowas wie http://www.google.com/search?q=path+planning+"tangent+graph"+OR+"visibility+graph"+OR+"Cell+Decomposition"+OR+Voronoi&btnG=Search&hl=en&sa=2 findet man da einiges dazu.

Hier sind z.B. ein paar Folien, wo auch (wie bei Folien üblich, sehr knapp) ein Algorithmus für die Suche mit einem Sichtbarkeitsgraphen beschrieben ist: http://gamma.cs.unc.edu/COMP290-58/SLIDES/Lecture2.pdf

 

[spyboot]

Ich weis jetzt wie ich es mache:

In Form einer Baumstruktur und von dem Chield dass dan das ziel hat nimmt mann immer wieder das Parent bid mann am Start ist und schon hatt man den Weg!

 

[Marco13]

Hm. :? Wenn meine erste Antwort gewesen wäre:
In Form einer Baumstruktur und von dem Chield dass dan das ziel hat nimmt mann immer wieder das Parent bid mann am Start ist und schon hatt man den Weg!
hätte dir das dann weitergeholfen?

Eigentlich baut man einen Graphen. Wo darin ein Baum vorkommen soll, ist mir nicht klar. Aber es reicht ja, wenn es dir klar ist :wink: