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 Infinity.
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.
Enemy AI
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 current world.
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 = 0).
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 limitations:
NPCs that are further than 15 steps from the player don't move. Their distance is still Infinity because it hasn't been computed yet.
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:
