4. Solving the Visibility ProblemOne of my goals keeping a game journal here is to collect all my research on isometric-related problems in one spot. Hopefully it's a good resource for someone down the road. However, I realized I left out one of the most important problems of all. How do you determine which actors to draw first?
The ideal solution would be to use a
Z-buffering algorithm. Unfortunately, this doesn't look to be practical. Drawing each pixel one at a time appears to be a slow process, but even if it weren't, we don't have 3D models. "Isometric actors" are really 2D images drawn to look 3D--but the computer can't work out the relative depths of each pixel from the artwork alone.
Instead, we're going to use the
painter's algorithm.
Here's the problem:
Two actors with unique coordinates (in the isometric coordinate system) overlap. We want to figure out which one is behind the other. The solution makes good use of linear algebra. If this is something you've never studied before, there's a great introduction
on Wolfire Blog, specifically written for game developers.
One of the first problems was mapping coordinates in the isometric system ("world coordinates") to screen coordinates. This was the first problem solved. The conversion formula is, where Sx, Sy are screen coordinates, and Gx, Gy, Gz are world coordinates:
Sx = Gx - Gy, Sy = 1/2 Gx + 1/2 Gy - Gz
In my illustration above, we have two actors that have the same Sx, Sy coordinates.
Now, here's something to think about. When converting from world coordinates to screen coordinates, we went from three dimensions to two. In effect, we deleted information. Points in the world are described with three variables... but in only two on the screen. What happened to that third piece of information?
It turns out that we really threw out the answer to the depth problem! So, we need to recover this lost information. What happened to it shouldn't be hard to visualize if you're familiar with those old big-box CRT monitors. Imagine "Actor 1" and "Actor 2" being suspended inside the monitor, at different depths. If you look at the screen straight-on, they overlap. However, one is really further back.
Both actors are on a vector that is orthogonal (perpendicular) to the screen. We just need to understand what this vector is, and then we can come up with a formula for the depth.
From the formula, since Sx = 1 * Gx - 1 * Gy, then Sx is a point on the vector <1,-1,0>. Furthermore, since Sy =
1/
2 * Gx +
1/
2 * Gy - 1 * Gz, then Sy is a point on the vector <
1/
2,
1/
2,-1>.
The cross-product of these two vectors will be a vector orthogonal to the screen--thus, overlapping actors will lie on this vector, and we can compute their depth by calculating how far from the origin, along this vector, they are. The cross-product is <1,1,1>, which gives this formula for Sz: 1 * Gx + 1 * Gy + 1 * Gz, or:
Sx = Gx - Gy, Sy = 1/2 Gx + 1/2 Gy - Gz, Sz = Gx + Gy + Gz
Now, here's a method you can use to draw your isometric actors.
Let's suppose you have an isometric world that is 400 x 400 x 400 units. On scene creation, initialize an array of 1200 "buckets" (400 + 400 + 400). Each bucket will hold actors that are to be drawn.
When an actor is moved from coordinate (Gx, Gy, Gz) to coordinate (Gx', Gy', Gz'), remove it from bucket # Gx+Gy+Gz and add it to bucket # Gx'+Gy'+Gz'
Now, in the drawing event, loop through all 1200 buckets. Since each of these buckets is itself a list of actors, you'll need to loop through the contents of each bucket.
Sadly, this won't be a perfect solution. Here's an example of what can go wrong:
So, what went wrong? The pillar that is clipping the player is really tall. Each actor is represented in the isometric world using only a single point. But different heights along the pillar will have different Sz values. Since the actors are different sizes, there's no standard that will handle every case.
The simplest solution I can think of for now is to have all actors be the same size, and split larger ones into standard-sized chunks. The pillar, for instance, can be split in half--so that each half is the same size as any other actor. This works.
In my current implementation, I use "Draw image of actor". But, it seems like it would be possible to split each actor's image into equal-sized tiles. These tiles can be saved in the extras folder, and then assembled in the drawing loop. Each tile would have its own Sz coordinate. The smaller each tile (and hence greater number of tiles per actor), the better. For this game, though, the only large actors I can imagine needing are structural (pillars, etc.). Since they don't have nearly as many frames as moving actors, splitting them isn't difficult at all.
