Collections.sort() explanation

Newbie & Debugging Questions
#1

I’m making a top down game and needed a way to render objects in the correct order based on their y-axis position. After a day of trying to hard code it, I ended up using Collections.sort() and it works perfectly, but I don’t understand why it does. The docs say it sorts by “natural ordering”, but I don’t understand what that actually is. Here is the code:


public static void sortAndRenderObjectsInYPositionOrder(
			ArrayList<GameObject> gameObjectList,
			SpriteBatch batch,
			ShapeRenderer shapeRenderer,
			ImageLoader imageLoader
			) {
		Collections.sort(gameObjectList);
		for (int i = 0; i < gameObjectList.size(); i++) {
			if (playerPositionIsWithinBoundsToRenderGameObjects(
					gameObjectList.get(0).getX(), 
					gameObjectList.get(0).getY(), 
					gameObjectList.get(i).getX(), 
					gameObjectList.get(i).getY(), 
					gameObjectList.get(i).getHeight(),
					gameObjectList.get(i).getWidth()
					)) {
				gameObjectList.get(i).renderObject(batch, shapeRenderer, imageLoader);
			}
		}
	}

My question is, how is the gameObjectList actually being sorted, and since each object has an x, y, width, and height, how is it seemingly sorting by the y-position of the objects without my specifying to sort that way?

#2

You implemented the ordering in your GameObject.compareTo(). Collections.sort(List) requires T to implement Comparable.
See: https://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#sort(java.util.List)

#3

I guess that’s another question. The compareTo method has nothing in it. It just returns 0.


@Override
	public int compareTo(Object arg0) {
		// TODO Auto-generated method stub
		return 0;
	}

How does it know what it’s comparing? Or does it just compare all the fields within the object? Also, thanks :slight_smile:

#4

If that is indeed so, then Collections.sort() will not do anything. It will not alter the ordering of the original list, because the sorting algorithm is stable (i.e. does not change the order of equal elements - with equal meaning that o1.compareTo(o2) == 0).

#5

The short answer is, it doesn’t work, you’re just “lucky” and probably haven’t noticed that it’s broken yet.

Cas :slight_smile:

#6

Well I guess I’ll be back when it breaks lol. I’ll play around with compareTo() and try to make it actually compare y values. All I know is for now, it’s all rendering in the correct order ¯¯¯_(ツ)_/¯¯¯ Thanks all :slight_smile:

#7

It might be interesting to manually (optionally) swap a couple y values in gameObjectList prior to sending it to this method, and see if you get the same results.

#8

Ok cool, I’ll see what happens and update tomorrow.

#9

Well yep I’m an idiot! The players are only 1 x 1, and every tile is also 1 x 1, so when the player was “in front” of the objects it looked like it was rendering correctly since they didn’t overlap. So I messed around with the compareTo() method but couldn’t really get it working correctly. I tried variations of this: (dont mind it being commented out, just did that to get the game back to the original state):


@Override
	public int compareTo(GameObject object) {
		/*
		if (this.getY() < object.getY()) {
			return 1;
		}*/
		return 0;
	}

Making the comparator > produces the same results, kinda like it’s rendering everything in wrong order. But I’m gonna mess around some more with it and see what I can do. I have a hunch, but it’s pure speculation, that is has to do with this code:


if (playerPositionIsWithinBoundsToRenderGameObjects(
					gameObjectList.get(0).getX(), 
					gameObjectList.get(0).getY(), 
					gameObjectList.get(i).getX(), 
					gameObjectList.get(i).getY(), 
					gameObjectList.get(i).getHeight(),
					gameObjectList.get(i).getWidth()
					)) {
				gameObjectList.get(i).renderObject(batch, shapeRenderer, imageLoader);
			}

And that method is here:


// This method determines whether the game object is close enough to the player to draw it to the screen.
private static boolean playerPositionIsWithinBoundsToRenderGameObjects(
			float playerX, 
			float playerY, 
			float gameObjectXPosition, 
			float gameObjectYPosition,
			float gameObjectHeight,
			float gameObjectWidth
			) {
		if (
				playerY > gameObjectYPosition - drawDistance &&
				playerY < gameObjectYPosition - gameObjectHeight + drawDistance &&
				playerX > gameObjectXPosition - drawDistance &&
				playerX < gameObjectXPosition + gameObjectWidth + drawDistance
				) { 
			return true;
		}
		return false;
	}

But I’m not sure as I haven’t tested it yet. I’ll keep ya posted.

#10

Why not (assuming coordinates are doubles)

@Override
public int compareTo(GameObject object) {
    return Double.compare(getY(), object.getY());
}

This will sort them in increasing order of y-values.

#11

I tried something similar, admittedly not sure if it was the same as that, but I shall try when I get home, or on my lunch break :slight_smile:

#12

This works perfectly! Thanks for helping me out guys, sort() and compareTo() make a lot more sense to me now. Hopefully this can help someone else in the future. 8)

#13

Try simply returning getY() - object.getY() instead.

Cas :slight_smile: