spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hallo,

ich habe in meinem Projekt das Problem, eine automatische Nachbarschaftsrelation von allen Polygonen in einer Karte berechnen zu müssen. Die Karte besteht aus bis zu tausenden Polygonen, die normalerweise alle aneinandergrenzen.

Leider ist das Kartenformat eine spezifische Art von XML, die zwar größtenteils hierarchisch (kleiner Elemente sind in größeren enthalten) sind, aber keine wirkliche geometrische Ordnung besitzen (man kann nicht sagen, welche Polygone sich in der Nachbarschaft eines anderen Polygons befinden).

Ich brauche das Ganze, um eine Routenplanung zu erstellen (mittels A*-Algorithmus), die Polygone übernehmen dann die Funktion der Knoten des Graphen.

Im Web habe ich einiges zur automatischen Generierung von Navigation Meshes gefunden, allerdings löst dies nicht das Problem des Auffindens der Adjazenz der Polygone.

Eine vorgeschlagene Lösung bestand (im Web) darin, jedem Vertex eines Polygons einen Hash mit Indizes auf die beteiligten Polygone mitzugeben, dies funktioniert allerdingds nur, wenn wirklich alle Polygone aneinandergrenzen und mit Integerzahlen gearbeitet wird. Beides ist in meinem Fall nicht sichergestellt, d.h. es handelt sich um Float-Werte, die voneinander abweichen können und in Ausnahmefällen können die Polygone auch einen (kleinen) Abstand haben.

Bin für alle Hinweise/Tipps dankbar,

AlGaN

Hallo nox,

es ist klar, dass sich die Nachbar-Polygone in der Nähe des betreffenden Polygons befinden müssen; ich habe schon mal eine Implementierung gesehen, bei der eine Art "unscharfe Grenze" definiert wurde (also etwa, alles was bis zu +/- 5 Einheiten von der Kante des Polygons weg ist, wird noch als Nachbar definiert), aber klar - das kompliziert die Sache noch.

Das Problem ist, dass die Karte aus einem anderen Format konvertiert wird (AutoCAD) und es aufgrund von Bugs in der Export-Funktion nicht sichergestellt werden kann, dass keine "Lücken" zwischen den Elementen auftreten.

Ich habe die Polygone schon komplett in Elementen/Klassen namens "Polygon", in der ein privates Datenmember eine Liste mit den Punkten hält.

Die Hardware ist ein normaler Windows Ultra Mobile PC (UMPC) (Sony VGN-UX1XN), keine Ahnung, was da für eine CPU drin ist (so ~ 1 GHz), mit Windows Vista. Die Berechnung der Nachbarschaftsrelationen muss allerdings auch nicht zur Laufzeit passieren, es würde ein Preprocessing-Schritt reichen...

Danke für alle Tipps,
AlGaN

Hallo,

danke für eure Tipps,

ok einen Brute-Force-Vergleich zu schreiben, dürfte nicht allzu schwierig sein, nur hatte ich gedacht, man könnte den Aufwand etwas reduzieren mit spz. Algorithmen etc. Auch eine Art Unschärfe bei der Abstandsberechnung einzubauen dürfte nicht das Problem sein.

@WarMuuh!!: Danke für den Tipp, ich hatte schon vor einiger Zeit mal nach Nachbarn-Algorithmen gesucht, und auch diesen Nearest Neighor Algo angeschaut, ihn dann aber wieder verworfen, da er meiner Erinnerung nach Punkte als Mengenelemente voraussetzte, aber den Tipp mit den Schwerpunkten der Polygone werd ich mir nochmals duch den Kopf gehen lassen...

Hintergrund des ganzen ist: Die Karte enthält verschiedene Arten von Polygon-"Elementen", Räume, Gänge, Treppen, Türen usw. in Gebäuden; Straßen, Wege, Grünflächen usw. draußen... davon sind manche begehbar, manche nicht; ich hoffte dadurch gleichzeitig auch die Kollisionsbehandlung mit erledigen zu können neben der Routenführung...