[Algoritme] botsing met vierkanten zeer snel opzoeken.

[esak]

Ik ben bezig met een bepaalde graphics engine en daar moet ik vierkanten zoeken die botsen met elkaar.
Dus je stopt 1000 vierkanten met verschillende grootte in een soort list en daarna wil je opzoeken welke vierkant allemaal botsen met het opgegeven vierkant.

Voorbeeld:
InsertRectangle(id, x, y, w, h);
// dit 1000 keer doen

array GetCollisionRectangles(x, y, w, h); //Geeft dus een array terug met welke vierkanten met het opgegeven vierkant botsen.

Dit is te doen met een quadtree maar het probleem: Ik gebruik een relatief trage taal (javascript) en het moet dus waanzinnig efficiënt gebeuren. Een quadtree is hier te traag voor. Wat ook een eigenschap is voor deze vierkanten is dat een aantal vierkanten elke step (een step is in mijn geval dus 1 frame) een andere positie aannemen en dat een aantal vierkanten altijd op dezelfde positie blijven.

Een goed voorbeeld is dit.
Maar dan moet het dus werken met tot 1000 vierkanten. Het voorbeeld gooit de hele quadtree elke step weg en vult hem weer met alle vierkanten, niet echt efficiënt lijkt mij.

Dus ik zoek eigenlijk hetzelfde algoritme met een mogelijk tot het updaten van posities ipv alles weg gooien en de nieuwe posities in de tree schrijven aangezien slechts 20% van het totaal aantal vierkanten beweegt en de rest heeft een vaste positie.

Kent iemand een algoritme of methode wat dit het meest efficiënt en snel kan doen?

[RobIII]

als 20% van 1000 vierkanten beweegt en de rest fixed is hoef je je toch alleen maar te concentreren op die 200 vierkanten

[esak]

de vaste vierkanten en bewegende vierkanten moeten ook met elkaar kunnen botsen. Het gaat er dus inderdaad om met welke vierkanten (fixed of niet) de bewegende vierkanten botsen. Maar daarvoor moet je dus ook alle vaste vierkanten in de tree zetten, toch?

[Janoz]

Maar als de vaste rechthoeken niet veranderen dan zou je deze in een aparte quadtree kunnen zetten die je niet telkens weggooit. Het uiteindelijke resultaat is dat je dan die 200 bewegende rechthoeken onderling moet testen en tegen de statische quadtree.

[acemoo]

Janoz schreef op maandag 22 augustus 2011 @ 15:12:
Maar als de vaste rechthoeken niet veranderen dan zou je deze in een aparte quadtree kunnen zetten die je niet telkens weggooit. Het uiteindelijke resultaat is dat je dan die 200 bewegende rechthoeken onderling moet testen en tegen de statische quadtree.

Zou het opnieuw opbouwen van de dynamic quadtree sneller gaan als de quadtree aan te passen wanneer iets verplaatst?

[esak]

Janoz schreef op maandag 22 augustus 2011 @ 15:12:
Maar als de vaste rechthoeken niet veranderen dan zou je deze in een aparte quadtree kunnen zetten die je niet telkens weggooit. Het uiteindelijke resultaat is dat je dan die 200 bewegende rechthoeken onderling moet testen en tegen de statische quadtree.

Hoe zou je dat dan kunnen doen? Volgens mij kan je niet zo maar twee quadtree's tegen elkaar zetten.

[Janoz]

@esak:
Je zou de 200 rechthoeken om de beurt kunnen matchen met de vaste quadtree en vervolgens onderling (middels de eigen quadtree). Je zou ook kunnen kijken of je enkel de dynamische vierkanten uit de quadtree kunt gooien of een kopie kunt maken van de vaste quadtree. In dat geval hoef je alleen maar het deel van de 200 dynamische rechthoeken opnieuw op te bouwen.

br men schreef op maandag 22 augustus 2011 @ 15:14:
Zou het opnieuw opbouwen van de dynamic quadtree sneller gaan als de quadtree aan te passen wanneer iets verplaatst?

Ik zie niet in hoe dit een vraag op mijn opmerking is. Maar ik kan me goed voorstellen dat het, bij een significant aantal aanpassingen, efficienter is om de boom opnieuw op te bouwen dan de bestaande elementen aan te passen.

[.oisyn]

Ik zou gewoon een regular grid gebruiken ipv een quadtree, 1000 is nou ook weer niet zoveel. Daarnaast, hou bij wat de afstand is tot het dichtstbijzijnde vierkant of cell boundary. Als je vierkant beweegt met een afstand die kleiner is dan dat dan hoef je ook niets te controleren.

Overigens geloof ik er geen zak van dat javascript "te langzaam" is voor quadtrees .

[ Voor 13% gewijzigd door .oisyn op 23-08-2011 12:28 ]

[R4gnax]

Je kunt natuurlijk ook kijken naar een voorgemaakte physics engine. Box2DJS zou bijv. wel moeten kunnen voldoen als je ziet wat sommige mensen er mee doen: http://experiments.lionel.me/blocs/

(Niet van mij overigens. Gewoon een showcase die ik gevonden heb.)

[ Voor 15% gewijzigd door R4gnax op 23-08-2011 18:56 ]

[Aloys]

Kan je niet een optimalisatie stap proberen in de richting van voorselectie? Stel elke vierkant voor als cirkel, niets binnen de straal van de bol/cirkel. Verwijderen deze dan uit je lijst van collisie-mogelijkheden. (Hoewel ik me afvraag of een voorselectie in dit geval wel het rekenwerk verminderd, 1000 is echt niet veel hoor).

In het voorbeeld merk ik ook direct dat het nogal uitmaakt welke browser je gebruikt .

[ Voor 12% gewijzigd door Aloys op 23-08-2011 19:15 ]

[esak]

Ik ga binnenkort eens kijken welke optimalisatie het beste werkt. Misschien hebben jullie wel gelijk dat javascript makkelijk 1000 objecten aan kan maar dat het tekenen op het scherm met 1000 objecten wel te traag gaat.

[Wolfboy]

Grote kans dat het renderen van 1000 objecten meer problemen oplevert dan het berekenen van de collisions.

Zolang je vierkanten niet draaien kan je gewoon een gesorteerde lijst van de X coordinaten bijhouden en daarmee door simpelweg door de lijst heen te lopen al zien welke vierkanten wel/niet met elkaar overlappen. Al zijn er waarschijnlijk wel slimmere algoritmen te verzinnen, met zo'n oplossing zou je het al makkelijk moeten redden.

[esak]

met 200 bewegende objecten zou dat dan 1000*200*30 (30 frames/second minimaal) zijn wat uitkomt op een 6 miljoen wat toch wel weer veel is voor javascript. En ik wil natuurlijk zo min mogelijk tijd besteden met het controleren van de collisions aangezien het tekenen van de sprites relatief waanzinnig veel tijd kost in javascript (canvas).

[Wolfboy]

Als je geen clusters van vierkanten hebt dan zou je eerder iets als "200 * 2 * lg(1000) * 30" hebben.

Per vierkant hoef je alleen de vierkanten tussen X en X2 (binary search tree, lg(n) lookup) te controleren.

[.oisyn]

@esak: Brute force is niet handig nee, maar wat je eerder beweerde was dat het bijhouden van een quadtree ook niet haalbaar was. Dat lijkt mij gewoonweg onzin.

@Wolfboy: of ze draaien of niet doet er niet zoveel toe voor jouw algoritme . Die datastructuur is trouwens in feite een segment tree, al is een interval tree voor dit geval waarschijnlijk practischer vanwege z'n dynamische aard.

[ Voor 16% gewijzigd door .oisyn op 24-08-2011 11:28 ]

[Wolfboy]

.oisyn schreef op woensdag 24 augustus 2011 @ 11:17:
@Wolfboy: of ze draaien of niet doet er niet zoveel toe voor jouw algoritme . Die datastructuur is trouwens in feite een segment tree, al is een interval tree voor dit geval waarschijnlijk practischer vanwege z'n dynamische aard.

Inderdaad, het maakt eigenlijk ook niet uit

Hoe dan ook... 1000 vierkanten zouden volgens mij geen problemen hoeven te geven.

Eventueel zou je nog de posities in 1 grote bitmap kunnen gooien waarbij je de colissions met een simpele AND kan vinden. Al is dat waarschijnlijk totaal niet zinnig en in de meeste gevallen zelfs trager.

[Verwijderd]

Dit lijkt me niet iets dat je, in redelijke tijd, zelf beter kan implementeren dan de bestaande libraries: http://www.google.nl/#q=javascript+2d+physics

[ Voor 7% gewijzigd door Verwijderd op 26-08-2011 01:35 ]

[.oisyn]

Physics != collision detection

[dusty]

.oisyn schreef op dinsdag 23 augustus 2011 @ 12:23:
Ik zou gewoon een regular grid gebruiken ipv een quadtree,

^^ wat hij zegt.
[...]
1000 is nou ook weer niet zoveel. Daarnaast, hou bij wat de afstand is tot het dichtstbijzijnde vierkant of cell boundary. Als je vierkant beweegt met een afstand die kleiner is dan dat dan hoef je ook niets te controleren.

Wat je in principe alleen kunt doen voor de bewegende vierkanten ten op zichte van de statische vierkanten, immers als twee bewegende vierkanten 100 pixels van elkaar zijn en ze bewegen 75pixels naar elkaar toe, zijn ze toch echt met elkaar in botsing

Overigens geloof ik er geen zak van dat javascript "te langzaam" is voor quadtrees .

Voor slechts 1000 vierkanten zou het inderdaad niet te langzaam moeten zijn, tenzij je op een 386 werkt

[.oisyn]

dusty schreef op zondag 28 augustus 2011 @ 17:19:
Wat je in principe alleen kunt doen voor de bewegende vierkanten ten op zichte van de statische vierkanten, immers als twee bewegende vierkanten 100 pixels van elkaar zijn en ze bewegen 75pixels naar elkaar toe, zijn ze toch echt met elkaar in botsing

Of je neemt wat ik zei niet al te letterlijk en bedenkt voor jezelf hoe je dat toe kunt passen op bewegende paren. Hint: snelheid is relatief.