Scenes in Backcountry (or worlds as we also call them) are grid-based,
with cells being 8x8 voxels wide. Each cell has a distance value, i.e. the number
of steps main character needs to take to reach it. If a cell contains an obstacle (a cactus,
rock, wall, building, etc.), its distance value is set to NaN.
Initially the distances of all "walkable" (non-obstacle) cells are set to
The cell where the player is gets the value of 0.
All the walkable neighbors of the current cell that were not visited yet
receive a distance value equal to current_distance + 1
If a neighbor was previously visited by the algorithm this frame and its distance was
calculated to a number higher than current_distance + 1, the distance score is
updated to the lower value.
To avoid visiting too many cells too many times, the algorithm implements a
breadth-first search. It considers cells closer to the player first before diving deeper
into the neighbors or neighbors.
The algorithm continues while the current distance is lower than 15.
Whenever the user selects a destination cell, the path finding system
(sys_player_control) looks for the shortest path from the target cell to the
character, each time choosing the neighbor with the lowest distance value.
The complete route is then saved in the player's Walking component in the
reverse order (from the player to the target cell). The first cell in the list is then set as
a current destination for the player.
The sys_navigate system orders the entity in the direction of the current
destination (central point of the first cell in the route list).
The actual movement is carried out by the sys_move system.
sys_navigate controls sys_move by writing direction vectors to the
Move component of the entity.
If the entity is close enough to the destination, and there are still cells in the
route list, the next one pops in as the next destination.
If the route list is empty, the character has reached its target cell, and
the distance field is recalculated again.
Calculating the distance field is expensive, so we used the one calculated for the player
in NPCs AI calculations.
"Friendly" NPCs don't want to kill the player - they are randomly wandering around the
Each NPC starts on a cell with a non-zero distance value, and then picks a
random distance number from the 0-14 range as the destination (14 is the maximum
value our algorithm calculates the distance field values to).
The same path-finding algorithm as above is then used to find the shortest way from the
current cell to the first cell with the target distance found in the scene.
Neighbors are also randomized for a more natural feel of the movement (without that, NPCs
would only do 90° turns).
When the NPC reaches its final destination, it selects another random
distance value and performs the algorithm again.
NPCs are "friendly" when they're in the town, and when their distance to the player is
greater than 5.
Hostile NPCs can be found in the desert and in the mine. When they are closer than 5 cells
to the player, they start attacking.
The destination cell is the one with the player on it (distance value =
They stop 2 cells before reaching the player.
They shoot every half a second in the player's direction.
Using the same distance field for both the player and the NPCs has the following
NPCs that are further than 15 steps from the player don't move. Their
distance is still Infinity because it hasn't been computed
NPCs in walkable areas that are cut off from the player with obstacles don't move
either. This can be observed in the city when the exit gate is still closed: