Question regarding game character display (depth) order

Hi,

I’m working on a game prototype and encountered some questions regarding the “checks” for the characters.

The game has a 2D map, where the characters are placed on. Because it is NOT a birds eye perspective but a faked toppled view where the characters can be seen from the side (for example please look at the perspective of the new “Kingdom Rush” game) I wonder what is the best way to check if a character is behind or in front of another, of buildings and so on? Doing this with Runtime Listeners for each character seems a ‘little bit’ too much :slight_smile: I think. Using a loop to check it for characters also seems taking to long and not good regarding performance.

How is this done without loosing too much performance? This kind of “checks” are critical for almost every game… I think there maybe is a professional solution doing this kind of things… but I can’t find anything about it.

Maybe you have asked yourself this question before me and found a solution?

Any help is welcome! :wink:

Thank you!

Daniela

Hi Daniela,

That’s a great question and a fun problem to think about.  I don’t have experience doing it myself, so I can’t speak to what will actually work from a performance perspective, but here are some things to think about.

We know that the order in which your display objects render in Corona is based on the “painter’s model,” where the objects you create earlier are rendered before the objects you create later.  You can then adjust the order by reinserting your objects into their parent groups using the :toFront(), :toBack(), or :insert() (with the optional index parameter) methods.  Since your characters will be moving around the screen, it’s a given you’ll have to use these methods from time to time.  I take it your question is when and how to do it most efficiently.

Looking at the perspective effect in Kingdom Rush, it seems like the “depth” is easy to define – objects that are higher up on the screen (low y coordinates) are “farther away” and should be rendered before objects that are lower down on the screen (high y coordinates), which are “closer”.

I think there are two broad approaches to trying to deal with this – “global” approaches that try to put *all* of your objects in the right order (even ones that aren’t overlapping, which means the render order wouldn’t actually make a difference visually), and “local” approaches that try to make sure any pair of overlapping objects are rendered in the right order (which is all that matters visually).

For the global approaches, some ideas would be:

  • A runtime enterFrame event listener.  Each frame, the listener would build an array of all your objects based on their y-coordinate, sort it, and then loop through the now-sorted array and reinsert each object into the parent.  For better performance, instead of doing this every frame you could do it every few frames (a user won’t really notice if it takes 0.2 seconds for an overlap to look right versus 0.033 seconds).

  • Similar to the first one, but instead of rebuilding and sorting the array each frame (sorting might be expensive depending on how many objects you have), you could predefine a depthField array.  depthField would be an array, where each item represents a y-coordinate.  Each item in the array would itself be an array that references all the display objects at that y-coordinate.  Then, you could have an enterFrame listener on each object that, each frame, puts each object into the right array within depthField.  Then you would loop through depthField and, for each sub-array of objects, insert those objects into the parent.  The advantage of this is that the “sorting” happens implicitly by the index, so there’s no need to actually sort it every frame.

  • Create a different display group for each level of depth in your scene.  At most, that would be one group for each y-coordinate, or if that’s too many, it could be one for every few pixels.  Then, as your characters move, insert them into the appropriate display group based on the character’s y-coordinate.  You could do that using an enterFrame listener on each object.  Of course, a disadvantage of this method is that you can’t group your objects for other purposes (since an object can only belong to a single group

  • Same as any of the above, but instead of enterFrame listeners, use a metatable on each object so that it only does the work when the object’s y-coordinate actually changes

For local approaches, some ideas would be:

  • Make all your objects sensors using the physics library.  Any time a collision is reported, figure out which object should be in front based on its y-cooordinate, and also check their indexes in their parent display group.  If the indexes aren’t right, swap them

  • Same as above, but instead of using the physics library, detect collisions yourself using basic bounding-box or radius collisions

Anyway, I hope this gets your noodle cooking!  Sorry if my ramble wasn’t completely clear in all cases, but I can try to elaborate or clarify where it’s helpful.  I’ll also be interesting in hearing what others on the forum can suggest who may have more experience with this.

  • Andrew

Hi Andrew!

Thank you very much for your detailed feedback and suggestions! This really helps a lot in getting started!

I really appreciate your long feedback with all this great ideas!!!

Best wishes,

Daniela

I decided to test the “- Same as above, but instead of using the physics library, detect
collisions yourself using basic bounding-box or radius collisions” approach.

Now I have 20 objects moving around the screen and all are checked for collisions which each other. I move the objects via  translate.to but performance with this is not so good. The movement is not smooth but has some lags from time to time.

Any ideas how this can be improved? Is transition.to the best choice for moving characters around the screen?

I also have some problems with checking what character is in front of the other because I test it when two characters collide, but while I change the order for them both it can happen, that a third character crashes into this group and then the order isn’t working anymore for a short time and the scene looks false.

I think this all should be some standard problem, but I can’t find anything useful.

Do you have any ideas on this topic, or maybe links to possible solutions?

Thank you!

Hi Daniela,

With 20 objects on the screen, each being checked for collisions with each other, that’s 20x19 = 380 checks every frame.  That may or may not be the cause of a performance issue depending on how efficiently you’ve implemented the collision checking.  The standard strategy to prune down this sort of collision checking is called sweep and prune: http://porwig.com/research/spatial/collision-detection-sweep-and-prune.html.

transition.to() is a fine choice for moving objects on the screen.  The choppiness you’re seeing is probably from something else.

I’m not sure why you’re seeing problems when three characters are colliding.  It may be an issue with your implementation.  If you compare each character to each other character, and swap them (by which I mean reinsert them into the parent display group into the other one’s index), I think it would work fine.

  • Andrew

I optimized a circle-circle collision test for max 30 characters and one building on the map and it works acceptable with those numbers… but I wonder if there are some optimization tricks to this, so maybe 50 or even 60 characters on the screen can be tested and keep a good framerate… oh and of course some more buildings on the map should work also?

I didn’t implement a sweep and prune algorithm yet because it looks very complicated and I have to look into it some more first.

Any other ideas on how to manage to “order” so much objects on the screen? Maybe some of Andrew’s first suggestions are faster than the circle-circle collision test? Does anybody have some knowledge about this?

Physics (sensor) didn’t work for me btw. … it was not exact enough compared to the circle-circle tests.

Any help welcome!

Daniela

The Sweep And Prune solved all my problems I had to order many sprites at the same time for the whole screen!

With a “normal” circle - circle collision check I could move max. 30 characters before the lags started to get bad. With the Sweep And Prune and some fixes where the checks are done and for what objects I could optimize it to over 100 animated sprites, including health-bars, transparent shadows and more, at the same time. The sprites itself are drawn in the correct depth order and the tested 120 characters max, including other animated sprites on the screen are working with a good frame rate.

Test finished successfully… now I can start working on a cool project I had in mind for some time. Very cool Corona is able to let me do this!!!

:D 

Best,

Daniela

Glad you’ve gotten it working and with good performance!

  • Andrew

With your help!

Thanks again for everything!

Daniela

Hi Daniela,

That’s a great question and a fun problem to think about.  I don’t have experience doing it myself, so I can’t speak to what will actually work from a performance perspective, but here are some things to think about.

We know that the order in which your display objects render in Corona is based on the “painter’s model,” where the objects you create earlier are rendered before the objects you create later.  You can then adjust the order by reinserting your objects into their parent groups using the :toFront(), :toBack(), or :insert() (with the optional index parameter) methods.  Since your characters will be moving around the screen, it’s a given you’ll have to use these methods from time to time.  I take it your question is when and how to do it most efficiently.

Looking at the perspective effect in Kingdom Rush, it seems like the “depth” is easy to define – objects that are higher up on the screen (low y coordinates) are “farther away” and should be rendered before objects that are lower down on the screen (high y coordinates), which are “closer”.

I think there are two broad approaches to trying to deal with this – “global” approaches that try to put *all* of your objects in the right order (even ones that aren’t overlapping, which means the render order wouldn’t actually make a difference visually), and “local” approaches that try to make sure any pair of overlapping objects are rendered in the right order (which is all that matters visually).

For the global approaches, some ideas would be:

  • A runtime enterFrame event listener.  Each frame, the listener would build an array of all your objects based on their y-coordinate, sort it, and then loop through the now-sorted array and reinsert each object into the parent.  For better performance, instead of doing this every frame you could do it every few frames (a user won’t really notice if it takes 0.2 seconds for an overlap to look right versus 0.033 seconds).

  • Similar to the first one, but instead of rebuilding and sorting the array each frame (sorting might be expensive depending on how many objects you have), you could predefine a depthField array.  depthField would be an array, where each item represents a y-coordinate.  Each item in the array would itself be an array that references all the display objects at that y-coordinate.  Then, you could have an enterFrame listener on each object that, each frame, puts each object into the right array within depthField.  Then you would loop through depthField and, for each sub-array of objects, insert those objects into the parent.  The advantage of this is that the “sorting” happens implicitly by the index, so there’s no need to actually sort it every frame.

  • Create a different display group for each level of depth in your scene.  At most, that would be one group for each y-coordinate, or if that’s too many, it could be one for every few pixels.  Then, as your characters move, insert them into the appropriate display group based on the character’s y-coordinate.  You could do that using an enterFrame listener on each object.  Of course, a disadvantage of this method is that you can’t group your objects for other purposes (since an object can only belong to a single group

  • Same as any of the above, but instead of enterFrame listeners, use a metatable on each object so that it only does the work when the object’s y-coordinate actually changes

For local approaches, some ideas would be:

  • Make all your objects sensors using the physics library.  Any time a collision is reported, figure out which object should be in front based on its y-cooordinate, and also check their indexes in their parent display group.  If the indexes aren’t right, swap them

  • Same as above, but instead of using the physics library, detect collisions yourself using basic bounding-box or radius collisions

Anyway, I hope this gets your noodle cooking!  Sorry if my ramble wasn’t completely clear in all cases, but I can try to elaborate or clarify where it’s helpful.  I’ll also be interesting in hearing what others on the forum can suggest who may have more experience with this.

  • Andrew

Hi Andrew!

Thank you very much for your detailed feedback and suggestions! This really helps a lot in getting started!

I really appreciate your long feedback with all this great ideas!!!

Best wishes,

Daniela

I decided to test the “- Same as above, but instead of using the physics library, detect
collisions yourself using basic bounding-box or radius collisions” approach.

Now I have 20 objects moving around the screen and all are checked for collisions which each other. I move the objects via  translate.to but performance with this is not so good. The movement is not smooth but has some lags from time to time.

Any ideas how this can be improved? Is transition.to the best choice for moving characters around the screen?

I also have some problems with checking what character is in front of the other because I test it when two characters collide, but while I change the order for them both it can happen, that a third character crashes into this group and then the order isn’t working anymore for a short time and the scene looks false.

I think this all should be some standard problem, but I can’t find anything useful.

Do you have any ideas on this topic, or maybe links to possible solutions?

Thank you!

Hi Daniela,

With 20 objects on the screen, each being checked for collisions with each other, that’s 20x19 = 380 checks every frame.  That may or may not be the cause of a performance issue depending on how efficiently you’ve implemented the collision checking.  The standard strategy to prune down this sort of collision checking is called sweep and prune: http://porwig.com/research/spatial/collision-detection-sweep-and-prune.html.

transition.to() is a fine choice for moving objects on the screen.  The choppiness you’re seeing is probably from something else.

I’m not sure why you’re seeing problems when three characters are colliding.  It may be an issue with your implementation.  If you compare each character to each other character, and swap them (by which I mean reinsert them into the parent display group into the other one’s index), I think it would work fine.

  • Andrew

I optimized a circle-circle collision test for max 30 characters and one building on the map and it works acceptable with those numbers… but I wonder if there are some optimization tricks to this, so maybe 50 or even 60 characters on the screen can be tested and keep a good framerate… oh and of course some more buildings on the map should work also?

I didn’t implement a sweep and prune algorithm yet because it looks very complicated and I have to look into it some more first.

Any other ideas on how to manage to “order” so much objects on the screen? Maybe some of Andrew’s first suggestions are faster than the circle-circle collision test? Does anybody have some knowledge about this?

Physics (sensor) didn’t work for me btw. … it was not exact enough compared to the circle-circle tests.

Any help welcome!

Daniela

The Sweep And Prune solved all my problems I had to order many sprites at the same time for the whole screen!

With a “normal” circle - circle collision check I could move max. 30 characters before the lags started to get bad. With the Sweep And Prune and some fixes where the checks are done and for what objects I could optimize it to over 100 animated sprites, including health-bars, transparent shadows and more, at the same time. The sprites itself are drawn in the correct depth order and the tested 120 characters max, including other animated sprites on the screen are working with a good frame rate.

Test finished successfully… now I can start working on a cool project I had in mind for some time. Very cool Corona is able to let me do this!!!

:D 

Best,

Daniela

Glad you’ve gotten it working and with good performance!

  • Andrew

With your help!

Thanks again for everything!

Daniela