Sorting Algorithms for Sprites
Author
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 >.<
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
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
Author
well ill play around wih linked lists and see how i do. Basically im only going to move the sprites when they have changed position.
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.)
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.)
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.
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.
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.
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:
[edited by - Faze on February 23, 2004 3:05:52 PM]
Add 2 CommandButtons and a ListBox to a Form and paste this code into the form:
Dim MyCol As New CollectionPrivate Sub Command1_Click() 'Add the numbers 1-15 to MyCol and reiterate the list For i = 1 To 15 MyCol.Add i Next i ReiterateListEnd SubPrivate Sub Command2_Click() 'Remove the selected item from MyCol and reiterate List1 MyCol.Remove List1.ListIndex + 1 ReiterateListEnd SubPrivate 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 iEnd Sub [edited by - Faze on February 23, 2004 3:05:52 PM]
Author
I thought objects in the VB Collection were required to have unique keys? In my game it may be possible for two sprites to be at the same position (this may change).
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?
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]
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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
