[Alg] Neighbour finding

[Verwijderd]

Ik heb een array van ruwweg honderdduizend objecten, die elk een x en y positie hebben. Nu moet ik bepalen welke van deze objecten zich binnen een straal r van een specifiek object S bevinden. Aangezien het hier om een programma met een wetenschappelijk doel gaat (meer specifiek, een classifier system) is het belangrijk dat het een beetje efficient met zn clockcycles omgaat, want hoe sneller het draait, hoe groter ik mijn simulatie kan maken. Ik wil dus voorkomen dat ik telkens de hele array door moet lopen om voor elk object de afstand tot S te bepalen en te checken of die kleiner is dan r. Het probleem wordt wat lastiger doordat de objecten kunnen bewegen, waardoor hun posities voortdurend veranderen, en doordat r van object tot object verschilt.

Kennen jullie een algoritme dat hier een beetje efficient mee om kan gaan?

[DieterVDW]

Ik zou al eerst de objecten sorteren op een van de twee coordinaten, neem bvb de x .
Als je dan de 2 objecten zoekt met de grootste en kleinste x waarvoor geldt dat x0-r <= x <= x0+r,
dan kun je sowieso al alle objecten die buiten die 'range' liggen elimineren.
Je kan dan nog sorteren op de tweede coordinaat per x coordinaat ook, en per kandidaat x coordinaat op dezelfde manier een range van kandidaat objecten afbakenen.
Je weet dan al zeker dat die kandidaten in het r*r vierkant rond je doelcoordinaat ligt,
je moet dan enkel nog eens van die kandidaten checken of ze ook binnen de cirkel liggen rond je doelkandidaat.

Je bewering dat de posities voortdurend veranderen doet die gehele uitleg wel zo'n beetje teniet,
aangezien je dan telkens opnieuw moet sorteren...
Maar misschien kun je de 'verplaatsing' handig implementeren zodat de sortering consistent blijft zonder alles opnieuw te moeten sorteren.

Mijn beste idee tot nu toe...

[Verwijderd]

Ik zou al eerst de objecten sorteren op een van de twee coordinaten, neem bvb de x .
Als je dan de 2 objecten zoekt met de grootste en kleinste x waarvoor geldt dat x0-r <= x <= x0+r,
dan kun je sowieso al alle objecten die buiten die 'range' liggen elimineren.
Je kan dan nog sorteren op de tweede coordinaat per x coordinaat ook, en per kandidaat x coordinaat op dezelfde manier een range van kandidaat objecten afbakenen.
Je weet dan al zeker dat die kandidaten in het r*r vierkant rond je doelcoordinaat ligt,
je moet dan enkel nog eens van die kandidaten checken of ze ook binnen de cirkel liggen rond je doelkandidaat.

Je bewering dat de posities voortdurend veranderen doet die gehele uitleg wel zo'n beetje teniet,
aangezien je dan telkens opnieuw moet sorteren...
Maar misschien kun je de 'verplaatsing' handig implementeren zodat de sortering consistent blijft zonder alles opnieuw te moeten sorteren.

Mijn beste idee tot nu toe...

Hier heb ik ook al aan gedacht... Maar inderdaad, het voortdurende bewegen is een probleem hiermee. Ik ben nu aan het uitzoeken of het mogelijk is per turn voor elk object eerst de neighbours te bepalen voordat beweging plaatsvindt, en om dan eventuele bewegingen tijdens de turn simpelweg te negeren. Op die manier zou ik maar 1x per turn hoeven te sorteren. Levert wel wat "lag" op, maar dat is juist wel goed denk ik: Dan ben ik meteen van het nadeel af dat een object dat eerst mag bewegen, misschien aan de interactie met zijn buurman kan ontsnappen.

Toch vraag ik me af of het niet handiger kan. Misschien een log bijhouden van welke objecten in range waren in de vorige turn? Dat zullen er nooit heel veel zijn (de ruimte is vrij groot), dus qua geheugen komt dat wel goed. Bijhouden of objecten sindsdien out of range bewogen zijn is niet zo moeilijk, maar hoe check ik dan of er nieuwe objecten in range gekomen zijn zonder weer alles langs te lopen...

[ Voor 11% gewijzigd door Verwijderd op 15-08-2005 07:10 ]

[jvdmeer]

Beweegt object S ook?

Zo niet, dan zou ik per object ook r bijhouden. Scheelt in ieder geval steeds de kwadraten uit te rekenen. Daarnaast, als de objecten zich niet te veel verplaatsen, dan zal de onderlinge volgorde van de verschillende r's niet te veel wijzigen.

Daarnaast kan je alleen een aparte array bijhouden met de objecten met een r < 2* (gewenste afstand). Val het object na verplaatsing binnen 2*r.

[MSalters]

Als je simulatie tick-based is, en de objecten bewegen langzaam genoeg, dan is er natuurlijk geen probleem. Objecten die eerst een afstand d hebben, hebben op de volgende tick een afstand [d-2v,d+2v]. Dat is maar een kleine verandering.

Verder kun je ook je objecten in een rastermet resolutie r*r indelen. In dat geval hoef je alleen punten te vergelijken uit de directe omgeving (9 rastercellen). Indien je puntenwolk veel groter is dan r, dan is dat een vrij grote besparing. Het is bovendien vrij triviaal om te bepalen of een punt of een grens schuift.

[jochemd]

Bewegen de objecten random? Hoe snel bewegen ze? Hoe dicht is je matrix?

Het idee van DieterVDW, dat bekend staat als een bounding box, is de simpelste mogelijkheid. Je kan daarnaast als ojecten relatief langzaam bewegen een tweede bounding box gebruiken om nog verder te cachen. Als de maximale snelheid waarmee objecten bewegen X is, bereken dan op t=0 niet alleen de bounding box r, maar ook de bounding box 2TX + r. Daarmee heb je alle objecten die de komende T beurten mogelijk binnen bereik komen te pakken en hoef je maar ééns in de T beurten de hele array door te lopen.

[.oisyn]

Is er maar 1 zo'n object S, of moet je het voor veel meer objecten weten? En hoe groot is de grootste r ten opzichte van de hele wereld waarin de bewegingen plaats vinden? En hoe verwacht je dat je objecten gaan bewegen?

Er zijn twee datastructuren die in mij op komen, een quadtree en een simpel grid. De quadtree heeft O(log n) insertion- en searchtime, voor het grid is dat respectivelijk O(1) en O(n) maar laat je door deze theoretische hoeveelheden niet van de wijs brengen .

Met een quadtree deel je je wereld recursief op in 4 gelijke delen (vierkanten dus, je hebt overigens ook een adaptive quadtree die je niet in gelijke delen deelt), en je insert de objecten in de bladeren van de boom. Op het moment dan x objecten in een bepaald blad zitten deel je dat blad weer op en insert je de objecten die in het blad zaten een niveau dieper. Zoeken gaat ongeveer hetzelfde: je begint bij de root node en je kijkt of de quadtree cell je object snijdt. Zo ja dan ga je verder met z'n 4 kinderen, en dat zo totdat je aan een blad bent en dan controleer je de objecten die daarin zitten.

Een grid is simpelweg een verdeling van je hele wereld in x bij y vaste cellen. Het nadeel hiervan is dat het in principe meer geheugen kan kosten dan een quadtree, maar het voordeel is dat je in constante tijd kunt bepalen in welke cel een object zit. Die O(n) zoektijd komt simpelweg van de aanname dat in elke cel gemiddeld n/(x*y) objecten zitten, in de praktijk valt dat bij een goed gekozen x en y dus erg mee, vooropgesteld dat je objecten in de wereld een beetje uniform verdeeld zijn.

Voor caching sluit ik me aan bij jochemd, tenzij je wat meer aannames kunt doen over de veranderingen in de bewegingen.

Wat clockcycles betreft, kies een taal als C++ en werk veel met pools waaruit je snel bepaalde blokken geheugen uit kunt alloceren. Probeer je datastructuur ook zo op te stellen dat hij goed werkt met de caches van de CPU: dus bijvoorbeeld geen array van pointers naar objecten die kris-kras door het geheugen staan, maar een array waarin de objecten echt sequentieel in het geheugen staan.

[MTWZZ]

[brainfart]
Is het niet een idee om in plaats van een aparte check methode tijdens de move actie van de objecten een check te maken.
Als S statisch is kun je neem ik aan bij een move actie bepalen of het object wel of niet binnen de range van S valt. Volgens mij elimineer je hiermee het probleem van het doorlopen van de tree/grid aangezien je dat toch al doet voor je collectie van objecten.
[/brainfart]

[Zoijar]

Misschien kan je ook eens "barnes hut" en "fast multipole methods (fmm)" opzoeken. Dat zijn bekende, complexe, algoritmen die worden gebruikt voor particle simulatie. Een bijkomstigheid daar is dat er bv zwaartekracht tussen elk deeltje moet worden uitgerekend, en je dus een O(n^2) operatie omzet naar een snellere variant. Verder zijn er parallele varianten bekend, in het geval je misschien toegang hebt tot een cluster computer.

(deze zijn ook gebaseerd op gebalanceerde space division trees)

[ Voor 10% gewijzigd door Zoijar op 15-08-2005 13:09 ]

[Verwijderd]

Allereerst, bedankt allemaal voor de reacties

Allereerst naar aanleiding van jullie vragen een (hopelijk) wat betere uitleg van het probleem

Ik heb 2 soorten objecten, laten we ze even class A en B noemen. Per cycle moet ik voor elk object uit A weten welke objecten uit A en uit B er zich binnen een afstand r bevinden. Objecten uit A kunnen bewegen, objecten uit B niet. De beweging die ze uitvoeren is, hoewel op het niveau van de individuele objecten doelgericht, op macroniveau min of meer random, en een object kan maximaal een afstand r_max bewegen per tick. De wereld is bij benadering 1000r_maxx1000r_max groot, en er zitten bij benadering 100.000 objecten in. Overigens kan r varieren per object uit A, van r_min tot r_max, waarbij er tussen die 2 ongeveer een factor 5 zit. Er zijn ruwweg 10000 objecten A, en 100000 objecten B.

Als je simulatie tick-based is, en de objecten bewegen langzaam genoeg, dan is er natuurlijk geen probleem. Objecten die eerst een afstand d hebben, hebben op de volgende tick een afstand [d-2v,d+2v]. Dat is maar een kleine verandering.

Helaas is de beweging van de objecten in de orde van grootte van r per tick.

Verder kun je ook je objecten in een rastermet resolutie r*r indelen. In dat geval hoef je alleen punten te vergelijken uit de directe omgeving (9 rastercellen). Indien je puntenwolk veel groter is dan r, dan is dat een vrij grote besparing. Het is bovendien vrij triviaal om te bepalen of een punt of een grens schuift.

Dit is inderdaad een idee. Het enige probleem dat ik hiermee zie is dat ik hiervoor een vrij grote array nodig zal hebben, aangezien de wereld toch zeker 1000rx1000r zal zijn qua omvang, en ik de mogelijkheid van meerdere objecten per cel open moet houden. Maar dit geeft inderdaad wel een grote besparing, aangezien er nooit meer dan enkele objecten per cel zullen zijn.

Er zijn twee datastructuren die in mij op komen, een quadtree en een simpel grid. De quadtree heeft O(log n) insertion- en searchtime, voor het grid is dat respectivelijk O(1) en O(n) maar laat je door deze theoretische hoeveelheden niet van de wijs brengen .

Met een quadtree deel je je wereld recursief op in 4 gelijke delen (vierkanten dus, je hebt overigens ook een adaptive quadtree die je niet in gelijke delen deelt), en je insert de objecten in de bladeren van de boom. Op het moment dan x objecten in een bepaald blad zitten deel je dat blad weer op en insert je de objecten die in het blad zaten een niveau dieper. Zoeken gaat ongeveer hetzelfde: je begint bij de root node en je kijkt of de quadtree cell je object snijdt. Zo ja dan ga je verder met z'n 4 kinderen, en dat zo totdat je aan een blad bent en dan controleer je de objecten die daarin zitten.

Een grid is simpelweg een verdeling van je hele wereld in x bij y vaste cellen. Het nadeel hiervan is dat het in principe meer geheugen kan kosten dan een quadtree, maar het voordeel is dat je in constante tijd kunt bepalen in welke cel een object zit. Die O(n) zoektijd komt simpelweg van de aanname dat in elke cel gemiddeld n/(x*y) objecten zitten, in de praktijk valt dat bij een goed gekozen x en y dus erg mee, vooropgesteld dat je objecten in de wereld een beetje uniform verdeeld zijn.

Ik verwacht dat mijn simulatie een soort klontenpap van objecten gaat geven: Ze zullen samenclusteren in kleine regionale groepen van ten hoogste 10 tot enkele objecten, die na verloop van tijd echter weer uit elkaar vallen, waarna er elders nieuwe groepen zullen ontstaan. De ruimte tussen de groepen zal echter niet leeg zijn, maar sporadisch enkele objecten bevatten.

Het lijkt me na jouw beschrijving en die van MSalters dat ik het best af ben met een simpel grid, omdat ik niet verwacht dat een quadtree heel veel minder geheugen gaat gebruiken gezien de vrij homogene verdeling die ik heb.

[MSalters]

1000r in het kwadraat? Makkie, gebruik een raster van 1 tot 16r, met een linked-list per cell. (Begin met 16r, split als je lists te lang worden). Een miljoen cellen is niets, dat zijn een miljoen pointers (4MB) en je linked-list overhead is nog een pointer per object (100000x4=0.4MB).

Overigens, wellicht ten overvloede: vergelijk natuurlijk niet r met r_max maar r² met r_max². Dat scheelt een hele dure operatie.

Geheugen zou geen probleem hoeven zijn. De meeste objecten zijn B's. Zorg wel dat die niet fragmenteren. Je weet precies hoeveel B's je in een cel hebt (N) , alloceer daarvoor 1 lang geheugenblok. Daar maak je dan N linked-lists nodes in. Theoretisch hoef je met een linked-list je elementen niet zo opeenvolgend te alloceren, maar het is cache-efficient. Als je echt aan het tweaken slaat kun je zelfs naar boven afronden op een veelvoud van 16 of 32 bytes, en die extra ruimte aanhouden voor de allocatie van een A node die toevallig in de buurt begint.
Wellicht ten overvloede, maar als een A object evrhuist, dan verschuif je dus gewoon de hele node. Dat kost geen geheugenallocatie, maar is simpelweg een paar pointeradjustments ( oldcell.first = nodeA.next; nodeA.next = newcell.first, newcell.first = nodeA; als nodeA vooraan de lijst van oldcell staat)

[ Voor 50% gewijzigd door MSalters op 16-08-2005 00:37 ]