Immutable Data Structures

All game related data structures and algorithms in Athena Crisis are "headless" and can run on the client, server, or during build time. Map and game state are represented using immutable persistent data structures. Immutable means that instead of directly changing the game state, any action like moving or attacking a unit returns a new game state object. Persistent refers to reusing all data that doesn't change between two game states. These two concepts together make it easy to keep many game states around, make it fast to check whether changes happened between two states, and is memory efficient.

Imagine a basic game state with a map that is three fields wide and one field high. The game state can be represented with an array, where each field either has a unit or not:

const state = [unit, null, null];

Many games use an imperative model. When you want to move the unit from one position to another, you might make a change like this:

state[2] = state[0];
state[0] = null;

This directly modifies the existing state object. It now becomes hard to know what the game state was before, which can cause problems when other operations still think they are operating on a previous version of the game state. It also makes it harder to compare what changed with a state transition.

Let's look at the same example with an immutable model:

const state = [unit, null, null];
const newState = [null, null, unit];

At the core, instead of mutating the game state, we create a completely new game state object each time with the immutable model. Note that the unit, assuming its an instance of a Unit class, did not change. However, when you are moving a unit in Athena Crisis, it has to be marked as "moved". In the imperative version, it might look like this:

const state = [unit, null, null];
const unit = state[0];
unit.moved = true;
state[2] = unit;
state[0] = null;

The immutable version could look something like this:

class Unit {
  move() {
    return this.copy({
      moved: true,
    });
  }
}
 
const state = [unit, null, null];
const newState = [null, null, unit.move()];

The imperative version is faster and memory efficient. However, if another part of the codebase is holding on to the unit, it might not know that the unit has moved, or it might not expect the unit object to be mutated. This can lead to hard to find bugs, especially when there are many variables and state changes involved. The immutable version is slower and uses more memory, especially when many things change at once. The downsides can be limited by using persistent data structures, which re-use as much data as possible between two game states.

In a real world example, you might be storing unit positions in a Map data structure which is expensive to copy each time a change is made. The immutable Map data structure from Immutable.js, which we released as a standalone package called @nkzw/immutable-map, makes use of structural sharing to make copying cheap. It works similar to git commits, where only the changes are stored and the rest is shared between two game states. Due to this, the immutable model can be more memory efficient and sometimes even faster than the imperative model.

These advantages make immutable state models ideal for turn-based strategy games like Athena Crisis.