# Depth Sorting (was: A lot of SDL Question and S

Another technique for speedier list insertions (in order) would be to
use a skip list.  Each node contains the normal "next" pointer, but
every (for example) 4 nodes could have an additional pointer set, to
the next 4th node.  You could also have every 8th node, 16th node,
etc. for several levels deep.  Then, you can almost get an
order(log2(n)) list insertion or search, by first following the "every
16th node" chain, until you find the one previous, then drop down to
the 8th node chain, and so on, until you find the actual node you were
looking for (or need to insert after).

If the elements don’t shift around much you can get by with sorting it
once (say with qsort), then each iteration through your game loop just
pass through the list once, swapping adjascent out of order entries.
The idea is to capitalize on the fact that the list is already close to
being sorted.

Another technique for speedier list insertions (in order) would be to
use a skip list. Each node contains the normal “next” pointer, but
every (for example) 4 nodes could have an additional pointer set, to
the next 4th node. You could also have every 8th node, 16th node,
etc. for several levels deep. Then, you can almost get an
order(log2(n)) list insertion or search, by first following the “every
16th node” chain, until you find the one previous, then drop down to
the 8th node chain, and so on, until you find the actual node you were
looking for (or need to insert after).

Hope this helps,

Warren

______________________________ Reply Separator _________________________________Subject: Re: [SDL] Depth Sorting (was: A lot of SDL Question and Sugg
Author: at internet-mail
Date: 7/27/99 9:57 AM

On Mon, 26 Jul 1999, Garrett wrote:

Of course I could go across my linked list looking at each object.z

variable and first blit the 0, go across again and blit the obj.z == 1 …
but

that isn’t much efficient if you got like up to 10 layers…
when going across your list the first items in the linked list will be 1, then
2…

Yes, you can insert things in the linked list in order (by traversing the
list to the correct location and dropping the new item in) but that can
get very slow. Imagine you have 100 objects, you could have to iterate
the linked list up to 5000 times! (Worst case, I know.)

What you really want to do, Jeremie, is one of two things. Either
implement a heap (consult your local CompSci book for details), a
structure that will quickly sort your elements as they are inserted, or
put pointers to your nodes in an array and use the qsort() function
(consult your local man page QSORT(3) for details).

Because your game is probably not a processor killer, the qsort() method
will give you the most bang for the buck, I think, because it is really
easy to implement.

Good luck.

-Chuck