Draw Order

[Kadoba]

So I'm trying to get my game objects to draw in an order based on a draw index. Basically objects that have a lower draw index gets drawn first. So if I have two objects and object A has a draw index of 2 and object B has a draw index of 1 then object B will get drawn first and object A will get drawn second. I'm trying to come up with a fast way to do this. Right now I'm just cramming all of the indexes in a table and using table.sort but if you have lots of objects that seems like it would be a pretty slow. Is there a better approach to this or am I just splitting hairs? I know I should probably just come back to this if and when it becomes a problem but I can't help wondering about it.

Premature optimization is a cardinal sin and all that.

[Jasoco]

I just use table.sort. It works fine on upwards of 500-1000 objects at once.

[BlackBulletIV]

You may want to look at my implementation which is contained in my framework. The main files you'll want to look at are World.lua (the draw, _updateLists, and _setLayers are the most important to this case), and Entity.lua.

[ivan]

Hey BlackBulletIV, I looked at your project's code very briefly and noticed something in one of your utility functions:

Code: Select all

function math.round(x)
  return math.floor(x + .5)
end

I don't think this would work correctly (or at least how I expect it to) with negative numbers.

[Kadoba]

You may want to look at my implementation which is contained in my framework. The main files you'll want to look at are World.lua (the draw, _updateLists, and _setLayers are the most important to this case), and Entity.lua.

I'm having trouble seeing the big picture but the idea is to use linked lists, right? That might work if I only updated the nodes when they moved. Since the greatest majority of objects are stationary and draw indexes based on the Y-position would only change in small amounts at a time that would probably work out really well.

I don't think this would work correctly (or at least how I expect it to) with negative numbers.

-1.6 + 0.5 = -1.1
floor(-1.1) = -2

-1.4 + 0.5 = -0.9
floor(-0.9) = -1

That works out doesn't it?

[vrld]

I'm having trouble seeing the big picture but the idea is to use linked lists, right?

No, the idea is to have several layer tables that contain references to the objects you want to draw, e.g.:

Code: Select all

background = {hill1, hill2, tree1, tree2, tree3}
middle = {road, house}
foreground = {player, enemy}
absolute_foreground = {particle_effect}

These tables can themselves be stored in another table, i.e.:

Code: Select all

layers = {}
layers.background = {}
layers.middle = {}
...

Instead of using names, you can use indices, which gives a nice way to draw the layers:

Code: Select all

layers = {}
layers[1] = {hill1, ...}
layers[2] = ...

for i = 1,#layers do
    for _, obj in pairs(layers[i]) do
        obj:draw()
    end
end

[ivan]

-1.6 + 0.5 = -1.1
floor(-1.1) = -2

-1.4 + 0.5 = -0.9
floor(-0.9) = -1

That works out doesn't it?

Oops my bad, actually you're right. I forgot how floor works with negative numbers.

[Kadoba]

Sorry I guess I wasn't very clear about my problem. I'm already using layers and layers are fine enough if you aren't concerned about the draw order of individual objects within those layers. But let's say I want to base the draw order of a game object off its Y position so those with a smaller Y value gets drawn first. This is very common in top-down perspective games. The Y position on certain objects is constantly changing so you are constantly having to update the draw order. Right now I am using table.sort to sort game objects by their Y position. This works exactly like I want it too except it's a little slow since it performs a sort on every game object on every update.

I think a linked list in which nodes update themselves when their index changes might be a potential solution.

[BlackBulletIV]

My implementation uses a linked list for every layer (linked lists are very efficient for adding and removing items), which are stored in a table. Every layer gets assigned a an index in the table; the lower the index, the later it gets rendered (meaning the higher it is on the screen). Using this index-based solution means I don't have to sort all the layers every time I add or remove a layer.

As for ordering objects by their Y position, I can't think of a faster way to do it off the top of my head.

[vrld]

I think a linked list in which nodes update themselves when their index changes might be a potential solution.

Unless you have some information you can (given an object's position) use to tell which object will come next, you won't be able to sort faster than table.sort does. Using a linked list wont make things faster. If it did, you'd had invented a sorting algorithm that can sort faster than in O(n logn), which is not possible*.

Within these bounds, you can still optimize a few things

• Use more layers. Divide things that change position often into several layers so that table.sort only works on small arrays.
• Sort using table.sort at the end of the update loop, but only if something changed it's vertical position.
• Use a skip list (see also here). If there are not too many objects that change position, this can be faster than table.sort.

* unless you have exploitable information, like radix sort has.