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.

In the `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 `SelectionLayer`

class:

```
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:

```
selectionLayer.selectCell(cell)
selectionLayer.notifyCellChanged(cell)
```

**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 `SelectionComponent`

class:

```
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 `MoveCost`

enum:

```
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[2] - self.__area[0]
self.__height = self.__area[3] - self.__area[1]
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 `width-2`

and `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 `nodes`

and `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 `INFINITE`

:

```
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[0] - area[0], source[1] - area[1])
if source[0] < 0 or source[0] >= self.__width \
or source[1] < 0 or source[1] >= 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`

array:

```
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[0])
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 `DistanceMap`

class:

```
def getPath(self, target: Tuple[int, int]) -> \
Tuple[List[Tuple[int, int]], List[int]]:
area, map = self.__area, self.__map
target = (target[0] - area[0], target[1] - area[1])
costs, path = [], []
for i in range(100):
cost = map[target]
if cost == 0:
break
costs.append(cost)
x, y = target
path.append((x + area[0], y + area[1]))
neighbors = np.delete(map[x - 1:x + 2, y - 1:y + 2].flatten(), 4)
neighbors = neighbors[permutation]
shift = index2shift[neighbors.argmin()]
target = (x + shift[0], y + shift[1])
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[0],y+shift[1]`

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 `if`

...`elif`

... blocks.

**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 `selectUnit()`

, `moveUnit()`

or `clearSelection()`

.

**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()
```

The `MoveUnitCommand`

class moves a unit from one cell to another. It has the usual `check()`

and `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).

The `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.