hej guys,
I am doing some research right now and was wondering, if someone got a good isometric depth sorting working on a good speed in corona for 100+ objects.
Everything I can find on the internet is a O(n^2) algorithm, which seems to be getting very slow on corona.
Any ideas, suggestions would be helpful.
Thanks a lot,
Philip
I don’t know of any that are premade, but it’s not tough to roll your own z-depth sorting functionality. I have one in “Crosstown Smash” and it doesn’t seem to affect the performance to a high degree.
a z-depth sorting seems to be not to complicated - still you would need to check every object against every object (at least on the screen) right? that what would make it expensive for 100+ objects on the screen.
Any suggestions on that?
cheers…
if it’s real-time, then yea, that might get expensive memory-wise, but you could also just set a variable that would have the depth function check ONLY objects that have moved. If it’s not real-time (RTS or whatever) then it would be even easier.
I could be over-simplifying things though. What kind of application is this solution going to target?
yes, its going to be real- time and also its going to be 100+ moving objects
(so not really performance improvement by checking ifMoved)
seems like the horror scenario 
Hi.
Presumably, your objects will tend to be spread out a bit, allowing you to do some kind of clustering, e.g. via the rows in your isometric map, assigning an object to, say, whichever row it’s “above”. O(n2) can certainly grow big fast but 10 rows of 102 checks (1000) would be an improvement over one big 1002 (10,000) situation. Of course you’d need to take some special care between neighboring clusters (and deal with “big” objects that can at least visually overlap several) and find ways to deal with objects that straddle the boundaries.
Also, are you using just one display group? It might make sense to make several of those as well, e.g. one per row in the above. For that matter, are you accessing the objects directly from the display group? At the 10,000 comparisons stage, it might start to matter all on its own that you’re constantly incurring the cost of the group’s __index metamethod and more important still, all the insert()'s will probably be doing signifcant data structure maintenance: if I had to guess, I’d say groups use C++'s std::vector under the hood (whether this is true or not, alternative data structures simply put a different spin on the problem), which can move large swaths of values to open / fill gaps (if an object is inserted at position 3, objects 4 through 100 must first be moved up one spot; if object 7 is removed, objects 8 through 100 are moved down one; and moving an object around in the same vector entails both of these).
If you’ll be moving the objects around and calculating their costs anyhow, one way to do the sort is to stuff them into a priority queue and then pull them out in order. This thread has some good discussion (and some implementations, e.g. a skew heap and maybe a binary heap too): http://lua-users.org/lists/lua-l/2008-03/msg00498.html
hej StarCrunch, thanks so much for your comment. This is one of the most useful information I read in a while now.
did you write something similar to this?
I already am using display groups to sort the basic depth, but I found that it gets very memory consuming very quickly, when I am trying to generate too many display groups. I try to do most of the data storage and sorting in tables now, as they seem less cost effective. and later sort them accordingly. I still don’t know if it makes sense in the long run.
Thanks so much, if you have more to read, please keep it coming.
I have not implemented anything isometric, alas, though at times I get ideas of building something on top of Equinox- or Landstalker-style mechanics, so I’ve definitely given it some thought. 
On the other hand, I have been knee-deep in optimization problems lately…
On the subject of clustering, it occurs to me that you might not be using physics (at least, it sounds non-trivial adapting it to isometric gameplay), in which case you could hijack the sensor functionality for that purpose. This assumes there’s a pretty decent chance objects do cluster, of course (otherwise it degenerates to “compare everything”).
On that note, random algorithm idea:
INITIALIZATION
ON CONTACT
When a new contact begins, put one object inside a list held by the other (arbitrarily choose the one with, say, the lower ID to hold the list); optionally put the list-holding object inside a “being touched” group to save iteration time later
If instead a contact ends, remove that object from the list held by the other (same condition); if you added the list-holder to a “being touched” group, remove if its list became empty
EACH FRAME
Prepare an empty collection of clusters
Iterate through all the “being touched” objects, and union-find them together (some code, docs)
For each object, find its root, and dump it in the root’s cluster (initializing it, when first encountered)
Sort each cluster
END OF FRAME
If that’s no good, you can always just try having a coarse grid and stuf objects into the appropriate bucket, sort each non-empty one of those, then insertion-sort them together at the end.
Anyhow, my dinner’s ready, so I’m going to post and hope this sort of made sense. 
oh god landstalker! I loved that game. Played that so much as a kid. Even more impressive, that they got that figured out with that basic hardware back then.
Using the physics engine to actually capture just the overlapping objects that need sorting is genius, but I think it will all come down to how fast the collision detection is in comparison to the brute-force sorting/different cluster approach. Would be interesting to get some insights of the corona engineers here.
I will definitely set up a stress test scene, compare the different approaches and post the results here if you are interested.
Maybe we could benefit both from a cooperation.
Might just take some time, as I am finishing up a game right now.
I already gave the coarse grid a try, but ended up with loads of memory consumption. maybe I used a too narrow grid in the end, before starting the actual sorting, will give it another thought though.
Thanks for all the thoughts and bon appetit
I don’t know of any that are premade, but it’s not tough to roll your own z-depth sorting functionality. I have one in “Crosstown Smash” and it doesn’t seem to affect the performance to a high degree.
a z-depth sorting seems to be not to complicated - still you would need to check every object against every object (at least on the screen) right? that what would make it expensive for 100+ objects on the screen.
Any suggestions on that?
cheers…
if it’s real-time, then yea, that might get expensive memory-wise, but you could also just set a variable that would have the depth function check ONLY objects that have moved. If it’s not real-time (RTS or whatever) then it would be even easier.
I could be over-simplifying things though. What kind of application is this solution going to target?
yes, its going to be real- time and also its going to be 100+ moving objects
(so not really performance improvement by checking ifMoved)
seems like the horror scenario
Hi.
Presumably, your objects will tend to be spread out a bit, allowing you to do some kind of clustering, e.g. via the rows in your isometric map, assigning an object to, say, whichever row it’s “above”. O(n2) can certainly grow big fast but 10 rows of 102 checks (1000) would be an improvement over one big 1002 (10,000) situation. Of course you’d need to take some special care between neighboring clusters (and deal with “big” objects that can at least visually overlap several) and find ways to deal with objects that straddle the boundaries.
Also, are you using just one display group? It might make sense to make several of those as well, e.g. one per row in the above. For that matter, are you accessing the objects directly from the display group? At the 10,000 comparisons stage, it might start to matter all on its own that you’re constantly incurring the cost of the group’s __index metamethod and more important still, all the insert()'s will probably be doing signifcant data structure maintenance: if I had to guess, I’d say groups use C++'s std::vector under the hood (whether this is true or not, alternative data structures simply put a different spin on the problem), which can move large swaths of values to open / fill gaps (if an object is inserted at position 3, objects 4 through 100 must first be moved up one spot; if object 7 is removed, objects 8 through 100 are moved down one; and moving an object around in the same vector entails both of these).
If you’ll be moving the objects around and calculating their costs anyhow, one way to do the sort is to stuff them into a priority queue and then pull them out in order. This thread has some good discussion (and some implementations, e.g. a skew heap and maybe a binary heap too): http://lua-users.org/lists/lua-l/2008-03/msg00498.html
hej StarCrunch, thanks so much for your comment. This is one of the most useful information I read in a while now.
did you write something similar to this?
I already am using display groups to sort the basic depth, but I found that it gets very memory consuming very quickly, when I am trying to generate too many display groups. I try to do most of the data storage and sorting in tables now, as they seem less cost effective. and later sort them accordingly. I still don’t know if it makes sense in the long run.
Thanks so much, if you have more to read, please keep it coming.
I have not implemented anything isometric, alas, though at times I get ideas of building something on top of Equinox- or Landstalker-style mechanics, so I’ve definitely given it some thought. On the other hand, I have been knee-deep in optimization problems lately…
On the subject of clustering, it occurs to me that you might not be using physics (at least, it sounds non-trivial adapting it to isometric gameplay), in which case you could hijack the sensor functionality for that purpose. This assumes there’s a pretty decent chance objects do cluster, of course (otherwise it degenerates to “compare everything”).
On that note, random algorithm idea:
INITIALIZATION
ON CONTACT
When a new contact begins, put one object inside a list held by the other (arbitrarily choose the one with, say, the lower ID to hold the list); optionally put the list-holding object inside a “being touched” group to save iteration time later
If instead a contact ends, remove that object from the list held by the other (same condition); if you added the list-holder to a “being touched” group, remove if its list became empty
EACH FRAME
Prepare an empty collection of clusters
Iterate through all the “being touched” objects, and union-find them together (some code, docs)
For each object, find its root, and dump it in the root’s cluster (initializing it, when first encountered)
Sort each cluster
END OF FRAME
If that’s no good, you can always just try having a coarse grid and stuf objects into the appropriate bucket, sort each non-empty one of those, then insertion-sort them together at the end.
Anyhow, my dinner’s ready, so I’m going to post and hope this sort of made sense.
oh god landstalker! I loved that game. Played that so much as a kid. Even more impressive, that they got that figured out with that basic hardware back then.
Using the physics engine to actually capture just the overlapping objects that need sorting is genius, but I think it will all come down to how fast the collision detection is in comparison to the brute-force sorting/different cluster approach. Would be interesting to get some insights of the corona engineers here.
I will definitely set up a stress test scene, compare the different approaches and post the results here if you are interested.
Maybe we could benefit both from a cooperation.
Might just take some time, as I am finishing up a game right now.
I already gave the coarse grid a try, but ended up with loads of memory consumption. maybe I used a too narrow grid in the end, before starting the actual sorting, will give it another thought though.
Thanks for all the thoughts and bon appetit