2018-01-29

Isometric Demo

I’ve been working on a new little project. It’s a game I’ve been thinking about writing for years that’ll hopefully going to turn out like a cross between the puzzle solving of Dizzy and the exploration of Metroid. Part of the delay in getting started was indecision about the best viewpoint for the game, which I’ve been debating for a long time.

If I opt for a Pokémon-style overhead viewpoint I’ll probably have an easier time with the artwork and the game will be much more sedate, which is something I’m aiming for. On the other hand, it prevents me from including any kind of gravity/jump mechanics, which are an important part of the exploration aspect of the game. If I opt for a Metroid-style sideways viewpoint it’ll allow for jumping but it will also likely introduce annoying Metroid-style platform negotiation that I want to avoid.

Recently I’ve been considering an isometric viewpoint like Head Over Heels or the ZX Spectrum version of Batman. It gives me the advantages of both the Pokémon and Metroid viewpoints, but doesn’t preventing jumping and seriously discourages any finicky platforming action. I’ve decided to give it a try.

I started out with this randomly-generated room:

Room

Rooms are represented as an array of tile structs, which are arranged such that the first element in the array represents the tile at (0,0,0) (the tile at the bottom of the stack at the leftmost side of the image):

Room

The first row of the x axis is the first set of data in the array, followed by the next row, working backwards in the y axis. Once we hit the end of the y axis we move up a level in the z axis and repeat.

The graphics consist of hexagonal bitmaps each representing a single tile in the map. In order to render the map we start with the tile at (0,0,max) and render all tiles to (0,0,0). We then move to (1,0,max) and render to (1,0,0). Once we’ve rendered the entire bottom level of the map we move to (0,1,max) and repeat the sequence again. Simply put, we render from back to front, left to right, bottom to top, using the painter’s algorithm. The map consists of tiles that don’t move and aren’t animated, so we can render it to a buffer and copy chunks of it to the framebuffer when we need to erase things.

Rendering moving objects turned out to be far more involved. The problem is occlusion: sometimes moving objects are in front of background elements and sometimes they’re behind them depending on where the objects are positioned in the 3D space described by the map. Sometimes objects are partially occluded.

The easiest way to handle occlusion is to re-render the entire scene, including moving objects, from back to front each time an object moves. This is inefficient and gets slower in proportion to the complexity of the scene.

A more efficient idea I had was to figure out which tiles were in front of moving objects, render those to separate buffers, and add them to the scene as foreground views. However, this turned out to be trickier to implement than I expected.

Yet another approach I came up with was to use raycasting to render the scene. For each pixel of the screen project a ray into the map and see where the ray intersects a tile. Find that pixel within the tile’s bitmap and draw it to the screen. This approach is promising for two reasons: each pixel is drawn precisely once; and it makes possible interesting enhancements to the game engine, like texture mapping instead of precanned hexagonal bitmaps, and the ability to rotate the map by an arbitrary amount. It’s a much simpler problem than a Wolfenstein-like first-person raycaster because the isometric perspective eliminates all of the complex 3D transforms and trigonometry.

After deciding that a raycaster was overkill I came up with an algorithm that uses a z-buffer instead. It’s split into two parts. First we generate the background image buffer and z-buffer in one step:

  • Create an array of ints with the same dimensions as the rendered bitmap (this is the z-buffer);
  • Fill the z-buffer with -1;
  • For each tile in the map in the order described above:
    • Draw the tile to the buffer;
    • For each pixel drawn to the buffer:
      • Write the depth of the tile (ie the tile count minus the current iteration count of the loop) to the z-buffer at the coordinates of the pixel.

That gives us the background image buffer we need plus a z-buffer in which each value describes the depth of a pixel in the image buffer.

Next we can draw any other objects:

  • Create another array to store the moveable-object z-buffer;
  • For each moveable object:
    • For each point in the left, right and top faces of the object within the 3D space of the map:
      • Calculate the 2D location of the point within the object’s bitmap and grab the pixel color;
      • Calculate the depth of the point;
      • Calculate the 2D location on screen where the pixel will be drawn;
      • Get the depth of the pixel in the background image buffer by looking up the appropriate index in the background z-buffer;
      • Get the depth of the pixel from the moveable object z-buffer;
      • Compare the depths and draw the pixel to the framebuffer if the depth from the moveable object is less than either depth from the z-buffers.

Erasing and redrawing is handled by marking the region that bounds the moveable object bitmap as dirty. When we redraw we blit the relevant background rect into the framebuffer then redraw the moveable objects on top.

Here’s what it looks like so far:

Unfortunately it’s too slow on the DS right now.