Fraculation

developers blog

A general approach to writing highly adaptable tests for grid-based games

Date: 25 Apr 2024 Time to read: 10m

Outline

Overview
Map Layout
- Goal
- Implementation
Command pattern
- Goal
- Implementation
Tying it all together (Real world Example)
- The TDD Workflow
- When to avoid
Conclusion

Overview

I want to share a game development technique I've repeated across two game jams (so far), and have found very useful when working on complex game logic. This technique drivings game logic by writing tests first in a way specialized for "grid-based" games. "grid-based" games include for example: Chess, Connect 4, Tetris, Sokoban, Baba Is You, Into the Breach, Tiny Epic Tactics, or the two games I've made with this approach: Disconnect, a riff on connect 4 and Gobbies Stole my Ruins, a puzzle dungeon crawler .

The logic of grid-based games is a perfect candiate for Test Driven Development: every entity has an exact location and interactions between entities are precisely defined. Most importantly, the state of the game is easily represented in a 2D or 3D array. With a concise way to create an array from a layout string we can build and assert against the entire world in every test.

First, we'll walk through the two components of this testing paradigm: a highly readable layout string and a command pattern to interact with the game state. Then I'll close out with a real-world test case from "Gobbies Stole my Ruins" along with guidlines for games which will benefit the most from this approach.

Map Layout String

The map layout string should be a readable representation of a whole game map in one string. Our goal will be to look at one of these strings and very quickly understand what the 2D or 3D map would look like. Ideally this makes our tests easy to read and simple to maintain.

Map Goal

We will map every character of a string into a single tile in the 3D grid. I chose to lay them out in horizontal slices and stack up the horizontal slices to get a full 3D world: imagine MRI data or a 3D printing slicer to visualize this. The left-most rectangular slice is the bottom slice and the right-most is the top slice. X is a block, - is empty space, and P is the player character. Here's an example of a string layout and the transformation it takes to become a 3D world.

XXX XXX ---
XXX --- ---
XXX -P- ---

Transforming a layered string into 3D space

To use this format in our tests we'll whip up two utility functions . CreateWorld builds a game world from the layout string. AssertWorldMatches asserts the world against a given layout string. For many of the movement-related tests this is the only assertion we need! As a demonstration of how the functions are used, and how useful they could be, compare the following examples. Which do you find easier to reason about?

[Test]
void TestPlayerMovesForward_ThenIsBlocked_WithLayout() {
  var map = @"
XXX -X-
XXX ---
XXX -P-
";
  World world = CreateWorld(map);
  /* ... move player forward ... */
  AssertWorldMatches(world, @"
XXX -X-
XXX -P-
XXX ---
");
  /* ... move player forward again ... */
  AssertWorldMatches(world, @"
XXX -X-
XXX -P-
XXX ---
");
}

[Test]
void TestPlayerMovesForward_ThenIsBlocked_WithoutLayout() {
  var world = CreateWorld(new Vector3Int(3, 2, 3));
  world.PlaceFloor();
  world.PlaceWall(new Vector3Int(1, 1, 2));
  world.PlacePlayer(new Vector3Int(1, 1, 0));
  /* ... move player forward ... */
  AssertPlayerPosition(world, new Vector3Int(1, 1, 1));
  /* ... move player forward again ... */
  AssertPlayerPosition(world, new Vector3Int(1, 1, 1));
}

If you're still not convinced, consider what the test fails with:

Expected:
XXX -X-
XXX -P-
XXX ---

Actual:
XXX -X-
XXX ---
XXX -P-

Versus:

Expected player at (1, 1, 1), instead found (1, 1, 0)

The difference here isn't extreme but will scale well when multiple moving entities are asserted at once.

Map Implementation

The map layout string can be built by stringing together a few components. First we must parse the string into a 3D array. From there we transform the axises of this 3D array to match the axis system of the world we are generating. To finish building the world, we need a way to turn a single character into an entity at a given position inside the game world. To this end we'll use a lookup dictionary of game entity factories keyed by char.

Parser

The parser is a series of successive string.Split operations, splitting by newline first, then the space separating the y-layers from each other, and finally splitting the string into its individual character components.

char[][][] ParseLayoutString(string layoutString){
  string[]   byLine = layoutString.Split("\n");
  string[][] byLineThenLayer = byLine
    .Select(line => 
      line.Split(" ")
    ).ToArray();
  
  char[][][] byLineThenLayerThenChar = byLineThenLayer
    .Select(line => 
      line.Select(lineLayer => 
        lineLayer.ToCharArray()
      ).ToArray();
    ).ToArray();
  
  return byLineThenLayerThenChar;
}

Done! Before we move on, consider the indexes we need to access the i character in this layout:

abc def gih
jkl mno pqr
stu vwx yz0

    ^
    N
< W x E >
    S
    v

Its indexed by line first, then by each layer in the line, then by the character order inside each segment. Therefore, charArray[0][2][1] == 'i'. This definitely isn't in x, y, z order according to the compass in the code block. Ideally we'd access i at the (x, y, z) position of (1, 2, 2).

Axis transformer

So we need to get our characters arranged in Unity's axis layout,in (x, y, z) order. We could use Unity's Matrix4x4 to do this, but I decided to home bake a utility specifically for re-ordering and flipping axises. Either way will work. This is roughly how we'll get the layout we need:

Array3D<char> TransformLayout(Array3D<char> input) {
  DimensionalityTransform transformation = GetDefaultCoordinateTransform();

  var newLayoutSize = transformation.Transform(input.GetSize());
  var output = new Array3D<char>(size: newLayoutSize);

  foreach (var inputCoordinate in AllCoordinatesInside(input.GetSize())) {
    var inputTile = input[inputCoordinate];

    var outputCoordinate = transformation.Transform(inputCoordinate);
    output[outputCoordinate] = inputTile;
  }

  return output;
}

For this layout we want this DimensionalityTransform: [-Z][+Y][+X] . This will end up with a layout where:

Z points upwards in the code block
- the first index selects Lines, so lines are mapped to the Z axis
- because lines are ordered from top down in text, so we need to invert to make sure Z increases up the page
Y points right across the layers (Layer Y+1 will be to the right of layer Y)
- the second index selects divisions between layers, so separate layers are mapped to the Y axis
- the layers are ordered left-to-right, and we want Y to increase to the right, so we do not need to invert
X points right inside contiguous character sequences
- the third index selects an individual character inside a line + layer, so the character index maps to the x axis
- char arrays are already ordered left to right, and we want X to increase to the right, so we do not need to invert

Laid out on a 2x2x2 grid, these are the Z, X, and Y coordinate values at every point:

World Building

From here, we need to take a single character and create one entity at that character's location in the world. In C#, we use a simple Func<> as our factory function, and bake in the assumption that every tile will contain at most one entity. So a Dictionary<char, Func<Vector3Int, IEntity>> maps each character to a factory function, and we invoke the factory based on the character found at each position in the entire map. With code:

World BuildWorld(
  Array3D<char> xyzLayout,
  Dictionary<char, Func<Vector3Int, IEntity>> tileFactories) 
{
  World world = new World(xyzLayout.GetSize());

  foreach (Vector3Int coordinate in AllCoordinatesInside(xyzLayout.GetSize()))
  {
    char atLocation = xyzLayout[coordinate];
    Func<Vector3Int, IEntity> factoryFunction = tileFactories[atLocation];

    IEntity createdEntity = factoryFunction(coordinate);
    world = world.AddEntity(createdEntity);
  }

  return world;
}

Dictionary<char, Func<Vector3Int, IEntity>> GetDefaultFactories()
{
  return new Dictionary<char, Func<Vector3Int, IEntity>>()
  {
    {'X', CreateWall   },
    {'P', CreatePlayer },
  }

}
IEntity CreatePlayer(Vector3Int location) { /* ... */ }
IEntity CreateWall  (Vector3Int location) { /* ... */ }

We can chain these 3 components together to create our world builder. To create the world assertion function we can supplement the factory functions. For my purposes I use a hard type-check for EX: a P character will verify there is an entity at that position of exact type Player. The assertion function is similar to the world building function, but in reverse. Instead of building the world from a string I build a string from the world based on type-checking entities at each position. Then I assert the built string is equal to the expected string. This isn't the only way to build the assertion function, but building up the world string allows us to output that actual string as part of the test assertion failure message.

As the implementation changes we can attach more complex assertions to those characters in the same way that we attach factory functions to them. It would be trivial to add assertion based on a string tag or the presence of a specific interface implementation. In Gobbies Stole My Ruins, all Pickup items are represented by the same Pickup class which contains the actual item to be picked up. So when we see a Pickup type in a cell, instead of asserting against the Pickup type we actually assert against the type of Pickup.containedItem. In the future we could change this implementation detail again without modifying the tests themselves, only the test harness assertions.

This gives us all the tools we need to build our world from a layout string and assert against it using the same format. To use this approach these are the only functions we need from our game world logic implementation:

Create an entity at a specific grid location, when building the world
Get entities at a specific grid location, when asserting against the world.

Any implementation of a game which supports those functions will attach to these tests. In theory we could even use this with GameObjects as long as they were kept at grid-aligned positions!

Command Pattern

Another useful component of these tests is the command pattern with immutable objects. To some degree this is optional but I believe that these approaches fit together very well in practice. The command pattern manages the entry-points into the system; games with smaller interfaces wouldn't need to go this far. The story is similar for usage of immutability. There is significant developement and performance overhead to implementing and using immutable data structures. But immutability forces many good practices which pay off when building something complex.

I'll demonstrate some of these advantages via examples as best I can. I'll focus on the command pattern since immutability is less relevant to the tests themselves and more about the code under test.

Command Goal

The command pattern will isolate our tests from most changes in our game logic. We would like to reference only a Factory and the ICommand interface in place of references to any part of the game entities. I'll start with a comparitive example:

[Test]
void TestPlayerMovesForward_WithCommands() {
  World world = /* ... create world ... */;
  EntityId playerId = world.GetSingleAt(new Vector3Int(1, 1, 0));
  ICommand moveForwardCommand = CommandFactory.MoveForward(playerId, 1);
  world = world.ApplyCommand(moveForwardCommand);
  /* ... assert movement occurred ... */
}

[Test]
void TestPlayerMovesForward_WithoutCommands() {
  World world = /* ... create world ... */;
  EntityId playerId = world.GetSingleAt(new Vector3Int(1, 1, 0));
  Player player = world.GetEntity<Player>(playerId);
  player.MoveForward(1);
  /* ... assert movement occurred ... */
}

Note that the tests which rely on Commands have no references to Player or even a IMove interface. The test case depends on shared types: World, EntityId, and ICommand. As well as components of the test harness via CommandFactory. The command-based test is isolated from the game implementation, indicating that this test case is more maintainable and less likely to require changes when the implementation changes.

Command Implementation

To set up our command pattern we will start with a foundation of various interfaces. The implementation itself becomes much clearer after we define the interfaces we're working with.

Interfaces

The interfaces describe how the command's implementation interacts with the world and how to execute any command on a world:

interface IWorldWriter {
  // The command makes changes to the world
  void SetEntity(EntityId id, IEntity newEntity);

  // The command needs data about the world
  IEntity GetEntity(EntityId id);
  IPathingWorld GetPathingData();
}
interface IPathingWorld {
  bool IsBlocked(Vector3Int position);
}
interface IHavePosition {
  Vector3Int GetPosition();
  // The command creates modified immutable copies of entities
  IEntity WithPosition(Vector3Int newPosition);
}
interface IEntity {}

// The world needs a simple interface to execute the command
interface ICommand {
  void Execute(IWorldWriter writer);
}

Interface Implementation

Now we can implement our command. The MoveForwardCommand holds all the logic related to moving and being blocked by walls.

class MoveForwardCommand : ICommand {
  public int distance;
  public EntityId targetEntityId;
  public void Execute(IWorldWriter worldWriter) {
    IEntity targetEntity = worldWriter.GetEntity(targetEntityId);
    IHavePosition entityWithPosition = targetEntity as IHavePosition;
    if (entityWithPosition == null) throw new InvalidOperationException("Attempted to move an entity which does not have a position");

    IPathingWorld pathData = worldWriter.GetPathingData();
    Vector3Int currentPosition = entityWithPosition.GetPosition();

    Vector3Int newPosition = MoveForwardFrom(currentPosition, pathData);

    IEntity newEntity = entityWithPosition.WithPosition(newPosition);
    worldWriter.SetEntity(targetEntityId, newEntity);
  }
  private Vector3Int MoveForwardFrom(Vector3Int position, IPathingWorld pathing) {
    /* ... implement moving forward, blocked by walls, this.distance steps ... */
  }
}

Anything could be inside this command depending on the game's specific implementation. Importantly an instance is constructed from only very basic types: an int and a custom EntityId type. All of the commands should be constructed from simple data-only serializable types such as this in order to reap the various benefits that come with using commands.

Aside - benefits of Commands in the game

Lets have a brief look at what commands do for the game outside of tests. In this example we use commands to represent user input rather than making method calls inside the input manager itself. This allowed us to trivially implement input queuing! By queuing the commands and waiting for the previous command to complete before executing the next command, the game never misses an input from the player.

class InputManager: MonoBehavior{
  private World _world;          // set on Start
  private EntityId _playerId;    // set after world initialization
  private KeyCode _dashKey = KeyCode.Shift;
  private KeyCode _stepKey = KeyCode.W;
  private Queue<ICommand> _queuedCommands;
  void Update() {
    var inputCommand = GetInputCommand();
    if (inputCommand != null) {
      _queuedCommands.Enqueue(inputCommand);
    }

    if (_world.IsUpdating && _queuedCommands.Count > 0){
      ICommand nextCommand = _queuedCommands.Dequeue();
      _world = _world.ApplyCommand(nextCommand);
    }
  }

  ICommand? GetInputCommand() {
    if (Input.KeyDown(this._dashKey)) {
      return new MoveForwardCommand() {
        distance = 2,
        targetEntityId = this._playerId
      };
    }
    if (Input.KeyDown(this._stepKey)) {
      return new MoveForwardCommand() {
        distance = 1,
        targetEntityId = this._playerId
      };
    }
    return null;
  }
}

Many features are unlocked by serialing commands, including:

Input queueing
Passing commands over the network
Saving commands in a local file
Replaying a recorded series of commands to acheive identical world state
Inspecting commands in other parts of the system with listeners. For example, triggering a sword animation after an AttackCommand listener triggered

Tying it all together

To tie together the map layout and commands, I'll use a real-world test right out of Gobbies Stole My Ruins (with added comments):

[Test]
public void WhenPlayerJumps_ThenDashesOverGap_MovesOverGap()
{
    // arrange
    var map = @"
XXX XXX ---
XXX --- ---
XXX -P- ---
";
    CreateWorld(map);
    // places the dash and jump items into the players inventory
    EnableDash();
    EnableJump();
    // search the world for a singleton entity of type Player
    EntityId playerId = GetSingle<Player>();
    // construct a set of commonly used commands bound to the player id
    var mv = new MovementCommands(playerId);
    
    // act + assert
    World = World
        .ApplyCommandsAndTick(mv.jump);
    AssertWorldMatches(@"
XXX XXX ---
XXX --- ---
XXX --- -P-
");
    
    World = World
        .ApplyCommandsAndTick(mv.dash);
    AssertWorldMatches(@"
XXX XXX -P-
XXX --- ---
XXX --- ---
");
}

So this is what we get by combining all these techniques together. In my opinion this is everything we need it to be:

Highly maintainable. The test has no direct dependencies on implementation details
- except for the GetSingle<Player> function call. This is allowed for convenience, and is isolated well enough that it could be replaced en masse via a regex replacement.
Easy to read thanks to the map layout strings

The TDD Workflow

Lets walk through what a typical update to the application logic would look like from a TDD perspective. We will be adding combat to the game! The player can attack to kill the enemy directly in front of them. If the player doesn't attack, then the enemy will instead attack and kill the player.

First, we write the test:


[Test]
public void WhenPlayerAttacks_KillsEnemy()
{
    // arrange
    var map = @"
XXX -E-
XXX -P-
";
    CreateWorld(map);
    EntityId playerId = GetSingle<Player>();
    var mv = new MovementCommands(playerId);
    
    // act + assert
    World = World
        .ApplyCommandsAndTick(mv.attackForward);
    AssertWorldMatches(@"
XXX ---
XXX -P-
");
}

[Test]
public void WhenPlayerIsHit_Dies()
{
    // arrange
    var map = @"
XXX -E-
XXX -P-
";
    CreateWorld(map);
    EntityId playerId = GetSingle<Player>();
    var mv = new MovementCommands(playerId);
    
    // act + assert
    World = World
        .ApplyCommandsAndTick(mv.noop);
    AssertWorldMatches(@"
XXX -E-
XXX ---
");
}

This test will not compile right away since mv.attackForward is not implemented yet. So we add an attacking command factory:

public static class CommandFactory {
  /* ... */
  public static ICommand AttackForward(EntityId id) {
    return NoopCommand();
  }
}
public class MovementCommands {
  /* ... */
  public ICommand attackForward;
  public MovementCommands(EntityId entityId){
    /* ... */
    attackForward = CommandFactory.AttackForward(entityId);
  }
}

At this point, our test is complete: compiling, executing, and failing. The implementation work will involve creating the AttackForwardCommand implementation, and implementing enemies attacking adjacent players. In the course of the implementation we'll replace the contents of the CommandFactory.AttackForward function as well.

I used this workflow extensively when developing Gobbies Stole My Ruins. My teammate would tell me "wouldn't it be neat if dash allowed you to move over open air, instead of stopping at the first ledge?" . Then I would immediately write the test. If I was working on something already, I would mark the test with a comment, ex:

// [Test] TODO Ignored: Until dash off ledge

Now I have that feature documented and can switch back to working on what I was before. Later on, I will look through all the ignored test cases, and pick one to uncomment and begin implementing. Sometimes this is linked to our issues board, sometimes not.

The important part is that I can document the feature request in a well-defined way pretty much immediately and without much interruption in flow. And implementing features is entirely contained in the code editor with rigidly defined requirements already set up. I find this makes it very easy to stay focused.

When to avoid

This approach will only work well for specific types of games. The article is about grid-based games for a reason, they fit the bill perfectly. These are the general requirements I imagine a game must have in order to fit into this test harness:

Deterministic
- The game must run the exact same way every time from the same starting conditions
- If randomness is used it must be based on a random seed such that supplying the same seed results in the same sequence of events
- In general this would apply to allowing game logic to be tested at all, regardless of the testing framework
Grid-aligned
- Everything under test must align to 2D or 3D grid positions, at creation time and at assertion time
- All game logic decisions should occur when entities are snapped to their grid positions
  - Without this requirement, it will eventually become necessary to create or assert against entities which are not grid-aligned.
- This is a looser requirement. We can always round positions to the nearest grid position but this could make our tests flaky.

Consider how we could make Chess fit into this framework. It is an ideal candidate since every game piece occupies a grid square. Every change to the game state is a movement of one piece from one grid square to another grid square. The chess community uses a standard format for commands, too: Algebraic notation (chess) (For example, Be5 bishop moves to e5). We could start writing tests using this command format before we implemented any part of the chess engine at all!

What if we wanted to test something like Minecraft? Minecraft's blocks are all Grid-aligned but the player character is allowed to walk around freely. The zombies and item pickups are also allowed to float free from the grid. Certainly we can say that the player and items are "inside" a certain cube coordinate, but the game will play differently depending on where exactly they are inside that cube. Therefore we could easily test the blocks' interactions but would have trouble testing the players or mobs in the same way. Of course we could use our method to test the blocks' logic alone, but there are edge cases!

For example, Minecraft sand will turn into a free-falling entity when the block underneath it is removed. While falling a TNT blast will send it flying on a new trajectory. How would we test that? It would be possible with this method but would depend on precise timing and implementation details of the physics engine. We must consider if the test harness will save us enough time to make up for exceptions to the rule like this.

For a game like Overwatch this testing approach is completely untenable. Movement at every timestep is both tiny in distance and gameplay relevant, there's no grid, and everything is highly reliant on implementation details of the physics engine. It may be possible to build a harness that uses the command pattern to represent player moves at best. But any attempt to constrain movement and actions to a grid will be so far from typical gameplay that it would be nearly useless.

Conclusion

Thanks for reading, if you have any feedback I'd love to hear it, contact me in the upper right or open an issue on the github repository for the shared library! I am building a shareable library around these concepts, please have a look if you'd like to dig deeper. Or contribute to the project if you find it useful! See the open-source project here: link to github

Did you like it? Why don't you try also...