Falling Performance

When thinking about the end-game and how that would play and look like, I got an idea for a set of levels where the theme is "Floor is Lava". A living room could easily morph into a castle inside a volcano where you're surrounded by flames and molten rock. In a kid's mind at least. I quickly mocked something up and this is how it would look like:

So unlike the regular levels, you have sheer cliffs to fall off from. And that gave me an idea that items pushed off the ledge should fall into oblivion. Fairly straightforward, right? The problem was however that the levels are very much 2D and the background layer (the room itself and the carpeted tiles) is prepared once and then just rendered as a single image before the objects are drawn on. If the blue ball were to fall off the edge, for example, it would need to go behind the small region of floor at the bottom to give the impression of depth.

At that moment the drawing logic was as follows:

1. Draw room background and floor tiles into a separate bitmap buffer; only once when loading and preparing the level
2. On each frame copy the background buffer into the screen buffer and draw objects onto it as well

Perhaps not the best approach, but easy code to maintain and performs okay for the most part.

As a lot of developers probably would, I thought I'd try the straightforward approach first and see where we end up. See how steep a mountain we needed to climb. Hacking into that draw loop, the effect of the ball disappearing behind the floor could be achieved by redrawing the floor on each frame and making sure certain objects are drawn before or after certain tiles. Essentially peforming previously listed steps on each frame (as a special mode.)

Running that in DosBox emulating a 33MHz 486DX (a once powerful spec of machine) performed... not well. There's just too much happening each frame. Drawing and overdrawing. Far from playable and much less so on yet weaker machines, which I had hoped I could target. You know, to capture that lucrative MS-DOS market to the fullest.

Sitrep: It's crap, but that's the fertilizer of our future

An obvious improvement would be to not draw everything every frame, and only update certain regions where there's been any change. Well, that's doable I thought. Just simply need to redo the whole scene state machine, animation logic and add a bounding box to each object and have them track its change between frames to know what region of the screen (if any) needed to be changed when moving or otherwisse animating. Then I could only redraw the objects and tiles intersecting that region into a separate scratch buffer and copy that region to screen in the end. Cue the A-Team music!

Lot to unpack here, but the white box bounds the previous frame (dark red) and current frame (fuchsia), marking our dirty area.

Modified draw logic to apply on every frame:

1. Iterate over dirty regions
2. [Conditional] For any falling object, redraw that section of the background buffer along with the object itself in there (achieving the masking effect)
3. Copy the background section into the screen buffer and draw other intersecting objects as well

Put it all together and... better but not good enough. Whenever the special background redraw is active, the performance tanks — there are still too many draw calls happening regarding drawing columns and tiles on top. Plus handling objects in that way caused some draw-order issues and the code complexity had ballooned a lot. I couldn't wait to throw it away. Ideally we would never have to redraw into the floor buffer after the initial load, and just copy from it.

Back to the drawing board. Is there another way to know whether some part of the floor is in front of another (and what its shape is) when what we have to work with looks like this?

It would look completely white if we also included the room background itself. How can you tell one section of the floor from another?! It's almost like a depth map with just 1 value, rendering it useless...

DEPTH MAP! That's it! What if we created a map (or mask) of sorts where each section of the floor had a unique value and we could use that to quickly tell if a pixel is in front or behind something. The end result looks something like this. I'm only batching tiles together here because I have 256 values to work with and the levels could easily span more than 16x16 squares. Without that limitation, each square could have separate value but the end result would be the same. If anyone's interested in the batching algorithm, I can describe that separately.

I am using VGA palettes and indexed colours, so the RGB values don't matter here and it's just for visualisation. There are also values for all the spaces between the floor pieces, but these are not drawn into the buffer. It's there virtually, in a 2D array. Whenever an object moves into that empty space and needs to fall down, it takes the value of that square from the array and uses a different drawing function to only draw pixels where that value is less than what's in the mask at any given location. In the following example, the ball is on a tile with depth value of 2, so that's the number to compare mask values against.

The Result

This is DosBox emulating a 33MHz 386DX, so about 50% less performant than the 486 that previously struggled to handle this! There may be additional gains to be found in the way the objects are displayed — a full object sprite is drawn into the scratch buffer even if only a small part of it intersects a dirty region. Theoretically it would be better to just draw that sub-rect of the sprite, but I'd have to refactor further to see if that'd make a significant difference.

There is still a lot to fix in light of all these changes, but I hope this was all worth it.

This is probably nothing new to a lot of you, but I'm still sometimes surprised how simple and effective certain solutions can be, and if I didn't perhaps overcomplicate things at first. In hindsight the masking approach makes sense but stepping on rakes is probably good for something as well. The intermediate step of implementing incremental drawing was a necessity in any case.

It has been a fun challenge but the greatest challenge of them all still awaits - actually finishing the game.

Written in C, using Allegro library.