Archived

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

Sorting Algorithms for Sprites

This topic is 5042 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I should mention that I am using VB6. Well I know what im going to be sorting my sprites by, but im just not sure how to do it. Should I put every sprite into a linked-list and sort that, or make an array out of them and sort that? I need some input please >.<

Share this post


Link to post
Share on other sites
When is the sorting likely to occur? Will you be sorting your sprites as they move around during game execution, re-sorting as things change location? If so, then it might be best to avoid using arrays, since sorting an array usually requires a lot of copying array elements to and fro, sometimes in large amounts, and can be inefficient in memory usage as well. A linked list can hold as few or as many objects as are required, while an array is fixed at a certain length unless the overhead (re-allocating, copying from old to new) of making it dynamic is implemented.

It is pretty easy to sort the sprites into the list as they are added, search through the list for one to remove, and re-sort it into a list as needed with minimal overhead using linked lists. The same would require whole chunks of objects in an array to be copied in order to make room in the middle of a list for an object to be inserted there.

If you only need to sort your sprites once when the sprite list is constructed, you know there will not be any insertions or deletions from the sprite list, and you know the maximum number of sprites the list can hold, you might be able to get away with an array. Just be aware that it won''t be nearly as flexible. You can overcome the overhead of copying objects by using an array of object pointers and sorting that, but the limitations of a fixed array still stand.


Golem
Blender--The Gimp--Python--Lua--SDL
Nethack--Crawl--ADOM--Angband--Dungeondweller

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I''m not sure I''d say that linked lists necessarily mean less copying than arrays.

If you use an array of pointers, you shouldn''t be moving any more data in the sorting process than you would with a linked list. You''ll definitely move less data if you''re planning on using a doubly linked list.

Plus, you might be able to get a faster sort with arrays, since some of the algorithms in the O(n log n) range are a PITA to implement on linked lists. This probably isn''t an issue if you aren''t dealing with a huge list of sprites at once or aren''t sorting the list every frame.

In the end though, it''s probably best to just stick with whatever data structure you''re using in the first place - the costs of moving all that data from an array to a list or and back again (or the other way around) will probably far outweigh any benefits you can find to doing so.

(Note: I''ve never programmed in VB and am not sure what the language supports. I remember QBasic had no pointers, which makes everything I just said not apply. Then again, even if VB doesn''t outwardly use pointers, it may be worth looking into how VB handles arrays. I''d imagine that arrays would be implemented internally to contain references to the data and not the data itself, so you may not be moving as much data as you think you are in arrays.)

Share this post


Link to post
Share on other sites
Are your maps going to change in size during run-time? If so then you''ll probably want to store your maps in a linked list or dynamic arrays of pointers. Your monster/character list will need to go in a structure like this since they are constantly moving around, dieing, spaning, and such.

I would also suggest checking out the book called "Algorithms in C++" by Sedgewick. This is a must for any game developer. It contains plenty of sorting info in addition to a ton of things that you will find indespensible.

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
I''m not sure I''d say that linked lists necessarily mean less copying than arrays.

If you use an array of pointers, you shouldn''t be moving any more data in the sorting process than you would with a linked list. You''ll definitely move less data if you''re planning on using a doubly linked list.

Plus, you might be able to get a faster sort with arrays, since some of the algorithms in the O(n log n) range are a PITA to implement on linked lists. This probably isn''t an issue if you aren''t dealing with a huge list of sprites at once or aren''t sorting the list every frame.

In the end though, it''s probably best to just stick with whatever data structure you''re using in the first place - the costs of moving all that data from an array to a list or and back again (or the other way around) will probably far outweigh any benefits you can find to doing so.

(Note: I''ve never programmed in VB and am not sure what the language supports. I remember QBasic had no pointers, which makes everything I just said not apply. Then again, even if VB doesn''t outwardly use pointers, it may be worth looking into how VB handles arrays. I''d imagine that arrays would be implemented internally to contain references to the data and not the data itself, so you may not be moving as much data as you think you are in arrays.)


Except for the fact that he is going to be re-sorting as the objects move, and constantly adding and removing objects as they move. Which generally means the whole list (or array, whatever) doesn''t need to be fully sorted every time; just that objects will need to be removed at some arbitrary times, and that other objects will need to be added, with proper sorting, at other arbitrary times. With an array, removing an object leaves a "hole", an empty slot in the array that needs to be filled in by shuffling the tail of the array beyond the hole up by one slot. Conversely, adding an object requires shuffling the entire array starting at the insertion point downward to make a slot for the object pointer to be inserted. If the array is merely an array of pointers, the copying is reduced, but there is still more copying done than with a linked list, which requires only 2 pointers to be changed (for a singly-linked list) in order to insert an object, and an object can be removed by changing one pointer.

For general-case, one-time sorting of a large block of data, you might be able to sort faster using arrays. For continuous sorting with lots of insertion and deletion, arrays are not the best choice that I have seen.

Share this post


Link to post
Share on other sites
Are you aware of the Collection object in VB? You should check it out, I think it'll solve your problems. You can Add and Remove objects from a Collection and the objects will sort themselves.

Add 2 CommandButtons and a ListBox to a Form and paste this code into the form:


Dim MyCol As New Collection

Private Sub Command1_Click()
'Add the numbers 1-15 to MyCol and reiterate the list
For i = 1 To 15
MyCol.Add i
Next i

ReiterateList
End Sub

Private Sub Command2_Click()
'Remove the selected item from MyCol and reiterate List1
MyCol.Remove List1.ListIndex + 1
ReiterateList
End Sub

Private Sub ReiterateList()
Dim i As Integer

List1.Clear

'Simply display the contents of MyCol in List1
For i = 1 To MyCol.Count
List1.AddItem MyCol(i)
Next i
End Sub




[edited by - Faze on February 23, 2004 3:05:52 PM]

Share this post


Link to post
Share on other sites
I''m not exactly sure what it is you are trying to do, but I know that Collections are much more easily sorted than an array. Can you explain a little better what you are trying to do?

Share this post


Link to post
Share on other sites
the VB Collection object 'seems' to act as a linked list and/or key map, that is you can store a chain of references with or without keys (when adding 'key' is an optional attribute)

so it should work, though i imagine it is still going to be slow, but thats vb for ya =/

Raymond Jacobs,

www.EDIGames.com

www.EtherealDarkness.com



[edited by - EDI on February 23, 2004 3:17:19 PM]

[edited by - EDI on February 23, 2004 3:21:04 PM]

Share this post


Link to post
Share on other sites
Yea, i do realize the shortcomings of vb, but I am using this more so as a learning experience. I''ve been playing around with the linked lists and i think I have something that works. Basically if the player or something moves, it checks to see if its still in its correct position in the list (its movement didn''t change its drawing position), and if it isn''t, it removes the sprite then adds it to the list. My add function adds sprites in their correct position so the list remains sorted the whole time. Would this method be slower than a collection?

Share this post


Link to post
Share on other sites
I would imagine that if you are implementing your own link list it will be slower than the collection obj.

in my exp with vb(2 years of programing game related stuff)

re-inventing the wheel wont get you speed gain (unlike you can somtimes do in C++) it seems that it is best to use built-ins when you can, dont fight the current=D

Raymond Jacobs,

www.EDIGames.com

www.EtherealDarkness.com

Share this post


Link to post
Share on other sites
Three and a half years of VB programming and EDI is right and wrong about reinventing the wheel in VB because it can be done and is necessary in lots of situations, but since that isn''t the topic, the Collection object should do everything you need and nothing extra that you do not need. Therefore, since you''ll need every aspect of it, use it since what you''d reinvent would do exactly what Collection already does.

Share this post


Link to post
Share on other sites
okay so if I wanted it to order a collection of my CSprite class by one of its properties (.z), how would i do this? I havent really used the collection object before. It is also possible for the z value of two sprites to be the same.

Share this post


Link to post
Share on other sites
Collection works just like an array. Just look at the code I posted earlier, it should be all you need. To return the contents of a Collection entry, just use Collection.Item(Index)

Share this post


Link to post
Share on other sites