In this article, I want to talk about one of the easiest ways to find paths for a two-dimensional map. I do not take into account the greedy search algorithm because of its simplicity and not optimality. Today we will talk about the algorithm for finding the shortest paths from one vertex of the graph to all the others, proposed by the Dutch scientist Edsger Wybe Dijkstra. Also, I will show you A* algorithm, based on Dijkstra.
In this article, I focus on adapting the algorithm to the problem of finding a path on a 2D map. General principles of the algorithm read here.
Let's imagine that we have a rectangular box, divided into an equal cell size. From each cell you can go in 8 directions:
- North (Up)
- Northeast (Up to right)
- East (Right)
- Southeast (Down to right)
- South (Down)
- Southwest (Down left)
- West (Left)
- Northwest (Up left)
Each cell has a passability parameter. That is, in order to stand on a cell, you need to spend a certain amount of energy.
| yx | 1 | 2 | 3 | 4 | 5 | 6 | x |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 1 | 2 | 2 | 3 | . |
| 2 | 2 | 3 | 2 | 1 | 2 | 3 | . |
| 3 | 9 | 9 | 9 | 2 | 1 | 9 | . |
| 4 | 1 | 2 | 2 | 3 | 3 | 2 | . |
| 5 | 1 | 1 | 2 | 3 | 4 | 2 | . |
| y | . | . | . | . | . | . | . |
For clarity, in this diagram, weights are indicated by numbers from 0 to 9.
Let us know our starting position and the point where we need to get. Our task is to find the most energy efficient route.
Let's assume that we have not spent any energy to get to the starting square.
First, let's create the traffic rules. Let's express this as a list of possible operations with coordinates:
SHIFTS = [
# Down
(-1, 0),
# Up
(1, 0),
# Right
(0, 1),
# Left
(0, -1),
# Up left
(-1, -1),
# Down left
(1, -1),
# Down right
(1, 1),
# Up rights
(-1, 1)
]Classically, the first coordinate is written x and the second y, but for the readability of the algorithm, it is proposed to swap them, since when considering a field as a list of lists, y is the first indexing parameter.
Now let's create a cell weights map. The weights will indicate the amount of energy that must be expended in order to stand on this cell.
WEIGHT_MAP = [
[1, 1, 2, 1, 3, 4, 2, 0, 1],
[2, 1, 2, 3, 2, 1, 2, 1, 1],
[3, 2, 1, 2, 3, 2, 3, 3, 3],
[1, 2, 1, 1, 9, 2, 3, 4, 1],
[2, 2, 2, 1, 9, 1, 1, 2, 1],
[5, 2, 1, 2, 4, 4, 5, 1, 2],
[9, 9, 1, 2, 1, 2, 1, 1, 1]
]Now let's think about it, the Dijkstra algorithm calculates the minimum cost of movement to each node in the graph. But we need to calculate the path, not the price. The thought comes to mind - every time the minimum weight on a node is updated, write down the node from which the check was made. This way we can unwind the path from end to beginning.
About connections in the graph. From the task it is clear that our graph will be undirected, that is, the links between the nodes have no direction. If node A and node B are connected, then you can move along this connection in both directions.
Based on the traffic rules, each node will have from 3 to 8 links. At the nodes bordering on the field, you will have to check for coordinates so as not to run into an indexing error in the array.
def dijkstra(start: tuple, weight_map: list, shifts: list) -> tuple:
# Generating route weights map.
field = [[None for x in row] for row in weight_map]
# Generating trace map. (Information to restore routes)
trace = [[None for x in row] for row in weight_map]
# Creating queue for nodes. Detected nods will appear here.
queue: list = []
# Here will appear checked nodes.
examined: set = set()
# Marking start point with zero weight.
field[start[0]][start[1]] = 0
# Adding start point to queue.
queue.append(start)
# While queue is not empty - process nodes.
while len(queue):
# Get current cords from the queue.
current_cords = queue.pop(0)
# If this cords ware examined - skip.
if current_cords in examined:
continue
# Getting current node calculated weight.
current_weigh = field[current_cords[0]][current_cords[1]]
# Adding this node to examined.
examined.add(current_cords)
# For each node connection:
for shift in shifts:
# Getting connected node cords.
cords = (current_cords[0] + shift[0], current_cords[1] + shift[1])
# If cords out of field range - continue. (For example on field border nodes)
if cords[0] not in range(0, len(field)) or cords[1] not in range(0, len(field[0])):
continue
# Checking if this node hasn't examined yet.
if cords not in examined:
# Getting connection weight.
weigh = weight_map[cords[0]][cords[1]]
# Adding connected not to the queue.
# We don't check if it is already in queue because of node examination check on each step in while loop.
queue.append(cords)
# If calculated weight is lower - assign new weight value.
if field[cords[0]][cords[1]] is None or field[cords[0]][cords[1]] > current_weigh + weigh:
field[cords[0]][cords[1]] = current_weigh + weigh
trace[cords[0]][cords[1]] = current_cords
return field, traceFunction arguments:
- start: tuple - Start cords | tuple(y, x).
- weight_map: list - Two dimensional list with connection weights.
- shifts: list - List with shifting tuples | tuple(y, x, weight).
The function returns a tuple from the map with the values of the minimum energy consumption to reach the cell and the map of the paths. From the path map, you can get the cheapest path to the selected cell.
So, in each cell of the path map, the coordinates of the cell from which we came and which is part of the shortest (in terms of energy) path are recorded. Here is the algorithm for getting the route:
def get_trace(position: tuple, trace_map: list) -> list:
trace = [position]
prev = position
# Creating trace chain.
while prev is not None:
trace.append(trace_map[prev[0]][prev[1]])
prev = trace_map[prev[0]][prev[1]]
return traceFunction arguments:
- position: tuple - Finish cell cords. tuple(y, x).
- trace_map: list - Trace map from dijkstra function.
So, we managed to find the shortest path between two points, but, at the same time, we calculated the paths to all cells on the map. This is not the most optimal algorithm in our situation, but it should give an understanding of how the paths are sought. For finding a path between two points, the Dijkstra-based algorithm called A* (AKA AStar) is more optimal.
The idea of the algorithm is that when traversing the graph, select the next points that are, potentially, closest to the goal. In order to turn the Dijkstra algorithm into the A* algorithm, it is necessary to change the queue so that it always returns the coordinates that have the smallest sum of the amount of energy already expended to reach this point and the calculated remaining energy from it to the goal.
To calculate the remaining distance from the coordinate to the place of arrival, we will use the Cartesian distance formula.
For python we will use sorted() function with key named parameter for sorting queue.
import math
def a_star(start: tuple, end: tuple, weight_map: list, shifts: list) -> list:
# Generating route weights map.
field = [[None for x in row] for row in weight_map]
# Generating trace map. (Information to restore routes)
trace = [[None for x in row] for row in weight_map]
# Creating queue for nodes. Detected nods will appear here.
queue: list = []
# Here will appear checked nodes.
examined: set = set()
# Marking start point with zero weight.
field[start[0]][start[1]] = 0
# Adding start point to queue.
queue.append(start)
# While queue is not empty - process nodes.
while len(queue):
# Get current cords from the queue.
current_cords = queue.pop(0)
# If we have reached destination - stop.
if current_cords == end:
return get_trace(end, trace)
# If this cords ware examined - skip.
if current_cords in examined:
continue
# Getting current node calculated weight.
current_weigh = field[current_cords[0]][current_cords[1]]
# Adding this node to examined.
examined.add(current_cords)
# For each node connection:
for shift in shifts:
# Getting connected node cords.
cords = (current_cords[0] + shift[0], current_cords[1] + shift[1])
# If cords out of field range - continue. (For example on field border nodes)
if cords[0] not in range(0, len(field)) or cords[1] not in range(0, len(field[0])):
continue
# Checking if this node hasn't examined yet.
if cords not in examined:
# Getting connection weight.
weigh = weight_map[cords[0]][cords[1]]
# Adding connected not to the queue.
# We don't check if it is already in queue because of node examination check on each step in while loop.
queue.append(cords)
# If calculated weight is lower - assign new weight value.
if field[cords[0]][cords[1]] is None or field[cords[0]][cords[1]] > current_weigh + weigh:
field[cords[0]][cords[1]] = current_weigh + weigh
trace[cords[0]][cords[1]] = current_cords
# Sort queue by sum of cord weight and expected remaining weight (for example, Cartesian distance)
queue = sorted(queue, key=lambda cord: math.dist(cord, end) + field[cord[0]][cord[1]])
return get_trace(end, trace)Function arguments:
- start: tuple - Start cords | tuple(y, x).
- end: tuple - Destination point cords | tuple(y, x).
- weight_map: list - Two dimensional list with connection weights.
- shifts: list - List with shifting tuples | tuple(y, x, weight).
I tried using these algorithms to find the distance on a spiral map, here is the result. Green symbols - path, blue symbol - end of path. The numbers indicate the weights of the nodes.
We figured out how to adapt the Dijkstra algorithm for 2D maps and figured out the A* search algorithm.
Thanks for your attention : )
Author: Danil Andreev
