Moving from point A to point B is the prime requirement for many games—whether it is a strategic tactic-based RPG (role-playing game) like Warcraft III or one that’s as simple as Snakes and Ladders. The source-to-destination navigation sometimes requires more intelligence from your character than you believe,it needs to find the path with ease. You can’t have your characters walking through a wall or bumping into a car while playing, can you?
This is where pathfinding algorithms are used. Pathfinding is the basic building block for most games. Players have to reach a destination by moving around blocks, cars, rivers, and prisons. The algorithm ensures that the character not only avoids the obstacles but also gets to the destination by using the shortest path.
Games like Warcraft III use the A* pathfinding algorithm, where the protagonist is not only expected to reach his destination by the shortest path. But also move around the castles, not get in through the huts, dungeon, or walk through a dragon on its way.
A* algorithm (Pronounced A-star algorithm)
The A* algorithm is the fastest graph search algorithm that finds the path that costs the least from source node to goal node. (A node can be hexagon, square or circle, etc.)
In the gaming world, a node graph is a map of your gaming world, and the path that costs the least is the shortest path; A* traverses a node graph and finds the path that costs the least
A* algorithm has properties of both Dijkstra and Best-first search. Unlike DFS and BFS, the A* algorithm selects the node which looks most promising instead of guessing the next node.
The cost function
The cost of node F is calculated as:
F=G+H
- G is the cost that is required to reach a particular node from the source node.
- H often termed the Heuristic Value (a heuristic, informally, is like an algorithm, which helps us determine the answer but not in a definite series of steps).It is the estimated cost from one square on the grid to the other square, which is the goal on the grid. H being heuristic,can never be perfect and is usually based on assumptions.
Here we implemented the Euclidean distance for the cost function. The Manhattan and the Chebyshev functions are also shown in case required.
1 2 3 4 5 6 7 8 9 10 11 | def estimate(self, xDest, yDest): """ Estimation function for the remaining distance to the goal. """ dx = xDest - self.x_position dy = yDest - self.y_position # Euclidian Distance d = math.sqrt(dx ** 2 + dy ** 2) # Manhattan distance: d = abs(xd) + abs(yd) # Chebyshev distance: d = max(abs(xd), abs(yd)) return d |
Let’s look at the following example:
Assume that the graph or table above is a game grid where our protagonist needs to move from the source node of the grid to the goal node.
We have implemented the node as coordinates depending on the type of object that is passed. The attributes that it will have are the position, distance, priority and the possible directions that the node object can move. These attributes are managed through the updatePriority and nextMove methods. The implementation is shown below. You might notice that the cost function shown above is the estimate method of the node object.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | class Node: """ for handling the individual nodes or spaces in the given map """ def __init__(self, coordinates, distance, priority, possible_directions): if isinstance(coordinates, Shift): self.x_position = coordinates.change_in_x self.y_position = coordinates.change_in_y elif isinstance(coordinates, Node): self.x_position = coordinates.x_position self.y_position = coordinates.y_position else: self.x_position = coordinates[0] self.y_position = coordinates[1] self.distance = distance self.priority = priority self.possible_directions = possible_directions def __lt__(self, other): """ comparison method for priority queue """ return self.priority < other.priority def estimate(self, xDest, yDest): """ Estimation function for the remaining distance to the goal. """ dx = xDest - self.x_position dy = yDest - self.y_position # Euclidian Distance d = math.sqrt(dx ** 2 + dy ** 2) # Manhattan distance: d = abs(xd) + abs(yd) # Chebyshev distance: d = max(abs(xd), abs(yd)) return d def updatePriority(self, xDest, yDest): """ employs the a-star heuristic """ self.priority = self.distance + self.estimate(xDest, yDest) * 10 def nextMove(self, d): """ give higher priority to going straight instead of diagonally d: direction to move """ if self.possible_directions == 8 and d % 2 != 0: self.distance += 14 else: self.distance += 10 |
Let’s consider that every block to the left, right, top, and bottom of the selected (parent) node is at a distance of 1 unit. That means that each block is at a diagonal distance of ?2, which is equal to 1.4.
To make things easier, multiply each value by 10, thereby converting the distance to 10 and 14 for adjacent and diagonal nodes, respectively.
Let’s make 2 lists of open and closed nodes. Any node that is selected for the path is moved to the closed node list. Any node that is not selected is considered to be an open node.
Assume that our protagonist is at the location source. Every block surrounding the location source has a certain F cost, which is the obtained by summing G (which is the distance from the source node) and H (which is the distance from the goal node).
For example, a block that is diagonally opposite to the source and marked in red would have a G value of 14 (1.4 * 10), an H value of 10 (2*1.4*10 +10), and an F value of 52. You can compute the values for all other blocks similarly.
After we have the cost of all the blocks, select the block which has the lowest cost. In this case, F=52 and mark it as closed.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | def a_chosen_direction(x, possible_directions): return (x + possible_directions // 2) % possible_directions def generate_path(possible_directions, dir_map, dx, dy, xA, yA, x, y): """ generate the path from finish to start by following the possible_directions """ path = "" while not (x == xA and y == yA): j = dir_map[y][x] c = str(a_chosen_direction(j, possible_directions)) path = c + path x += dx[j] y += dy[j] return path |
Repeat the entire process with all the open nodes (nodes which are not selected), and select the block with the lowest F value as you head towards your goal.
Once you reach the goal, the path traversed is the lowest possible path for a given matrix. This process has been represented in red and purple for the problem above.
However, in a game, the path is not so simple. It is usually filled with hurdles and areas that the character is not supposed to walk in.
Assume that, in a game, the section in black is the area which cannot be traversed by the player. We will use the same approach that we used in the previous example while keeping in mind that there is now a black node that the player cannot traverse.
1 2 3 | def collision_with_obstacle(x_y_shift, the_map, closed_nodes_map): return any((the_map[x_y_shift.change_in_y][x_y_shift.change_in_x] == 1, closed_nodes_map[x_y_shift.change_in_y][x_y_shift.change_in_x] == 1) |
Select the Source node and calculate the F cost of all its surrounding nodes (F=G+H). Now select the node with the smallest value, which in this case is 48. Once you select the node with the smallest value, find the F values of all its surrounding nodes. The process of selecting the smallest node continues.
But what if two nodes have the same values, like F=48, in the table above?
In such cases, you must select any one of the nodes with a similar F value and proceed with finding F values of its surrounding nodes.
Select the node with the smallest F value and carry on along the path. You will soon reach the goal node by the shortest path possible.
Summary of A * Algorithm
- Select the starting point and put it in the open list.
- Find the F cost to the current node.
- Mark it in the closed list.
- For each of the 8 nodes adjacent to the current node, do the following:
- If the node is in the closed list or cannot be walked through, then ignore it.
- If it is not open, then put it on the open list and find the G, H, and F values for it.
- If it is in the open list, then check if the path has a better cost and make it the parent node.
- Stop when your target node is marked as closed, or there are no more nodes to be marked as open.
At this point, you should have a decent conceptual understanding of how the A* pathfinding algorithm can be adapted to a platform. This article is not a definitive work on the subject, rather it is a beginner’s guide of sorts.
Remember that A* only finds the most optimal path. The graph search is only one piece of the puzzle. A* does not handle things like object movement, map changes, etc.
Why don’t you create your own 2D game with movement and hone your skills as your game evolves with better algorithms?
If you enjoy algorithms as much as I do, read my other article on the Elo rating algorithm.
PS: For code enthusiasts, here is the python code to the A* algorithm.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 | # -*- coding: utf-8 -*- """ # A* Shortest Path Algorithm # http://en.wikipedia.org/wiki/A* """ from __future__ import print_function from heapq import heappush, heappop # for priority queue import math import time import random # for compatibility with both py2 and py3 try: input = raw_input except NameError: pass class Node: """ for handling the individual nodes or spaces in the given map """ def __init__(self, coordinates, distance, priority, possible_directions): if isinstance(coordinates, Shift): self.x_position = coordinates.change_in_x self.y_position = coordinates.change_in_y elif isinstance(coordinates, Node): self.x_position = coordinates.x_position self.y_position = coordinates.y_position else: self.x_position = coordinates[0] self.y_position = coordinates[1] self.distance = distance self.priority = priority self.possible_directions = possible_directions def __lt__(self, other): """ comparison method for priority queue """ return self.priority < other.priority def estimate(self, xDest, yDest): """ Estimation function for the remaining distance to the goal. """ dx = xDest - self.x_position dy = yDest - self.y_position # Euclidian Distance d = math.sqrt(dx ** 2 + dy ** 2) # Manhattan distance: d = abs(xd) + abs(yd) # Chebyshev distance: d = max(abs(xd), abs(yd)) return d def updatePriority(self, xDest, yDest): """ employs the a-star heuristic """ self.priority = self.distance + self.estimate(xDest, yDest) * 10 def nextMove(self, d): """ give higher priority to going straight instead of diagonally d: direction to move """ if self.possible_directions == 8 and d % 2 != 0: self.distance += 14 else: self.distance += 10 def a_chosen_direction(x, possible_directions): return (x + possible_directions // 2) % possible_directions def generate_path(possible_directions, dir_map, dx, dy, xA, yA, x, y): """ generate the path from finish to start by following the possible_directions """ path = "" while not (x == xA and y == yA): j = dir_map[y][x] c = str(a_chosen_direction(j, possible_directions)) path = c + path x += dx[j] y += dy[j] return path def outside_map(x_y_shift, horizontal_size_of_map, vertical_size_of_map): return any((x_y_shift.change_in_x < 0, x_y_shift.change_in_y < 0, x_y_shift.change_in_x > horizontal_size_of_map - 1, x_y_shift.change_in_y > vertical_size_of_map - 1)) class Shift: """ x -> change in x y -> change in y """ def __init__(self, x, y): self.change_in_x = x self.change_in_y = y def collision_with_obstacle(x_y_shift, the_map, closed_nodes_map): return any((the_map[x_y_shift.change_in_y][x_y_shift.change_in_x] == 1, closed_nodes_map[x_y_shift.change_in_y][x_y_shift.change_in_x] == 1)) def generate_a_child_node(x_y_shift, node, direction, finish_coord): child_node = Node(x_y_shift, node.distance, node.priority, node.possible_directions) child_node.nextMove(direction) xB, yB = finish_coord child_node.updatePriority(xB, yB) return child_node def pathFind(the_map, horizontal_size_of_map, vertical_size_of_map, possible_directions, dx, dy, xA, yA, xB, yB): """ A-star algorithm. The path returned will be a string of digits of direction """ finish_coord = (xB, yB) start_coord = (xA, yA) row = [0] * horizontal_size_of_map # map of closed (tried-out) nodes closed_nodes_map = [list(row) for _ in range(vertical_size_of_map)] # map of open (not-yet-tried) nodes open_nodes_map = [list(row) for _ in range(vertical_size_of_map)] # map of possible_directions dir_map = [list(row) for _ in range(vertical_size_of_map)] priority_queues = [[], []] # priority queues of open (not-yet-tried) nodes priority_queue_indx = 0 # create the start node and push into list of open nodes node = Node(start_coord, 0, 0, possible_directions=possible_directions) node.updatePriority(xB, yB) heappush(priority_queues[priority_queue_indx], node) open_nodes_map[yA][xA] = node.priority # mark it on the open nodes map # A* search while len(priority_queues[priority_queue_indx]) > 0: # get the current node with the highest priority # from the list of open nodes top_node = priority_queues[priority_queue_indx][0] node = Node(top_node, top_node.distance, top_node.priority, possible_directions=possible_directions) x = node.x_position y = node.y_position heappop(priority_queues[priority_queue_indx]) # remove the node from the open list open_nodes_map[y][x] = 0 closed_nodes_map[y][x] = 1 # mark it on the closed nodes map # quit searching when the goal is reached if node.estimate(xB, yB) == 0: if node.x_position == xB and node.y_position == yB: return generate_path(possible_directions, dir_map, dx, dy, xA, yA, node.x_position, node.y_position) # generate moves (child nodes) in all possible possible_directions for direction in range(possible_directions): change_in_x = node.x_position + dx[direction] change_in_y = node.y_position + dy[direction] x_y_shift = Shift(change_in_x, change_in_y) if not (outside_map(x_y_shift, horizontal_size_of_map, vertical_size_of_map) or collision_with_obstacle(x_y_shift, the_map, closed_nodes_map)): child_node = generate_a_child_node(x_y_shift, node, direction, finish_coord) # if it is not in the open list then add into that if open_nodes_map[x_y_shift.change_in_y][x_y_shift.change_in_x] == 0: open_nodes_map[x_y_shift.change_in_y][x_y_shift.change_in_x] = child_node.priority heappush(priority_queues[priority_queue_indx], child_node) # mark its parent node direction dir_map[x_y_shift.change_in_y][x_y_shift.change_in_x] = a_chosen_direction(direction, possible_directions=possible_directions) elif open_nodes_map[x_y_shift.change_in_y][x_y_shift.change_in_x] > child_node.priority: # update the priority open_nodes_map[x_y_shift.change_in_y][x_y_shift.change_in_x] = child_node.priority # update the parent direction dir_map[x_y_shift.change_in_y][x_y_shift.change_in_x] = a_chosen_direction(direction, possible_directions=possible_directions) # replace the node by emptying one priority_queues to the other one # except the node to be replaced will be ignored and # the new node will be pushed in instead while not (priority_queues[priority_queue_indx][0].x_position == x_y_shift.change_in_x and priority_queues[priority_queue_indx][0].y_position == x_y_shift.change_in_y): heappush(priority_queues[1 - priority_queue_indx], priority_queues[priority_queue_indx][0]) heappop(priority_queues[priority_queue_indx]) heappop(priority_queues[priority_queue_indx]) # remove the target node # empty the larger size priority queue # to the smaller one if len(priority_queues[priority_queue_indx]) > len(priority_queues[1 - priority_queue_indx]): priority_queue_indx = 1 - priority_queue_indx while len(priority_queues[priority_queue_indx]) > 0: heappush(priority_queues[1-priority_queue_indx], priority_queues[priority_queue_indx][0]) heappop(priority_queues[priority_queue_indx]) priority_queue_indx = 1 - priority_queue_indx heappush(priority_queues[priority_queue_indx], child_node) # add the better node instead return '' # if no route found if __name__ == "__main__": possible_directions = 8 # number of possible directions to move on the map if possible_directions == 4: dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] elif possible_directions == 8: dx = [1, 1, 0, -1, -1, -1, 0, 1] dy = [0, 1, 1, 1, 0, -1, -1, -1] horizontal_size_of_map = 100 vertical_size_of_map = 100 the_map = [] row = [0] * horizontal_size_of_map for i in range(vertical_size_of_map): # create empty map the_map.append(list(row)) # fillout the map with a '+' pattern for x in range(horizontal_size_of_map // 8, horizontal_size_of_map * 7 // 8): the_map[vertical_size_of_map // 2][x] = 1 for y in range(vertical_size_of_map//8, vertical_size_of_map * 7 // 8): the_map[y][horizontal_size_of_map // 2] = 1 # randomly select start and finish locations from a list sf = [] sf.append((0, 0, horizontal_size_of_map - 1, vertical_size_of_map - 1)) sf.append((0, vertical_size_of_map - 1, horizontal_size_of_map - 1, 0)) sf.append((horizontal_size_of_map // 2 - 1, vertical_size_of_map // 2 - 1, horizontal_size_of_map // 2 + 1, vertical_size_of_map // 2 + 1)) sf.append((horizontal_size_of_map // 2 - 1, vertical_size_of_map // 2 + 1, horizontal_size_of_map // 2 + 1, vertical_size_of_map // 2 - 1)) sf.append((horizontal_size_of_map // 2 - 1, 0, horizontal_size_of_map // 2 + 1, vertical_size_of_map - 1)) sf.append((horizontal_size_of_map // 2 + 1, vertical_size_of_map - 1, horizontal_size_of_map // 2 - 1, 0)) sf.append((0, vertical_size_of_map // 2 - 1, horizontal_size_of_map - 1, vertical_size_of_map // 2 + 1)) sf.append((horizontal_size_of_map - 1, vertical_size_of_map // 2 + 1, 0, vertical_size_of_map // 2 - 1)) (xA, yA, xB, yB) = random.choice(sf) print('Map size (X,Y): ', horizontal_size_of_map, vertical_size_of_map) print('Start: ', xA, yA) print('Finish: ', xB, yB) t = time.time() route = pathFind(the_map, horizontal_size_of_map, vertical_size_of_map, possible_directions, dx, dy, xA, yA, xB, yB) print('Time to generate the route (seconds): ', time.time() - t) print('Route:') print(route) # mark the route on the map if len(route) > 0: x = xA y = yA the_map[y][x] = 2 for i in range(len(route)): j = int(route[i]) x += dx[j] y += dy[j] the_map[y][x] = 3 the_map[y][x] = 4 # display the map with the route added print('Map:') for y in range(vertical_size_of_map): for x in range(horizontal_size_of_map): xy = the_map[y][x] if xy == 0: print('.' ,end="") # space elif xy == 1: print('O' ,end="") # obstacle elif xy == 2: print('S', end="") # start elif xy == 3: print('R', end="") # route elif xy == 4: print('F', end="") # finish print() |
Leave a Reply