Depth sorts | GameDev.net

Oberon_Command · 2003-05-08T15:37:50+00:00

Okay, I sort of got a tile demo working. But I can''t figure out how to do a good depth sort. I tried to implement my own sorter, but it didn''t work. How would I do this?

In my engine at http://www.javaengines.dk/arenabots I maintain a linked list of the entities to draw. Background tiles aren't moving, so they're just in a 2-dimensional array. Every time after an entity has moved it traverses the linked list it belongs to until it's correctly placed. The coordinate system I use is the following:

, and the ordering used: Suppose you have 2 entities, A and B, if A.x + A.y > B.x + B.y, then B will be drawn before A (convince yourself that the equation x + y = c describes a horizontal line on the screen). I also keep pointers to the first entity in each layer, these have to be fixed every frame to ensure that they really do point to the first entity in the list.

Java source code (Entity.updateInLayer) for updating entities in their linked lists( all entities have last and next pointers)

              
/**
Moves the Entity to the right position in the linked list.
The ordering used is the order in which the Entities should be painted,that is,if A.y + A.x< B.y + B.x, then A should be painted before B.
*/
public void updateInLayer()
{
	//If the Entity (if any) that comes after this one should be painted first, 

	//then we have to move forwards in the list until the next Entity 

	//(if any) is to be painted after this one

	if(next != null && (next.position.y + next.position.x) < (position.y + position.x))
	{ //First remove this drawable from current position, and patch "gap"

		if(last != null)
			last.next = next;
		next.last = last;
		//Now move until positioned correctly

		do
		{
			last = next;
			next = next.next;
		}
		while(next != null && (next.position.y + next.position.x) < (position.y + position.x));
		//Make last and next point to this, to insert in list

		if(next != null)
			next.last = this;
		last.next = this;
	}
	//If the Entity that comes before this one should be painted later, 

	//then we have to move backwards in the list 

	else if(last != null && (last.position.y + last.position.x) > (position.y + position.x))
	{
		if(next != null)
			next.last = last;
		last.next = next;
		do
		{
			next = last;
			last = last.last;
		}
		while(last != null && (last.position.y + last.position.x) > (position.y + position.x));
		if(last != null)
			last.next = this;
		next.last = this;
	}
}

GameModel.updateLayers() that fixes linked lists, and Entity.getFirst() that gets called from updateLayers().

          
/**
Some Entity objects might have been moved to a position before the previous first Entity. 
Fix this.
*/
private void updateLayers()
{
	for(int i = 0; i < layers.length; i++)
		layers[i] = layers[i].getFirst();
}


public Entity getFirst()
{
	Entity first = this;
	while(first.last != null)
		first = first.last;
	return first;
}

Of course, we also need to insert our entities in the linked list, this is done by calling insertInLayer() on the Entity to be inserted, with the (pointer to in C, but this is Java, pointers are implicit) Entity that serves as the handle of the list;

      

public void insertInLayer(Entity layer)
{
	next = layer;
	if(layer != null)
		layer.last = this;
	updateInLayer();
}

[edited by - blackone on May 9, 2003 6:09:05 PM]

[edited by - blackone on May 9, 2003 6:14:30 PM]

Topic Locked