We move units using pathfinding, which computes the shortest path to reach a target cell.
This post is part of the 2D Strategy Game series
The player selects the knight with the left mouse button in the following video. Then, (s)he moves the mouse cursor, showing the shortest path to the pointed cell with the total movement cost. At last, (s)he moves the knight to a cell using the left mouse button:
The selection layer trick: we want to select a unit in the world with a left mouse click and add a selection box around:
To get this result, we have to draw this selection box. A first approach directly renders the corresponding tile given the coordinates of the currently selected cell. This approach can look easier, but it requires computing the screen coordinates, which depend on many parameters.
A second approach uses the existing layer utilities to avoid another computation of the screen coordinates. Indeed, layer UI components render their tiles without the need to compute the coordinates explicitly. So, if we create a new
SelectionLayer layer class, and a corresponding UI component
SelectionComponent, then setting a cell in the selection layer will show a selection box.
WorldComponent class, which contains all layer components, we create these new objects:
self.__selectionLayer = SelectionLayer(world.size) self.__selectionComponent = SelectionComponent(theme, state, self.__selectionLayer) self.addComponent(self.__selectionComponent, cache=True)
Line 1 creates an instance of a new
SelectionLayer class: it a child class of
Layer, with some method related to selection. Note that we create it in
WorldComponent in the
ui package, not in the
core package! It is related to UI, and the game logic does not need it. As a result, we can't add new values in the
CellValue enum that lists world cell value types. Instead, we create a new
SelectionValue enum with all cell value our selection layer can take: at the current moment, NONE (not selected) and SELECT (selected).
Lines 2-3 create and add an instance of a new
SelectionComponent class, a child class of
LayerComponent, that renders selection tiles. Then, we only need to set a selection layer cell to show a selection box. To this end, we add the following methods to the
class SelectionLayer(Layer): def selectCell(self, cell: Tuple[int, int]): self.setValue(cell, SelectionValue.SELECT) def unselectCell(self, cell: Tuple[int, int]): self.setValue(cell, SelectionValue.NONE) ...
If we follow a call to one of these methods with a notification, then
SelectionComponent will render the selection box, for instance:
Selection box tiles: we can render a selection box using a single tile, for instance:
With a single tile, the selection box hides the unit a bit. To better surround the unit, we can use a larger tile, for instance, a 3x3 tile:
We render these tiles in the
render() method of the
def render(self, surface: Surface): ... valid = cells == SelectionValue.SELECT for dest, value, cell in renderer.coords(valid): rect = tilesRects[value][currentPlayerId] shift = vectorSubDiv2I(rect.size, tileSize) dest = vectorSubI(dest, shift) surface.blit(tileset, dest, rect)
We select the cell coordinates with a
SelectionValue.SELECT value (line 3) and iterate through these coordinates (line 4). Then, for each cell, we select the tile corresponding to the current player (line 5). Since the selection tile is larger than a regular tile, we compute the shift that centers it on screen (line 6). The mathematical equivalent of this function package is:
shift = (rect.size - normalTileSize) / 2. Finally, we apply the shift to the screen location (line 7) and blit the tile (line 8).
Distance map: we compute the shortest between a selected cell and any other world cell using a Distance map. It is a 2D array with as many cells as there are world cells, where each cell contains the smallest cost to reach it:
In this example, we selected the knight cell. On this cell, the move cost is zero. Then, the values around the selected cell are the costs for each direction. For instance, riding to the bridge on the right costs one point, and moving to a forest costs four points. This principle is repeated for each cell, except that we sum up all previous costs. For instance, going to the top-left cell costs 10 points: 1 (road) + 1 (road) + 4 (forest) + 4 (forest):
Since it is a distance map, the costs are always the lowest possible: if we try to reach the top-left cell from the right of the mountain, it costs 12 points: 4 (rocks) + 4 (forest) + 4 (forest).
The distance map gives the data to compute the shortest path. The algorithm is simple: choose a target cell and always select a neighboring cell with the smallest value. Then, repeat until you reach a cell with zero cost. You can see more examples running the attached code: select the knight with the left mouse button, then hit F8 twice, showing the distance map.
Cost graph: computing the distance map requires a graph where nodes represent locations and edges the cost from one place to another. Here is an example with the knight node and its edges:
We value edges, where each value is the cost of moving from one node to another.
If you select the knight in the game and then hit F8 once, you can see the edge values:
This graph allows us to compute the distance map using the Dijkstra algorithm. However, before that, we must choose how we calculate the edge values.
Edge values: there is no unique way to compute these values, and we propose here one among others.
We first define costs for moving between cells of the same kind. We put these costs in a new
class MoveCost(IntEnum): ROAD_STONE = 1, ROAD_DIRT = 2, GROUND = 3, OBJECTS = 4, INFINITE = 10000
For instance, going from a ground cell to a ground cell costs 3 points. We also define an
INFINITE cost representing cells that units can't walk on, like sea or mountain.
Then, we choose to define edge values as the maximum cost between two cells. For instance, moving from a stone road, a dirt road, or a ground cell to an object cell costs 4 points. It is a game design choice where we want to penalize leaving low-cost cells. For instance, if a unit is on a road tile, it costs a lot to hide in a forest. Other rules are possible; for instance, one could choose to compute the average cost between two cell costs.
Computation of the distance map: we create a new class
DistanceMap, that handles the computation of a distance map in some world area.
We use the same trick as in the
Layer class: we consider an area with extra rows/columns to handle borders. As a result, in the constructor of the
DistanceMap class, we enlarge the area (lines 3-7):
def __init__(self, world: World, area: Tuple[int, int, int, int]): self.__world = world x1, y1, x2, y2 = area self.__area = ( max(-1, x1 - 1), max(-1, y1 - 1), min(world.width + 1, x2 + 1), min(world.height + 1, y2 + 1) ) self.__width = self.__area - self.__area self.__height = self.__area - self.__area self.__nodes = np.empty([self.__width, self.__height], dtype=np.int32) self.__edges = np.empty([self.__width, self.__height, 8], dtype=np.int32) self.__map = np.empty([self.__width, self.__height], dtype=np.int32)
We create Numpy arrays with this extended area (lines 10-12), knowing that we will only compute values for indices
x from 1 to
y from 1 to
height-2. Thanks to this trick, we won't have to check if we are outside the area when looking for neighbor cells. The
edges arrays will contain the graph values and
map the final distance map.
We compute the distance map in the
compute() method of the
DistanceMap class values. As much as possible, we use Numpy functions to get low computational time. We first fill all arrays with an infinite cost:
nodes.fill(MoveCost.INFINITE) map.fill(MoveCost.INFINITE) edges.fill(MoveCost.INFINITE)
Then, we start the computation of the cell costs in the
node array. We assign to all ground cells in the area the corresponding move cost:
ground = world.ground.getArea(area) selection = ground == CellValue.GROUND_EARTH nodes[selection] = MoveCost.GROUND
We use the same approach to compute all cell costs in
node (impassable, roads, objects, units). Then, we set border rows/columns to
nodes[:, 0] = MoveCost.INFINITE nodes[:, -1] = MoveCost.INFINITE nodes[0, :] = MoveCost.INFINITE nodes[-1, :] = MoveCost.INFINITE
This step ensures that paths end when we reach the area's edges as if the world only contains the area.
The last step of cell costs computation assigns a zero cost at the location of the cell to reach (called source):
source = (source - area, source - area) if source < 0 or source >= self.__width \ or source < 0 or source >= self.__height: return nodes[source] = 0
Note that we could set more cells with a zero cost, in which case the distance map would contain the shortest path to the closest source.
The graph edge values are the maximum cost between two cells in a given direction. We consider eight directions (from top-left to bottom-right) and thus compute eight values per cell in the
edges[1:, 1:, 0] = np.maximum(nodes[1:, 1:], nodes[:-1, :-1]) edges[1:, :, 1] = np.maximum(nodes[1:, :], nodes[:-1, :]) edges[1:, :-1, 2] = np.maximum(nodes[1:, :-1], nodes[:-1, 1:]) edges[:, 1:, 3] = np.maximum(nodes[:, 1:], nodes[:, :-1]) edges[:, :-1, 4] = np.maximum(nodes[:, :-1], nodes[:, 1:]) edges[:-1, 1:, 5] = np.maximum(nodes[:-1, 1:], nodes[1:, :-1]) edges[:-1, :, 6] = np.maximum(nodes[:-1, :], nodes[1:, :]) edges[:-1, :-1, 7] = np.maximum(nodes[:-1, :-1], nodes[1:, 1:])
This computation is fast and compact thanks to the rows/columns trick and the ability of Numpy to handle array slices. For instance,
1: means indices from 1 to the last, or
:-1 from 0 to the penultimate.
The last step is the computation of the distance map using the Dijkstra algorithm:
queue = PriorityQueue() map[source] = 0 queue.put((0, source)) while not queue.empty(): _, cell = queue.get() x, y = cell costs = map[x, y] + edges[x, y] # Top Left cellTo = (x - 1, y - 1) cost = int(costs) if map[cellTo] > cost: map[cellTo] = cost queue.put((cost, cellTo)) ...other directions...
This algorithm is, at the same time, simple and complex. It fits in a few lines but performs smart processing that leads to the distance map with linear complexity. Unfortunately, explaining this algorithm requires the introduction of graph theory, which is beyond the scope of this post: if you want to understand it, you can find many tutorials on the Internet.
Path computation: once we computed the distance map, we can get the shortest map to any cell of its area. We compute it in the
getPath() method of the
def getPath(self, target: Tuple[int, int]) -> \ Tuple[List[Tuple[int, int]], List[int]]: area, map = self.__area, self.__map target = (target - area, target - area) costs, path = ,  for i in range(100): cost = map[target] if cost == 0: break costs.append(cost) x, y = target path.append((x + area, y + area)) neighbors = np.delete(map[x - 1:x + 2, y - 1:y + 2].flatten(), 4) neighbors = neighbors[permutation] shift = index2shift[neighbors.argmin()] target = (x + shift, y + shift) return path, costs
We start by considering the cell we want to reach (in the
target argument) and walk through the distance map until we find a cell with zero cost. At each step, we add the current target to the path, choose a neighboring cell with the smallest value, and set the target to this cell. If the distance map is valid, this process always succeeds. However, if for some reason it is not the case, the walk could last forever: it is the reason why we use a for loop with a fixed number of steps (line 6). If it happens, the resulting path is wrong, but the game does not freeze.
Lines 13-15 compute the shift from the current location
x,y such as
x+shift,y+shift is a cell with the smallest value. To get this result, we first retrieve the neighboring values (line 13):
map[x - 1:x + 2, y - 1:y + 2] extracts the 3x3 values around the current cell,
flatten() turns this 2D array into a 1D array, and
np.delete(...,4) removes the fourth item (it corresponds to the current cell).
The relative cell locations of costs are: top-left, left, bottom-left, top, bottom, top-right, right, and bottom-right. If there are equal neighboring values, we want to select non-diagonal directions. To get this behavior, we change the order with the following array (line 14):
permutation = np.array([1, 3, 4, 6, 0, 2, 5, 7])
After line 14, the order is: left, top, bottom, right, top-left, bottom-left, top-right and bottom-right.
Finally, we use the following array to translate the index of the smallest value (line 15):
index2shift = [(-1, 0), (0, -1), (0, 1), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]
This trick leads to a shorter and faster code than many
Display cost numbers: we use the same trick as with the selection box. We consider a new range of 100 values in the selection layers, the first being
SelectionValue.NUMBER_FIRST and the last
SelectionValue.NUMBER_LAST. Then, we create as many corresponding tile numbers:
SelectionValue.NUMBER_FIRST is tile "0",
SelectionValue.NUMBER_FIRST+1 is tile "1", ...,
SelectionValue.NUMBER_LAST-1 is tile "99". We also add a new
showPath() method in the
SelectionLayer class that sets all the cells of a given path:
def showPath(self, path: List[Tuple[int, int]], costs: List[int]): self.clearNumbers() for cell, cost in zip(path, costs): value = SelectionValue.NUMBER_FIRST + cost if value >= SelectionValue.NUMBER_LAST: continue self.setValue(cell, value)
Once we set path cells using this method, we trigger a content change notification, and
SelectionComponent updates its rendering.
Play game mode: we create a new
PlayGameMode class, child of
DefaultGameMode, that handles most of the UI logic for selecting and moving a unit:
We capture the mouse click with the
worldCellClicked() event of
IComponentListener interface, as we did for editing the world. The
WorldComponent class triggers it when the player clicks on a world cell and provides the world cell coordinates. Depending on the mouse button and current selection, we call
Select a unit: the
selectUnit() method first updates the currently selected cell and unit (lines 2-3):
def __selectUnit(self, unit: Unit, cell: Tuple[int, int]): self.__selectedCell = cell self.__selectedUnit = unit self._selectionLayer.selectCell(cell) self._selectionLayer.notifyCellChanged(cell) x, y = cell radius = 31 area = (x - radius, y - radius, x + radius + 1, y + radius + 1) self.__distanceMap = DistanceMap(self.world, area) self.__distanceMap.compute(cell)
Then, it sets a box in the selection layer (line 4). The
selectCell() method of the
SelectionLayer class assign a
SelectionValue.SELECT to a cell of the selection layer. This assignment only changes the layer's content, as if it was game data, but does not necessarily lead to a visual update. As we did for other layer updates (in the game logic), we notify the cell change (line 5): the
SelectionComponent class receives it and redraws itself.
The end of the method builds a distance map where the source cell is that of the selected unit. First, lines 7-10 compute a box area around the unit: the size of this area should be large enough to handle moves of the fastest units (right now, there is no limit to unit speed, so the value is arbitrary). Then, lines 11-12 create and compute the distance map.
Move a unit: the
moveUnit() method creates a new
MoveUnitCommand instance, schedules it, and clears the current selection:
def __moveUnit(self, targetCell: Tuple[int, int]): command = MoveUnitCommand(self.__selectedCell, targetCell) self._logic.addCommand(command) self.__clearSelection()
MoveUnitCommand class moves a unit from one cell to another. It has the usual
execute() methods. The first one starts with many checks (not shown here) and computes the shortest path between the two cells:
def check(self, logic: Logic) -> bool: ...checks... fromX, fromY = self.__fromCell toX, toY = self.__toCell radius = 10 area = ( min(fromX, toX) - radius, min(fromY, toY) - radius, max(fromX, toX) + radius + 1, max(fromY, toY) + radius + 1 ) distanceMap = DistanceMap(world, area) distanceMap.compute(self.__fromCell) self.__path, costs = distanceMap.getPath(self.__toCell) return len(self.__path) != 0:
We first calculate an area that includes the path's beginning and end (lines 3-9). Note that we enlarge the area to handle the case of a detour. The shortest path computation is as we saw before; we store it in an attribute so we can use it in the
execute() method (lines 10-12). Finally, we return
True if the path is not empty (line 13).
execute() method updates unit position and schedules another command if the path is not over:
def execute(self, logic: Logic): unitsLayer = logic.world.units unit = unitsLayer.getUnit(self.__fromCell) unitsLayer.setUnit(self.__fromCell, CellValue.NONE) targetCell = self.__path[-1] unitsLayer.setUnit(targetCell, CellValue.UNITS_UNIT, unit) unitsLayer.notifyCellChanged(self.__fromCell) unitsLayer.notifyCellChanged(targetCell) if len(self.__path) > 1: command = MoveUnitCommand(targetCell, self.__toCell) logic.addCommand(command)
We first retrieve the unit at the starting location (lines 1-2). Then, we remove it from this location (line 4), get the following position in the path (line 5), put the unit in this new location (line 6), and notify that the two cells have changed (lines 7-8). Finally, if the path is not over (line 9), we schedule a new move unit command starting from the current unit location (lines 10-11).
This implementation means that the unit moves one cell per game epoch. Furthermore, since we compute a distance at each command check, the unit can follow a different path than the initial one if other cells in the world change during its move. Note that it is a game design choice: we could also move it directly to the final position using a single command.