Datenstruktur gesucht

Hi,

ich benötige eine passendere (vermutlich sortierte) Datenstruktur als map.

Folgendes Szenario:
In einer 2D-Ebene existieren bis zu 10.000 Punkte, die natürlich aus x und y Koordinate bestehen - jeweils ein double.
Es soll nun möglich sein durch eine "unscharfe" Anfrage eine Teilmenge der Punkte zu erhalten.
Sind die Koordinaten zB aus einem Bereich [0, 100]*[0, 100] lautet eine Anfrage:
"Gib mir alle Punkte, die euklidisch dichter als 30 an den Koordinaten 23/56 dran sind)!". Unscharf daher, da es keinen einzigen Punkt an genau dieser Stelle geben muss.

Bisher haben all meine Punkte einfach eine ID und ich gehe die map linear durch und entscheide für jeden Punkt, ob er dicht genug ist - dies dauert allerdings viel zu lange da es sich um eine echtzeitkritische Anwendung handelt.

Gibts da eine bessere Möglichkeit?

Im 1D-Fall (Punkte haben nur x-Koordinate) ist es natürlich leicht - ich nehme eine priorityQueue mit x als key und gehe vom dichtesten ausgehend nach links und rechts und sammel alle ein. Notfalls durch einen selbstgebauten balancierten Suchbaum. Ich könnte auch die beiden Intervallgrenzen in log(N) Zeit suchen und alles dazwischen ausgeben - Aber im 2D?

Worüber ich natürlich schon nachdenke sind "submaps" bzw. "Planquadrate" oder "Quadranten". Dh ich durchsuche weiterhin linear Datenstrukturen - aber eben nur diejenigen, die mögliche Kandidaten enthalten.
Hierbei ist aber das Problem, dass die Punkte regelmäßig leicht verschoben werden und somit auch von Quadrant zu Quadrant wechseln - dh ich müsste jeweils aus einem Quadranten entfernen und in einem anderen einfügen. Außerdem hatte ich gehofft es gibt evtl. jemanden der eine schnellere Lösung kennt.

Noch einige Infos:
Es passiert nur zu 0,01%, dass ein neuer Punkt dem Feld hinzugefügt wird - hier darf also auch gerne Laufzeit nötig sein, um eine sortierte Datenstruktur zu erhalten. (Das Programm initialisiert mit einem leeren Feld). Die restlichen 99,9% entfallen auf "Auswahl des geeignetsten Punktes aus der vorher ausgewählten Teilmenge". Anschließend wird der ausgewählte Punkt noch verschoben.

Schau dir mal nen Quadtree an.

also die genannten quadtrees sind eine möglichkeit.

das hier von dir:

kuddlmuddl schrieb:

Worüber ich natürlich schon nachdenke sind "submaps" bzw. "Planquadrate" oder "Quadranten". Dh ich durchsuche weiterhin linear Datenstrukturen - aber eben nur diejenigen, die mögliche Kandidaten enthalten.
Hierbei ist aber das Problem, dass die Punkte regelmäßig leicht verschoben werden und somit auch von Quadrant zu Quadrant wechseln - dh ich müsste jeweils aus einem Quadranten entfernen und in einem anderen einfügen. Außerdem hatte ich gehofft es gibt evtl. jemanden der eine schnellere Lösung kennt.

Zum Vergrößern anklicken....

eine andere und nein, das ist nicht langsamer, sondern schneller:

im grunde ist das nichts anderes als hashen. du diskretisierst deine x und y koordinaten. d.h. du kategorisierst. deine punkte aus [0..100]x[0...100] (double) sortierst du z.b. in ein 10x10
gitter ein, doer 100x100 gitter etc. indem du die koordinaten skalierst und rundest findest du den passenden quadranten.

diese methode macht sinn, wenn du pro quadrant im allgeminen nicht allzuviele punkte hast, bzw. wenn du genug arbeitsspeicher hast um deine gitter fein genug zu haben, damit das erfüllt wird. dann findest du den quadranten in konstnter zeit und bei nur konstant vielen punkten pro quadrant (im schnitt) den passenden punkt auch.

das verschieben von punkten geht in konstanter zeit: einfach aus einem quadranten entfernen (suchen, element an der gefundenen position löschen - nehme hier listen an - und in die liste des neuen quadranten einhängen).

hast du gar keine schranken für die konzentration der punkte an verschiedenen stellen, dann sind die quadtrees die richtige wahl.

unter umständen mcaht es sinn beides zu kombinieren.

EDIT: jeh nach anwendungsszenario kannst du beides auch dynamisch kombinieren, d.h. in ein gitter hashen und für die quadranten listen benutzen. und falls in einem quadrant zuviele punkte landen (mit der zeit kann das ja passieren), die liste dieses quadranten durch einen quadtree ersetzten, aber nur für diesen quadranten. sinkt die zahl wieder änderst du nichts.

Ein relativ simpler und schnell programmierter Ansatz:

Ich würde die Punkte in 2 Listen sortieren. Eine wo die Punkte nach X-Koordinaten sortiert sind und eine nach Y-Koordinaten sortiert sind.

Wenn du dann fragst, gibt mir Punkte welche eine maximale Entfernung von 3.0 haben, dann könntest du einfach erst durch Intervallhalbierung die in Frage kommenden Punkt in der ersten Liste und zweiten Liste ermitteln.

Anschließend bildest du die Schnittmenge -> Das sind deine Trefferkandidaten.


Punktverschiebungen sollten relativ einfach sein, indem du bei jedem Punkt dir zusätzlich noch merkst wie der index jeweil in der x bzw. y-liste ist, dann kannst du diese sehr schnell entfernen und wieder durch intervall-halbierung sehr schnell an der richtigen stelle wieder einsortieren.


Ist sicher nicht der perfekte Algorithmus, aber es ist sehr einfach und reicht von der Performance vermutlich.

man sollte bei banthors ansatz beachten: das bestimmen der schnittmenge (ohne weiteres) ist quadratisch in der menge der punkte. und da man erst einmal eine der beiden koordinaten ganz ignoriert kann das schon ein lineare anteil der gesamtpunktmenge sein -> nein, vermutlich reicht die performance davon nicht aus.

man müsste die schnittmengenbestimmung effizienter machen (was auch geht, aber nicht unbedingt das ganze einfacher macht), oder das setting passt zu dem ansatz.

auserdem noch ein problem, wenn nach euklidischen abständen gefilter werden soll, dann hat man mit dem ansatz noch ein problem: der ansatz such nur alles in x abstand (z.b.) 3 und y abstand 3. in der diagonale muss aber x und y kleiner sein (kreis halt).

bei den obigen ansätzen gibt es mehrere möglichkeiten das zu erreichen (unter anderem radialkoordinaten, also radius und winkel).

Dese schrieb:

man sollte bei banthors ansatz beachten: das bestimmen der schnittmenge (ohne weiteres) ist quadratisch in der menge der punkte. und da man erst einmal eine der beiden koordinaten ganz ignoriert kann das schon ein lineare anteil der gesamtpunktmenge sein -> nein, vermutlich reicht die performance davon nicht aus.
).

Zum Vergrößern anklicken....

Ich denke nicht, dass das quadratisch ist. Quadratisch wäre es nur, wenn ich beide Listen linear durchsuchen würde. Mein Vorschlag war jedoch eine Intervallhalbierung zu nutzen.

Das man die gefundenen Punkte noch genauer anschauen muss ist auch klar, denn es sollen ja die Elemente im Umkreis und nicht im Rechteckt gesucht werden. Deshalb schrieb ich auch, dass das erstmal nur Kandidaten sind. Es geht ja in erster Linie ja daru m die Punktwolke aus 10000den Elementen auf ein handliches Maß zu reduzieren.

Je nachdem wie "dicht" diese Punkte in der Praxis sind, wird der Algorithmus denke ich schon schnell genug sein. Das muss man einfach mal ausprobieren. Wenn nicht, kann man sich immer noch etwas komplizierteres suchen.

Hi!

Ich knobel auch gerade dran rum. Ich hätte noch ein paar Fragen bezüglich des Szenarios.

- Ist die Ebene tatsächlich so groß, dass sie mit double Werten angesprochen werden muss? Was wären maximale Ausmaße?

- Sind die Suchdistanzen immer die gleichen, jeweils nur von unterschiedlichen Punkten aus, oder varrieren diese ebenfalls?

- Wie sieht es mit der erlaubten Speicherbelegung aus? Beliebig oder auch begrenzt?

Erstmal danke für die rege Teilnahme und die qualifizierten Kommentare.

Der Quadtree sieht schon sehr gut aus - er ist ja im Grunde ähnlich der Idee mit submaps wobei die Auflösung dynamisch den Bedürfnissen angepasst ist.
Da meine Punkte aber grob gesagt gleichverteilt sind und die max Anzahl auch ziemlich genau vorher bekannt ist, ist der Vorteil vermutlich nicht groß genug diese dynamischen Datenstruktur zu verwenden gegenüber der statischen submaps.

Das was Dese sagt ist auch das was ich vorhatte..

das verschieben von punkten geht in konstanter zeit: einfach aus einem quadranten entfernen (suchen, element an der gefundenen position löschen - nehme hier listen an - und in die liste des neuen quadranten einhängen).

Zum Vergrößern anklicken....

Das was Banthor vorschlägt hatte ich auch schon überlegt - ich denke nur, der Geschwindigkeitsvorteil ist nicht groß genug und da kann ich auch direkt die Submaps umsetzen. Außerdem stört mich die "doppelte Datenhaltung" die ich natürlich über Pointer realisieren könnte - aber dann wird das ständige "aus einer sortierten Liste rausnehmen und an einer anderen Stelle einfügen" ja doppelt so oft nötig. Außerdem kostet das Schnittmengen bilden dann sicher zu viel Zeit. Dann würde ich eher direkt NUR nach x sortiert arbeiten und meine generierte Teilmenge würde einfach aus allen Punkten bestehen, die zumindest nach x betrachtet noch nicht den max-erlaubten Abstand überschreiten.
Das dabei keine "Kreise" sondern "Quadrate" entstehen wäre kein großes Drama - nur halt nicht Optimal. Die Teilmenge wird eh immer so gewählt, dass sie "Überschätzt" damit der einzige Punkt den ich im Endeffekt suche auch tatsächlich enthalten ist.

- Ist die Ebene tatsächlich so groß, dass sie mit double Werten angesprochen werden muss? Was wären maximale Ausmaße?

Zum Vergrößern anklicken....

Es handelt sich um reale Areale von bis zu mehreren km wo halt Koordinaten mit Nachkommastellen gespeichert werden sollen - float reicht nicht, wie ich durch probieren rausgefunden habe (schneller wurds dadurch auch nicht).

Sind die Suchdistanzen immer die gleichen, jeweils nur von unterschiedlichen Punkten aus, oder varrieren diese ebenfalls?

Zum Vergrößern anklicken....

Das steht nicht so richtig fest - ich könnte auch erstmal mit konstanten Suchdistanzen arbeiten aber da ich auf den ersten Blick (unabhängig vom Karten Ansatz) keinen vorteil gesehen habe, diese konstant zu lassen wollte ich erstmal auch dynamische zulassen.

- Wie sieht es mit der erlaubten Speicherbelegung aus? Beliebig oder auch begrenzt?

Zum Vergrößern anklicken....

Das gesamte Programm liegt zur Zeit unterhalb von 3MB RAM - es soll zwar theoretisch evtl. auch mal in ein EBS aber erstmal ist dem Speicher absolut keine Grenze gesetzt

Ich denke die Idee mit den Submaps ist bisher immernoch das vielversprechendste..

Bischen was zum Hintergrund:
Die Punkte sind Orientierungspunkte von Robotern (sogenannte Landmarken) und das Areal ist halt eine reale Umgebung in der ein autonomes Fahrzeug fährt - also begrenzt aber durchaus mehrere km groß.

Bisher ist der Ablauf wie von den erfindern des Algorithmus auch vorgeschlagen ganz stupide:
Sieht der Sensor eine Landmarke versucht der Algorithmus diese Landmarkensichtung einer bekannten Landmarke zuzuordnen (Sensor-Daten-Assoziation). Da jede Landmarke als eine Normalverteilung modelliert wird (Mittelwert als schon genannte x, y Koordinate und zwei StdAbweichungen) kann hier nicht einfach die Landmarke als "erkannt" benutzt werden die am dichtesten an der Sichtung liegt sondern es muss über nen Maximum-Likelihood-Schätzer die "wahrscheinlichste" gewählt werden. Einfach gesagt: Liegen zwei Landmarken ähnlich dicht an der Sichtungsposition wird diejenige gewählt, deren Position unsicherer ist - dh deren Gausglocke breiter und flacher ist.
Da aber eben diese berechnung der Assoziationswahrscheinlichkeit relativ Viel Zeit in Anspruch nimmt und natürlich O(N) (N Anzahl der LM) benötigt habe ich das ganze erstmal ganz stupide beschleunigt indem ich einen Schwellwert benutze - nur von Landmarken, die eine maximale Entfernung von der Sichtung aus nicht überschreiben wird überhaupt die Assoziationswahrscheinlichkeit berechnet - sonst ist sie immer einfach 0.
Diesre Ansatz kostet ist zwar immernoch O(N) aber ich berechnet nur selten - der Geschwindigkeitsunterschied war schon enorm. Allerdings habe ich in meinen Testszenarien auch höchstens 200 Landmarken für die es gerade noch echtzeitfähig funktioniert - realistisch sind aber leider bis zu 10.000. Dh ich kann unmöglich bei jeder Landmarkensichtung alle 10.000 durchgehen - und nur für den euklidisch "dichten" Teil die Wahrscheinlichkeit berechnen sondern brauch irgendein vorauswahl von Teilmengen - wahrscheinlich wirklich am besten über Submaps.
Der Scanner hat ne 360° Scanfrequenz von ca 10Hz und pro Scan können schon mal mehr als 10 Landmarken gesehen werden - die Verarbeitung einer Landmarkensichtung darf also aller höchstens 10ms benötigen und die hier diskutierte Auswahl der geeignetsten Landmarke darf nur einen Bruchteil davon in Anspruch nehmen..

Edit:
Hier nochmal ein Bild dazu, wie das ganze mit submaps aussehen soll:

Im blauen Quadranten wird ein Objekt gesehen und nur der blaue und die angrenzenden Grünen sind die "Teilmenge" deren Landmarken zur Berechnung der Assoziationswahrscheinlichkeit verwendet werden.
Dynamische euklidische Abstände sind so auch leicht zu realisieren, weil ich einfach nur jedesmal die entsprechend nahen Quadranten wählen muss.

Der große Vorteil dieses Ansatzes wäre auf jeden Fall, dass es nahezu egal ist, wie groß das Areal eigtl ist und daher auch, wie viele Landmarken im Endeffekt verwendet werden. Wichtig für die Geschwindigkeit ist dann nur die dichte der Landmarken, die nie besonders hoch sein wird. Aus kostengründen werden tatsächlich sogar meist so wenig wie möglich dieser Landmarken verwendet.

Frage zu Deinem Scanner der wird dir doch nicht Position sondern Winkel und Distanz liefern, oder?

Wenn dem so ist und unter den anderen Voraussetzungen: Sehr viele Abfragen, bei wenig Änderungen der eigenen oder Fremdpositionen und nur sehr wenig Zeit für die Berechnungen. Bist du eigentlich bei dem gleichen Problem wie die ersten Ego-Shooter angekommen. Das war jetzt kein Scherz. Für dein Problem dürfte es sich lohnen mal einen Blick in die DOOM-Engine zu werfen. Die standen damals eigentlich vor dem gleichen Problem, wie du jetzt. Die benutzten Binary-Space-Partition und haben die Form der möglichen Objekte auf Quadrate (dürfte als Hüllform für deine Normalverteilung ausreichen) und Geraden beschränkt. Wenn dir das reicht, findest du da eine sehr schnelle Implementierung. Was du natürlich vorher machen musst, ist deine Eingangsdaten entsprechen vorbehandeln, aber dafür dürftest du wesentlich mehr Zeit und Speicher habe als bei der einzelnen Suche.

Also, wenn du sagst, Speicher ist egal, feste Distanzen wären möglich und es werden nur sehr selten Punkte hinzugefügt, dann könnte man auch folgendes probieren:

• Eine Liste, die alle existierenden Punkte hält.
• Beim Hinzufügen eines neuen Punktes werden alle bereits existierenden Punkte gesucht, die im Suchradius des hinzuzufügenden Punktes sind. Diese Punkte werden als "Suchmenge" innerhalb einer Liste im neuen Punkt gespeichert. Äquivalent dazu wird der neue Punkt in die Liste jedes Punktes der Suchmenge eingetragen.

Damit hast du zwar ein ordentliches Maß an Redundanz, wenn der Radius allerdings klein genug ist und/oder die Punktedichte nicht allzu hoch ist, wie du ja selber meintest, müssten die Abfragen schon deutlich schneller funktionieren.

Banthor schrieb:

Ich denke nicht, dass das quadratisch ist. Quadratisch wäre es nur, wenn ich beide Listen linear durchsuchen würde. Mein Vorschlag war jedoch eine Intervallhalbierung zu nutzen.

Zum Vergrößern anklicken....

ja das geht, dann hast du eine laufzeit von n*log n. die eine liste musst du linear durchsuchen und in der anderen kannst du mit intervallhalbierung in log n zeit checken ob der punkte der ersten liste drinn ist.

immer noch um welten langsamer als alle oben beschriebenen methoden.

aber ja, mein fehler, n*n ist es nicht, vorausgesetzt, die listen sind sortiert.

man beachte dann aber, die listen sortiert halten hat pro einfüge operation eine laufzeit von Theta(L), L die listenlänge, also auch linear pro einfgefügten punkt.

oder anders, mit der methode bist du mindestens um den faktor n insgesamt langsamer als alle obigen methoden.

@ghorst: das haben wir doch schon oben

Bei festen distanzwerten, also im vorfeld bekannten abzufragenden distanzen und wenn die zeit beim generieren der daten (beim einfügen der landmarken) im grunde egal ist, dann ist sowas wie von Killkrog beschrieben machbar.

nur, schneller als mit den obigen methoden wirst du eigentlich auch wieder nicht, da du ja mit geeigneter gitterwahl dieselbe laufzeitschranke erreichst.

im grunde bleibt die gittermethode + evtl. dynamische verfahren innerhalb eines quadranten sowohl die laufzeit effektivsten als auch die flexibelsten methode.

wenn du die gitter fein genug wählst hast du in konstanter zeit deine distanzabfragen beantwortet. musst du innerhalb eines gitter weiter filtern, so kannst du das in logarithmischer zeit innerhalb eines quadranten, der aber nur wenige (bei geigneter wahl konstant viele punkte enthält). besser geht's nicht.

Die Idee von Killkrog wäre natürlich optimal unter der Voraussetzung, dass einmal eingetragene Objekte an ihrem Platz bleiben - aber genau da liegt das Problem.
Bei jeder erneuten Sichtung einer bereits bekannten Landmarke (die 99,9% der Fälle) wird die Position aktualisiert - dh ich müsste aufgrund der Redundanz jede andere Landmarke angucken, und die aktuell veränderte auch dort aus- bzw. eintragen. Die Landmarken "wandern" nämlich garnicht mal so wenig.
Somit scheidet das Verfahren leider aus.

Ghorsts BSP klingen auch interessant - ich habs mir mal bischen angelesen. Und natürlich sind neben X/Y auch Winkel und Abstand vorhanden. Der Sensor liefert immer gleich beides und ich verwende mal das eine und mal das andere.
Bevor ich da einschätzen kann, ob sowas:
http://symbolcraft.com/graphics/bsp/
auch in meinem Fall einen so großen Vorteil hat, muss ich erst nochmal
http://doom.wikia.com/wiki/Doom_rendering_engine
genauer durchlesen... mach ich nachher.
Ich vermute mal ich könnte dadurch quasi den Winkel einschränken aber evtl. nicht den Abstand. Ich glaub mittlerweile, dass die Submaps schon ziemlich gut sind und vor allem auch noch am leichtesten zu realisieren.
Was ich mich aber im Zusammenhang frage ist dann, wie das bei Strategie-Spielen gelöst wird. Wenn ich zB in Warcraft3 mit nem Flächenangriff auf der Karte rumbewege werden die betroffenen Einheiten eingefärbt - dh es wird der FPS entsprechend entschieden, welche Einheiten betroffen sind. Die können also im Prinzip auch genau meins extrem schnell. Andererseits wird War3 ja auch auf modernen High-End Rechner langsam, sobald man mit vielen Einheiten spielt wie bei Footmen-Frency.
Aber bei nem C&C/Starcraft/... stellt sich ja die selbe Frage, wenn irgendwo ein Flächenangriff stattfindet und die haben dafür eine brauchbare Lösung. Sieht man in den Map-Editoren nicht auf Wunsch so ein eingeblendetes Gitternetz? Evtl ist für jede Einheit einfach vermerkt in welchen Gitternetz-Quadranten (anstatt an welcher reelwertigen Koordinate) sie sich gerad befindet. Dann wäre das ja direkt der Submap-Ansatz.

Dese schrieb:

ja das geht, dann hast du eine laufzeit von n*log n. die eine liste musst du linear durchsuchen und in der anderen kannst du mit intervallhalbierung in log n zeit checken ob der punkte der ersten liste drinn ist.

immer noch um welten langsamer als alle oben beschriebenen methoden.

aber ja, mein fehler, n*n ist es nicht, vorausgesetzt, die listen sind sortiert.

man beachte dann aber, die listen sortiert halten hat pro einfüge operation eine laufzeit von Theta(L), L die listenlänge, also auch linear pro einfgefügten punkt.

oder anders, mit der methode bist du mindestens um den faktor n insgesamt langsamer als alle obigen methoden.

Zum Vergrößern anklicken....

Ich will nicht kleinlich sein, aber du machst es immer noch langsamer als es ist.

Punkt 1:
Die erste Liste muss man nicht linear durchsuchen, auch hier kann man mit einer Intervallhalbierung das "Zielgebiet" finden. Anschließend findet man sofort alle "Nachbarn", die auch Treffer sind.

Wie der TE schrieb, könnte man optimieren, indem man an Ort und Stelle die andere Koordinate prüft, dann musst man keine Schnittmenge bilden.

Punkt 2:
Das Einfügen in eine sortierte Liste hatte keinen linearen Aufwand. Hier kann Ebenfalls mit Intervallhalbierung sehr schnell die richtige Stelle gefunden werden.


Natürlich ist das nicht der schnellste Algorithmus, aber man muss sich grundsätzlich immer fragen "Wie schnell muss etwas denn sein?" Die Antwort ist: schnell genug!

Bubblesort z.b. ist für kleine Sortiermengen vollkommen ausreichend und nicht relevant langsamer als quicksort. Bubblesort ist aber wesentlich schneller gecodet als Quicksort und von den meisten Codern vermutlich sogar seltener mit Fehlern behaftet.



Ich sehe das auf der Arbeit immer wieder, wie Leute teilweise viele Tage in die Optimierung eines Codes investieren und sich damit brüsten, dass dieser nun 10x schneller ist. Dass dieser Code aber für weniger als 1% der Laufdauer verantwortlich ist und die Optimierung allenfalls messbar ist wird dann vergessen.

Wenn ich nun die weiteren Ausführungen des TE lese, denke ich allerdings, dass er für den Anwendungszweck gleich den besten Algorithmus nehmen sollte. Die Punktwolke, die er bearbeitet wird in Zukunft vermutlich stetig wachsen, da kommt es dann auf jedes bißchen an.

Ich wünsch dem TE jedenfalls viel Spass bei der Implementierung, da hätte ich auch gerade Bock drauf...

kuddlmuddl schrieb:

Was ich mich aber im Zusammenhang frage ist dann, wie das bei Strategie-Spielen gelöst wird. Wenn ich zB in Warcraft3 mit nem Flächenangriff auf der Karte rumbewege werden die betroffenen Einheiten eingefärbt - dh es wird der FPS entsprechend entschieden, welche Einheiten betroffen sind. Die können also im Prinzip auch genau meins extrem schnell. Andererseits wird War3 ja auch auf modernen High-End Rechner langsam, sobald man mit vielen Einheiten spielt wie bei Footmen-Frency.
Aber bei nem C&C/Starcraft/... stellt sich ja die selbe Frage, wenn irgendwo ein Flächenangriff stattfindet und die haben dafür eine brauchbare Lösung. Sieht man in den Map-Editoren nicht auf Wunsch so ein eingeblendetes Gitternetz? Evtl ist für jede Einheit einfach vermerkt in welchen Gitternetz-Quadranten (anstatt an welcher reelwertigen Koordinate) sie sich gerad befindet. Dann wäre das ja direkt der Submap-Ansatz.

Zum Vergrößern anklicken....

Bei diesen Spielen ist der Suchalgorithmus der betroffenen Einheiten mit Sicherheit unterfordert. Bei Warcraft3 z.b. sind doch höchstens 90 Einheiten/Spieler auf der Karte. Da würde sich selbst ein Algorithmus, der jedes Element einzeln prüft, sich langweilen.

Das Strategiespiel mit den meisten gleichzeitigen Einheiten ist vermutlich Supreme Commander, wo im Extremfall bis zu 4000 Einheiten auf dem Schlachtfeld sind (500 max / Spieler) und selbst da wird sich jede CPU langweilen.

Ich denke, dass diese Spiele andere Performanceprobleme haben: Schwarm-KI + Wegfindung.

Ich denke, dass diese Spiele andere Performanceprobleme haben: Schwarm-KI + Wegfindung.

Zum Vergrößern anklicken....

Auch hierbei schafft selber lesen Klarheit...
Wen es interessiert: Warzone2100 ist im Sourcecode verfügbar und wird auch noch gepflegt: wz2100.net. Die beschreiben die Wegfindung als eines ihrer Probleme und haben dazu sogar einen kurzen Übersichtsartikel in ihre Wiki gestellt. Das dort genutzte Konzept wird aus meiner Sicht dem OT aber eher wenig helfen.

Darfst du die Ebene in eine feste Anzahl von Unterbereichen einteilen?

Wenn ja, könntest du für jeden dieser Bereiche eine doppelt verkette Liste mit Punkten anlegen, die in diesem Unterbereich liegen. Das jeweils erste Element solch einer Liste speicherst du in einem Array.

Auf diese Weise kannst du für jeden Punkt den Index des Bereichs berechnen, in dem er liegt. Damit natürlich auch die Indize der Nachbarbereiche. So hast du Zugriff auf alle Listen mit Punkten, die überhaupt erst für eine Überprüfung in Frage kommen würden. Je kleiner die Unterbereiche sind, desto genauer kannst du die kritischen Listen bestimmen.

Wenn sie eine Landmarke bewegt, kannst du berechnen, von wo nach wo sich der Punkt bewegt hat und die zwei entsprechenden Listen aktualisieren.

Darfst du die Ebene in eine feste Anzahl von Unterbereichen einteilen?

Zum Vergrößern anklicken....

Ich darf einteilen wie ich möchte.
Das Problem ist nur, dass die Orientierung (Richtung) der Karte nicht von vorn herein bekannt ist. Ich kann also nicht zu Beginn wissen, dass nur im Bereich [-100, 500]*[-100, 100] Werte liegen, weil es sich um einen Flur handelt, der zB 500 lang ist in x. Ich müsste dann die 500 in alle Richtungen vorsehen. Ich überlege daher das ganze direkt "dynamisch" zu machen. Dh ich gebe in meiner neuen Karten-Datenstruktur zwar vor, wie groß ein Quadrant ist (zB 10 Meter Kantenlänge) aber es werden dynamisch neue Quadranten angelegt, sofern eine Landmarke der gesamten Karte hinzugefügt wird, die außerhalb aller bisherigen Quadranten liegt.
Also zB ein 2x2 Vector für die Quadranten der jeweils ne Liste enthält

könntest du für jeden dieser Bereiche eine doppelt verkette Liste mit Punkten anlegen

Zum Vergrößern anklicken....

Sowas in der Art habe ich auch vor. Obs da dann ne list, map oder set wird muss ich nochmal sehen.. da sie ungeordnet sein dürfen ists wahrscheinlich egal, da ich eh linear alle durchgehen muss.

Auf diese Weise kannst du für jeden Punkt den Index des Bereichs berechnen, in dem er liegt. Damit natürlich auch die Indize der Nachbarbereiche. So hast du Zugriff auf alle Listen mit Punkten, die überhaupt erst für eine Überprüfung in Frage kommen würden. Je kleiner die Unterbereiche sind, desto genauer kannst du die kritischen Listen bestimmen.

Zum Vergrößern anklicken....

Für jeden Punkt den Index des Quadranten zu bestimmen brauche ich nie, oder? Die Abfage läuft ja eher andersherum: Ich nehme einen Quadranten und gucke mir dessen Inhalt an. Dann weiß ich ja eh schon, welchen Quadranten ich gerad habe.

Das grundsätzliche Problem ist der zweite Performance-Flaschenhals: Die Karte wird zur Laufzeit viele male dupliziert, leicht modifiziert und evtl. gelöscht - es existieren also meist ca 200 "ähnliche" Karten. Daher wäre dann doch minimaler Speicherbedarf wichtig - habe ich oben nicht bedacht. Es existiert immer genug Ram, aber (speichertechnisch) große Karten führen natürlich zu extrem langsamen Kopiervorgängen.
Um diese Redundanz nicht mitzukopieren existiert schon ein Vorschlag, wie man dies über Bäume in O(logN) statt O(N) realisiert, aber dann verliere ich (glaube ich) die Möglichkeit diesen Quadrantenansatz umzusetzen..
Da ich aber bisher beides nicht implementiert hab ist jetzt die Frage was mehr bringt, und ob mans doch vereinen kann... muss ich nochmal drüber nachdenken :/
Oder nochmal mit dem neuen VisualStudio Profiler genauer untersuchen was mehr Zeit verschlingt bei großen Karten: Das vielfache Kopieren von Redundanten Kartenteilen oder die lineare Suche nach der aktuell gesehenen Landmarke

Auch wenn es wahrscheinlich niemanden mehr interessiert wollte ich nochmal neue Erkenntnisse mitteilen.
Ich bin leider nicht dazu gekommen wirklich etwas auszuprobieren aber bin zufällig auf eine Lösung gestoßen, als ich mich mit etwas ganz anderem beschäftigt habe.
Der Tipp von ghorst war schon genau richtig - und auch sein beschriebener Ansatz.
Im Prinzip taucht das selbe Problem auf beim Thema Collision_detection wo eben auch genau sein Vorschlag mit Achsenparallelen Quaderförmigen Hüllen beschrieben wird.
Hier nur der Link, falls es wen interessiert:
http://en.wikipedia.org/wiki/Collision_detection#Optimization
http://en.wikipedia.org/wiki/Sweep_and_prune

Da ich ja die wenigen bei diesem Verfahren entstehenden Kandidaten einfach manuell prüfen kann ist das sicher "optimal" so.

Wenn ich das jetzt richtig verstehe, klingt dein gewählter Ansatz nach einem k-d-Baum. Oder liege ich da völlig falsch?

bei fixen punktmengen ist ein k-d baum effizient.
bei dynamischen punktmengen aber ist der quadtree flexibler.

macht ihr gerade so eine computer graphics veranstaltung in der uni oder wie?
das wird noch richtig hart, wenn ihr 3d-punktmengen bzw objekte glätten sollt.

Die Idee mit dem k-d-Baum wurde glaub ich damals schon irgendwo gemacht
Das Problem ist, dass die Punkte leicht wandern, da die Position bei mehrmaliger Beobachtung immer etwas anders sein wird.
Der Quadtree - evtl auch mit fixer Rasterbreite, da die Punkte gleichverteilt sind - war ja auch meine Idee das ganze beschleunigt aber einfach umzusetzen.

Die Idee von ghorst aus den 3D-Shootern (Kollisions-Detektion) ist aber noch eine andere. Man verwaltet die Punktmenge zB in einem Array aber speichert redundant Listen je Koordinaten-Achse die man immer sortiert hält.
Dh eine Liste wo nur die X-Koordinaten sortiert sind und eine wo nur die Y-Koordinaten sortiert sind.

Das ganze kommt aus der Robotik:
Ein Fahrzeug sieht einen Orientierungspunkt und fragt sich, ob es den schon kennt.
Hierfür wird für jeden bereits bekannten Orientierungpunkt berechnet, wie wahrscheinlich es ist, dass es sich um diesen handelt. Quasi wie der Abstand zwischen "bei (x1/y1) sehe ich etwas" und "bei (x2/y2) kenne ich schon einen punkt" mit noch zusätzlich der Berücksichtigung der Messgenauigkeit.
Maximum-Likelihood-Schätzer..
Ist dann kein Punkt passend genug wird die gesehene Landmarke als "neu" Klassifiziert und der Karte hinzugefügt.

Das grundsätzliche Problem ist, dass es noch einen weiteren Laufzeit-Flaschenhals gibt.. die Karten werden pausenlos zu hunderten leicht variiert kopiert und verworfen (SMCM) - dh jede Art von zusätzlicher Datenmenge macht diesen Schritt deutlich langsamer. Ich würde das Problem eigtl. nur verschieben, wenn ich die Identifikation beschleunige aber das Kopieren weiter verlangsame.
Hier müsste ich erstmal für Große Szenarien ausprobieren, was eigtl. mehr Zeit kostet - das kopieren oder die Landmarken-Identifikation.
So gut diese Idee nun auch ist, wirds daher wahrscheinlich doch maximal auf die Rasterung rauslaufen.. Siehe auch #8 von mir mit dem Bild.