Best way to handle depth?

[Agro]

Right now, in my game, to handle depth(like which entities are behind eachother) so that entities appear correctly layered behind one another, what I do is this:

1. Each entity has a depth (negative y position)
2. Each loop of the game, I run my whole ArrayList of entities through the sorting method of who has a higher depth than others etc.

That did the trick, but sometimes it says I’m violating the contract I gave to the sorting method, but at other times the depth doesn’t work.

Anyone have a better solution/fix to what im doing?

[deepthought]

we can’t help you if you don’t give us your sorting method.

[Agro]

Sorry, I thought it was a problem with concept.

Collections.sort(entities, new Comparator<Entity>() {

			@Override
			public int compare(Entity a, Entity b) {
				if(a.getDepth() > b.getDepth()) {
					return -1;
				} else if(a.getDepth() < b.getDepth()) {
					return 1;
				}
				return 0;
			}

		});

[ClickerMonkey]

Have layers of entities (an array of entity lists), assign each layer a specific purpose. Render the layers from back to front.

[jonjava]

What seems to be the problem? Looks fine to me.

You might want to take a peek at this topic: http://www.java-gaming.org/topics/sorted-list/24888/msg/212173/view.html

I’ve used a similar method for for sorting tiles in my isometric experiment except that instead of sorting the whole list I surgically insert the tile in its correct position using Collections.binarySearch()

class zComparator implements Comparator<ISOObject> {
		// A Comparator class to compare objects z values
		public int compare(ISOObject obj1, ISOObject obj2) {
			// compare z value
			if (obj1.getZ() == obj2.getZ())
				return -1;
			if (obj1.getZ() < obj2.getZ())
				return -1;
			else
				return 1;
		}
	}

	// Methods
	public void add(ISOObject obj) {
		if (arrayList.size() <= 0) {
			// If there are no other objects in the list ( no need to sort )
			arrayList.add(obj);
		}
		// adds an object to the array list at its correct position
		// ( depends on z value )
		Comparator<ISOObject> c = new zComparator();
		int index;
		index = Collections.binarySearch(arrayList, obj, c);
		if (index < 0)
			index = -(index + 1);
		// index is a negative value of the position it would have taken
		// if it doesn't fit between any two other objects
		// more info in javadocs about Collections.binarySearch()
		arrayList.add(index, obj);
	}

[Riven]

Inserting items in a list/array is among the slowest ways to do sorting.

Dump all your values in a list/array and sort it as a final step.

I told you that in the thread you quoted…

[jonjava]

Yeah it was discussed quite thoroughly so I thought the old thread would be relevant.

I actually use both methods, but the latter (slower) method is used for when the world is already instantiated.

I.e:

@Riven

There are two situations we have to distinguish:

1. You have to add one or a handful of items to a list, which must be ordered.
   In that case, use binarySearch(…) to insert the item(s)

2. You have to add more than a handful of items to a list, which must be ordered.
   In that case, add the N items to the end of the list, and sort(…) the entire list

[lincore]

To avoid violating the contract make sure that

(a.compareTo(b) == 0) == (a.equals(b))

(see http://docs.oracle.com/javase/7/docs/api/java/lang/Comparable.html).

Populating and sorting a list every frame sounds needlessly expensive to me. You should consider updating such a list only when needed, which I guess would be far less often than every frame.
If you are using OpenGL and you don’t need the list for game logic but only for rendering, I’d let the gpu handle that by using a 3d vector for vertex positions, which will automagically render everything in order. Otherwise you should organise your entities in layers as was mentioned earlier. Assuming you use integer depth values this can be as easy as having a

TreeMap<Integer, List<Entity>

where each List is a layer. To render you just iterate over the map. Of course you should not have too many different depth values.

[ClickerMonkey]

Avoid Autoboxing like the plague! Change that to an array Entity lists

[lincore]

@ClickerMonkey

Avoid Autoboxing like the plague! Change that to an array Entity lists

Why? It’s not like you do complex calculations with them, you just use them as hash keys.

[Riven]

TreeMap and TreeSet are like the LinkedList of List implementations… just use PriorityQueue.

[lincore]

@Riven

TreeMap and TreeSet are like the LinkedList of List implementations… just use PriorityQueue.

Didn’t know that one, nice :~)