[GetSet]

I'll go into more detail to clear up any ambiguities albeit "stack" being a misnomer on my part but one that i use to name the alternative approach for lack of another.

When it comes time to delete a character's ID from the Z-Depth it is occupying, if you decided on an array of integers as opposed to some other scheme, what would be the fastest way to delete the ID that would take the least amount of loop cycles (or ideally, zero loop cycles)?

Suppose the integer list is 10 20 05 32 09

If you used a shifting method to delete the 3rd index (value 05) for example, your code would copy 32 to the 3rd index, and 09 to the 4th index, then decrement the count. So you'd have:

10 20 32 09

The number loop cycles then is a function of "count" and the array index so targeted whose value is to be deleted. If count is 100 for example, and the value at the 3rd index is to be deleted, count - 3 loop cycles would have to take place to shift delete that value in order to preserve the logical order of the numbers.

A faster approach which uses zero loop cycles is to simply swap delete. For example, using the same integer list:

10 20 05 32 09

To delete the value at the 3rd index, swap it's value with the value at index count. So, 09 and 05 would change positions. Then you'd decrement count. You'd then have:

10 20 09 32

That is you would have used no loop cycles and thus the swap method is faster. But, though faster, the logical order is not retained because in order to ensure that sprites that had arrived earlier are drawn earlier, the swap delete would change that order: in this case, 09 which had been added to the Z-Depth last will not be drawn before 32 which had arrived earlier than it.

So the swap delete though faster than the shift delete, mucks up the logical order that we desire for characters occupying the same Z-Depth.

A link list however has no such limitations. The logical order of a link list is always maintained, and you would use a swap delete in this case, the shifting method on a linked list being absolutely pointless.

So in a nut shell, a linked list approach comes with many advantages to include this one.

[GetSet]

GetSet, on 24 February 2012 - 06:26 PM, said:

That is you would have used no loop cycles and thus the swap method is faster. But, though faster, the logical order is not retained because in order to ensure that sprites that had arrived earlier are drawn earlier, the swap delete would change that order: in this case, 09 which had been added to the Z-Depth last will not be drawn before 32 which had arrived earlier than it.

Well, earlier arrived sprites should be drawn after newer ones so that they are on "top", which in this case, using the same implementation, you would iterate the link list in reverse during animation. But still starting from Z1 to Zn. Just when reading the entries of the linked list, start from the last (logical last) value.

[CasiOo]

My first thought was to make some kind of relative layout. Every entity would have a reference to another entity at a deeper level, or null if none are deeper. When you ask an entity to render itself, it will answer (recursively) "Okay but you will have to render this Entity first, because relative to me, he is at a deeper lever".
The relative-bindings would then happen at each collision between two entities.

It was just a quick thought, and I haven't thought it through. And I doubt it will be any faster than what many of you have already suggest

[GetSet]

CasiOo, on 24 February 2012 - 07:21 PM, said:

My first thought was to make some kind of relative layout. Every entity would have a reference to another entity at a deeper level, or null if none are deeper. When you ask an entity to render itself, it will answer (recursively) "Okay but you will have to render this Entity first, because relative to me, he is at a deeper lever".
The relative-bindings would then happen at each collision between two entities.

It was just a quick thought, and I haven't thought it through. And I doubt it will be any faster than what many of you have already suggest

I like the way you think.

[cfoley]

Is this really a problem? I would have a single list/array of sprites and sort it with whatever built-in sort() method my language has. If my code can render all those sprites every frame, and make AI decisions for all the NPCs then it can damn well do an almost O(n) sort!

Why almost O(n)? Well, the list is already almost sorted. There will only be a few items out of place and there are sorting algorithms that do very well on this kind of list. A bidirectional bubble sort may trump any of the fancier suggestions here.

[GetSet]

stayscrisp, on 24 February 2012 - 04:47 AM, said:

So I thought of coming up with different algorithms or techniques to solve this problem. One such option is to just loop through all of the characters on screen and compare their Y positions, and sort the Z depth accordingly ie. lower Y means higher z depth. This seems like it could be a lot of processing though if there are a lot of things on screen at once and seems to be a waste of resources.

My other thought was to only compare and sort depths when there is a bounding box collision between objects, this leaves the algorithm open to standard performance enhancing techniques associated with bounding box collision.

Does anyone have any other ideas or ways in which you would tackle this?

The original poster was looking for alternatives other than sorting or alternatives that minimized the need to sort as often. To resort back to sorting indiscriminately as a solution because it works and is fast enough on todays processors -- I agree, it is. Nonetheless every saved loop cycle on the other hand in turn opens up room for more expansion elsewhere in the game engine that won't affect game speed performance as much, due to the tweaked code in every other part. This benefit lends to tweaking code for speed, despite that other methods using supplied sort commands are readily available.

[cfoley]

Yes, but I also think my solution is the fastest. Let's go with a bidirectional bubble sort instead of the built in function. It will run in O(n) time each iteration, and will only degenerate to O(n^2) if all the sprites get scrambled (which will never happen, unless there is magic).

Anything to do with collisions has O(n) time too, O(n^2) time if implemented naively, and I believe the constant will be higher for that too.

Maintaining separate lists for each layer has potential but I don't think it will save much, if anything, over a simpler solution. It also adds the confusion over when you move it between lists. As you are calculating movement? Flag moved sprites and update the lists later? At least a bubble sort can have a separate and nicely defined step of its own.

[GetSet]

cfoley, on 29 February 2012 - 02:17 AM, said:

Yes, but I also think my solution is the fastest. Let's go with a bidirectional bubble sort instead of the built in function. It will run in O(n) time each iteration, and will only degenerate to O(n^2) if all the sprites get scrambled (which will never happen, unless there is magic).

Anything to do with collisions has O(n) time too, O(n^2) time if implemented naively, and I believe the constant will be higher for that too.

Maintaining separate lists for each layer has potential but I don't think it will save much, if anything, over a simpler solution. It also adds the confusion over when you move it between lists. As you are calculating movement? Flag moved sprites and update the lists later? At least a bubble sort can have a separate and nicely defined step of its own.

Hi.

Surely you can't be serious that sorting is the faster option than not having to sort at all? But i don't know if you are serious or not. I heard of dreamincode some years back. Been swamped by work and school, didnt have much free time to post or read outside of other things. Nonetheless, for you to acknowledge that the link list method might be worthy, it's important to delineate it's worthy features. But I must say at the outset, which may here may seem like after the fact to some, I never viewed answering the original poster's query for suggestions as a contest. If it were a contest then we would be posting test timer results in milliseconds, to weigh the weight of implemented methods against processor types and cache sizes. But that is not the case. Our discussion is purely friendly, purely conceptually. And conceptually speaking, speed wise, to sort versus to not have to sort is obvious enough.

Whatever. Okay. So to some sorting is faster than to not have to sort. Okay. I don't know how. But i do know, to sort is slower. To not have to sort is faster. Run-time wise.

Now granted, coding wise, it may take much longer to implement a double link list or even a single linked list (a single is sufficient actually) to do the job as described in my earlier post. I thought the whole point of the matter was for us to come together to find an ultimate solution, not outwit the other with faith-based "faster" solutions.

"Coding-wise" in that it may take the programmer longer to code it, to develop a working algorithm, a class library that works as expected, etc. BUT Run-time wise, make no mistake, a linked list where the sort order itself is based on insertion, what other data structure is faster run-time wise? There is none.

[GetSet]

On other matters, the bidirectional bubble sort, excellent! I tend to use bubble sort in it's regular fashion but i see the merits of your analysis in comparison to the normal bubble sort, and have investigated it's advantages since your post. Plan to test it out for testing out purposes. I wonder, when did this algorithm come about? The only thing that gives me pause is how to efficiently implement the bidirectional strategy. Likely a variable that alternates based on a modulus value of the current loop cycle. Will have to play around with it for fun's sake.

[cfoley]

My apologies if I came across confrontational. I'm not trying to make it a competition, just saying what I think the best solution is. And I like discussing the merits of different solutions because I always learn something.

I was serious about the bidirectional bubble sort. One ascending pass will have placed all the sprites that have moved up a layer in the correct positions, and will have determined if a descending pass is needed. If it is, one descending pass will have placed all the sprites that have moved down a layer in the right positions.

Further passes will only be needed if groups move over layers together or sprites overtake each other in the same direction. In some games, these situations may be common but I think they will be rare in most side-scrolling beat em ups.

Linked Lists seem nice but there is a lot more dereferencing of pointers going on. Removing an item from one list to put into another list has a lot more operations than swapping values in an array, not to mention that if a lot of sprites occupy the same layer, you will have to scan the linked list to find the sprite you are looking for.

The side-scrolling beat em ups I remember had 10-20 sprites on the screen, max. From that point of view, any organisation technique will be fast. If you were to do an analysis, you have to count actual operations since the asymptotic big O notation won't apply. A quick scan of a small array with a couple of swaps seems very fast to me.

I think it is touch and go between these techniques in terms of time, and the sort is simpler to code: Start with a built in search function because it is the least effort and will probably be fast enough. If/when this section becomes a bottleneck, switch to a bidirectional bubble sort.

[GetSet]

cfoley, on 05 March 2012 - 06:51 AM, said:

My apologies if I came across confrontational. I'm not trying to make it a competition, just saying what I think the best solution is. And I like discussing the merits of different solutions because I always learn something.

I see your point. I always learn something or another from this site and programming forums in general. Debate in of itself, as we are doing in the instant matter, is always a learning experience as well, as new ideas come about or further motivation to implement a different or modified coding strategy.

Quote

Linked Lists seem nice but there is a lot more dereferencing of pointers going on. Removing an item from one list to put into another list has a lot more operations than swapping values in an array...

Not true. Referencing and dereferencing a single node as opposed to re-sorting a whole list, is exactly the point. It also uses less loop cycles, in fact, as mentioned, a linked list approach uses zero loop cycles. The overhead is nonexistant, whereas with sorting, the overhead (lag) is a function of list size and as you mentioned, relative sort order going in for the bi-directional approach.

Quote

...not to mention that if a lot of sprites occupy the same layer, you will have to scan the linked list to find the sprite you are looking for.

The link lists wouldn't be used for anything other than displaying the sprites to effecuate the visual Z-depth. They will be read in logical order of the lists and simultaneously displayed to screen. No searching. You would maintain your characters array independently. The link lists serves as a dynamic "memory" of Z-depth for those characters, and other visual elements such as foreground objects.

In terms of maintaining the link lists (referencing and dereferencing of any given node), this will occur for a given character or foreground object when Y location changes. No loop to update the link lists. No scanning the lists via a loop except during animation, which you would have to do anyway even if you didnt have a link list. In short, no overhead. As mentioned, the reads are sequential based on logical order. No searching.

Quote

The side-scrolling beat em ups I remember had 10-20 sprites on the screen, max. From that point of view, any organisation technique will be fast.

This statement is akin to passing off code design onto hardware engineers. I agree in part that 10-20 sprites, not such a big deal on fast hardware, but whose saying that this link list approach is complicated to implement? It's not really, and it can handle however many sprites you throw at it.

If you can consider foreground objects (tree's you can go behind, cars, fire hyrdrants, etc.), why not make the game more of everything.

That is to say, scalable.

But I say "in part" because even with fast hardware, who knows how many layers of abstraction the run-time is removed from that hardware. Take Javascript for example in a web browser, nowhere near as fast as compiled C++.

And then one must consider the hardware platform itself. From desktops to mobile phones. From legacy consoles to the latest and greatest. Faster software is always better right, all other things being equal?

Quote

A quick scan of a small array with a couple of swaps seems very fast to me.

"small" is a relative term.

Quote

If/when this section becomes a bottleneck, switch to a bidirectional bubble sort.

And when the bidirectional bubble sort becomes a bottleneck, then what?

Best regards,

In short: Agree to disagree.