Should I use space partitioning in a 2D platform game?

Member
Posts: 249
Joined: 2008.10
Post: #1
Hi dudes!

Should I use space partitioning in a 2D platform game? A game like Rolando or SpyBot. Is it necessary?

Thanks for suggestions.
Quote this message in a reply
Member
Posts: 166
Joined: 2009.04
Post: #2
It depends ... how big are your levels ? how many sprites you will render on a given level and how many of them will be visible on the display screen at any given time ?
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #3
For a single screen game:
collision detection: yes
rendering: obviously not

For a game that scrolls and has largish levels:
collision detection: absolutely necessary
rendering: probably, but depends on how many draw calls you need to make

I made a scrolling race game once with very large levels, but it only drew a few hundred triangles total. Didn't need to cull any drawing. Collision detection used my physics library that had spatial indexing built in.

For rendering, spatial partitioning can be as simple as using tilemaps and only rendering the part of the tilemap that is on the screen. For sprites and collision shapes, you can get away with using a low resolution grid with lists of objects in each cell.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Member
Posts: 249
Joined: 2008.10
Post: #4
I forgot to say I'm using BOX2D and my levels are a large as Rolando.

Now my scene graph (a vector of vectors, just to try to imitate photoshop layers) test if and object overlaps with camera rectangle, int this case I render it, otherwise I ignore it.

Skorche, I guess that is not a space partitioning, am I right?

Thanks for replies.
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #5
No, that is not space partitioning. For a lowish number of objects though, a bounds check is going to be much faster than submitting geometry that doesn't get drawn. That might be good enough for most applications if rendering everything without caring does not.

Collision detection is where it's most important. Rendering without partitioning means you are taking every object and rendering it or doing a simple bounds test then rendering. Not really so bad, rendering a few hundred objects is not so expensive. For collision detection without partitioning, you are taking every object and colliding it against every other object. Colliding a few hundred objects against a few hundred objects is very very expensive.

For the race game I was talking about, levels were probably 100x8 screenfuls. The terrain was rendered as a few hundred triangles + about 100 more sprites. I was easily able to hit 60fps without any culling. http://www.youtube.com/watch?v=LuOrC95K26E

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Member
Posts: 249
Joined: 2008.10
Post: #6
Skorche Wrote:No, that is not space partitioning. For a lowish number of objects though, a bounds check is going to be much faster than submitting geometry that doesn't get drawn. That might be good enough for most applications if rendering everything without caring does not.

Collision detection is where it's most important. Rendering without partitioning means you are taking every object and rendering it or doing a simple bounds test then rendering. Not really so bad, rendering a few hundred objects is not so expensive. For collision detection without partitioning, you are taking every object and colliding it against every other object. Colliding a few hundred objects against a few hundred objects is very very expensive.

For the race game I was talking about, levels were probably 100x8 screenfuls. The terrain was rendered as a few hundred triangles + about 100 more sprites. I was easily able to hit 60fps without any culling. http://www.youtube.com/watch?v=LuOrC95K26E

Interesting video.

About collisions: What should I do if I use BOX2D (ie I do not program collisions)?

Thanks for your suggestions.
Quote this message in a reply
Post Reply