Archived

This topic is now archived and is closed to further replies.

NuffSaid

Rapid sorting of linked-list

Recommended Posts

Here''s the problem I''m facing. All my sprites are stored in a linked list. because it is an isometric game, what I''m doing at the moment is going through the list and drawing the sprites with the highest Y coordinate value first, followed by those with lower Y coordinate values. The problem with this approach is that it requires many passes. One way I''ve managed to solve this is to create a seperate linke d-list that does an insertion sort. This brings about 2 major problems.
  • It wastes memory as there is another list in memory
  • It wastes CPU cycles. Objects coordinates are updated every frame, meaning that the second linked list has to be destroyed and recreated each frame. Major problem
Thus, the way I figure I''ll be able to solve this mess is to get rid of the 2nd list and sort the 1st list each frame before rendering begins. Now, apart from an insertion sort (or a bubble sort), I don''t know how else to sort a linked-list. Is there anyway to apply a quicksort to a linked-list? Or is there a better method that I should adopt? Thanks

Share this post


Link to post
Share on other sites
One approach would be to have an array of pointers to you linked list node type. Walk through the linked lists adding them to the array, then quick sort that array.

This means you never actually sort you linked list only the temporary array.

Another approach is when adding to the linked list insert the node at the correct place, but if you change the depth order of the sprite you would have to cut then re-add it.

[The views stated herein do not necessarily represent the view of the company Eurocom ]

Eurocom Entertainment Software
www.Eurocom.co.uk

The Jackal

Share this post


Link to post
Share on other sites
The array approach sounds more plausible than the remove and reinsert method. I might take a look into it, but my original question still stands. Is there a way to apply a quick sort to a linked list?

Share this post


Link to post
Share on other sites
It may also be an idea to adapt your list node insertion code to walk the list and place the node in a sorted position.

Also depending on the operations and how nodes are created you another idea is to put the nodes themselves into a pre-allocated array (aka pool) i.e. if you know that every frame you always have between 80 and 158 nodes per frame rather than using a normal memory allocator, just make an array of nodes with 158 entries - this can (with smallish nodes) do wonders for your cache coherency compared to using malloc/new to allocate nodes.

We do something similar to handle texture changes - although we use multiple lists (all within an array though) one for each unique texture encountered, and also a list of lists for fast lookups.

--
Simon O''''Connor
Creative Asylum Ltd
www.creative-asylum.com

Share this post


Link to post
Share on other sites
Nuffsaid,

If you know how many elements are in the linked list (which would be pretty easy), then, yes, you could do a quicksort or merge sort. Just set the high, middle, and low pointers to the right place, and start the algorithm. The implementation would be a bit more complex than using an array, but if you have good list manipulation functions, then it shouldn''t be a big problem.

Nutts

Share this post


Link to post
Share on other sites
You can perform merge sort on a linked list rather easily.. The trick is how you break the list in half. Because it''s a linked list, just taking the first half and the second half isn''t really a good idea. Instead, it''s better to divide the list into elements at even positions and elements at odd positions, mergesort those smaller lists, then join them.

Because I''ve got it sitting around, I''ll post some code for doing that in OCaml.

  
let rec mergeSort lst =
let rec split ls =
match ls with
[] -> ([], [])
| [hd] -> ([hd], [])
| first :: second :: rest ->
let
l1, l2 = split rest
in
(first :: l1, second :: l2)
and merge tup =
match tup with
[], [] -> []
| ls, [] -> ls
| [], ls -> ls
| h1 :: t1, h2 :: t2 ->
if h1 <= h2 then
h1 :: (merge (t1, h2 :: t2))
else
h2 :: (merge (h1 :: t1, t2))
in
match lst with
[] -> []
| [hd] -> [hd]
| _ ->
let
l1, l2 = split lst
in
merge (mergeSort l1, mergeSort l2)
;;


I don''t expect you''ve ever seen any variant of ML before, so that''s probably useless... But it does show that sorting a linked list can be done in place, in O(n lg n) time.

Share this post


Link to post
Share on other sites
I know there is an "optimized" sort for linked lists, because STL provides a container-specific "sort" method for lists, but I don''t know what that method is. Generally, "sort" and "linked list" shouldn''t be mentioned in the same breath. Sounds like you''re trying to have your cake and eat it too. If I were you I''d keep with the two-container method and just eat the memory waste, but it depends on the size of your containers.

Share this post


Link to post
Share on other sites
Just had a look at the STL headers and man, I don''t understand a thing. It is all way too cryptic for me.

I''m using a double linked list, so I presume, using a quicksort isn''t going to be much of a problem(huh?). I''ve got no idea how to do that. I''ll try figure out c_wraith''s code later. Mind is too fuzzy now to do anything...

Thanks a lot for the info.

Share this post


Link to post
Share on other sites
quicksort is a problem in linked lists because in order for quicksort to be efficient, it requires efficient random access to the container. Linked lists--even double-linked lists--have linear random access times, the worst you can get. This is why I said it looked like you''re trying to "have your cake & eat it too": linked lists buy you fast insertion at any point at the cost of slow random access. It''s what we call in the biz a "tradeoff".

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You could keep a fixed size array of pointers to your nodes just make it far bigger then you''ll ever need. Or each node could have multible links (like next1,next2) so that the list could be gone through in two different ways one could be sorted with out fucking up the other.

Share this post


Link to post
Share on other sites
If you want to keep the linked-list, insertion sort it and remove&re-insert when something moves.

Merge-sorting a list holds more promise than qsort does.

Why can''t you use a re-sizable array?

Anyway, I''m going to add "sorting a list" to my "damn good reason to use the stl" bag.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Yes, it would be a good idea to try using the STL, that''s what it''s there for, but..

It appears that you are trying to do a type of "depth" drawing. Why don''t you just use a binary tree? Items will be inserted into their correct location when they are inserted, and to draw you just iterate through the tree, and everything will already be in the correct order.

-nt20

Share this post


Link to post
Share on other sites
The radix sort is well suited to linked lists. It runs in O(n) time, and is quite fast even for a small number of items. Try to find some information on it, I can''t really explain it too well.

And Stoffel, what good is a cake if you can''t eat it?

Share this post


Link to post
Share on other sites
After toying with the idea last night, I think I might move to a resizable array of pointers. Sure, it might use more memory than a linked list, but it sure saves me a lot of headaches. Resize only when necessary (which shouldn''t be too frequent).

The reason I''m not using the STL is because I wanna learn to do my own data structures If it was a commercial program, sure, using the STL will be the first thing that I''ll do. But seeing as the purpose of this game is ''educational'', I''ll use my home brewed lists.

To the anon who suggested binary trees. What happens when the coordinates are updated? Will I have to recreate the entire tree?

I''d really like to thank you guys for the useful info. Its been really helpful.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Hey I was the one who mentioned binary trees -

I was thinking that you probably were using objects to represent the isometerics...then you could add a pointer to the object into the tree. The coordinates being updated would not affect the tree, only the objects in the tree. From what I gather, you have to update the coordinates in some fashion right now anyway, albeit deleting a link list entry and entering a new one, etc?

However, I see your point. You''d have to resort the tree every time coordinates changed....

I think the list of pointers sounds like a good idea too.

-nt20

Share this post


Link to post
Share on other sites
Hmm. I'm not sure if I've got the problem down right, but here's my analysis.

Considering the fact that you know each object will have a Y coordinate value, and thus need to be drawn in order, and this is the assumption part.. Why not just have n linked lists of the Y coordinates? You can just move the objects from list to list.

For example.

Array of pointers["Here's the max range of Y values"]

Array[Y=0]->Linked list of all objects with Y 0
Array[Y=1]->Linked list of all objects with Y 1

Then when the Y changes...
Just add it to Array[Y].

Maybe I've missed some of the problem?

"So much fun, so little time."
~Michael Sikora




Edited by - guardian_light on October 18, 2001 5:03:58 PM

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
My two cents goes to Guardian_Light.

Just an array of pointers, with each index pointing to the
beginning of a linked list of sprites with the corresponding
y-coordinate.

Look up time shouldn''t be too bad, if you know where it is,
you can go to the appropriate index rather quickly.

I haven''t done an isometric game, so I''m wondering why

"because it is an isometric game, what I''m doing at the moment
is going through the list and drawing the sprites with the
highest Y coordinate value first, followed by those with lower
Y coordinate values."

Pardon my ignorance on the making of isometric games.

Share this post


Link to post
Share on other sites
In an isometric game, the object with a higher Y value, is lower down the screen, and thus "nearer" towards you. because of this, an object with a lower Y value is higher up the screen, and thus, "further" from you.

This kinda simulates 3D. So, in order for this to work, the "nearer" object must occlude(right term?) the "further" object. That''s why I''m going through the list and drawing stuff like that.

Share this post


Link to post
Share on other sites
Well I've written a few iso games, (champion checkers can be seen at the GD showcase) although it's one of my first =)

I've used the pointer index list in my games, and it's a fairly quick method that can also be useful for collision detection, mouse position, etc; becuase each 'row' is a list. Anyways, I need to stop rambling, I've a party to go to =)

"So much fun, so little time."
~Michael Sikora

Edited by - guardian_light on October 19, 2001 1:38:25 PM

Share this post


Link to post
Share on other sites