Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » FAST array sorting ? array structure order problems

Credits go to Evert, HoHo, kentl, ReyBrujo, and Simon Parzer for helping out!
This thread is locked; no one can reply to it. rss feed Print
FAST array sorting ? array structure order problems
Pavel Hilser
Member #5,788
April 2005
avatar

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.
So I need really quick to find what monsters to draw in what order :-/

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 :(

_____________________________________
Mein Cannon - see my new 2d game

ReyBrujo
Moderator
January 2001
avatar

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.

--
RB
光子「あたしただ…奪う側に回ろうと思っただけよ」
Mitsuko's last words, Battle Royale

HoHo
Member #4,534
April 2004
avatar

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 :P

__________
In theory, there is no difference between theory and practice. But, in practice, there is - Jan L.A. van de Snepscheut
MMORPG's...Many Men Online Role Playing Girls - Radagar
"Is Java REALLY slower? Does STL really bloat your exes? Find out with your friendly host, HoHo, and his benchmarking machine!" - Jakub Wasilewski

kentl
Member #2,905
November 2002

I would use some sort of priority queue.

HoHo
Member #4,534
April 2004
avatar

Also if your array is mostly sorted something like bubblesort can be much faster than qsort ;)

__________
In theory, there is no difference between theory and practice. But, in practice, there is - Jan L.A. van de Snepscheut
MMORPG's...Many Men Online Role Playing Girls - Radagar
"Is Java REALLY slower? Does STL really bloat your exes? Find out with your friendly host, HoHo, and his benchmarking machine!" - Jakub Wasilewski

Evert
Member #794
November 2000
avatar

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
avatar

The bigger your objects are, the more effective is a linked list in comparison to an array.
But I believe you don't have to care about speed issues in that case. The drawing does mostly need the most performance.

Pavel Hilser
Member #5,788
April 2005
avatar

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.)

_____________________________________
Mein Cannon - see my new 2d game

ReyBrujo
Moderator
January 2001
avatar

Just to clarify, a list implies order. So, you insert elements in the correct order instead of inserting them anywhere, then ordering them ;)

--
RB
光子「あたしただ…奪う側に回ろうと思っただけよ」
Mitsuko's last words, Battle Royale

Pavel Hilser
Member #5,788
April 2005
avatar

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.
(and take care that the sort is as fast as possible)

_____________________________________
Mein Cannon - see my new 2d game

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
avatar

Well, I'm not afraid that this would not work, I've done this hundred times before :D (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 ;)

_____________________________________
Mein Cannon - see my new 2d game

Jonatan Hedborg
Member #4,886
July 2004
avatar

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
avatar

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.

---
Me make music: Triofobie
---
"We need Tobias and his awesome trombone, too." - Johan Halmén

Elverion
Member #6,239
September 2005
avatar

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:
http://www.cs.pitt.edu/~kirk/cs1501/animations/Sort2.html
http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html
http://max.cs.kzoo.edu/~abrady/java/sorting/InsertionSort.html

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.

--
SolarStrike Software - MicroMacro home - Automation software.

Go to: