2D Sprite draw order issue (image attached)

Newbie & Debugging Questions
#1

Hey guys n’ gals,

I have a query relating to the ordering of sprites in a 2D tile-based scene.

Within the ‘active viewport’, I have something in the region of 14 x 8 tiles visible. This tile map consists of a number of overlaid elements.

First, there’s the floor tiles - which get rendered first starting from the top-left, working row-by-row until it reaches the bottom-right of the viewport.

Second, I render the wall objects using the same draw method as above.

However, when it comes to active sprites, I’m a bit flummoxed as to how I order them with the correct depth without having to make lots of unnecessary texture bind switches.

Here’s a quick n’ dirty visualisation of what I mean:

Sprites need to be able to overlap each other on the ‘z’ plane (bottom to top), but it seems like the only way to do this is to check every sprite each time I draw a tile to find out if it should be at that exact depth. With potentially many sprites visible on the screen at one time - wouldn’t this be tremendously slow? I’m sure I’m thinking about this wrong.

Any advice would be most appreciated. Thanks!

#2

It’s not necessarily slow. But since CPU is much more expensive than memory these days you can do optimizations in various ways (i.e, sacrifice memory for more free cpu time).

3D games use a z-buffer (also called depth-buffer) for this. This means that they store the depth of every single pixel on the screen and each time they render a pixel they check to see if that pixel is behind the one already stored in the z-buffer, and if it is they skip it, otherwise they draw the pixel on the screen and save its depth in the z-buffer.

Or you can sort the sprites based on their depth each time you render or when a sprite has moved. In tile based movement games (where sprites seems to move around but they actually only change position (depth) every they move from or to a tile and NOT while they are transitioning from one tile to another) you can have the sprites already sorted and then cherry pick remove/add (with binary search) the sprite that is changing position.

I’ve used all 3 of these in my games at some point and to be honest I don’t think I needed the optimizations and could have just sorted all the visible sprites each render (which is probably the most cpu intensive method but easiest to implement). So I suggest you try that first and optimize later if need be or if you’re unhappy of how much cpu it is hogging.

Oh and I know this is obvious but in your game it seems like the sprites lowest down have the least depth so [z = -y] (This also means you’d only need to sort the sprites when their y-value has changed and you can ignore the x-value). In 3D games they set z to the distance to the camera and in isometric games it’s usually a variation of [z = -(x + y)]

PS:
Here’s a post where I made a while ago about sorting lists and binary search to achive depth in the game (here I ended up using the cherry picking method): http://www.java-gaming.org/topics/sorted-list/24888/msg/212173/view.html

#3

Many thanks for your detailed and informative reply. I’ll take a look at your other post as well, but I’m most likely going to implement a worst-case scenario first to see what the performance is like.

Thanks again!