Ich habe eine Sackgasse mit meinem Universitätsprojekt erreicht und ich kann keine Lösung finden. Das Problem ist:Pathfinding mit voronoi
einen Kreisroboter (grüner Kreis) mit dem Radius r gegeben Ich brauche einen Weg zu finden (jeden Pfad nicht die beste) bis zum Endpunkt, das der blaue Punkt ist.
Bild unten
Die Hindernisse sind die roten Polygone und um sie herum die cyanfarbene Linien die Minkowski-Summe darstellt.
Die schwarzen Punkte repräsentieren das Voronoi-Diagramm.
- Die blaue Box ist um die äußere Grenze
Also zuerst obwohl ich, ich sollte die näher Punkte auf den Startpunkt (Roboter) und dem Endpunkt der Voronoidiagramm Punkte finden. Und diese Punkte werden im Bild angezeigt (cyan dots).
Dann dachte ich mit einigen König des Algorithmus wie der A * nach dem Pfad für die cyan Punkte oben entlang der Voronoi Punkte suchen, auf diese Weise werde ich die sicherste Weg Art finden.
Das Problem ist, dass ich keine Möglichkeit habe zu wissen, welche Nachbarn die einzelnen Punkte im Voronoi-Diagramm sind. Denn wie Sie in den einzelnen Teilen des Diagramms sehen können, gibt es große Lücken.
Was schlagen Sie vor?
Vielen Dank für Ihre Zeit.
gibt es eine Grenze für die Größe der Karte? – Saikios
Das blaue Polygon um die Hindernisse ist die Grenze. Seine Abmessungen sind etwa 1000x700 Pixel (abhängig von der Fenstergröße). –
so schlimmsten Fall Szenario, wenn Sie keine Möglichkeit haben, nichts über die Karte zu wissen ist, durch alle Punkte gehen, nur in eine obere Ecke oder unten gehen und beginnen von dort aus alles Wenn es eine Karte was war Am besten funktionierte es für mich in der Vergangenheit, immer nach links zu gehen, aber in diesem Fall mit unregelmäßigen Karten ist es manchmal besser, einfach alle Punkte durchzugehen. – Saikios