search

schteppe / p2.js

JavaScript 2D physics library
Other
2.64k stars 330 forks source link

Does p2 have a quadtree? #267

Closed soylomass closed 6 years ago

soylomass commented 7 years ago

I want to find all the bodies overlapping a certain area. And as all the bodies of my world are of similar sizes, I think a quadtree would be the best way, as aabbQuery does a N^2 query. Can I do this with p2?

Fxlr8 commented 6 years ago

world.broadphase.aabbQuery is what you need. Check this issue https://github.com/schteppe/p2.js/issues/288

schteppe commented 6 years ago

I believe the question has been answered so I’ll close the issue. I just wanted to add that aabbQuery is definitely not O(N^2)... even if you implemented it naively it would still be linear complexity. The SAPBroadphase should be linear - it sorts the bodies using insertion sort (should be linear) and then builds and returns the result (also linear).