Sweep and prune collision detection lib + demo

[dreadkillz]

Hello everyone, I've been very interested in learning about different broad phase/coarse collision detection along with teaching myself about lua and love. My last demo on here was a quadtree implementation, but it was pretty crappy and slow. This led me to research other methods.

From what I've seen on here and from my research online, using a grid to divide up the world space into smaller "cells" is a very fast and simple method to limit the amount of collision pairs you have to check. I then found another algorithm called sweep and prune to manage the broad phase collision detection.

For those that don't know about sweep and prune (SAP), the algorithm involves creating a list of AABB's intervals for each axis and doing an insertion sort pass for each axis. Different AABB's are checked with each other for intersection when you perform swaps on each list.

The performance of SAP is very fast when objects move slowly/maintain their temporal coherence/maintain relative position to other objects because of how insertion sort works, best case being O(n) where n = number of objects. Because of this, SAP has the potential to be even faster than a uniform grid under certain conditions. Likewise, SAP performs poorly when objects move quickly and the insertion sort has to perform many swaps to sort each list, worst case being O(n^2).

A simple way of mitigating the worst case scenario is to combine the grid method with the SAP method. Each cell in the grid is its own SAP instance. The amount of overall swaps is reduced because each SAP only has to sort local AABB's within its cell.

The only glaring weakness with the addition of the grid is that AABB's are added to all cells that it touches, which increases the amount of work the algorithm has to do because you can have duplicate entries in each SAP.

Libraries w/ MIT license + LOVE Demo: Github Repo
Demo v1.3a

[MarekkPie]

Is the sort and sweep tied directly into insertion sort? If not, then you probably could just swap it out with something like merge sort or heap sort and decrease the worst case to O(nlogn).

[kikito]

This could not come at a better timing. Last night I started working on a grid-like structure for my game.

Please set up that github account. I might not take the code verbatim, but I'd like to use it as an inspiration.

[vrld]

Very interesting. Did you try to do any measurements comparing grid/spatial hash vs. SAP vs. grid + SAP?

[dreadkillz]

Is the sort and sweep tied directly into insertion sort? If not, then you probably could just swap it out with something like merge sort or heap sort and decrease the worst case to O(nlogn).

The original SAP method is tied directly to using insertion sort because of comparisons done during swap. I've not found useful documentations for using other sort methods.

Very interesting. Did you try to do any measurements comparing grid/spatial hash vs. SAP vs. grid + SAP?

From my unscientific testing:

high temporal coherence:
SAP+grid is sometimes faster than SAP is faster than grid

low temporal coherence:
grid is faster than SAP+grid is faster than SAP

very low temporal coherence:
grid scales waaaay better vs SAP and SAP+grid

This is to be expected because SAP is most effective when objects move very little or maintain their relative positions to one another, which reduces the amount of sorting it has to do. Using a grid to have separate instances of SAP per cell helps, but it is not a magic bullet.

Also, the lib could use some clean up/improvements before I post a licensed version. You're free to study the demo until then. If you want to use the code in the demo, just give me credit and all that jazz.

[ishkabible]

I was thinking about remaking my zombie game with a bigger map and different mechanics. I was thinking about not having the zombies stack on each other this time; that would require lots of collision detection. this might just be the thing(I was just going to use hashing to try and reduce the effects)

[dreadkillz]

I updated my sweep and prune stuff + demo. I cleaned up the code and reorganized it. Also a prettier readme. If you're curious about implementing sweep and prune in Lua, check my stuff for inspiration!

[Roland_Yonaba]

Checked, demo downloaded, Repo watched & zipballed!

[dreadkillz]

Updated the libraries and demo to v1.2. I got rid of the complicated flagging system when swapping items while sorting. Now it does a simple overlap test instead. The demo also runs a good amount faster .

[litearc]

Really cool, and very useful! I've never really looked into collision detection algorithms, but this seems pretty efficient since I get almost no lag every with 600 objects. Thanks a lot! I probably will be looking at the code if I decide to use this.