Grid-Based Movement Systems Part 1:
Basic Movement
By Kalle Kiiskinen
Sept. 14, 2021
Click here for this article's source code.
Introduction
When I begin development on a new video game project, I often consider if a grid-based movement system would be suitable for exploring, expanding upon, and presenting the game's core mechanics.
A grid-based movement system is one that constrains the positions of entities to discrete locations on a two-dimensional grid. Entities are only allowed to move between grid spaces, and each grid space can only be occupied by a single entity. Entities typically move simultaneously during distinct movement turns, and no other movement occurs outside of or between movement turns.
Grid-based movement systems are not appropriate for all video games or video game genres, but they are often seen in turn-based strategy games, roguelikes, and puzzle games. A special programming language has even been created for designing grid-based games.
As this article will demonstrate, one advantage of grid-based movement systems is that they are simple to implement. This is especially true when compared to using a realtime physics and collision detection system to generate motion. Grid-based movement systems also allow for easy debugging, since entity movement can be recreated exactly, and bugs can be traced back to a specific interaction between entities. In puzzle games, constraining entities to a grid can reduce ambiguity with regard to how and where entities can move as the player attempts to reason about potential solutions to a puzzle.
Entities
In the context of the grid-based movement system being discussed here, entities are the objects in the game world that move around on the grid. Note that the grid itself does not actually exist in the game world; there is no "grid" entity. The grid is instead defined implicitly by the movement logic. Entities will be aligned to the grid when their positions are initialized, and the movement logic must then ensure that entities remain aligned to the grid after each movement turn.
Entity behaviour and entity movement behaviour are determined by Entity Types and Move Types, respectively. The entity behaviour that I have chosen to implement in this article is inspired by the original block-pushing game Sokoban.
Entity Types
The entity types used in Sokoban are the Player, Block, Wall, and Floor entities, which have been defined in the following enum.
enum entity_type_enum : int
{
EnumEntityTypePlayer,
EnumEntityTypeFloor,
EnumEntityTypeWall,
EnumEntityTypeBlock,
};
The Player entity moves in response to user input. Block entities move when they are pushed by the Player entity, while Wall entities prevent Player and Block entity movement.
Floor entities have no effect on movement in Sokoban, but they will be used here to prevent the Player from moving to any grid space that does not contain a Floor entity.
To differentiate between empty grid spaces and Wall entities, Block entities will still be allowed to move to empty grid spaces. Otherwise, empty grid spaces would be the same as Wall entities with respect to their ability to prevent the Player and Block entities from moving.
It should be noted that Sokoban also contains a Target entity type that is used to specify where Blocks must be placed in order to solve a puzzle. However, as the focus of this article is on movement and not gameplay logic, I have omitted Target entities from the current discussion.
Entity Move Types
All entities will be assigned a move type that determines whether or not the entity can move. The move types I have defined below are Static, Dynamic, and NoMovement.
enum move_type_enum : int
{
EnumMoveTypeStatic,
EnumMoveTypeDynamic,
EnumMoveTypeNoMovement,
};
Dynamic entities can move, while Static entities cannot move. Dynamic entities will be prevented from moving when they try to move into Static entities. Dynamic entities can push other Dynamic entities. The NoMovement move type is assigned to entities that do not move and do not prevent other entities from moving. Floor entities are an example of an entity with NoMovement move type.
Note that the movement behaviour for Static, Dynamic, and NoMovement move types is effectively the same as the movement behaviour for Player, Block, Wall, and Floor entities described earlier. While entity move types may seem redundant, move types will be included in the movement system to allow movement behaviour to be defined more easily for new entity types that might be added to the game later.
Entity Struct Definition
The data that entities require to enable grid-based movement is contained inside the "entity" struct defined below.
struct entity
{
vec2 Position;
vec2 NextPosition;
int EntityTypeEnum;
int MoveTypeEnum;
bool IsMoving;
};
An entity's current grid position will be stored in a two-dimensional "Position" vector. The final grid position of a moving entity will be stored in a two-dimensional "NextPosition" vector. The EntityTypeEnum and MoveTypeEnum integer variables will store the entity's Entity Type and Move Type, respectively. A single flag called "IsMoving" indicates if an entity is moving to a new grid space.
Some entity types and move types will not use certain member variables in the entity struct. For example, entities with Static move type do not use the NextPosition or IsMoving variables. However, using a single entity struct with fields to store the data used by the various entity and move types keeps the movement system logic relatively simple compared to defining separate structs to contain specific data for the Player, Block, Wall, and Floor entities.
The movement system logic expects entities to be stored in an array of entity structs, which can be defined as follows:
#define MAX_ENTITIES ( 1024 )
int EntityCount;
entity Entities[MAX_ENTITIES];
A level or puzzle can be created by initializing some or all of the entities in this array with appropriate entity types, move types, and grid positions.
Game State
For entities to move around the grid, the movement system will monitor certain data that applies to all moving entities that would not be appropriate to store on a per-entity basis. This data is referred to here as game state.
Game States
While teleporting entities to their next grid position is an option, the movement logic will instead move entities at a constant speed from their initial position to their final position. Therefore, two game states will be utilized to separate the handling of player input from the actual moving of entities. These states are defined below as the HandleInput and MoveEntities game states.
enum game_state_enum : int
{
EnumGameStateHandleInput,
EnumGameStateMoveEntities,
};
Game State Struct Definition
Game state data is contained inside the game_state struct defined below. The game_state struct stores the current game state (i.e. HandleInput or MoveEntities) using the CurrentGameStateEnum member variable.
struct game_state
{
int CurrentGameStateEnum;
int PlayerIndex;
vec2 MoveDirection;
float TotalMoveDistance;
};
Since the Player entity is of special interest given that it is the source of all entity movement, the game_state struct stores the location of the Player entity in the Entities array using the PlayerIndex integer variable. Variables that are used exclusively in the MoveEntities game state (aside from being initialized in the HandleInput game state) include the two-dimensional MoveDirection vector that stores the direction in which entities are moving, and the floating-point TotalMoveDistance variable that keeps track of how far entities have moved during the MoveEntities game state.
As will be seen later, storing the Player index in the game_state struct prevents the movement logic from having to search for the Player in the Entities array before every movement turn when deciding which entities will be moving. Use of this index implies that there is only one Player entity in the Entities array, and that the Player entity does not and can not change its location in the Entities array. Therefore, entities will not be added to or removed from the Entities array after a level or puzzle has been initialized.
Movement Logic
The entity movement logic has been placed inside a function called UpdateEntities. This function contains handlers for both of the HandleInput and MoveEntities game states defined earlier.
The arguments for the UpdateEntities function include:
The Horizontal/VerticalInputDirection arguments are expected to be either -1, 0, or +1, where, for example, if the horizontal input direction was '-1', the movement direction would be toward the left side of the game window.
void UpdateEntities(entity *Entities, int EntityCount, game_state *GameStatePointer,
int HorizontalInputDirection, int VerticalInputDirection,
float DeltaTime)
{
switch ( GameStatePointer->CurrentGameStateEnum )
{
case EnumGameStateHandleInput:
{
// Handle player input...
}
break;
case EnumGameStateMoveEntities:
{
// Move entities...
}
break;
}
}
The details of the game state handlers inside the UpdateEntities function are described below.
Handle Input Game State
The HandleInput game state handler first checks if the player pressed a directional input, exiting the handler early if no input was pressed. If at least one input direction was pressed, this direction is assigned to the GameStatePointer's MoveDirection member variable to be used later in the MoveEntities game state handler. If a horizontal and vertical input direction were pressed at the same time, the y-component of MoveDirection is reset to '0' to prevent entities from moving diagonally (the choice to reset the y-component of MoveDirection is arbitrary; it is equally valid to reset the x-component instead).
if ( !HorizontalInputDirection && !VerticalInputDirection )
{
// Exit input handler if no input was pressed:
break;
}
GameStatePointer->MoveDirection = { (float)HorizontalInputDirection,
(float)VerticalInputDirection };
if ( HorizontalInputDirection && VerticalInputDirection )
{
// Arbitrarily reset one movement direction to prevent diagonal movement:
GameStatePointer->MoveDirection.y = 0.f;
}
Determining which entities will move begins with the Player entity. As mentioned earlier, the Player entity can only move to a grid position if it contains a Floor entity, so we must first check if there is a Floor entity located at the Player's next position. This is accomplished using a utility function called FindFloorEntityAtPosition (see the Finding Entities section of this article for details about this function). If no Floor entity is found then the Player cannot move, and we can exit the input handler at this point as no other entities will be moving either.
If a Floor entity is found at the Player's next position, then the Player will be able to move as long as they are not trying to push a Static entity (or Dynamic entities being pushed by the Player are not trying to push a Static entity).
In preparation for determining which entities are being pushed by the Player, every entity has its "IsMoving" flag reset to "FALSE". For entities with Static or NoMovement move type, it does not matter if their IsMoving flags are set to "TRUE" or "FALSE". Therefore, we can simply reset the IsMoving flags for all entities regardless of move type, instead of only resetting IsMoving flags for entities with Dynamic move type.
// Check for a Floor entity at the Player's next movement position:
vec2 NextPlayerPosition = Entities[GameStatePointer->PlayerIndex].Position
+ ENTITY_SCALE * GameStatePointer->MoveDirection;
i32 FloorEntityIndex = FindFloorEntityAtPosition(Entities, EntityCount, NextPlayerPosition);
if ( FloorEntityIndex == INVALID_ENTITY_INDEX )
{
// No Floor entity was found for the Player entity to move to;
// no entities will move, so exit the Handle Input game state handler:
break;
}
// Reset movement-related flags for all entities:
for ( int EntityIndex = 0; EntityIndex < EntityCount; EntityIndex++ )
{
Entities[EntityIndex].IsMoving = FALSE;
}
After IsMoving flags have been reset, the movement logic begins searching consecutive grid spaces for Static and Dynamic entities along the movement direction (starting at the Player's current position) to determine which entities are being pushed by the Player. The search for entities stops when either a Static entity is discovered, or neither a Static or Dynamic entity is discovered.
While searching for entities that are being pushed by the Player, it is assumed that every Dynamic entity that is found will be moving, and so these Dynamic entities have their NextPosition calculated and IsMoving flag set to TRUE. As the movement logic only reads from the NextPosition and IsMoving variables while in the MoveEntities game state, it is not necessary to reset/clear these variables if it is later determined that no Dynamic entities are moving.
As shown in the following code, the NextPosition for each Dynamic entity is calculated as being one grid space away from its current Position in the direction of movement.
// Search for Dynamic entities that will move, and Static entities that will prevent movement:
int CurrentEntityIndex = GameStatePointer->PlayerIndex;
vec2 CurrentPosition = Entities[CurrentEntityIndex].Position;
while ( CurrentEntityIndex != INVALID_ENTITY_INDEX )
{
if ( Entities[CurrentEntityIndex].MoveTypeEnum == EnumMoveTypeDynamic )
{
Entities[CurrentEntityIndex].IsMoving = TRUE;
Entities[CurrentEntityIndex].NextPosition = Entities[CurrentEntityIndex].Position
+ ENTITY_SCALE * GameStatePointer->MoveDirection;
}
else if ( Entities[CurrentEntityIndex].MoveTypeEnum == EnumMoveTypeStatic )
{
break;
}
// Search in the direction of movement for an entity located at the next grid position:
CurrentPosition += ENTITY_SCALE * GameStatePointer->MoveDirection;
CurrentEntityIndex = FindStaticOrDynamicEntityAtPosition(Entities, EntityCount, CurrentPosition);
}
After the search for Static and Dynamic entities has ended, the movement logic checks if the search ended with the discovery of a Static entity. If a Static entity was found, the movement logic exits the HandleInput game state handler, as this implies the Player is ultimately trying to push an unmovable Static entity, and therefore no entities can move.
If the search ended without finding a Static entity, then at least one Dynamic entity can and will be moving, and the movement logic will transition to the MoveEntities game state. The GameStatePointer's TotalMoveDistance variable should now be reset to '0' to indicate that entities have not yet moved any distance.
if ( ( CurrentEntityIndex != INVALID_ENTITY_INDEX )
&& ( Entities[CurrentEntityIndex].MoveTypeEnum == EnumMoveTypeStatic ) )
{
// The last entity found was Static; exit the HandleInput game state handler since
// no entities will be moving:
break;
}
// No Static entity was found and at least one dynamic entity is moving;
// go to the Move Entities game state:
GameStatePointer->CurrentGameStateEnum = EnumGameStateMoveEntities;
GameStatePointer->TotalMoveDistance = 0.f;
Move Entities Game State
The MoveEntities game state begins by determining "Displacement," the maximum distance that entities will move during the current frame. The Displacement is then added to the GameStatePointer's TotalMoveDistance to update the TotalMoveDistance variable to its end-of-frame value.
float Displacement = ENTITY_MOVE_SPEED * DeltaTime;
GameStatePointer->TotalMoveDistance += Displacement;
If the TotalMoveDistance (at the end of the current frame) is less than the length of one grid space, then the positions of moving entities will be advanced in the MoveDirection by the Displacement distance calculated earlier.
Entities will stop moving when the TotalMoveDistance is equal to or exceeds one grid space distance (the "ENTITY_SCALE" macro seen in the code below defines a length that is equal to one grid space distance). When an entity stops moving, it is placed at its NextPosition and its IsMoving flag is reset to FALSE. Once entities stop moving, the game transitions back to the HandleInput game state.
if ( GameStatePointer->TotalMoveDistance < ENTITY_SCALE )
{
// Entities have not moved one grid space distance
for ( int EntityIndex = 0; EntityIndex < EntityCount; EntityIndex++ )
{
if ( !Entities[EntityIndex].IsMoving ) continue;
Entities[EntityIndex].Position += Displacement * GameStatePointer->MoveDirection;
}
}
else
{
// Entities will have moved one grid space distance by the end of the current frame
for ( int EntityIndex = 0; EntityIndex < EntityCount; EntityIndex++ )
{
if ( !Entities[EntityIndex].IsMoving ) continue;
Entities[EntityIndex].Position = Entities[EntityIndex].NextPosition;
Entities[EntityIndex].IsMoving = FALSE;
}
// Return to Handle Input game state now that entities have stopped moving:
GameStatePointer->CurrentGameStateEnum = EnumGameStateHandleInput;
}
Finding Entities
Let's now take a look at the "FindFloorEntityAtPosition," and "FindStaticOrDynamicEntityAtPosition" utility functions used in our movement logic. As their names imply, these functions search for an entity located at the 2D Position argument passed to the function, filtering out entities based on entity type or move type.
To determine if an entity is located at the position of interest, an AABB (axis-aligned bounding box) is first constructed around "Position." A point-versus-AABB collision test is then performed with each entity that matches the specific entity type or move type criteria (such as Floor entities in the case of the "FindFloorEntityAtPosition" function), where each entity Position is treated as the "point" in the collision test. Collision tests are performed until a collision is detected (i.e. an entity position is found to be inside the AABB), or all entity positions have been tested without detecting a collision.
Note that as long as one of these utility functions never searches for entities that can share a grid space (such as the Player and a Floor entity), the collision test should never find two or more entities at the same position.
int FindStaticOrDynamicEntityAtPosition(entity* Entities, int EntityCount, vec2 Position)
{
// Assemble an AABB around "Position"
float AabbMinX = Position.x - ENTITY_HALF_SCALE;
float AabbMaxX = Position.x + ENTITY_HALF_SCALE;
float AabbMinY = Position.y - ENTITY_HALF_SCALE;
float AabbMaxY = Position.y + ENTITY_HALF_SCALE;
// Initialize return value for function:
int FoundEntityIndex = INVALID_ENTITY_INDEX;
for ( int EntityIndex = 0; EntityIndex < EntityCount; EntityIndex++ )
{
// Skip entities that do not have Static or Dynamic move type:
if ( ( Entities[EntityIndex].MoveTypeEnum != EnumMoveTypeStatic )
&& ( Entities[EntityIndex].MoveTypeEnum != EnumMoveTypeDynamic ) ) continue;
// Perform a collision test between the 2D AABB and the current entity's position:
// (If the current entity is outside of the AABB, move on to the next entity)
if ( Entities[EntityIndex].Position.x < AabbMinX ) continue;
if ( Entities[EntityIndex].Position.x > AabbMaxX ) continue;
if ( Entities[EntityIndex].Position.y < AabbMinY ) continue;
if ( Entities[EntityIndex].Position.y > AabbMaxY ) continue;
// Current entity is inside the AABB. Stop searching for entities now, as
// only one Static or Dynamic entity can be located at a grid position:
FoundEntityIndex = EntityIndex;
break;
}
return FoundEntityIndex;
}
Movement Macros
I'll end with a brief explanation of some of the macros that were used in the above movement logic.
Three macros used for controlling entity movement are ENTITY_SCALE, ENTITY_MOVE_TIME, and ENTITY_MOVE_SPEED. The ENTITY_SCALE macro defines both the horizontal and vertical dimensions of entities, as well as the dimensions of grid spaces.
Assuming entities move between grid spaces with constant speed, a single ENTITY_MOVE_TIME macro can be used to tune the amount of time it takes for entities to move to their NextPosition(s). The ENTITY_MOVE_TIME macro is used to calculate the value of the ENTITY_MOVE_SPEED macro, which in turn defines the speed at which entities move between grid spaces.
#define ENTITY_SCALE ( 1.f )
#define ENTITY_MOVE_TIME ( 0.2f ) // Time in seconds
#define ENTITY_MOVE_SPEED ( ENTITY_SCALE / ENTITY_MOVE_TIME )
If desired, the ENTITY_MOVE_SPEED macro could be replaced with a member variable (e.g. "MoveSpeed") in the game_state struct so that the entity move speed can be modified. With some extra logic, this could be used to accelerate and decelerate entities at the start and end of the MoveEntities game state. The move speed could also change based on specific game conditions, such as the Player moving on a Conveyor Belt entity that speeds up or slows down movement when the Player moves with or against the belt direction.
Click here for this article's source code.