Changing perspective

So it’s been a while! I was holding out on doing another post until I finished the loose material and liquid simulation and rendering. Well, its been quite a journey, and unfortunately most everything I tried over the last few weeks has ended up no better or much worse that what I started with. That’s just how life (and game development) goes sometimes.

Not everything was a loss though. Failure can be just as valuable as success (if not more so), and I certainly learned a lot about what doesn’t work. Also, I now have much better tools to debug and iterate on algorithms in general, which I hope will accelerate development down the line.

Moving to 2D

As I mentioned my last post, I was making rapid progress on loose material and liquid simulation. In just a few days, much of the issues visible in the first video were already addressed, and it looked pretty good. However, there were some performance issues, and a few minor graphic artifacts that I wanted to polish up. Then I could move on to problems unique to water (translucency and running / infinite water sources).

Should be done in a week, no problem…

Unfortunately, my velocity started seriously bogging down. After a several days of not making significant progress, I realized I needed to change my workflow. I had a few observations:

The world data model was not friendly to tinkering.

Because of the sheer size of the world that may be loaded, the Terra Diem’s in-memory chunk format is highly optimized in order to fit up to 1024x1024x256 blocks in memory (over 268 million cubic meters). This is great if you want to support a big world, but it makes it quite awkward and slow to iterate on – especially when the best solution is not readily apparent.

Debugging was difficult.

In a 3D world, it is just harder to see what is going on. First of all, the view is from an arbitrary direction. When stepping through simulation or evaluating how render mesh is built, it is easy to forget or get wrong which way is north, south, east, or west. Secondly, much of the world is completely hidden. For performance reasons, the game cannot render every block – it only renders the surface that is visible. That makes understanding what the simulation is doing within a volume more challenging.

Setting up experiments in game was time consuming.

To test out different scenarios, I often need to build custom configurations. My choices were to either hard code it in the world generator (this is how the Terra Diem tower is built), or use in-game editing tools. The former is much slower to do initially, and the latter is much slower if I want to do repeated experiments.

To speed up the latter, I spent some time to add more editing tools to the game. Specifically, I could mass edit regions of space by specifying a volume and then adding, deleting, or replacing material en masse. However, creating the volume was tedious (using keyboard controls only), and there still were annoyances with placement as a volume hovering in space is hard to know where it really is.

I was working out ideas on graph paper first.

The last “ah ha” moment was that due to all of the above, I was working out algorithms almost entirely with pencil and paper on graph paper (much like the diagrams below). I’d been doing this for a long time (for example, that is how the tree algorithm came to be). However, simulating an animation algorithm on graph paper is so much more tedious (and wasteful of paper, erasers, or both).

My wonderful wife bought me a reMarkable 2 tablet for Christmas, which changed my life in this regard. I continue to use it to quickly sketch out things. The multiple graph paper settings (including perspective and isometric graph paper!), drawing layers, and editing tools make working on “paper” amazing. Plus it all syncs to the cloud.

In any case, the big realization was that pretty much all of the algorithms in the game translated almost directly between 2D and 3D. This was true both of the solutions, and more importantly, the problems.

That was it. I decided to make a 2D version of the game.

Making the 2D game

Despite all the reasons above, making a 2D version of the engine and game was not an easy decision. I had spent a long time building the 3D version of the engine (years of calendar time, and certainly many months of actual development time). Certainly I didn’t have to start over from scratch, but there was still a lot to do as the engine only had 3D graphic support and the game itself was fully 3D-centric. Rewriting these two things could still be time consuming. I decided to timebox myself to a week, and reassess then.

2D rendering

The first requirement was I needed to render in 2D. There were a bunch of readily available options:

• Use SDL: The Game Bits engine which backs Terra Diem already uses the SDL 2.0 library for platform abstraction (input devices and window management). While SDL does not provide a 3D API, it does provide a fairly robust API for doing basic 2D rendering. However, to this point I largely have hid SDL dependencies in the engine, as an implementation detail. I wasn’t sure I wanted to rely so heavily on it.

• Use ImGUI: Game Bits also uses the popular (and amazing) Dear ImGUI for all its UI. While being UI-centric, it actually does have extensive controls for rendering text and images. It is super flexible and fast to iterate on in code. I probably wouldn’t have even considered this as an option, except a while back a coworker had mentioned that they did this for their own game. However, using ImGUI would still require some sort of wrapping to use nicely as a 2D game renderer.

• Build it in 3D: I had already written a Game Bits backend for ImGUI to render its 2D scene in 3D. This was a trivial amount of code and graphics shaders to do for ImGUI, and I reasoned it would be trivial for a 2D Terra Diem as well. Another advantage was that I could reuse a lot of infrastructure from the 3D game (resource management, texture loading, etc.)

I decided to do the latter, and I actually had a simple 2D rendering engine working in less than a day with zooming and panning support.

2D game representation

There were several important requirements for the game itself:

• Structurally similar to 3D: In order for an algorithm to pass from 2D to 3D, it was important that the high level structure was the same. For instance, I needed to have a world built out of chunks containing blocks (see Terrain for what this is in 3D). Ideally, when moving back to 3D, it could be a pretty direct translation adding in the third coordinate and making only local changes to deal with representation differences.

• Simple to work with: Really, this means do no optimizations. Represent everything as simply as possible. In the 2D version of the game, a single block takes easily 50x more memory than the the same block in 3D. This is ok, because I have 10,000x less blocks to deal with. I also added lots of convenience methods to store copies and iterate over the entire world instead of optimizing to limit which blocks or chunks I needed to store or look at. These could be replaced with more optimal storage, lookup strategies, and iteration in the 3D game without affecting the underlying algorithm.

• Fully configurable: Parameterize as many things as possible (like chunk size and block material volume). This allows me to simply things when working out a problem, and then validate it works well with the intended final values. Flow amount, for instance may be highly dependent on how material can be stored in each block.

Better tooling

The 2D perspective makes editing and inspecting much simpler. As a screen / monitor is a 2D interface, everything is direct. For instance, selecting on a block maps directly to the screen coordinate in 2D, whereas in 3D it requires shooting a ray through 3D mesh to see what it hits. Edit volumes are unambiguous and trivial, as you can just drag out an edit box with the mouse (no requirement for keyboard controls – although I have those too).

Also, because the world structure is so simple, I could trivially support serialization which enabled nice features like save/load, and even recording the entire state of the world for every simulation frame with DVR-style controls for going back and forward through recorded history.

I implemented serialization using FlatBuffers in about 100 lines of code (about 50 to save and 50 to load). To give an idea of how simple the world is, this is the FlatBuffer description of the world:

namespace td2d;

struct IVec2 {
  x: int32;
  y: int32;
}

struct BlockAmount {
  material: uint16;
  amount: int16;
}

table Block {
  solid: uint16;
  fill: uint16;
  solid_mask: uint8;
  amounts: [BlockAmount];
}

table Chunk {
  blocks: [Block];
}

table World {
  size: IVec2 (required);
  chunk_size: uint16;
  chunks: [Chunk];
}

The algorithm

Once the 2D engine and game was up and running, I went to work porting the 3D version of the algorithm to 2D. The pseudo-code version of the initial algorithm is as follows:

// Coordinates go from (0, 0) in the bottom left to 
// (max_x, max_y) in the top right.

iterate chunk_y from 0 to max_chunk_y
  iterate chunk_x from 0 to max_chunk_x
    iterate block_y from 0 to chunk_size - 1
      iterate block_x from 0 to chunk_size - 1
        x = chunk_x * chunk_size + block_x
        y = chunk_y * chunk_size + block_y
        move material from (x, y) to (x, y-1) if there is room
        move material from (x, y) to (x-1, y) up to piling difference
        move material from (x, y) to (x+1, y) up to piling difference

There are a couple of key properties to this algorithm:

1. Material only flows from a higher elevation to a lower elevation. This ensures that the algorithm is stable. In actual fluid dynamics, this isn’t how things work at all – but that isn’t what I was going after. As a result, this is a highly dampened simulation and doesn’t produce second order effects like waves or turbulence of any kind.

2. The simulation modifies the state of the world as it runs. What this means is that material that moves from block (0,0) to block (1,0) may then move again when block (1,0) is evaluated next. The reverse is not true. If material moves from block (1,0) to block (0,0) then that’s it. Block (0,0) was already evaluated, so it doesn’t move again. This makes the flow asymmetric with material tending to flow more to the right than the left.

A final note, is that in the actual code there are some basic optimizations, as I only iterate over blocks that are tagged for simulation. This is entirely unnecessary in 2D as the world is so small, but makes mapping back to 3D more accurate as this also affects how the simulation runs. Here is a graphical representation of the algorithm over a couple simulation frames.

• For the purposes of illustration a “full” block has 8 units of material. This example also has a piling amount of zero (like a liquid) to make visualizing it easier.
• Blue outlined blocks are the ones marked for simulation at the start of the frame. Any blocks changed during a frame are marked for simulation in the subsequent frame.
• The red outlined block is the block currently being evaluated.
• Red numbers indicate the amount of material that will flow out from the block. Green numbers are the corresponding amount flowing in. Note that these are done iteratively (down then left then right), although that is not broken out in the diagram to keep it small.
• The final result for a frame (and start of the next frame that the player sees), is highlighted in light blue.

For the most part, this super simplistic asymmetric algorithm works surprisingly well in 2D and in 3D (the only difference in 2D is that it does the horizontal flow in the four cardinal directions instead of just right and left). However, there was one very noticable graphical glitch that occured due to the asymmetric nature of the algorithm. When material flowed over a cliff to the right, it would leave a hole:

I spent the remainder of my time experimenting with different approaches to resolve this glitch:

1. Flow material for all the blocks down first, then do the horizontal flow. This solved the discontinuity, but had some additional unfortunate artifacts.
2. Flow material based entirely based on the prior frame. In this iteration, I also considered both right and left neighbors simultaneously to make sure material flows evenly between the two sides. This ensures perfect symmetry in the simulation. Unexpectedly, this was the absolute worst algorithm visually.
3. Combine algorithm 1 & 2: Flow down first, then flow right and left considering the prior (post flow down) state. This was better, but still pretty terrible.

The differences and artifacts are easier to see animated:

What’s next

Since the video recording earlier this week, I haven’t had any time to actually work on the game (what time I had went into writing this blog post). I do have one last simple change I’m going to try, and then I am moving on to water rendering in 3D. This is really a 3D only issue, as in 2D you can’t see through one block into another.

At this point, I am going to punt infinite and running water problems to much later (water will simulate like lava), as it is time to move on to other fundamental systems like saving/loading world state, an actual “player” that can move through the world, and basic inventory and gameplay.