Fraculation

developers blog

An approach to writing tests in a highly adaptable way for grid-based games

Date: 25 Apr 2024 Time to read: 8m

Outline

Overview
Map Layout string
- Goal
- Implementation
Command pattern
- Command Goal
- Command Implementation
Tying it all together
- The TDD Workflow
- When not to use
Conclusion

Overview

I've built a couple grid-based games during game jams at this point. They are a delight to work with due to the simplicity of the domain. Because every object has an exact location, interactions between objects can be precisely defined. And the state of the game can be easily represented and/or stored in something akin to a 2D or 3D array. Examples of what I'd call "grid-based games" are: Chess, Connect 4, Tetris, Sokoban, Baba Is You, Into the Breach, Tiny Epic Tactics, or the two games I've made: Disconnect, a riff on connect 4 and Gobbies Stole my Ruins, a puzzle dungeon crawler .

The purpose of this blog post is to keep track of my own thoughts and share them with you. I'd like to turn this approach into a more reusable package and potentially release it as FOSS, so I welcome any feedback on potential footguns I could be walking into here.

First, we'll walk through the two greatest 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" and my guidlines for games which will benefit the most from this approach.

Map Layout String

The map layout string is designed to be a readable representation of the geometry of a whole map in one string. Ideally this will make our tests easy to read and simple to maintain.

Map Goal

We want to map every character of the string into a single tile in the 3D grid. We can lay them out in horizontal slices then stack up the horizontal slices to get a full 3D world: similar to MRI data or the output of a 3D printing slicer. The left-most 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 and what the world generated by the string would look like:

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

We need two utilities to use this string format. A function to build a world from the string and another to assert a world against a given world string. For many of the movement-related tests is the only assertion we need! 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();
  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 failure messages would look like:

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 it scales well when we add multiple moving entities into the mix.

Map Implementation

The map layout string can be build up from a few components. A parser to parse the string into a 3D array, an axis transformer, and a lookup table of game entity factories.

Parser

The parser is relatively simple, consisting of a few successive Split commands:

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 in this layout:

abc def gih
jkl mno pqr
stu vwx yz0

Its indexed by line first, then by each layer in the line, then by the character order inside each segment. So we'd need something like charArray[0][2][1] . This definitely isn't in x, y, z order. Ideally we'd access it at the (x, y, z) position of (1, 2, 2) .

Axis transformer

So we'd like to get an array we can access with Unity's axis layout, in (x, y, z) order. We could use unity's Matrix4x4 to do this for us, once we found the correct combination of flips and rotations. I decided to home bake a utility specifically for re-ordering and flipping axises. 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 outputCoordinate in AllCoordinatesInside(newLayoutSize)) {
    var inputCoordinate = transformation.InverseTransform(outputCoordinate);

    var inputTile = input[inputCoordinate];
    output[outputCoordinate] = inputTile;
  }

  return output;
}

For this specific layout we want our DimensionalityTransform to look something like this: [-Z][+Y][+X] . This will end up with a layout where:

Z points up (lines are ordered from top down, so we need to invert)
X points left (char arrays are already ordered left to right)
Y points left across the layers

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

Lookup table

From here, we need a way to map a single character to a way to create something at that location. In C#, we can use the Func<> type for this. So we'll build something like a Dictionary<char, Func<Vector3Int, IEntity>> , and invoke the Func pointed to by each character at each position. With code:

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

  foreach (Vector3Int coordinate in AllCoordinatesInside(xyzLayout.Size)) {
    char atLocation = xyzLayout[coordinate];

    if (tileFactories.TryGetValue(atLocation, out var factoryFunction)){
      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 get our world builder working! To get a world assertion working from here, we can supplement the factory functions. For my purposes, I use a hard type-check: a P verifies there is an entity at that position of exact type Player. One can imagine attaching more complex assertions to those characters, in the same way that we attach factory functions to them. For example asserting based on a string tag match or the presence of a specific interface.

This gives us all the tools we need to build our world from a layout string, and assert against it! This approach can be adapated into the test harness for any kind of grid-based game. We only need a couple things from our world implementation to attach this harness to it:

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

In theory we could even use this with GameObjects as long as they were at grid-aligned positions!

Command Pattern

The other useful components of these tests are the command pattern and immutable objects. To some degree this is optional, but I believe that these approaches fit together very well in practice. The command pattern helps manage the entry-points into the system, so 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 immutable data structures. But it forces many good practices which pay of when building something complex.

I'll demonstrate some of these advantages via examples as best I can; focusing on the command pattern. Immutability is less relevant to the tests themselves and more about how the code under test is arranged.

We see usage of the command pattern via the helper struct MovementCommands which contains a set of commonly used commands. For example, mv.jump == DungeonCommandFactory.JumpEntity(id) == new JumpCommand(id) . We see evidence of immutability in the repeated use of World = World, keeping the World field up-to-date with all commands.

Command Goal

In our tests, 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 instead of referencing any methods directly on 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(playerId);
  player.MoveForward(1);
  /* ... assert movement occurred ... */
}

Note that the tests which rely on Commands enjoy a greater separation of concerns. The test case code itself depends on shared types: World, EntityId, and ICommand. As well as components of the test harness via CommandFactory. This is an indicator that this test case may be much more maintainable.

Command Implementation

To set up our command pattern we will start with a foundation of various interfaces. The command implementation itself becomes much clearer after we define the interfaces it has to work with.

The Interfaces

We'll have several interfaces. Most of these describe how the command's implementation interacts with the world, and finally the interface which the command itself must conform to:

interface IWorldWriter {
  IEntity GetEntity(EntityId id);
  void SetEntity(EntityId id, IEntity newEntity);
}
interface IPathingWorld {
  bool IsBlocked(Vector3Int position);
}
interface IHavePosition {
  Vector3Int GetPosition();
  IEntity WithPosition(Vector3Int newPosition);
}
interface IEntity {}

interface ICommand {
  void Execute(IWorldWriter writer);
}

The Implementation

Now we can implement our command. The MoveForwardCommand should hold 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");

    Vector3Int newPosition = MoveForwardFrom(entityWithPosition.GetPosition(), worldWriter.pathingData);

    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 ... */
  }
}

Really anything could be inside this command, depending on the game's specific implementation. Importantly it can be constructed from only very basic types: an int and a custom EntityId type. All of the commands should be constructed from simple serializable types such as this.

Aside - benefits of Commands in the game

Lets have a brief look at what commands can do in a game's implementation. In this example we use commands to represent user input directly rather than making method calls inside the input manager itself! This allowed us to trivially implement input queuing:

class InputManager: MonoBehavior{
  private World _world;          // set on Start
  private EntityId _playerId;    // set after world initialization
  private KeyCode _dashKey = KeyCode.Shift;
  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
      };
    }
    return null;
  }
}

One can imagine a many options unlocked by serializable 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:

[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();
    EntityId playerId = GetSingle<Player>();
    var mv = new MovementCommands(playerId);
    AssertPosition(playerId, 1, 1, 0, FacingDirection.North);
    
    // 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 because the test has no direct dependencies on implementation details
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.

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 ---
");
}

We're adding attacking! And enemies killing us if we don't kill it first. This test will not compile right away, first we need to 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 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.

When not to use

This approach may only work well for specific types of games. The article is about grid-based games for a reason: typically, grid games are totally predictable or can be made to be deterministic. These are the general requirements I imaging 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
Grid-aligned
- Everything under test must align to 2D or 3D grid positions, at creation time and at assertion time
- This is a looser requirement. we can always round positions to the nearest grid position, but could make our tests flaky.

Consider how we could make Chess fit into this framework. It is an ideal candidate! Every game piece occupies a grid square. Every change to the game state is a movement of one piece from one grid square to the next grid square. The chess community has already started using a standard format for commands, too: Algebraic notation (chess) (For example, Be5 bishop moves to e5). We could start writing tests representing the whole board and a series of moves to test a chess rules engine right away!

What if we wanted to test something like Minecraft? Minecraft's blocks are all necessarily 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. 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 on only the blocks if we would like to ignore the edge cases! We must consider if the test harness will save us enough time to make up for the exceptions to the rule.

For a game like Overwatch this testing approach is completely untenable. Every movement is both tiny in distance -and- potentially relevant, there's no grid, and everything is highly reliant on potentially unpredictable physics. It may be possible to build a harness that uses the command pattern to represent player moves at best.

Conclusion

In the future, I hope to build a shareable library around these concepts! I'll make another blog post at that point. Hopefully after I've battle-tested it in a few more game jams. Thanks for reading, if you have any feedback I'd love to hear it!

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