Quad - Tree Literatur??
-
Kannst du mir bitte das mit den grids genauer erklären oder mir Links mitteilen, wo sowas erklärt wird. Vorzugsweise auf Deutsch.
Danke!
-
rapso schrieb:
muestest du das durch einen quadtree machen, wuerdest du O(log n) and zeit brauchen statt O(1) wie beim Grid
Man kann den Quadtree ohne weiteres so implementieren, dass die Nachbarn in O(1) gefunden werden können.
-
Genau vor dem Problem stehe ich gerade.
Ich weiß nicht, wie ich feststellen kann, wieviele Nachbarn ein Quadrat hat.
Rein theoretisch könnten es doch unendlich viele sein, je feiner die Rasterung ist (Baumtiefe).
Oder sehe ich das flasch?
-
T.jay03: Du hast immer noch keine genaueren Angaben zur Problemstellung gemacht. Soweit ich es verstanden habe würde ich wie rapso einfach den A* empfehlen. Ich verstehe nicht wirklich wozu Du nen Quadtree haben willst.
Mein Hinweis war eher theoretischer Natur und hat nichts mit Deiner konkreten Aufgabenstellung (die ich ja nicht kenne) zu tun.
-
Man kann den A* auf ein gerastertes Gitter anwenden. Hierbei werden jedoch nur horizontale/vertikale/diagonale Zick-Zack Wege gefunden. Der 2. Nachteil ist, die extrem lange Rechenzeit. Durch einen QuadTree kann man dieses Feld ebenso Rastern und alle Bereiche indenen kein Hindernis ist, zu einem großen Feld zusammenfassen. Dies sollte doch die Rechenzeit reduzieren. Weiterhin erhoffe ich mir, dass zwar immernoch Zick-Zack Wege entstehen, jedoch diese natürlicher aussehen.
Jetzt habe ich 2 Ansätze. Ich gebe dem A* alle Mittelpunkte der im QuadTree befindlichen Quadrate. Nun muss ich allerdings Wissen, wieviele und welche Nachbarn jedes Quadrat hat. Dies könnte man vorberecnen und zusätzlich Zeit sparen.
Der 2. Ansatz: Ich kombiniere diesen QuadTree mit dem Sichtbarkeitsalgorithmus, was aber wie ich denke zu komplex werden würde.Also nochmal ganz konkret:
Wie kann ich prüfen, welche und wieviele Nachbar Quadrate jedes Quadrat hat, damit ich dann z.B. den A damit füttern kann.*Zwischen zwei benachbarten Quadraten muss immer eine direkte Verbindung existieren.
Ich hoffe das war verständlich
-
Jester schrieb:
rapso schrieb:
muestest du das durch einen quadtree machen, wuerdest du O(log n) and zeit brauchen statt O(1) wie beim Grid
Man kann den Quadtree ohne weiteres so implementieren, dass die Nachbarn in O(1) gefunden werden können.
ja, fuer den sonderfall das die unterste eben ein grid ist. das bringt's natuerlich dann einen quadtree drueber zu packen.
-
rapso schrieb:
ja, fuer den sonderfall das die unterste eben ein grid ist. das bringt's natuerlich dann einen quadtree drueber zu packen.
nein und ja.
Auch wenn in dem Grid einige Punkte fehlen geht das noch prima.
Den Quadtree drüberzupacken kann Sinn machen, wenn man erst ne grobe und anschließend ne feine Suche macht. Beispielsweise könnte man in nem Vorverarbeitungsschritt einige Quads gleich ganz rauswerfen für bestimmte Suchanfragen.
-
Jester schrieb:
Auch wenn in dem Grid einige Punkte fehlen geht das noch prima.
sobald punkte fehlen, musst du ueber die node darueber nehmen, oder noch eine darueber, aber um ueberhaupt festzustellen wie weit du runtergehen kannst bis keine nodes mehr da sind muesstest du von der root ausgehen.
somit hast du O(log n) sobald kein prefektes grid drunter liegt.
Den Quadtree drüberzupacken kann Sinn machen, wenn man erst ne grobe und anschließend ne feine Suche macht. Beispielsweise könnte man in nem Vorverarbeitungsschritt einige Quads gleich ganz rauswerfen für bestimmte Suchanfragen.
Dafuer benutzt man multi-resolution-grids (ist glaub ich in irgendeinem gem programming games zu beschrieben). hat viel weniger verwaltungsaufwand als ein tree.
-
rapso schrieb:
Jester schrieb:
Auch wenn in dem Grid einige Punkte fehlen geht das noch prima.
sobald punkte fehlen, musst du ueber die node darueber nehmen, oder noch eine darueber, aber um ueberhaupt festzustellen wie weit du runtergehen kannst bis keine nodes mehr da sind muesstest du von der root ausgehen.
somit hast du O(log n) sobald kein prefektes grid drunter liegt.
Ich erklär's einfach mal am 1D-Beispiel:
Du hast eine gerasterte Linie und einige Punkte fehlen. Die sortierste in nen (balancierten) binären Baum ein. Nun willste den Nachbarn eines gegebenen Punktes finden. Das kostet O(log n).
Führst Du aber gleichzeitig die Blätter geordnet in einer doppelt verketten Liste mit (das kann man beim Einfügen/Löschen miterledigen), dann kannste die Nachbarn in O(1) finden, indem Du Deiner Liste einfach nach links/rechts folgst.
Allerdings ist natürlich klar, dass im 2D-Fall logarithmisch viele Nachbarn haben kann. Die alle zu betrachten braucht also Zeit. Finden geht aber trotzdem schnell.
-
Jester schrieb:
Führst Du aber gleichzeitig die Blätter geordnet in einer doppelt verketten Liste mit (das kann man beim Einfügen/Löschen miterledigen), dann kannste die Nachbarn in O(1) finden, indem Du Deiner Liste einfach nach links/rechts folgst.
Wie ich schon sagte,
wenn die ganze unterste ebene vorhanden ist, hast du nicht mehr als ein sehr aufwendiges (multiresolution) grid.
wenn die unterste ebene nicht komplett vorhanden ist, kannst du nicht einfach einen nachbarn nehmen, da eine node dann mehrere nachbarn an einer seite haben kann
+---+++-+ | +++ | | +++-+ | | | | +---+-+-+wie findest du nun von der linken Node ausgehend in O(1) den richtigen rechten nachbarn?