Rendering in order of Z-value, not array order

Game Mechanics
#1

I am currently working on a 2D RTS game. I made a custom Entity Manager which stores all the game entities in a single ArrayList. What I have now renders these entities in the order they appear in the array, but I want to render them in order of a z-value instead. I am fairly sure I know how I am going to accomplish this, but wanted to see if anyone had any thoughts before I get too deep into implementation. So any ideas guys?

#2

If the order never changes then you can just insert each new gameobject in the correct z order.

If the order changes during game play then you must update the List when the order changes.

#3

The only way to do this is to sort all the things you want to render by their z-value each time you want to render them.

Because this problem is very common stuff like OpenGL uses Depthbuffers(a buffer which stores the depthvalue of each screen pixel)

#4

Just a thought. You could write your own system that is a sort of “depth buffer” (I have no idea how OpenGL’s depth buffer works). My idea of this would be implemented either as your render system or along side it and you’d simply call db.drawImage(image, x, y, z) (or whatever draw call). Under the hood you could maintain an ArrayList, or whatever data structure would be fastest, of images representing each buffer “level”. When a call is made to a draw method, draw to the specified “level” based on the z value. If there isn’t an image for that level then create one and add it to the list at the correct location. Then have a method to draw the depth buffer to the screen, compressing all the layers in the correct order. This is just something I came up with while reading through the thread, I wouldn’t suggest actually using it x) It seems rather roundabout and inefficient.

EDIT: The method of drawing to the screen could be as simple as g.drawImage(db.getImage(), 0, 0, null);

#5

how you determine z depends on the game, but yeah, sort by z, render in order

#6

My method is like this:


for(each row of pixels in the screen) {
     for(each entity on screen)
          if(entity.y == y) 
               render entity
}

I’m sure this isn’t the best method to use, but is the simplest.

#7

What I ended up doing is implementing a simple bubble sort, which works fine for now. Thanks for all the suggestions though!

#8

We had the same Problem in our 2D RPG.
We solved it like this:

We have an ArrayList which holds every Static object. This List is sorted by the Y Value of the objects (mid of where they “stand”, not the Image Y Value).
Before rendering, every static Object is copied into a RenderList. After that every nonstatic Object is sorted in that List.

After that we can render this List from 0 = ArrayList.size()-1 and everything is in the right order.


http://img6.myimg.de/renderlistb6d21.png

(yes our Player is a Smily…and the tree is stolen from Pokemon…)

I hope this was what you’te looking for :S

#9

java.util.Arrays.sort() offers a pimped merge sort for free.

#10

IIRC, since java 6u24 it uses a dual pivot quick-sort.

#11

I see now, for primitive types its quick sort, for objects its a merge sort variation.

#12

I am sorry to post in your topic, but is there any way to sort an ArrayList firstly by y-coordinate and then by layer? (layer in Tiled, i’m using Slick2D).

Let’s say we have an array like this: {[0, 0], [0, 1], [3, 2], [2, 1], [4, 6]} and it should be sorted like: {[0, 0], [0, 1], [2, 1], [3, 2], [4, 6]} (first is the Y and second is the layer (bigger = upper))

#13

You can do that by implementing your own Comparator and call Arrays.sort() with it.

#14

Another option is to bit pack the two values.