:evil: Sprite sort ordering

[jdarling]

I have been playing with my sprite code, trying to optimize it quite a bit, when I relized that my ordering is completely wrong. I won't go into all the things I've tried to get it right, but am curious as to how others are performing sprite ordering so that when you display your maps they come out proper. I'd love to see an article on it, but I can't seem to find any .

[cairnswm]

I use a two pass system. Pass one does all the background tiles (ie Ground).

Pass two does all the Objects on the map.

Whenever a sprite moves I remove it from the drawing list it is in, move it, then put it back into the list - in an ordered position.

[jdarling]

Hmm... Guess I didn't ask that right. Multipass rendering is a given, but how are you actually performing object sorting? For example, if you have two sprites witch one gets drawn on top. I have a solution that works currently, I keep track of the objects (sprites) "room (tile)" and its fine position within the room. From their when I render a room, if it has objects inside of it they get added to a list to draw in pass 2. At pass two I simply itterate the list and display the items. This is fine on small tiles (32x32) but could present a problem in larger ones as I need to actually be ordering the objects in the specific areas. I thought of using the Y coord, but that only works part of the time, and its slow to itterate all objects to locate them properly. So what sorting algo's is everyone using?

[LP]

In our own project we do the following:

1) Determine what objects are visible, by querying every object and filling a visible object list. The visibility test is actually a rectangle intersection test between the object's bounding rectangle and the screen, which can be arbitrary. The resulting list is called "auxiliary" and consists of pointers to actual game objects (game objects are stored in doble-linked list).

2) Sort the auxiliary list using the popular QuickSort algorithm using each object's "ViewOrder" and object's IDs (so objects with the same ViewOrder will also be ordered by their ID).

3) Pass through the resulting list, rendering objects one by one.

If you order your objects/sprites at the moment of creation by inserting them in the right position, when there are hundreds of objects created and destroyed every frame, you will be having a major overhead (especially if only few of these objects are really visible on the screen). The idea of the above method is that only visible objects are ordered (and rendered).

[cairnswm]

This is one place where I learnt a lot from DelphiX

Here are three Methods from the DXSprite Unit:
[pascal]
procedure Add(Sprite: TSprite);
procedure Remove(Sprite: TSprite);
procedure AddDrawList(Sprite: TSprite);
..
procedure TSprite.Add(Sprite: TSprite);
begin
if FList=nil then
begin
FList := TList.Create;
FDrawList := TList.Create;
end;
FList.Add(Sprite);
AddDrawList(Sprite);
end;

procedure TSprite.Remove(Sprite: TSprite);
begin
FList.Remove(Sprite);
FDrawList.Remove(Sprite);
if FList.Count=0 then
begin
FList.Free;
FList := nil;
FDrawList.Free;
FDrawList := nil;
end;
end;

procedure TSprite.AddDrawList(Sprite: TSprite);
var
L, H, I, C: Integer;
begin
L := 0;
H := FDrawList.Count - 1;
while L <= H do
begin
I := (L + H) div 2;
C := TSprite(FDrawList[I]).Z-Sprite.Z;
if C < 0 then L := I + 1 else
H := I - 1;
end;
FDrawList.Insert(L, Sprite);
end;
[/pascal]


Then Whenever the Z values changes (or for 2D you use the Y value)


[pascal]procedure TSprite.SetZ(Value: Integer);
begin
if FZ<>Value then
begin
FZ := Value;
if Parent<>nil then
begin
Parent.FDrawList.Remove(Self);
Parent.AddDrawList(Self);
end;
end;
end;
[/pascal]

The sprite is removed (from the drawinglist) and then added again at its new position in the list.

While processing wise not greatly efficient it works very very well and can be used for any game that isn;t doing 1000s of sprites (ie dont use it for a particle engine)

[User137]

I hardly ever need sorting. Instead Z-Buffer in OpenGL is such a handy tool

[Traveler]

I hardly ever need sorting. Instead Z-Buffer in OpenGL is such a handy tool

Unfortunately when using ortho mode, the Z-buffer is not an option.

[Paulius]

Unfortunately when using ortho mode, the Z-buffer is not an option.

Why not? It's only perspective, it doesn?¢_Tt mess up the Z buffer or anything.

[Sly]

The type of sorting you do is dependent on your view. If its isometric, then the sprites are usually ordered on their Y coord at the base of their feet. Once you get a list of all the sprites to be drawn in a room, use a quicksort algorithm to sort the list based on the Y coord. The quicksort algorithm is the most commonly used algorithm for this sorting.

If you have walls that may obscure objects in the room, then you may need to render the room in several passes:
- objects behind the back walls
- back walls
- floor
- objects inside the room
- front walls
This is to get the walls in front of the objects correctly obscuring the objects, but also having the objects being drawn over walls that are behind them.

User137, in 3D you do still need sorting when dealing with translucent polygons. You need to render these polygons from back to front or they do not look right. It is also a little known fact that when rendering opaque polygons, rendering from front to back is slightly quicker because if you have a lot of overdraw (objects drawing over the top of each other), then the objects behind will get drawn quicker because they more often than not fail the Z-test and the video card will not even try to draw the pixel. The quickest polygon is the one you don't draw. There are tools such as Pix in the DirectX SDK that can graphically show the amount of overdraw in a scene. To get the fastest rendering possible, you need to reduce the amount of overdraw in your scene.

I hope that helps.

[jdarling]

Well it seems that I'm basically doing what everyone else is doing. Damn, here I was hoping that their would be something that was faster and better. It seems a waste to spend so much time scanning all objects (course thats why right now their owned by a room instead of the map).

- Jeremy