12
\$\begingroup\$

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.

\$\endgroup\$
8
  • 2
    \$\begingroup\$ You should post more information. Can objects stack (3d)? Objects have positions or the map has objects? etc. \$\endgroup\$
    – kaoD
    Mar 21, 2012 at 22:46
  • 2
    \$\begingroup\$ Is this the same as gamedev.stackexchange.com/questions/8151/… \$\endgroup\$
    – Tetrad
    Mar 21, 2012 at 23:14
  • \$\begingroup\$ @Tetrad yeah, but there is slightly little difference about the objects we put in the scene. \$\endgroup\$
    – Ali1S232
    Mar 21, 2012 at 23:41
  • \$\begingroup\$ @Gajet (after your update) objects can only be 1*X and X*1 or also X*Y? Could you afford to split the objects in several sub-objects? (like green being 4 sub-green objects) Is the object's orientation fixed? \$\endgroup\$
    – kaoD
    Mar 22, 2012 at 0:22
  • \$\begingroup\$ Also: how many adjacent tiles does your object's height obscure? \$\endgroup\$
    – kaoD
    Mar 22, 2012 at 0:29

4 Answers 4

10
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ that algorithm is also the first one came to my mind, but see my update, that's why you can't use it without a change. \$\endgroup\$
    – Ali1S232
    Mar 22, 2012 at 0:03
  • 1
    \$\begingroup\$ @Gajet and that's the kind of thing you have to post in your question in the first place :P \$\endgroup\$
    – kaoD
    Mar 22, 2012 at 0:19
  • 3
    \$\begingroup\$ This is the way to go, split up the big parts in 'tiles' +1 \$\endgroup\$
    – Valmond
    Mar 22, 2012 at 16:06
2
\$\begingroup\$

I have no special knowledge on this subject, but here's a thought.

Start by marking each cell as "not drawn". (Or, equivalently, use an array to represent the location of the closest "drawn" thing on each "near-far line" of cells, or a set, etc.) Then, for each cell (I would probably go through them in the order kaoD described): check whether that cell has been drawn; if it has not been drawn and contains an object, check whether each cell that would be obscured by that object has been drawn, and if not draw it recursively; draw the object contained by that cell if necessary; and mark that cell and any cells occupied by its object as "drawn".

I'm assuming that you can quickly map a cell to the object inside it, if any. I believe this is O(n) time, though it could end up building a large stack (which you may want to turn into a linked list if you're worried about running out of stack space).

If you really need a list, you can append to a list instead of drawing. I suspect that starting with a mostly-sorted list doesn't help.

\$\endgroup\$
1
  • \$\begingroup\$ I believe this algorithm can be seen as a form of topological sort adapted to the problem; I was just about to point vaguely in that direction myself. Topological sort is a solution to most ordering/dependency problems. \$\endgroup\$
    – Kevin Reid
    Mar 22, 2012 at 1:27
1
\$\begingroup\$

I'd use the painter's algorithm with a taxicab distance from the furthest cell away from the camera, drawing the ones closest to the camera first and then moving outward.

Edit: This doesn't work unless you can draw the contents of each cell individually.

\$\endgroup\$
1
  • \$\begingroup\$ this might work, but I can't tell how it differs from algorithms byte56 or kaoD suggested. to me it seems it still has same problems as described in my second edit. \$\endgroup\$
    – Ali1S232
    Mar 22, 2012 at 12:25
1
\$\begingroup\$

What makes you believe it's “mathematically provable that there is at-least one draw order to satisfy problem needs”? Here is a trivial counterexample where you cannot rely on z-sorting objects:

enter image description here

\$\endgroup\$
3
  • \$\begingroup\$ Just out of curiosity... could you elaborate the counterexample? That's not a grid. \$\endgroup\$
    – kaoD
    Mar 23, 2012 at 8:41
  • \$\begingroup\$ well note that there is only one object on each tile, and object may occupy one or more tiles, but they always have rectangular projection on the plane. these two condition are enough for proving that statement. \$\endgroup\$
    – Ali1S232
    Mar 23, 2012 at 9:10
  • \$\begingroup\$ Okay, with those restrictions and the fact that the grid is flat there is a solution. I will post it later. \$\endgroup\$ Mar 23, 2012 at 11:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .