Beat em' up game space management?

Question

I am in the process of making my 2D engine for a Beat'em Up game (Castle Crashers is what I call Beat'em Up or Brawler kind of game ).

I will support 2D sprites and 2D particle emitters. This is all done in the engine now. But I have come to an issue that I would like to ask for advice:

It's about "space" management, what I thought was to do something as this image shows:

alt text http://img337.imageshack.us/img337/9162/spacingprototype1.png

My idea is to make a grid ( Spatial Hash or Grid ), of the ground where my Particle Emitters / 2D sprites will live. In my picture, I have enumerated this slots from 1 to N, (don't have to be 35, it's just for showing purposes ). My idea is to draw the "GameElements" (Sprites/Emitters) in order from 0 to N , ( going from bucket 0 to bucket N ) , so then I will get them to display correctly overlapped on screen (back to forward).

I know this could be done by just comparing the lower Y axis of each Element and performing a "quicksort" too, but having the Grid could allow me to perform Collision Detection in a better way , and if I do something like A* to implement some kind of AI, it could help me too.

Answer 1

If you want to have some sort of optimization for the number of objects you need to test against each other, you might want to think about using a Quadtree http://en.wikipedia.org/wiki/Quadtree

The idea is to divide the screen up in 4 nodes, placing all items in the node they belong, then divide the nodes you just created up in another 4 if there are sprites/items/whatever in there that need to be tested. Keep doing this until a certain size or amount of items in a node has been reached.

You can then ask the top-node if it contains the item you want to test. This node will then ask the child-nodes if it contains the item, which in their turn will ask their children. This way a large part of the screen can be skipped already (if it's located in child 00, you can skip child 01, 10 and 11). Then you get a list of items you perform more specific collision detection on when it's desired to do so.

If you were to make it visual, it would look a bit like this:

alt text http://geodata.ethz.ch/geovite/tutorials/L2GeodataStructuresAndDataModels/en/images/quadtree.gif

Answer 2

Fire them out to the Z buffer and let that worry about it.

If you find that in the future it is too slow (via profiling obviously) then look at optimizing it.

Take the simplest solution and move on.

Answer 3

Your method fails if you have two sprites occupying the same box in the grid. Suppose you have two enemies both standing in the same box. One stands slightly in front of the other. Which do you draw first? You would need two algorithms - one which divides the sprites into the grid, and the second which looks at the z co-ordinates of all the sprites in a given grid box and draws them based on that value.

A far simpler method is to have a single collection of all sprites. It should store all sprites sorted by their z co-ordinates (from the back of the screen at the head of the list to the front of the screen at the back). Loop through the collection and draw each sprite as it appears. When a sprite moves into or out of the screen (ie. its z co-ordinate changes) you can perform a very simple sort to move that single sprite within the collection. Keep swapping it with the next sprite in the list until the next sprite's z co-ordinate is greater than/less than (as appropriate) the changed sprite's co-ordinate.