Monday, December 03, 2007

Tiles Don't Generalize

For a couple months, I've been experimenting a bit with SVG during my free time to get a feel for how to use it cleanly on the web. In particular, I've been playing around with trying to create a little tile-based game using SVG and JavaScript.

The nice properties of grid-based tiles using an isometric or 3/4 perspective are well-known. As long as every object in the game fits exactly in a 1x1 grid cell, then everything works great. It's easy to figure out an order to draw the objects in order to ensure that nearer objects properly occlude further objects. You can stack objects within a grid and do other nice stuff too.

After seeing all those isometric-perspective computer games with characters running in-between grid tiles and with all manner of odd-shaped objects though, I assumed that the algorithms for choosing the order to draw objects in the isometric perspective generalized in some nice way. Of course, I realized that things couldn't generalize arbitrarily. If you allowed for arbitrary objects in arbitrary poses, then you'd end up with an arbitrary 3d scene drawn from an orthographic perspective. Then you'd need the full painter's algorithm with polygon chopping etc.

But, I assumed that if all objects were in non-overlapping axis-aligned bounding boxes, then I could figure out some way to order the objects without needing to chop any of them (since you can't really do this is SVG). In particular, I wanted the floor tiles and the objects to be all mixed up in the rendering code. But for the isometric perspective, it is possible to create degenerate examples where objects mutually occlude each other. So you can't generalize algorithms for the isometric perspective this way. In particular, my plan of having floor tiles and wall tiles, plus arbitrarily sized objects sitting on the floor tiles just wouldn't work.




In fact, the same thing happens with the three-quarter perspective as well (I've shifted the perspective a bit so that it's easier to see the depth of the objects).



So having arbitrarily sized objects that can stack on top of each other arbitrarily won't work. Having objects in non-overlapping axis-aligned bounding boxes where all the bounding boxes sit on the same plane, that seems to work ok. With the isometric perspective, it seems like it might be a little bit hard to get the right ordering of objects during drawing, but it seems doable at least. With the 3/4 perspective, everything works out well in that particular situation.

So basically, one way to get around this problem is to have a flat floor and use tiles to cover the floor as one layer, then on a second layer, you can have objects and walls and stuff that you can order separately. I imagine there are other cases that lead to an easy ordering of objects (perhaps if everything has a fixed height? or maybe in the 3/4 perspective, if you allow for only two levels: one for arbitrary height terrain and then another for things on top?), but I haven't really figured it out yet. Perhaps in reality, degenerate cases never really end up occuring, so you can just sort of hack in lots of special cases in the rendering engine to make sure all the objects are rendered in the right order.

Well, in any case, the point of this post is to show that tiles are trickier than I thought. They really don't generalize nicely, so you have to put a lot of thought into how to handle things once you allow for objects that don't fall exactly within grid boundaries.