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.

2010-09-08

Redrawing with Damaged Rects

The Problem: Bad APIs and Suboptimal Redrawing

The existing gadget redrawing system in Woopsi sucks. It’s inefficient and makes the API ugly.

For example, here is a completely bare-bones startup method that will get Woopsi into a usable (but empty) state:

void SomeApp::startup() {
    enableDrawing();
    redraw();
}

The two function calls in the startup() method ensure that the Woopsi instance is visible. When an instance of the Woopsi class is created, its redraw system is disabled. This allows the initial set of gadgets to be added without them appearing on-screen one at a time. Once the initial state has been set up, drawing can be enabled, and the initial state can be drawn.

You might notice that these two lines of code aren’t required in any other UI framework you’ve used. Neither winforms, AWT, Swing, GTK, KDE or anything else requires that you manually enable redrawing and redraw the display once you’ve finished adding UI components to your application.

The reason for this is the way that Woopsi handles redrawing. In Woopsi, each gadget is responsible for redrawing itself. All gadgets know which portions of themselves are visible, and they also know when their appearance has been changed. When a gadget is created it knows that it must redraw itself, and does so. Likewise, when a gadget moves, or is resized, or is clicked, it will redraw itself. So, when we add gadgets to Woopsi, they will draw themselves to the screen one at a time instead of the entire screen being drawn in a single operation. This piecemeal redraw looks odd and wastes CPU time, so drawing is initially disabled. Users must re-enable drawing themselves when the UI is ready.

The problem of wasted CPU cycles is more onerous in other situations. Consider the TextBox gadget. This redraws itself every time its text is changed. If we run the following code, the textbox will redraw four times:

textbox->appendText('t');
textbox->appendText('e');
textbox->appendText('x');
textbox->appendText('t');

The textbox redraws every time a character is added to its text. If we were to add one hundred characters, the textbox would redraw one hundred times. Now suppose that the textbox fills the entire bottom DS screen. Changing the text in the textbox changes roughly 8x8, or 64 pixels, per update. That means we’ve changed 6,400 pixels. However, we’ve redrawn every pixel on the screen one hundred times. We’ve redrawn 256x192, or 49,152 pixels, per update. We’ve redrawn 4,195,200 pixels when we only needed to redraw at most 6,400. 99.87% of the redrawing was just wasted CPU time.

Woopsi offers a workaround in the form of the enableDrawing() and disableDrawing() methods of the Gadget class:

textbox->disableDrawing();
textbox->appendText('t');
textbox->appendText('e');
textbox->appendText('x');
textbox->enableDrawing();
textbox->appendText('t');

However, this is a nasty hack. It requires that the developer knows enough about Woopsi’s internals to be able to predict when it will redraw and when it is safe to prevent the automated redraws from running. In the above code, it isn’t particularly obvious why drawing is re-enabled before the last character is added (so that the final append triggers a redraw) and it isn’t something that developers should need to care about.

The Competition: What Everyone Else Does

In the majority of other UI kits, redrawing is handled by tracking damaged rectangles. These are areas of the screen that have been modified and therefore need redrawing. In these systems, instead of our textbox redrawing itself, it would notify an object responsible for tracking these damaged rectangles that its visible areas had changed. The tracking object would store any of those rectangles that it hadn’t been previously notified of in a list. At frequent intervals (every VBL, say) the tracker would order the gadget hierarchy to redraw all of the damaged rectangles in its list. Using this system, the textbox would only be drawn once no matter how many times it was changed.

Justifying Woopsi’s Behaviour: DMA and Bad Code

Woopsi doesn’t use a damaged rectangle system for two reasons. Firstly, it makes extensive use of the DS’ DMA hardware to copy areas of the framebuffer around. It is especially important to the scrolling system that everything on-screen is up-to-date. If redrawing was postponed until a later time it is likely that the scrolling system would be working with out-of-date data. The second reason is the complexity of the rectangle splitting algorithm discussed here and here. Trying to get the code that splits up rectangles to do anything slightly different would be horribly complicated because, well, the code itself is horrible.

Potential Benefits of Changing Woopsi

But what if Woopsi could use the damaged rectangle system for redrawing? How would that affect the API and the framework? It would instantly obsolete about a dozen of the most complicated methods, and it would make a bare-bones Woopsi setup function look like this:

void SomeApp::startup() { }

Adding one hundred characters to a textbox would require a single redraw without any extra developer effort. Even actions such as moving gadgets would be more efficient - they are currently entirely erased from one location and redrawn at another, even if they move by just one pixel. A damaged rectangle system would reduce the number of rendered pixels in such a situation by almost 50% because there wouldn’t be an erasing step.

Fixing the Rectangle Splitter

The existing code used to split up rectangles into intersecting and non-intersecting sub-rectangles is 207 lines long. At times, it has nested if statements and for loops nearly a dozen deep.

(I’d originally intended to add the code in here, except my current WordPress theme breaks the “more” tag, making the post far too long for the front page of the blog. Additionally, trying to force the code into a smaller div by adding a “style” attribute breaks the syntax highlighter and causes angle brackets to be interpreted as HTML tags. I really need to get a new theme that’s less cluttered and easier to read, but nothing I’ve found so far fits.)

Anything nested that deeply is in dire need of refactoring. I looked at it the other day and realised that the entire algorithm was vastly overengineered. A far more efficient approach presented itself to me and I set about rewriting it. The replacement method is 74 lines long and contains just 4 if statements with no nesting at all.

The new method is a massive improvement over the original code. It is considerably smaller and easier to understand, it is faster and best of all, it produces the optimal result each time.

In all situations where there is an intersection, the original code produced (2n-1) rectangles, where n is the optimum number of rectangles. The larger the number of rectangles produced by this method, the more clipping the renderer will have to do later, so having a function that always produces the optimal result is a very good thing.

Switching to Damaged Rectangles

With the rectangle splitting routine rewritten and moved into the Rect class, where it should have been from the start, switching to a damaged rectangle-based rendering system starts to become feasible. The last problem to solve is the issue of scrolling. The scroll routines must be working with the latest bitmap data, which means rendering cannot be deferred.

I don’t know how much thought I’ve put into into solving this during the course of Woopsi’s development, but I’d never managed to hit on a solution until a couple of days ago. The answer is painfully obvious once you know it: make any functions that use the scrolling abilities of Woopsi flush any pending damaged rectangle redraws before they start. That way, the screen will be up-to-date before any scrolling is done.

Simple, obvious.

The upshot of all this is that Woopsi’s rendering engine is now based on damaged rectangles. Instead of the TextBox calling redraw() when its text changes, it now calls markRectsDirty(). It sends its list of visible rectangles to a new DisplayManager class (I might change the name of that class at some point), which works out which parts of the damaged rectangles it knows about (and discards them) and which are new (and remembers them). Once every VBL the DisplayManager redraws the display.

Redrawing is achieved by splitting the damaged rectangles into intersections with the gadgets. The DisplayManager performs a depth-first walk of the gadget tree in order to redraw in front-to-back order. Any rectangles that are redrawn are removed from the damaged rects list. Once that list is empty, the redraw method ends.

What has changed?

So, what has changed? There’s no need to call enableDrawing() or redraw() in the startup() method, for a start. In fact, both enableDrawing() and disableDrawing() no longer exist. The redraw() method has gone too, as well as the following:

  • Gadget::erase()
  • Gadget::eraseGadget()
  • Gadget::redrawDirty()
  • Gadget::drawChildren()
  • Gadget::redrawDirtyChildren()
  • Woopsi::eraseRect()

As previously mentioned, these were some of the cludgiest, most unpleasant functions in the system. I’m glad to have chucked them out.

There’s always a Catch

Unfortunately, the hack that the DimmedScreen class exploited no longer works. That class has had to be deleted.