Friday, December 9, 2016

algorithm - How do I determine the draw order in an isometric view flash game?


This is for a flash game, with isometric view. I need to know how to sort object so that there is no need for z-buffer checking when drawing. This might seem easy but there is another restriction, a scene can have 10,000+ objects so the algorithm needs to be run in less than O(n^2). All objects are rectangular boxes, and there are 3-4 objects moving in the scene. What's the best way to do this?


UPDATE


in each tile there is only object (I mean objects can not stack on top of each other). and we access to both map of Objects and Objects have their own position.


UPDATE2



see these figures:


enter image description here enter image description here


in first one first blue object should be drawn then green then red. while in second one you have to draw them in reverse order. you need to draw red first and then green and finally blue object. as you can see there is no difference in position of blue and red objects ,they both have different distance from camera and so on. but because of their relative position to green box, you need to change their draw order between two images. that's what makes this problem a mess.


side-note: since all objects are rectangular prism, it's mathematically provable that there is at-least one draw order to satisfy problem needs.



Answer



This is actually very simple if your objects match up with your isometric tiles. Take a look at this image:


Isometric drawing order


You should first draw the object at the red position, then objects at blue, then green, then yellow, then magenta, and so on... It should be fairly obvious how to implement this if your board has objects in it instead of objects having position as an attribute. If that's not your case, you should keep a separate data structure, updating it whenever an object moves (which should be fairly easy too.)


This has a new problem: you can easily see how now its complexity is O(N) where N is your board size (N=W*H). To overcome this problem just create a new linear data structure where each index in your structure matches a given depth, updating it whenever an object changes depth.


The case where an object doesn't match with a single tile is a bit harder, so I will post it if you need it as soon as you update your question.



No comments:

Post a Comment

Simple past, Present perfect Past perfect

Can you tell me which form of the following sentences is the correct one please? Imagine two friends discussing the gym... I was in a good s...