|
FAST array sorting ? array structure order problems |
Pavel Hilser
Member #5,788
April 2005
|
I plan to make my new game and here is a problem I have to solve. I always put all monsters and objects into one array. In the main cycle the game calls "do_AI(int monster)", where "monster" is the index to this array and this function does anything that is needed for the specific monster. And here goes my problem - I plan to make an isometric game, so i need to draw the monsters that are behind first and last the monsters that are in front. Anybody can help? I'd like not to use classical quicksort (etc) to sort the y value Is there a way to solve this with another structure as array ? (I mean to solve it faster?) Thanx for any comment _____________________________________ |
ReyBrujo
Moderator
January 2001
|
Maybe a linked list where you add the monsters sorted instead. Or a list of pointers to your array. You sort the list, and use the pointers to know to which monster each makes use. In the worst case, just use the qsort function to sort the array. It should be faster than what you think. -- |
HoHo
Member #4,534
April 2004
|
Unless you have about 10k items in that array using regular array with qsort will not cause any speed problems unless you do something stupid of cource __________ |
kentl
Member #2,905
November 2002
|
I would use some sort of priority queue. |
HoHo
Member #4,534
April 2004
|
Also if your array is mostly sorted something like bubblesort can be much faster than qsort __________ |
Evert
Member #794
November 2000
|
Quote: Is there a way to solve this with another structure as array ? (I mean to solve it faster?) Having an array of indices and sorting that should already be faster than sorting the array itself (at least if it's an array of objects larger than 4 bytes in size). That said, I do things slightly differently: I construct a linked list in my main draw loop using insertion sort. That sort takes care of the drawing order (among other things) and I just draw everything in the queue in order once the list is build. Works pretty well and is quite flexible. My original reason for doing this, by the way, is that I have several types of objects on the screen with their own peculiarities (player character, monsters, treasure, particles, projectiles...). I can either make them all the same type and put them in the same array (which I don't want to do) or do it like this. |
Simon Parzer
Member #3,330
March 2003
|
The bigger your objects are, the more effective is a linked list in comparison to an array. |
Pavel Hilser
Member #5,788
April 2005
|
well, i suppose you are right, linked list and sort it .. (my array has about 100 bytes so i don't have to move all of this.) _____________________________________ |
ReyBrujo
Moderator
January 2001
|
Just to clarify, a list implies order. So, you insert elements in the correct order instead of inserting them anywhere, then ordering them -- |
Pavel Hilser
Member #5,788
April 2005
|
well, that's a good idea ... cause inserting to drawing is about 1 to 99 percent, so in inserting I could easy handle where to put them.. BUT - my objects are moving, so if I insert it somewhere, I have to move it to another place in my array, as it moves I thing I'll try to do my array, array of pointers and then simply sort the array when the level is redrawn. _____________________________________ |
kentl
Member #2,905
November 2002
|
Make it work first, optimize it later. If you design things in a good way you will be able to change the way it sorts later on, and get it working soon. |
Pavel Hilser
Member #5,788
April 2005
|
Well, I'm not afraid that this would not work, I've done this hundred times before (in my every game is this monster-array), but the only thing different is the need to have the array sorted I've done some different sorting algorytms before and know how they work, but I didn't realized the use of a linked array to another array _____________________________________ |
Jonatan Hedborg
Member #4,886
July 2004
|
Another way to do it would be to put a pointer to the actor on the tile on each tile. So when you want to draw stuff, iterate through each tile and draw the tile-sprite and then anything on it (actor). This is easiest to implement if you have "grid-based" movements though. Otherwise you would need to make some evil offset value that changes as the actor moevs around and then at a certain point you move the actor "move" to another tile.
|
Tobias Dammers
Member #2,604
August 2002
|
Or you can just use the might % operator (or even & for power-of-2-sized tiles) to determine the current tile for the actor each time it move. --- |
Elverion
Member #6,239
September 2005
|
We have recently went over several sorting routines in my C++ class. Most of the time, the teacher just showed us java applications for examples instead of programming everything out in C++. You might find these websites pretty useful. All the work is done for you, so you just get a quick overview of how each sorting method works. Links: But heres an idea...how about only a partial qsort? That is, instead of compleetly resorting the array, or vector, or whatever it is you want to use each logic step, only sort a small chunk of it. It would prevent the game from getting too slow with a very large number of objects, and who cares if one object breifly appears in front of some other object that it's not supposed to for only 1 frame as they move past each other. Once they are sorted, it's not going back...so it shouldn't cause any flicker. In special cases, you might wish to call a full resort (such as just loading a new room or map). Also, if objects will not just be jumping out everywhere randomly, you will want to choose a sorting algorithm that performs faster as things are more sorted. -- |
|