Brainroll Postmortem Part 4: Movement, Ropes & Undo
Brainroll Postmortem Part 4: Movement, Ropes & Undo
Brainroll is a sokoban-style puzzle game where the main mechanic is that you slide on ice. Traditionally in Sokoban games, each level is presented as a grid layout where each cell comprises either a floor or a wall. Within this grid, the floor cells serve as potential placements for boxes, while certain designated cells act as storage locations for these boxes.
The player, represented as a character or object, has the ability to move in any of the four cardinal directions: Up, Down, Left, and Right. This movement occurs within the confines of the grid and is permitted on any unobstructed floor cell. Moreover, the player can push boxes horizontally or vertically as long as the direction they wish to move the box also leads to a floor cell.
The primary objective of the game is to strategically maneuver each box onto its respective storage location. By pushing and arranging the boxes into these predefined spots, the player successfully completes the level. The challenge lies in navigating the obstacles, planning efficient movements, and avoiding getting boxes stuck in corners or against walls, ultimately requiring logical thinking and problem-solving skills to solve each level.
Brainroll introduces some mechanics that deviate from the classic Sokoban gameplay. First of all, the grid set of cells in the grid is modified by replacing traditional floor cells with two distinct terrain types: ice and snow cells.
The ice cells introduce an element of sliding movement mechanics. When the player character traverses an ice cell, they continue sliding uncontrollably in the same direction until they encounter an obstacle, such as a wall. This mechanic adds an additional layer of challenge and strategic planning, requiring players to anticipate the sliding movements while navigating the level.
Conversely, the snow cells in Brainroll adhere to the familiar Sokoban mechanics.
Furthermore, Brainroll diverges from the traditional Sokoban objective of maneuvering boxes into storage cells. Instead, Brainroll simplifies the win condition by only requiring the player to navigate the character into a specific goal within each level. However, the player still needs to move Brainroll’s version of boxes in order to reach that goal.
By modifying these fundamental rules while preserving the essence of Sokoban-like puzzle-solving, Brainroll introduces a unique blend of strategic thinking, spatial reasoning, and adaptability, challenging players to navigate through sliding ice cells and traditional snow cells to achieve their goal points
Movement implementation
Since Brainroll is a deterministic puzzle game, the most of the game’s code is related to the movement rules of the game and thats why I thought that might be the most interesting to dive into. A very important decision of Brainrolls entire system was to make it deterministic, Wikipedia has a very nice explanation of what this means in computer science:
A deterministic model of computation, for example a deterministic Turing machine, is a model of computation such that the successive states of the machine and the operations to be performed are completely determined by the preceding state.
This means is that with a given world state within Brainroll, a move will always yield the same result. This might seem very obvious for a puzzle game but there are puzzle games that has involved timing or physics based puzzles which I do not consider being deterministic, reason is because in order to get a deterministic result from a physics simulation you would need the exact same input at the exact same given time which is very hard if not impossible to reproduce.
In order to achieve this with Brainroll I decided to separate simulation with the game’s logic. I thought of it as separating what the player sees visually and what the player does physically through inputs. This can be seen by looking how my world is structured.
struct world
{
entity *Entities;
u32 EntityCount;
entity_handle *Static;
entity_handle *Dynamic;
u32 Width;
u32 Height;
};Each world has a set of entities, everything on the grid in Brainroll is an entity. The entities array is allocated upon level load and it contains every entity in the level in the order that it was read from the level. Next we have two arrays of type entity_handle which is basically a set of references into the Entities array. These represents the internal world state and the reason it is split up into two is to solve the problem of having entities stacked on top of eachover, for example the player (dynamic) standing on top of a floor (static) cell.
The arrays static and dynamic are created of the size of Width * Height in order to be able to represent each cell in the level through a reference. Each entity keeps track of its own position in the world while the game’s internals only cares about the Static and Dynamic handles, if an entity is moved the references will only change places within the Dynamic array which allows the game to actually move stuff around while the visuals not being forced to change. While this obviously works I wouldn’t recommend anyone doing it this way because we basically have two sources of truth here and there has been bugs in the past where the two states has been out of sync which is just an annoying thing to have happen.
How I tell stuff to move around is something I call the “event system”. Every entity has a event_queue inside them containing a list of tasks this entity has to perform. En event is structured in the following way:
enum event_type
{
EVENT_TYPE_MOVE,
EVENT_TYPE_WALL_COLLISION,
};
struct move
{
vector2i Start;
vector2i Destination;
move_direction MoveDirection;
};
struct wall_collision
{
vector2i Position;
move_direction MoveDirection;
};
struct event
{
event_type Type;
entity *Entity;
union
{
move Move;
wall_collision WallCollision;
// NOTE(Oskar): There are more events here but I removed it to keep the snippet shorter.
};
};
So when an event is created it assigned a type as well as a target entity that “owns” this event. For example when a new move event has been created we specify which entity it is that is moving as well as setting the start and destination cell for the move.
Each frame the game checks if there are events to plays back and if there are, the events are simulated. For example if an entity has a move event strapped on it we will simulate it moving towards the move’s destination cell until it arrives. The same goes for every other type of event in the game, if we take a look at the wall_collision event which is basically just a cosmetic event that tells the game to play a small particle effect upon collisions it checks the Position of the collision and the MoveDirection which decides in which direction the particles should fly.
Moving on to looking at how a single move is made we have the actual brains of the program. I have removed the code related to the ropes because it literally makes the move function hundreds of lines longer. In retrospect when removing the rope logic this code actually isn’t that bad.
STN_INTERNAL void
PerformMove(entity *Entity, event_queue *EventQueue, vector2i CurrentTile,
move_direction MoveDirection, world *World)
{
Assert(Entity->Type == ENTITY_TYPE_BRAINROLL);
if (Entity->Brainroll.HasBeenAmended)
{
return;
}
b32 NextTileIsOutOfBounds = false;
vector2i MovementVector = MoveDirectionToVector(MoveDirection);
vector2i Destination = Vector2Add(CurrentTile, MovementVector);
if (MoveFromCurrentTileIsBlocked(World, CurrentTile))
{
EventQueuePushWallCollision(EventQueue, Entity, CurrentTile, MoveDirection);
return;
}
NextTileIsOutOfBounds = WorldTileIsOufOfBounds(World, Destination);
entity *NextTile = WorldGetStaticEntityAt(World, Destination);
entity *NextObject = WorldGetDynamicEntityAt(World, Destination);
while (NextTile == NULL &&
NextObject == NULL &&
NextTileIsOutOfBounds == false)
{
Destination = Vector2Add(Destination, MovementVector);
NextTileIsOutOfBounds = WorldTileIsOufOfBounds(World, Destination);
if (NextTileIsOutOfBounds)
{
break;
}
NextTile = WorldGetStaticEntityAt(World, Destination);
NextObject = WorldGetDynamicEntityAt(World, Destination);
}
if (NextTileIsOutOfBounds)
{
EventQueuePushMove(EventQueue, Entity, CurrentTile, Destination, MoveDirection);
EventQueuePushOutOfBounds(EventQueue, Entity);
}
else
{
if (NextObject)
{
MoveCheckDynamicCollision(Entity, EventQueue, CurrentTile, Destination, MoveDirection, World, NextObject);
}
else if (NextTile)
{
MoveCheckStaticCollision(Entity, EventQueue, CurrentTile, Destination, MoveDirection, World, NextTile);
}
else
{
if (Destination.X != 0 || Destination.Y != 0)
{
EventQueuePushMove(EventQueue, Entity, CurrentTile, Destination, MoveDirection);
WorldSwapTiles(World, CurrentTile, Destination);
}
}
}
}
Starting from the top we look at which direction we’re going and we build up a destination based of that. Since floor cells are made up of ice in Brainroll we simply don’t look ahead a single cell but instead we continue looking ahead once cell at the time untill we find another entity to collide with. This can either be a static entity such as a wall or a snow cell or a dynamic entity such as a brain block (I will talk about those soon).
When looking ahead we are looking at entities, the reason for this is that upon a collision, the event system needs to know which entity the event belongs. The actual lookup is done by looking at the entity_handles because they are the current single source of truth for the game logic.
STN_INTERNAL entity *
WorldGetStaticEntityAt(world *World, vector2i Position)
{
entity *Result = 0;
entity_handle Handle = World->Static[Position.Y * World->Width + Position.X];
Result = EntityFromHandle(Handle, World->Entities, World->EntityCount);
return (Result);
}Retrieving the dynamic entities works in the exact same way. Upon a collision we have two functions MoveCheckStaticCollision and MoveCheckDynamicCollision which handles logic specific to coliding with some entities. It can be for example the wall_collision event upon coliding with a wall or an activation event for a pressure plate. Then we finally have what is actually performing the move itself which is the WorldSwapTiles function which is just really simple way of swapping the positions of two entity handles, since static entities are static we never move them, which make the swap function very simple.
STN_INTERNAL void
WorldSwapTiles(world *World, vector2i Position1, vector2i Position2)
{
entity_handle A = World->Dynamic[Position1.Y * World->Width + Position1.X];
entity_handle B = World->Dynamic[Position2.Y * World->Width + Position2.X];
World->Dynamic[Position1.Y * World->Width + Position1.X] = B;
World->Dynamic[Position2.Y * World->Width + Position2.X] = A;
}There is one final detail about the movement code before moving on and that is the case when moving connected entities. Brainroll has also removed the concept of sokoban boxes in favor of brains that can stick to the player, when the player collides with a brain block it is connected to you and will mimic your every move. Brain blocks can also be connected to other brain blocks and through this you can form big chains of brains that moves together.
The way this is solved programatically is actually right now a simple hack. Before we move the player we check if he has anything connected to him. If he does we loop through the entire level and check each cell to see if it contains a connected brain or not. If it does we move it before we move the player. The movement code for the brains is the exact same codepath as for the player.
STN_INTERNAL void
PerformGroupMove(event_queue *EventQueue, move_direction MoveDirection,
world *World, entity *Player)
{
Assert(Player->Type == ENTITY_TYPE_BRAINROLL);
if (Player->Brainroll.HasConnectedBrainroll == false)
{
vector2i PlayerTile = Vector2InitI32(Player->TileX, Player->TileY);
PerformMove(Player, EventQueue, PlayerTile, MoveDirection, World);
}
else
{
switch(MoveDirection)
{
case MOVE_DIRECTION_UP:
{
for (u32 TileY = 0; TileY < World->Height; ++TileY)
{
for (u32 TileX = 0; TileX < World->Width; ++TileX)
{
vector2i Tile = Vector2InitI32(TileX, TileY);
PerformMoveIfBrainrollOnTile(EventQueue, MoveDirection, World, Player, Tile);
}
}
} break;
case MOVE_DIRECTION_DOWN:
{
for (i32 TileY = World->Height - 1; TileY >= 0; --TileY)
{
for (u32 TileX = 0; TileX < World->Width; ++TileX)
{
vector2i Tile = Vector2InitI32(TileX, TileY);
PerformMoveIfBrainrollOnTile(EventQueue, MoveDirection, World, Player, Tile);
}
}
} break;
case MOVE_DIRECTION_LEFT:
{
for (u32 TileX = 0; TileX < World->Width; ++TileX)
{
for (u32 TileY = 0; TileY < World->Height; ++TileY)
{
vector2i Tile = Vector2InitI32(TileX, TileY);
PerformMoveIfBrainrollOnTile(EventQueue, MoveDirection, World, Player, Tile);
}
}
} break;
case MOVE_DIRECTION_RIGHT:
{
for (i32 TileX = World->Width - 1; TileX >= 0; --TileX)
{
for (u32 TileY = 0; TileY < World->Height; ++TileY)
{
vector2i Tile = Vector2InitI32(TileX, TileY);
PerformMoveIfBrainrollOnTile(EventQueue, MoveDirection, World, Player, Tile);
}
}
} break;
}
}
}I think I just wrote this one pass and then just kept it throghout the entire development of the game. Deffinately a point of improvement.
Ropes (Chain blocks)
The most unique mechanic in Brainroll is the chain blocks which is internally refered to as “Ropes”. The idea of the ropes is to introduce a mechanic that limits the movement of entities in the game by having it be connected to a fixed position only allowing it to be moved a fixed number of cells away from it. A shorter and perhaps more accurate explanation that I heard from a player was “foldable walls”. This mechanic was interesting not only within the game but also interestin to implement as it did prove to not be trivial.
I did mention that this does make the movement code quite a bit longer (mainly because I never bothered to clean it up) so I will only talk about the relevant snippets of code moving forwards. If you’re interested in the entire PerformMove function with the included rope code I’ve created a gist for you.
The first most obvious change is that now before we start to actually move the target entity we perform a pre-check if it has a rope connected to it. If it does we need to make sure that the rope can follow if the entity moves in the specified move_direction. This is basically a single step of the previously displayed while loop over destinations. I did this because the PerformMove function starts with the Destination being one step towards the moving direction and in case of a collision it takes one step in the opposite direction to correct it. With ropes this becomes a problem in case the Destination is valid for the target entity but invalid from the ropes perspective. It is ugly and makes the function hard to grasp and should be refactored sometime in the future.
if (Entity->HasRopeConnection)
{
if (EntityIsFirstInRope(Entity, World))
{
RopeBuildOrder = ROPE_LIST_BUILD_ORDER_FORWARDS;
}
rope_list RopeList = RopeListCreate(Entity, World, &Arena, RopeBuildOrder);
if (!RopeInAdjacentTile(RopeList.Next, World, Destination))
{
rope_transaction_list *TransactionList = RopeCreateTransactionList(&Arena);
if (!RopeTryMove(RopeList.Next, World, &Arena, MoveDirection, EventQueue, Entity, TransactionList))
{
Destination = Vector2Minus(Destination, MovementVector);
EventQueuePushWallCollision(EventQueue, Entity, Destination, MoveDirection);
}
else
{
// TODO(Oskar): Carefull cause we are not checking if Destination is occupied!!
entity *NextTile = WorldGetStaticEntityAt(World, Destination);
entity *NextObject = WorldGetDynamicEntityAt(World, Destination);
if ((NextTile == NULL && NextObject == NULL) ||
(NextObject != NULL && NextObject->Type == ENTITY_TYPE_ROPE && RopeListContainsEntity(RopeList.Next, World, NextObject)) ||
(NextObject == NULL && NextTile != NULL && NextTile->Type == ENTITY_TYPE_PRESSURE_PLATE) ||
(NextObject == NULL && NextTile != NULL && NextTile->Type == ENTITY_TYPE_SLIME))
{
if (IsMovingTowardsRope(MoveDirection, CurrentTile, RopeList.Next->Tile))
{
RopeTransactionsCommit(TransactionList, World, EventQueue);
MoveManagePressurePlateOnMove(EventQueue, Entity, World, CurrentTile, Destination);
EventQueuePushMove(EventQueue, Entity, CurrentTile, Destination, MoveDirection);
WorldSwapTiles(World, CurrentTile, Destination);
if (NextTile != NULL && NextTile->Type == ENTITY_TYPE_PRESSURE_PLATE)
{
EventQueuePushEnterPressurePlate(EventQueue, Entity, NextTile);
}
CurrentTile = Destination;
Destination = Vector2Add(Destination, MovementVector);
DidAlterDestination = true;
}
else
{
MoveManagePressurePlateOnMove(EventQueue, Entity, World, CurrentTile, Destination);
EventQueuePushMove(EventQueue, Entity, CurrentTile, Destination, MoveDirection);
WorldSwapTiles(World, CurrentTile, Destination);
if (NextTile != NULL && NextTile->Type == ENTITY_TYPE_PRESSURE_PLATE)
{
EventQueuePushEnterPressurePlate(EventQueue, Entity, NextTile);
}
CurrentTile = Destination;
Destination = Vector2Add(Destination, MovementVector);
RopeTransactionsCommit(TransactionList, World, EventQueue);
DidAlterDestination = true;
}
}
}
}
}Focusing on this snippet will give us most of the information about how the rope logic works. If we are dealing with a rope I build up a temporary linked list, the reason I dont cache these is because I had an idea in mind that you should be able to break the chains but I never got around to that. Once our rope_list has been created we check if there is a rope tile adjacent to the destination we’re moving to, we do this because if there is then we don’t have to move the rope.
If there is none we know that we will want to move the rope or that the entity that is currently being moved will be blocked or stopped from moving. We start with creating a rope_transaction_list to keep track of all the moves that entities within our rope has to make and then we attempt to move the rope through the RopeTryMove function. The function then goes through the entire lsit of rope entities with an almost exact same process as any other entity and builds up the transaction list with movement events that the entire rope needs to do in order for the original entities move to be valid.
Then we depending on if the entity is moving towards the rope or not we just submit the movement events in different orders to not make them clash. Even though this system can see a lot of improvement it was actually refactored a lot, the old implementation was way different to the point that it was unmaintainable. It started with me trying A* pathfinding for the rope to just find the best path to take upon a move and then I opted for my own algorithm where I build up lists of all the possible solutions and tried to pick the best move but in the end this solution to just treat the individual rope entities as normal entities and pass them through a similar movement process as any other entity was the best solution.
Undo implementation
I wont talk too much about how I solved undo in Brainroll because it’s just a really big hack. I don’t know why but I decided not to implement undo but changed my mind just a week or two before the release and I didn’t spend any time being clever about this and instead just built the absolutely simplest thing I could think of. Since the solution is pretty weird and I don’t know if someone did anything similar I decided to write something short about it in this post.
So the entire undo system is just a linked list of world states, what I do upon every move is that i take a complete memory copy of the world struct that we saw earlier in this post and just compress it to save space. When the player undo a move I just replace the world state with the last one in our linked list. It is super simple and it works really well except for it taking up more memory than it has to.
STN_INTERNAL compressed_world
_UndoStateCreateWorldCopy(undo_state *State, const world &WorldState)
{
compressed_world Result = {};
Result.Width = WorldState.Width;
Result.Height = WorldState.Height;
Result.NumberOfMoves = WorldState.NumberOfMoves;
Result.EntityCount = WorldState.EntityCount;
u32 Size = Result.Width * Result.Height;
Result.Static = (entity_handle *)MemoryArenaAllocateAndZero(&State->MemoryArena, Size * sizeof(entity_handle), 1);
Result.Dynamic = (entity_handle *)MemoryArenaAllocateAndZero(&State->MemoryArena, Size * sizeof(entity_handle), 1);
// NOTE(Oskar): Compress entity buffer and store it along with its size within the undo_world.
{
u32 EntityBufferSize = Size * sizeof(entity);
entity *EntityBuffer = (entity *)MemoryArenaAllocateAndZero(State->TemporaryArena, EntityBufferSize);
MemoryCopy(EntityBuffer, WorldState.Entities, EntityBufferSize);
const int MaxCompressionBound = LZ4_compressBound(EntityBufferSize);
char *CompressedBuffer = (char *)MemoryArenaAllocate(State->TemporaryArena, MaxCompressionBound);
Result.CompressedEntitiesSize = LZ4_compress_default((const char *)EntityBuffer, CompressedBuffer, EntityBufferSize, MaxCompressionBound);
Result.CompressedEntities = MemoryArenaAllocateAndZero(&State->MemoryArena, Result.CompressedEntitiesSize, 1);
MemoryCopy(Result.CompressedEntities, CompressedBuffer, Result.CompressedEntitiesSize);
MemoryArenaFreeBytes(State->TemporaryArena, EntityBufferSize); // CompressedBuffer
MemoryArenaFreeBytes(State->TemporaryArena, EntityBufferSize); // EntityBuffer
}
_UndoStateCopyEntityReferences(State, WorldState, &Result);
return (Result);
}For this I used a library called LZ4 which is a fast compression library together with virtual memory arenas in Windows. This way I can allocate an absurdly big arena which only grows as more memory is needed. Of course none of this would ever be needed for a proper undo system but this is something I added just before the release of the game and I found it to be the quickest solution.
Thoughts
Through the entire journey of creating this game I’ve learned a lot about many things. When I was younger and played around with creating games I often barely even got things to render to the screen as I often got stuck trying to figure out the best way of doing every single thing possible.
Starting with creating a new game I would have to open a new window, first thing I did was to research the most optimal and complete way to open windows. Doing this for every single thing will really get you nowhere. Some of the code I show in this post is far from perfect or optimal but it helped me reach the goal by working on average 2 hours per day after my normal job which I think is very valuable, more valuable than being stuck with a unfinished game that has the best movement or rope code.
If i go back to the Brainroll codebase now to try improve it I would deffinately try to simplify the rope related code, maybe have it perform less checks or try make it go through the same codepath as the other entities (PerformMove instead of RopeTryMove). I also noticed a lot of dead code while writing this that can be removed.
I don’t know if it is because of me having spent so much time on the codebase but I feel like the logic in Brainroll is very simple. Many times I wonder if I have had a slow development time creating this game. I have a hard time judging if I spent a lot of time writing code for easy problems. I briefly mentioned how the rope mechanic went through over 3 iterations with completely different approaches, why did I even do the 2 first ones? How come I didn’t start with the simplest one instead of starting with the hardest one? I think there are many times during the development that I went through something similar of me creating something that is way too complex and having to cut it or me just implementing something that I don’t end up using.
Part of the fun of programming in your own projects is to have the ouportunity to go through those journeys with code but when working against the clock I wonder if it somehow should be limited with better planning or dicipline.
Did you know that you get access to the Maraton source code if you become a paid subscriber to my website? If you’re interested in learning or to be a part of the development then don’t hesitate and click the button below!