Rumblesushi3D Collision Grid demo

[rumblesushi]

I'm in the process of tweaking and optimising my collision broadphase, so I can get on with working on my first game.

With all the talk of collision grids etc recently, I've decided to upload it and show the performance.

I LOVE grids as a collision broadphase. With small enough grid nodes, you can get the amount of checks down as low as a quadtree, but with almost no overhead.

The grid is so simple and so fast.

It's 360 objects (little spaceships) running at 60fps easy on an average computer.

Brute force that would be like 130,000 odd checks.

Here it is - http://rumblesushi.com/grid.html

Drag the mouse to control the camera.

Space bar - pan camera out.

r - change the rendering of the grid to a Geometry Wars style pure wireframe.

s - Spawn ship.

For people with fast computers, you can spawn up to 1000 ships. That would be 1,000,000 checks using brute force ;)

Cheers,
RumbleSushi

[vonWolfehaus]

Very nice. Looks really fun and the performance is excellent.

So how does your grid work? Do you rebuild it every tick or update the cells as objects move around in them? Mind posting code or being more specific as to how you got so little overhead with it?

PS: Huh. Interesting website.

[rumblesushi]

The trick is to not rebuild it and not traverse the grid as you would a tree.

So the grid nodes are simply updated by the objects that move around.

Grids are brilliant as a collision broadphase, especially for moving objects. It's moving objects that really put a dent in the performance of something like a BSP tree, but as long as you handle it well, a grid does it insanely fast.

I don't loop through the grid at all. I could theoretically have a grid with 200,000 nodes running at exactly the same speed as this one.

[vonWolfehaus]

Wait, you don't loop through it ever? How do you check the active cells for collisions then? If each cell is an independent object that gets updated regardless, then that's still technically looping...

The best method I've found so far is to use a linked list for the cells, and on update have the objects put themselves in (like you said). But I wipe the cells every time by scratching the grid object (ie not calling "new", just reseting it). So after all the objects put themselves in, I have a new list of active cells and just loop through that to check for collisions.

[TheCanadian]

That's awesome! 1001 ships runs easily without even a framerate drop

[rumblesushi]

No, each node does not get updated regardless, that's the most important part of achieving this performance. The nodes get updated by the moving objects (they add/remove themselves, flag the node as being occupied etc) - and if the node is occupied, the object loops through the other objects that are currently in the node and collides if they are close enough.

I don't compile a list of active cells then loop through all the objects in those cells, that's a waste, I check for collisions as they are being added/removed.

And like I said before, this very efficient method means that I could have a grid with an absurd amount of nodes, like a few hundred thousand, running at exactly the same speed as this.

Canadian - excellent, cheers. Even on a Core Duo it runs at 60fps with 1000 objects. I decided to cap it at 1000 objects though, as any more than that, the rendering becomes more of a bottleneck than the collisions, and well, 1000 is a lot anyway ;)

PS - It says 361 / 1001 because the extra 1 is the grid.

PPS - This is obviously just a tech demo, but say I make a shoot em up in this style, which look do you prefer out of the default flat shaded wireframe on the grid, or the Geo Wars style pure wireframe (toggled with r) ?

[Gathan]

PPS - This is obviously just a tech demo, but say I make a shoot em up in this style, which look do you prefer out of the default flat shaded wireframe on the grid, or the Geo Wars style pure wireframe (toggled with r) ?
Well the darker colored pure wireframe doesn't fit that well with the color of the ships, the black part for example on the back makes it at times become almost invisible.
So change up the color on that and make it brighter and I could see myself liking that.
Both provide a different look and feel to the game, it all boils down to which kind of feel your going for, I could lean either way really.
Ps-The performance of that demo is awesome, even on my old machine it runs at 20+ fps with 1000+ objects on the screen. How did you achieve such awesomeness, did you find a existing 3d engine and massively maxed out the performance and if so which one? Or did you write your own 3d engine from scratch, kudos either way, keep it up:D

[rumblesushi]

Thanks for the input Gathan, obviously yep either way more attention would be paid to the colour scheme of the enemies and objects in the world. I quite like both too, I'm not sure which would look best for a 3D retro style shooter.

And this is running on my own 3D engine, Rumblesushi3D, built from scratch, with a huge amount of effort put into performance, which is why it, well, performs so well ;)

[theRemix]

very nice!

does your engine have a git repo i can fork? ;)

[Death Cut]

I don't know much about 3D game programming, but high frame-per-second is a good thing.

Excellent engine.

[rumblesushi]

Thanks.

And theRemix - as of now, it's a proprietary engine, developed purely to make games.

[Freshmaker]

Nice work as usual, sushi!

As food for thought for those concerned about grid size, it is possible to have an infinitely large grid (via hashing).

[Sirisian]

Oddly enough I wrote up a quick tutorial on the subject a while back.
Grid spatial partitioning (http://wiki.gamedev.net/index.php/Spatial_Partitioning). Haven't really shared it since I've been meaning to revise it. (Grammar mistakes and what not).



It's 360 objects [...]

Brute force that would be like 130,000 odd checks.

For people with fast computers, you can spawn up to 1000 ships. That would be 1,000,000 checks using brute force ;)

Actually the equation is (n-1) * n / 2. It comes from:

for (int i = 0; i < n - 1; ++i)
{
for (int j = i + 1; j < n; ++j)
{
// Check object[i] against object[j]
}
}
So 360 is 64,080 and 1,000 is 499,500. Still a lot of checks.

[rumblesushi]

That's optimised brute force, making sure you have no duplicate checks. Pure brute force would be every object checking every other object.

But yes, even with optimised brute force, it's still 500,000.

[Broadsmile]

Do You add an object to multiple cells? In case of such situation:
http://img708.imageshack.us/img708/6776/gridcollision.jpg

Thanks for performance hint, it will be useful for me :)

[rumblesushi]

No collisions are missed ;)

I don't add objects to multiple nodes, I simply check to see if neighbouring nodes are occupied, which is faster than adding/removing from multiple nodes.

[Valaran]

Hey there Rumble, I'd like to follow up on that! You check the adjacent node to see if its empty, I get the reasoning here. But what if it is occupied? Do you check against all objects in that node then or is there some other process in work? If there are many objects circling around the nodes, does this really provide a performance gain from moving objects between nodes? (By insertion and removal)

Edit: Nevermind :P

[Broadsmile]

No collisions are missed ;)

I don't add objects to multiple nodes, I simply check to see if neighbouring nodes are occupied, which is faster than adding/removing from multiple nodes.

Rumblesushi, now, when You say it, it seem to be so obvious, that I have a feeling I would do it in an exactly same way. In fact, I would probably do a lot of benchmarks to find out what You give on a plate here, so thanks.

If You feel encouraged enough by my adulation, could You elaborate on grid cells size? I know that it depends on size of objects, and more on their speed and how many objects there are, but I would like to hear some general statements like what to consider, your thoughts about the subject etc.

Thanks in advance.

P.S. Oh and the "Romance" is pure awesomness :hugegrin:

[rumblesushi]

Val, yes if any of the adjacent nodes are occupied, any objects currently in that node are checked. Which is very fast of course, you simply check if the squared distance is less than the squared radius (NOT square roots obviously), if so, you activate the collision response.

And yep, as long as the nodes are small enough, ie just a bit bigger than your largest object size (or average object if you have some huge ones) - then yes it IS faster than adding and removing each object to/from up to 4 nodes.

Broad - cheers, in regards to grid node size, you do have to get the size right for max performance, but it's not that difficult really. As I said to Val, if you objects don't differ in size much, just make the grid nodes slightly bigger than your largest object.

If for example most of your objects are fairly small, but you have just a handful of HUGE objects, like some big boulders, or monsters etc, it wouldn't make sense to make your nodes bigger than these huge objects, because you would get situations where one of these big nodes could get packed with smaller objects (say for example, MOST of your smaller objects) thus making the broadphase very inefficient.

So in that situation you want to make your nodes slightly bigger than the AVERAGE size object, then insert the handful of big objects into the grid via their bounding box, calculating how many nodes they occupy via this box, adding it to all of them, then removing them. So you'd add these large objects to multiple nodes, but still keep all other objects only occupying one node.

While the majority of your objects are smaller than the node size, it's not going to cost much to add just a handful of huge objects to the grid and remove them.

By the way, the motion graphics on my website is actually done in AS2 :D

Yes, I can get pretty good performance from AS2 too ;)

[Broadsmile]

Rumblesushi, You're great. I didn't expect to get as valuable information from You as I did.

I think now about making a grid cells size suiting rockets, not starships. I'll also script my grid in the way where I can easily change cell size, and log performance to see what works out best.]

You're a Performance King indeed!

[Commadorecrunch]

Is the grid that you use to hold the data effectively a 3d matrix so it can hold more than 1 object per node or is there a more efficient way that won't use so much memory?

[rumblesushi]

Commadore - it's a standard grid, not a hash grid, so it has an array of node classes, and each node is filled with a list of objects and polygons. The memory usage is minimal to be honest, especially compared to the memory that thousands of polygons consume and the textures they use.