Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

My game is in HTML5 canvas, but I assume this concept applies to any language.

In the past I've used a multi-dimensional array to keep track of sprite positions. Here is a simplified example:

[
[ [],[[plant12]],[],[],[] ],
[ [],[[apple]],[],[],[] ],
[ [],[],[],[],[] ],
[ [[apple]],[],[[apple]],[],[] ],
[ [],[],[],[],[] ],
]

And this would always draw sprites with the correct z-index, as the map was always read left-to-right, top-to-bottom:

correct z-index

But with a more experienced game developer's advice, I started using quad trees for collision.

Since I will have a tree of objects with x/y coordinates, I thought I might as well abandon using a sprite map, and just draw the sprites based upon the quad tree data.

But the problem is that if the objects are not collected in a precise order, the sprites will be drawn in incorrect order, resulting in such:

incorrect z-index

If I am not using a sprite map, what is the best way for me to ensure I am drawing sprites in the correct order/z-index?

I am thinking that maybe I will make a collection method for the quad tree that will collect objects from a left->right, top->bottom order, and then draw each object's corresponding sprite in a loop. But honestly, that sounds a lot less inefficient that a having a predefined map, especially considering that all that traversing is a lot of recursive calls.

Another approach is to create some sort of z-index system, but I think that may be over-complicating things as well.

Any advice on how to approach this?

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

Implement a QuadTree was indeed a good idea. Scene culling and collision detection will be more efficient with a QuadTree.

Your only option is to learn a sorting algorithm or get a library that implement one. I don't know a javascript library that meets this condition.

First you select the visible sprites. This will be fast thanks to the quad tree. This is the scene culling.

Second, you will have an array of sprites in any z-order. Then you apply a sorting algorithm to efficiently sort the array from the lower z value to the higher one.

Third, now you have the same array but with all sprites ordered by their z position. Render all sprite in the array.

Sorting algorithms reference: http://www.sorting-algorithms.com/

Play all animations and choose which one to implement. I remember have used Quick3 in the past for a QuadTree.

It may be the case that you don't want to pay the time cost of learn an algorithm at this stage of your project. In my opinion it won't take so much time and will be good later. But if you still want to avoid the sorting algorithms for now, do brute force as a temporary solution:

When you are inserting the sprites into the array, for each new sprite, increase the array size by 1, iterate through the entire array, compare the arriving sprite z with each of the other sprites. Remember that the array is sorted from the beginning because all sprites where inserted using this method. When you find the first sprite with a higher z-order, move that sprite and all sprites next to that one by 1 to the end of the array. Then insert the arriving sprite where the first sprite with higher z-order was.

Note: that is very inefficient. It only will work to make possible to see the game graphics correctly drawn for now, but you probably cannot publish your game until you implement a more efficient method. If all scenes of the game are so simple that this method is enough maybe the quad tree was not needed in the first place. As you are using a quad tree, then you expect your scenes to reach considerable complexity, and sorting algorithms will be needed too.

share|improve this answer
    
Thanks for your answer. Right now I'm trying to completely understand retrieval within quad trees, but I understand the process of sorting and then rendering that you are describing. And thanks for the link to the sorting algorithms! There are some really cool stuff there. –  user2736286 Oct 15 '13 at 0:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.