June 22, 2017 at 10:00Implementation of Algorithm A *
- Transfer
This article is a continuation of my introduction to the A * algorithm . In it, I showed how breadth-first search, Dijkstra's algorithm, greedy search for the best first match, and A * are implemented. I tried to simplify the explanation as much as possible.
Graph search is a family of similar algorithms. There are many variations of algorithms and their implementations. Treat the code in this article as a starting point, not a final version of the algorithm, suitable for all situations.
1. Python implementation
Below I will explain most of the code. The implementation.py file is slightly wider. The code uses Python 3 , so if you use Python 2, then you will need to change the call
super()and function printto analogues from Python 2.1.1 Wide search
Let's implement a breadth-first search in Python. The first article shows the Python code for the search algorithm, but we also need to determine the graph that we will work with. Here are the abstractions I use:
Graph : a data structure that can report the neighbors of each of the points (see this tutorial )
Points (locations) : a simple value (int, string, tuple, etc.) that marks the points in the
Search column : an algorithm that receives a graph, a start point and (optionally) an end point that calculates useful information (visited, pointer to the parent element, distance) for some or all points.
Queue : data structure used by the search algorithm to select the order of processing points.
In the first article, I mainly looked at search . In this article, I will explain everything else necessary to create a fully working program. Let's start with the graph :
class SimpleGraph:
def __init__(self):
self.edges = {}
def neighbors(self, id):
return self.edges[id]Yes, and that’s all we need! You may ask: where is the node object (Node)? Answer: I rarely use a node object. It seems to me more simple to use integers, strings or tuples as points, and then use arrays or hash tables to take points as indices.
Note that the edges have a direction : we can have an edge from A to B, but not edges from B to A. In game cards, the edges are mostly bidirectional, but sometimes there are one-way doors or jumps from ledges, which are designated as directed edges. Let's create an example graph where the points will be indicated by the letters AE.
For each point, you need a list of points to which it leads:
example_graph = SimpleGraph()
example_graph.edges = {
'A': ['B'],
'B': ['A', 'C', 'D'],
'C': ['A'],
'D': ['E', 'A'],
'E': ['B']
}Before using the search algorithm, we need to set the queue :
import collections
class Queue:
def __init__(self):
self.elements = collections.deque()
def empty(self):
return len(self.elements) == 0
def put(self, x):
self.elements.append(x)
def get(self):
return self.elements.popleft()This queue class is just a wrapper for an inline class
collections.deque. You can use it directly in your code deque. Let's try to use our graph example with this queue and the breadth-first search code from the previous article:
from implementation import *
def breadth_first_search_1(graph, start):
# печать того, что мы нашли
frontier = Queue()
frontier.put(start)
visited = {}
visited[start] = True
while not frontier.empty():
current = frontier.get()
print("Visiting %r" % current)
for next in graph.neighbors(current):
if next not in visited:
frontier.put(next)
visited[next] = True
breadth_first_search_1(example_graph, 'A')Visiting 'A'
Visiting 'B'
Visiting 'C'
Visiting 'D'
Visiting 'E'Grids can also be expressed as graphs. Now I will define a new graph
SquareGrid , with a tuple of (int, int) points . Instead of storing the edges explicitly, we will compute them in a function neighbors.class SquareGrid:
def __init__(self, width, height):
self.width = width
self.height = height
self.walls = []
def in_bounds(self, id):
(x, y) = id
return 0 <= x < self.width and 0 <= y < self.height
def passable(self, id):
return id not in self.walls
def neighbors(self, id):
(x, y) = id
results = [(x+1, y), (x, y-1), (x-1, y), (x, y+1)]
if (x + y) % 2 == 0: results.reverse() # ради эстетики
results = filter(self.in_bounds, results)
results = filter(self.passable, results)
return resultsLet's test it on the first grid from the previous article:
from implementation import *
g = SquareGrid(30, 15)
g.walls = DIAGRAM1_WALLS # список long, [(21, 0), (21, 2), ...]
draw_grid(g). . . . . . . . . . . . . . . . . . . . . ####. . . . . . .
. . . . . . . . . . . . . . . . . . . . . ####. . . . . . .
. . . . . . . . . . . . . . . . . . . . . ####. . . . . . .
. . . ####. . . . . . . . . . . . . . . . ####. . . . . . .
. . . ####. . . . . . . . ####. . . . . . ####. . . . . . .
. . . ####. . . . . . . . ####. . . . . . ##########. . . .
. . . ####. . . . . . . . ####. . . . . . ##########. . . .
. . . ####. . . . . . . . ####. . . . . . . . . . . . . . .
. . . ####. . . . . . . . ####. . . . . . . . . . . . . . .
. . . ####. . . . . . . . ####. . . . . . . . . . . . . . .
. . . ####. . . . . . . . ####. . . . . . . . . . . . . . .
. . . ####. . . . . . . . ####. . . . . . . . . . . . . . .
. . . . . . . . . . . . . ####. . . . . . . . . . . . . . .
. . . . . . . . . . . . . ####. . . . . . . . . . . . . . .
. . . . . . . . . . . . . ####. . . . . . . . . . . . . . . To recreate the paths, we need to save the point from which we came, so I renamed
visited(True / False) to came_from(point):from implementation import *
def breadth_first_search_2(graph, start):
# возвращает "came_from"
frontier = Queue()
frontier.put(start)
came_from = {}
came_from[start] = None
while not frontier.empty():
current = frontier.get()
for next in graph.neighbors(current):
if next not in came_from:
frontier.put(next)
came_from[next] = current
return came_from
g = SquareGrid(30, 15)
g.walls = DIAGRAM1_WALLS
parents = breadth_first_search_2(g, (8, 7))
draw_grid(g, width=2, point_to=parents, start=(8, 7))→ → → → ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← ← ← ####↓ ↓ ↓ ↓ ↓ ↓ ↓
→ → → → → ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← ← ← ← ####↓ ↓ ↓ ↓ ↓ ↓ ↓
→ → → → → ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← ← ← ← ← ####→ ↓ ↓ ↓ ↓ ↓ ↓
→ → ↑ ####↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← ← ← ← ← ← ####→ → ↓ ↓ ↓ ↓ ↓
→ ↑ ↑ ####→ ↓ ↓ ↓ ↓ ↓ ↓ ← ####↑ ← ← ← ← ← ####→ → → ↓ ↓ ↓ ↓
↑ ↑ ↑ ####→ → ↓ ↓ ↓ ↓ ← ← ####↑ ↑ ← ← ← ← ##########↓ ↓ ↓ ←
↑ ↑ ↑ ####→ → → ↓ ↓ ← ← ← ####↑ ↑ ↑ ← ← ← ##########↓ ↓ ← ←
↑ ↑ ↑ ####→ → → A ← ← ← ← ####↑ ↑ ↑ ↑ ← ← ← ← ← ← ← ← ← ← ←
↓ ↓ ↓ ####→ → ↑ ↑ ↑ ← ← ← ####↑ ↑ ↑ ↑ ↑ ← ← ← ← ← ← ← ← ← ←
↓ ↓ ↓ ####→ ↑ ↑ ↑ ↑ ↑ ← ← ####↑ ↑ ↑ ↑ ↑ ↑ ← ← ← ← ← ← ← ← ←
↓ ↓ ↓ ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ← ← ← ← ← ← ←
→ ↓ ↓ ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ← ← ← ← ← ←
→ → → → → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ← ← ← ← ←
→ → → → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ← ← ← ←
→ → → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ← ← ← In some implementations, by creating a Node object, internal storage is used to store
came_fromother values for each node in the graph. Instead, I decided to use external storage , creating a single hash table to store came_fromall the nodes in the graph. If you know that the points on your map have integer indices, then there is another option - use an came_fromarray for storage .1.2 Early exit
Repeating the code of the previous article, we just need to add the if construct to the main loop . This check is optional for the breadth-first search and Dijkstra's algorithm, but required for the greedy search for the best first match and A *:
from implementation import *
def breadth_first_search_3(graph, start, goal):
frontier = Queue()
frontier.put(start)
came_from = {}
came_from[start] = None
while not frontier.empty():
current = frontier.get()
if current == goal:
break
for next in graph.neighbors(current):
if next not in came_from:
frontier.put(next)
came_from[next] = current
return came_from
g = SquareGrid(30, 15)
g.walls = DIAGRAM1_WALLS
parents = breadth_first_search_3(g, (8, 7), (17, 2))
draw_grid(g, width=2, point_to=parents, start=(8, 7), goal=(17, 2)). → → → ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← . . . . ####. . . . . . .
→ → → → → ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← . . . ####. . . . . . .
→ → → → → ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← Z . . . ####. . . . . . .
→ → ↑ ####↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← ← ← ← . . ####. . . . . . .
. ↑ ↑ ####→ ↓ ↓ ↓ ↓ ↓ ↓ ← ####↑ ← ← . . . ####. . . . . . .
. . ↑ ####→ → ↓ ↓ ↓ ↓ ← ← ####↑ ↑ . . . . ##########. . . .
. . . ####→ → → ↓ ↓ ← ← ← ####↑ . . . . . ##########. . . .
. . . ####→ → → A ← ← ← ← ####. . . . . . . . . . . . . . .
. . . ####→ → ↑ ↑ ↑ ← ← ← ####. . . . . . . . . . . . . . .
. . ↓ ####→ ↑ ↑ ↑ ↑ ↑ ← ← ####. . . . . . . . . . . . . . .
. ↓ ↓ ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ####. . . . . . . . . . . . . . .
→ ↓ ↓ ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####. . . . . . . . . . . . . . .
→ → → → → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####. . . . . . . . . . . . . . .
→ → → → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####. . . . . . . . . . . . . . .
. → → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####. . . . . . . . . . . . . . . As we can see, the algorithm stops when it finds a target
Z.1.3 Dijkstra's Algorithm
This adds complexity to the algorithm, because we will begin to process the points in an improved order, and not just “first in, first out”. What principle will we use?
- The count needs to know the cost of movement.
- Queues need to return nodes in a different order.
- The search should track this value in the graph and pass it to the queue.
1.3.1 Count with weights
I am going to add a function
cost(from_node, to_node)that tells us the cost of moving from a point from_nodeto its neighbor to_node. In this map with the forest, I decided that the movement will depend only on to_node, but there are other types of movement that use both nodes . An alternative to implementation is to merge it into a function neighbors.class GridWithWeights(SquareGrid):
def __init__(self, width, height):
super().__init__(width, height)
self.weights = {}
def cost(self, from_node, to_node):
return self.weights.get(to_node, 1)1.3.2 Priority Queue
A priority queue associates with each element a number called a “priority”. When the item returns, it selects the item with the smallest number.
insert : adds the item to the
remove queue : removes the item with the smallest number
reprioritize : (optional) changes the priority of the existing item to a lower number.
Here's a reasonably fast priority queue that uses a binary heap but is not supported by reprioritize. To get the correct order, we use a tuple (priority, element). When you insert an item that is already in the queue, we get a duplicate. I will explain why this suits us in the Optimization section.
import heapq
class PriorityQueue:
def __init__(self):
self.elements = []
def empty(self):
return len(self.elements) == 0
def put(self, item, priority):
heapq.heappush(self.elements, (priority, item))
def get(self):
return heapq.heappop(self.elements)[1]1.3.3 Search
There is a tricky moment of implementation here: since we add the cost of movement, that is, the probability of a repeated visit to a point with a better one
cost_so_far. This means that the line if next not in came_fromwill not work. Instead, we need to check if the cost has decreased since the last visit. (In the original version of the article, I did not check this, but my code worked anyway. I wrote notes about this error .) This map with the forest was taken from the previous article .
def dijkstra_search(graph, start, goal):
frontier = PriorityQueue()
frontier.put(start, 0)
came_from = {}
cost_so_far = {}
came_from[start] = None
cost_so_far[start] = 0
while not frontier.empty():
current = frontier.get()
if current == goal:
break
for next in graph.neighbors(current):
new_cost = cost_so_far[current] + graph.cost(current, next)
if next not in cost_so_far or new_cost < cost_so_far[next]:
cost_so_far[next] = new_cost
priority = new_cost
frontier.put(next, priority)
came_from[next] = current
return came_from, cost_so_farAfter the search, you need to build the path:
def reconstruct_path(came_from, start, goal):
current = goal
path = [current]
while current != start:
current = came_from[current]
path.append(current)
path.append(start) # необязательно
path.reverse() # необязательно
return pathAlthough paths are best understood as a sequence of edges, it is more convenient to store as a sequence of nodes. To create a path, start from the end and follow the map
came_frompointing to the previous node. When we reach the beginning, the job is done. This is the return path, so in the end reconstruct_pathwe call reverse()if we need to store it in direct sequence. In fact, sometimes it’s more convenient to store the path in reverse. In addition, it is sometimes convenient to store the starting node in the list. Let's try:
from implementation import *
came_from, cost_so_far = dijkstra_search(diagram4, (1, 4), (7, 8))
draw_grid(diagram4, width=3, point_to=came_from, start=(1, 4), goal=(7, 8))
print()
draw_grid(diagram4, width=3, number=cost_so_far, start=(1, 4), goal=(7, 8))
print()
draw_grid(diagram4, width=3, path=reconstruct_path(came_from, start=(1, 4), goal=(7, 8)))↓ ↓ ← ← ← ← ← ← ← ←
↓ ↓ ← ← ← ↑ ↑ ← ← ←
↓ ↓ ← ← ← ← ↑ ↑ ← ←
↓ ↓ ← ← ← ← ← ↑ ↑ .
→ A ← ← ← ← . . . .
↑ ↑ ← ← ← ← . . . .
↑ ↑ ← ← ← ← ← . . .
↑ #########↑ ← ↓ . . .
↑ #########↓ ↓ ↓ Z . .
↑ ← ← ← ← ← ← ← ← .
5 4 5 6 7 8 9 10 11 12
4 3 4 5 10 13 10 11 12 13
3 2 3 4 9 14 15 12 13 14
2 1 2 3 8 13 18 17 14 .
1 A 1 6 11 16 . . . .
2 1 2 7 12 17 . . . .
3 2 3 4 9 14 19 . . .
4 #########14 19 18 . . .
5 #########15 16 13 Z . .
6 7 8 9 10 11 12 13 14 .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
@ @ . . . . . . . .
@ . . . . . . . . .
@ . . . . . . . . .
@ #########. . . . . .
@ #########. . @ @ . .
@ @ @ @ @ @ @ . . . The line
if next not in cost_so_far or new_cost < cost_so_far[next]can be simplified to if new_cost < cost_so_far.get(next, Infinity), but I did not want to explain get()Python in the last article, so I left it as it is. It can also be used collections.defaultdictwith the default infinity value.1.4 Search A *
Both the greedy search for the best first match and A * use a heuristic function. The only difference is that A * uses both heuristics and ordering from Dijkstra's algorithm. Here I will show A *.
def heuristic(a, b):
(x1, y1) = a
(x2, y2) = b
return abs(x1 - x2) + abs(y1 - y2)
def a_star_search(graph, start, goal):
frontier = PriorityQueue()
frontier.put(start, 0)
came_from = {}
cost_so_far = {}
came_from[start] = None
cost_so_far[start] = 0
while not frontier.empty():
current = frontier.get()
if current == goal:
break
for next in graph.neighbors(current):
new_cost = cost_so_far[current] + graph.cost(current, next)
if next not in cost_so_far or new_cost < cost_so_far[next]:
cost_so_far[next] = new_cost
priority = new_cost + heuristic(goal, next)
frontier.put(next, priority)
came_from[next] = current
return came_from, cost_so_farLet's try:
from implementation import *
came_from, cost_so_far = a_star_search(diagram4, (1, 4), (7, 8))
draw_grid(diagram4, width=3, point_to=came_from, start=(1, 4), goal=(7, 8))
print()
draw_grid(diagram4, width=3, number=cost_so_far, start=(1, 4), goal=(7, 8)). . . . . . . . . .
. ↓ ↓ ↓ . . . . . .
↓ ↓ ↓ ↓ ← . . . . .
↓ ↓ ↓ ← ← . . . . .
→ A ← ← ← . . . . .
→ ↑ ← ← ← . . . . .
→ ↑ ← ← ← ← . . . .
↑ #########↑ . ↓ . . .
↑ #########↓ ↓ ↓ Z . .
↑ ← ← ← ← ← ← ← . .
. . . . . . . . . .
. 3 4 5 . . . . . .
3 2 3 4 9 . . . . .
2 1 2 3 8 . . . . .
1 A 1 6 11 . . . . .
2 1 2 7 12 . . . . .
3 2 3 4 9 14 . . . .
4 #########14 . 18 . . .
5 #########15 16 13 Z . .
6 7 8 9 10 11 12 13 . . 1.4.1 Straightened paths
If you implement this code in your own project, you may find that some of the paths are not as “direct” as we would like. This is normal . When using grids , and especially grids in which each step has the same cost of movement, you will get equivalent options : many paths have exactly the same cost. A * chooses one of many short cuts, and very often it does not look very pretty . You can apply a quick hack that eliminates the equivalent options , but it is not always fully suitable. It would be better to change the map view, which will greatly accelerate A * and create more direct and enjoyable ways. However, this is suitable for static cards in which each step has one movement cost. For the demo on my page, I use a quick hack, but it only works with my slow priority queue. If you switch to a faster priority queue, you need another quick hack.
2 C ++ implementation
Note: to run part of the sample code, add redblobgames / pathfinding / a-star / implementation.cpp . I use C ++ 11 for this code , so if you are using an older version of the C ++ standard, you will have to partially modify it.
2.1 Wide search
Check out the Python section first. There will be code in this section, but not the same explanations. First, add a generic graph class:
template
struct SimpleGraph {
typedef L Location;
typedef typename vector::iterator iterator;
unordered_map > edges;
inline const vector neighbors(Location id) {
return edges[id];
}
}; and the same graph example from Python code that uses to mark points
char:
SimpleGraph example_graph {{
{'A', {'B'}},
{'B', {'A', 'C', 'D'}},
{'C', {'A'}},
{'D', {'E', 'A'}},
{'E', {'B'}}
}}; Instead of defining a queue class, we use a class from the C ++ standard library. Now we can try to do a breadth-first search:
#include "redblobgames/pathfinding/a-star/implementation.cpp"
template
void breadth_first_search(Graph graph, typename Graph::Location start) {
typedef typename Graph::Location Location;
queue frontier;
frontier.push(start);
unordered_set visited;
visited.insert(start);
while (!frontier.empty()) {
auto current = frontier.front();
frontier.pop();
std::cout << "Visiting " << current << std::endl;
for (auto& next : graph.neighbors(current)) {
if (!visited.count(next)) {
frontier.push(next);
visited.insert(next);
}
}
}
}
int main() {
breadth_first_search(example_graph, 'A');
} Visiting A
Visiting B
Visiting C
Visiting D
Visiting EThe code is a bit longer than in Python, but this is quite normal.
What about square grids? I will define another class of graph. Note that it is not associated with the previous class of the graph. I use templates, not inheritance. The graph should only provide a typedef
Locationand function neighbors.struct SquareGrid {
typedef tuple Location;
static array DIRS;
int width, height;
unordered_set walls;
SquareGrid(int width_, int height_)
: width(width_), height(height_) {}
inline bool in_bounds(Location id) const {
int x, y;
tie (x, y) = id;
return 0 <= x && x < width && 0 <= y && y < height;
}
inline bool passable(Location id) const {
return !walls.count(id);
}
vector neighbors(Location id) const {
int x, y, dx, dy;
tie (x, y) = id;
vector results;
for (auto dir : DIRS) {
tie (dx, dy) = dir;
Location next(x + dx, y + dy);
if (in_bounds(next) && passable(next)) {
results.push_back(next);
}
}
if ((x + y) % 2 == 0) {
// эстетическое улучшение для сеток квадратов
std::reverse(results.begin(), results.end());
}
return results;
}
};
array SquareGrid::DIRS {Location{1, 0}, Location{0, -1}, Location{-1, 0}, Location{0, 1}}; In the help file,
implementation.cppI defined a function for rendering grids:#include "redblobgames/pathfinding/a-star/implementation.cpp"
int main() {
SquareGrid grid = make_diagram1();
draw_grid(grid, 2);
}. . . . . . . . . . . . . . . . . . . . . ####. . . . . . .
. . . . . . . . . . . . . . . . . . . . . ####. . . . . . .
. . . . . . . . . . . . . . . . . . . . . ####. . . . . . .
. . . ####. . . . . . . . . . . . . . . . ####. . . . . . .
. . . ####. . . . . . . . ####. . . . . . ####. . . . . . .
. . . ####. . . . . . . . ####. . . . . . ##########. . . .
. . . ####. . . . . . . . ####. . . . . . ##########. . . .
. . . ####. . . . . . . . ####. . . . . . . . . . . . . . .
. . . ####. . . . . . . . ####. . . . . . . . . . . . . . .
. . . ####. . . . . . . . ####. . . . . . . . . . . . . . .
. . . ####. . . . . . . . ####. . . . . . . . . . . . . . .
. . . ####. . . . . . . . ####. . . . . . . . . . . . . . .
. . . . . . . . . . . . . ####. . . . . . . . . . . . . . .
. . . . . . . . . . . . . ####. . . . . . . . . . . . . . .
. . . . . . . . . . . . . ####. . . . . . . . . . . . . . .Let's do a breadth-first search, tracking
came_from:#include "redblobgames/pathfinding/a-star/implementation.cpp"
template
unordered_map
breadth_first_search(Graph graph, typename Graph::Location start) {
typedef typename Graph::Location Location;
queue frontier;
frontier.push(start);
unordered_map came_from;
came_from[start] = start;
while (!frontier.empty()) {
auto current = frontier.front();
frontier.pop();
for (auto& next : graph.neighbors(current)) {
if (!came_from.count(next)) {
frontier.push(next);
came_from[next] = current;
}
}
}
return came_from;
}
int main() {
SquareGrid grid = make_diagram1();
auto parents = breadth_first_search(grid, std::make_tuple(7, 8));
draw_grid(grid, 2, nullptr, &parents);
} → → → → ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← ← ← ####↓ ↓ ↓ ↓ ↓ ↓ ↓
→ → → → → ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← ← ← ← ####↓ ↓ ↓ ↓ ↓ ↓ ↓
→ → → → → ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← ← ← ← ← ####→ ↓ ↓ ↓ ↓ ↓ ↓
→ → ↑ ####↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← ← ← ← ← ← ####→ → ↓ ↓ ↓ ↓ ↓
→ ↑ ↑ ####↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ####↑ ← ← ← ← ← ####→ → → ↓ ↓ ↓ ↓
↑ ↑ ↑ ####↓ ↓ ↓ ↓ ↓ ↓ ← ← ####↑ ↑ ← ← ← ← ##########↓ ↓ ↓ ←
↑ ↑ ↑ ####→ ↓ ↓ ↓ ↓ ← ← ← ####↑ ↑ ↑ ← ← ← ##########↓ ↓ ← ←
↓ ↓ ↓ ####→ → ↓ ↓ ← ← ← ← ####↑ ↑ ↑ ↑ ← ← ← ← ← ← ← ← ← ← ←
↓ ↓ ↓ ####→ → * ← ← ← ← ← ####↑ ↑ ↑ ↑ ↑ ← ← ← ← ← ← ← ← ← ←
↓ ↓ ↓ ####→ ↑ ↑ ↑ ← ← ← ← ####↑ ↑ ↑ ↑ ↑ ↑ ← ← ← ← ← ← ← ← ←
↓ ↓ ↓ ####↑ ↑ ↑ ↑ ↑ ← ← ← ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ← ← ← ← ← ← ←
→ ↓ ↓ ####↑ ↑ ↑ ↑ ↑ ↑ ← ← ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ← ← ← ← ← ←
→ → → → → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ← ← ← ← ←
→ → → → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ← ← ← ←
→ → → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ← ← ←Some implementations use internal storage and create a Node object to store
came_fromother values for each node in the graph. I preferred to use external storage , creating a single std::unordered_mapstorage came_fromfor all nodes of the graph. If you know that the points on your map have integer indices, then there is another option - use a one-dimensional or two-dimensional array / vector to store came_fromother values.2.1.1 TODO: struct points
In this code, I use
std::tupleC ++ because I used tuples in my Python code. However, tuples are unfamiliar to most C ++ programmers. Will be a little more lengthy define struct a {x, y}, because it will need to define a constructor, copy constructor, assignment operator and a comparison of equality with the hash function, but this code will be more familiar to most programmers in C ++. It will be necessary to change it. Another option (I use it in my code) is to encode {x, y} as
int. T If the code A * always has a dense set of integer values instead of arbitrary typesLocation, this allows you to use additional optimizations. You can use arrays for different sets, rather than hash tables. You can leave most of them uninitialized. For those arrays that need to be reinitiated each time, you can make them constant for A * calls (possibly using the local thread store) and reinitialize only those parts of the array that were used in the previous call. This is a more complex technique that I do not want to use in the entry-level tutorial.2.2 Early exit
As in the version for Python, we just need to add a parameter to the function and check the main loop:
#include "redblobgames/pathfinding/a-star/implementation.cpp"
template
unordered_map
breadth_first_search(const Graph& graph,
typename Graph::Location start,
typename Graph::Location goal) {
typedef typename Graph::Location Location;
queue frontier;
frontier.push(start);
unordered_map came_from;
came_from[start] = start;
while (!frontier.empty()) {
auto current = frontier.front();
frontier.pop();
if (current == goal) {
break;
}
for (auto& next : graph.neighbors(current)) {
if (!came_from.count(next)) {
frontier.push(next);
came_from[next] = current;
}
}
}
return came_from;
}
int main() {
SquareGrid grid = make_diagram1();
auto parents = breadth_first_search(grid, SquareGrid::Location{8, 7}, SquareGrid::Location{17, 2});
draw_grid(grid, 2, nullptr, &parents);
} . → → → ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← . . . . ####. . . . . . .
→ → → → → ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← . . . ####. . . . . . .
→ → → → → ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← ← . . . ####. . . . . . .
→ → ↑ ####↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ← ← ← ← ← ← . . ####. . . . . . .
. ↑ ↑ ####→ ↓ ↓ ↓ ↓ ↓ ↓ ← ####↑ ← ← . . . ####. . . . . . .
. . ↑ ####→ → ↓ ↓ ↓ ↓ ← ← ####↑ ↑ . . . . ##########. . . .
. . . ####→ → → ↓ ↓ ← ← ← ####↑ . . . . . ##########. . . .
. . . ####→ → → * ← ← ← ← ####. . . . . . . . . . . . . . .
. . . ####→ → ↑ ↑ ↑ ← ← ← ####. . . . . . . . . . . . . . .
. . ↓ ####→ ↑ ↑ ↑ ↑ ↑ ← ← ####. . . . . . . . . . . . . . .
. ↓ ↓ ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ← ####. . . . . . . . . . . . . . .
→ ↓ ↓ ####↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####. . . . . . . . . . . . . . .
→ → → → → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####. . . . . . . . . . . . . . .
→ → → → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####. . . . . . . . . . . . . . .
. → → ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ####. . . . . . . . . . . . . . .2.3 Dijkstra's Algorithm
2.3.1 Count with weights
We have a grid with a list of forest tiles, the cost of movement for which is 5. In this forest map, I decided to perform the movement only depending on
to_node, but there are other types of movement that use both nodes .struct GridWithWeights: SquareGrid {
unordered_set forests;
GridWithWeights(int w, int h): SquareGrid(w, h) {}
double cost(Location from_node, Location to_node) const {
return forests.count(to_node) ? 5 : 1;
}
}; 2.3.2 Priority Queue
We need a priority queue. In C ++, there is a class
priority_queuethat uses the binary heap, but without the operation of changing the priority. I am using a pair (priority, element) for queue elements to get the correct order. By default, a C ++ priority queue first returns the std::lessmaximum element using a comparator . We need a minimal element, so I use a comparator std::greater.template
struct PriorityQueue {
typedef pair PQElement;
priority_queue,
std::greater> elements;
inline bool empty() const { return elements.empty(); }
inline void put(T item, priority_t priority) {
elements.emplace(priority, item);
}
inline T get() {
T best_item = elements.top().second;
elements.pop();
return best_item;
}
}; In this example code, I wrap a C ++ class
std::priority_queue, but I think it would be wise to use this class without a wrapper.2.3.3 Search
See the map with the forest from the previous article .
template
void dijkstra_search
(const Graph& graph,
typename Graph::Location start,
typename Graph::Location goal,
unordered_map& came_from,
unordered_map& cost_so_far)
{
typedef typename Graph::Location Location;
PriorityQueue frontier;
frontier.put(start, 0);
came_from[start] = start;
cost_so_far[start] = 0;
while (!frontier.empty()) {
auto current = frontier.get();
if (current == goal) {
break;
}
for (auto& next : graph.neighbors(current)) {
double new_cost = cost_so_far[current] + graph.cost(current, next);
if (!cost_so_far.count(next) || new_cost < cost_so_far[next]) {
cost_so_far[next] = new_cost;
came_from[next] = current;
frontier.put(next, new_cost);
}
}
}
} The types of variables
costmust match the types used in the graph. If you use int, then you can use intfor variable cost and priorities in the priority queue. If you use double, then you also need to use it double. I used it in this code double, but I could use it int, and the code would work the same way. However, if the cost of the edges of the graph is stored in double or double is used in heuristics, then here you need to use double. And finally, after the search, you need to build the path:
template
vector reconstruct_path(
Location start,
Location goal,
unordered_map& came_from
) {
vector path;
Location current = goal;
path.push_back(current);
while (current != start) {
current = came_from[current];
path.push_back(current);
}
path.push_back(start); // необязательно
std::reverse(path.begin(), path.end());
return path;
} Although paths are best understood as a sequence of edges, it is convenient to store them as a sequence of nodes. To build the path, start from the end and follow the map
came_frompointing to the previous node. The process will end when we reach the beginning. This is the return path, so if you want to store it directly, then reconstruct_pathyou need to call it at the end reverse(). Sometimes it’s more convenient to store the path in reverse. Sometimes it’s also useful to keep the starting node in the list. Let's try:
#include "redblobgames/pathfinding/a-star/implementation.cpp"
int main() {
GridWithWeights grid = make_diagram4();
SquareGrid::Location start{1, 4};
SquareGrid::Location goal{8, 5};
unordered_map came_from;
unordered_map cost_so_far;
dijkstra_search(grid, start, goal, came_from, cost_so_far);
draw_grid(grid, 2, nullptr, &came_from);
std::cout << std::endl;
draw_grid(grid, 3, &cost_so_far, nullptr);
std::cout << std::endl;
vector path = reconstruct_path(start, goal, came_from);
draw_grid(grid, 3, nullptr, nullptr, &path);
} ↓ ↓ ← ← ← ← ← ← ← ←
↓ ↓ ← ← ← ↑ ↑ ← ← ←
↓ ↓ ← ← ← ← ↑ ↑ ← ←
↓ ↓ ← ← ← ← ← ↑ ↑ ←
→ * ← ← ← ← ← → ↑ ←
↑ ↑ ← ← ← ← . ↓ ↑ .
↑ ↑ ← ← ← ← ← ↓ ← .
↑ ######↑ ← ↓ ↓ ← .
↑ ######↓ ↓ ↓ ← ← ←
↑ ← ← ← ← ← ← ← ← ←
5 4 5 6 7 8 9 10 11 12
4 3 4 5 10 13 10 11 12 13
3 2 3 4 9 14 15 12 13 14
2 1 2 3 8 13 18 17 14 15
1 0 1 6 11 16 21 20 15 16
2 1 2 7 12 17 . 21 16 .
3 2 3 4 9 14 19 16 17 .
4 #########14 19 18 15 16 .
5 #########15 16 13 14 15 16
6 7 8 9 10 11 12 13 14 15
. @ @ @ @ @ @ . . .
. @ . . . . @ @ . .
. @ . . . . . @ @ .
. @ . . . . . . @ .
. @ . . . . . . @ .
. . . . . . . . @ .
. . . . . . . . . .
. #########. . . . . .
. #########. . . . . .
. . . . . . . . . .The results do not completely match the results of the Python version, because for the priority queue I use the hash tables built in, and the iteration order for the hash tables will not be constant.
2.4 Search A *
A * almost completely repeats Dijkstra's algorithm, with the exception of the added heuristic search. Note that the algorithm code can be used not only for grids . The knowledge of grids is in the graph class (in this case
SquareGrids) and in the function heuristic. If you replace them, then you can use the algorithm code A * with any other graph structure.inline double heuristic(SquareGrid::Location a, SquareGrid::Location b) {
int x1, y1, x2, y2;
tie (x1, y1) = a;
tie (x2, y2) = b;
return abs(x1 - x2) + abs(y1 - y2);
}
template
void a_star_search
(const Graph& graph,
typename Graph::Location start,
typename Graph::Location goal,
unordered_map& came_from,
unordered_map& cost_so_far)
{
typedef typename Graph::Location Location;
PriorityQueue frontier;
frontier.put(start, 0);
came_from[start] = start;
cost_so_far[start] = 0;
while (!frontier.empty()) {
auto current = frontier.get();
if (current == goal) {
break;
}
for (auto& next : graph.neighbors(current)) {
double new_cost = cost_so_far[current] + graph.cost(current, next);
if (!cost_so_far.count(next) || new_cost < cost_so_far[next]) {
cost_so_far[next] = new_cost;
double priority = new_cost + heuristic(next, goal);
frontier.put(next, priority);
came_from[next] = current;
}
}
}
} The type of values
priority, including the type used for the priority queue, must be large enough to contain both the cost of the graph ( cost_t) and the heuristic value. For example, if the value of the graph is stored in int, and the heuristic returns double, then it is necessary that the priority queue can receive double. In this code example, I use doublefor all three values (value, heuristic and priority), but I could use and intbecause my value and heuristic have integer value. A small note: it would be more correct to write
frontier.put(start, heuristic(start, goal)), notfrontier.put(start, 0), but this is not important here, because the priority of the starting node does not matter. This is the only node in the priority queue and it is selected and deleted before something is written there.#include "redblobgames/pathfinding/a-star/implementation.cpp"
int main() {
GridWithWeights grid = make_diagram4();
SquareGrid::Location start{1, 4};
SquareGrid::Location goal{8, 5};
unordered_map came_from;
unordered_map cost_so_far;
a_star_search(grid, start, goal, came_from, cost_so_far);
draw_grid(grid, 2, nullptr, &came_from);
std::cout << std::endl;
draw_grid(grid, 3, &cost_so_far, nullptr);
std::cout << std::endl;
vector path = reconstruct_path(start, goal, came_from);
draw_grid(grid, 3, nullptr, nullptr, &path);
} ↓ ↓ ↓ ↓ ← ← ← ← ← ←
↓ ↓ ↓ ↓ ← ↑ ↑ ← ← ←
↓ ↓ ↓ ↓ ← ← ↑ ↑ ← ←
↓ ↓ ↓ ← ← ← . ↑ ↑ ←
→ * ← ← ← ← . → ↑ ←
→ ↑ ← ← ← ← . . ↑ .
↑ ↑ ↑ ← ← ← . . . .
↑ ######↑ . . . . .
↑ ######. . . . . .
↑ . . . . . . . . .
5 4 5 6 7 8 9 10 11 12
4 3 4 5 10 13 10 11 12 13
3 2 3 4 9 14 15 12 13 14
2 1 2 3 8 13 . 17 14 15
1 0 1 6 11 16 . 20 15 16
2 1 2 7 12 17 . . 16 .
3 2 3 4 9 14 . . . .
4 #########14 . . . . .
5 #########. . . . . .
6 . . . . . . . . .
. . . @ @ @ @ . . .
. . . @ . . @ @ . .
. . . @ . . . @ @ .
. . @ @ . . . . @ .
. @ @ . . . . . @ .
. . . . . . . . @ .
. . . . . . . . . .
. #########. . . . . .
. #########. . . . . .
. . . . . . . . . .2.4.1 Straightening paths
When implementing this code in your project, you may notice that some of the paths are not as “direct” as we would like. This one is fine . When using grids , and especially grids in which each step has the same cost of movement, the result is equivalent options : many paths have the same cost. A * chooses one of the many shortest paths, and very often it does not look very pretty . Equivalent options can be eliminated with a quick hack, but it is not completely suitable. It would be better to change the map view, which will greatly accelerate A * and create more direct and beautiful paths. However, this only works with static cards, in which each step has the same cost of movement. For the demo on my page, I used a quick hack, but it only works with my slow priority queue. If you move to a faster priority queue, you will need another fast hack.
2.4.2 TODO: vector neighbors () must be passed
Instead of highlighting and returning a new vector for the neighbors each time, the A * code must select one vector and pass it to the neighbors function each time. In my tests, this made the code much faster.
2.4.3 TODO: eliminate template parameterization
The goal of this page is to create easy-to-understand code, and I believe that parameterizing a template makes reading it too complicated. Instead, I use a few typedef.
2.4.4 TODO: add requirements
There are two types of graphs (weighted and unweighted), and the graph search code does not tell which type is needed where.
3 Implementation in C #
These are my first C # programs, so they may be uncharacteristic or stylistically incorrect for this language. These examples are not as complete as the examples from the Python and C ++ sections, but I hope they will be useful. Here is a simple graph and breadth-first implementation:
using System;
using System.Collections.Generic;
public class Graph
{
// Если вы всегда используете для точек типы string,
// то здесь разумной альтернативой будет NameValueCollection
public Dictionary edges
= new Dictionary();
public Location[] Neighbors(Location id)
{
return edges[id];
}
};
class BreadthFirstSearch
{
static void Search(Graph graph, string start)
{
var frontier = new Queue();
frontier.Enqueue(start);
var visited = new HashSet();
visited.Add(start);
while (frontier.Count > 0)
{
var current = frontier.Dequeue();
Console.WriteLine("Visiting {0}", current);
foreach (var next in graph.Neighbors(current))
{
if (!visited.Contains(next)) {
frontier.Enqueue(next);
visited.Add(next);
}
}
}
}
static void Main()
{
Graph g = new Graph();
g.edges = new Dictionary
{
{ "A", new [] { "B" } },
{ "B", new [] { "A", "C", "D" } },
{ "C", new [] { "A" } },
{ "D", new [] { "E", "A" } },
{ "E", new [] { "B" } }
};
Search(g, "A");
}
} Here is a graph representing a grid with weighted edges (an example with a forest and walls from a previous article):
using System;
using System.Collections.Generic;
// Для A* нужен только WeightedGraph и тип точек L, и карта *не*
// обязана быть сеткой. Однако в коде примера я использую сетку.
public interface WeightedGraph
{
double Cost(Location a, Location b);
IEnumerable Neighbors(Location id);
}
public struct Location
{
// Примечания по реализации: я использую Equals по умолчанию,
// но это может быть медленно. Возможно, в реальном проекте стоит
// заменить Equals и GetHashCode.
public readonly int x, y;
public Location(int x, int y)
{
this.x = x;
this.y = y;
}
}
public class SquareGrid : WeightedGraph
{
// Примечания по реализации: для удобства я сделал поля публичными,
// но в реальном проекте, возможно, стоит следовать стандартному
// стилю и сделать их скрытыми.
public static readonly Location[] DIRS = new []
{
new Location(1, 0),
new Location(0, -1),
new Location(-1, 0),
new Location(0, 1)
};
public int width, height;
public HashSet walls = new HashSet();
public HashSet forests = new HashSet();
public SquareGrid(int width, int height)
{
this.width = width;
this.height = height;
}
public bool InBounds(Location id)
{
return 0 <= id.x && id.x < width
&& 0 <= id.y && id.y < height;
}
public bool Passable(Location id)
{
return !walls.Contains(id);
}
public double Cost(Location a, Location b)
{
return forests.Contains(b) ? 5 : 1;
}
public IEnumerable Neighbors(Location id)
{
foreach (var dir in DIRS) {
Location next = new Location(id.x + dir.x, id.y + dir.y);
if (InBounds(next) && Passable(next)) {
yield return next;
}
}
}
}
public class PriorityQueue
{
// В этом примере я использую несортированный массив, но в идеале
// это должна быть двоичная куча. Существует открытый запрос на добавление
// двоичной кучи к стандартной библиотеке C#: https://github.com/dotnet/corefx/issues/574
//
// Но пока её там нет, можно использовать класс двоичной кучи:
// * https://github.com/BlueRaja/High-Speed-Priority-Queue-for-C-Sharp
// * http://visualstudiomagazine.com/articles/2012/11/01/priority-queues-with-c.aspx
// * http://xfleury.github.io/graphsearch.html
// * http://stackoverflow.com/questions/102398/priority-queue-in-net
private List> elements = new List>();
public int Count
{
get { return elements.Count; }
}
public void Enqueue(T item, double priority)
{
elements.Add(Tuple.Create(item, priority));
}
public T Dequeue()
{
int bestIndex = 0;
for (int i = 0; i < elements.Count; i++) {
if (elements[i].Item2 < elements[bestIndex].Item2) {
bestIndex = i;
}
}
T bestItem = elements[bestIndex].Item1;
elements.RemoveAt(bestIndex);
return bestItem;
}
}
/* Примечание о типах: в предыдущей статье в коде Python я использовал
* для стоимости, эвристики и приоритетов просто числа. В коде C++
* я использую для этого typedef, потому что может потребоваться int, double или
* другой тип. В этом коде на C# я использую для стоимости, эвристики
* и приоритетов double. Можно использовать int, если вы уверены, что значения
* никогда не будут больше, или числа меньшего размера, если знаете, что
* значения всегда будут небольшими. */
public class AStarSearch
{
public Dictionary cameFrom
= new Dictionary();
public Dictionary costSoFar
= new Dictionary();
// Примечание: обобщённая версия A* абстрагируется от Location
// и Heuristic
static public double Heuristic(Location a, Location b)
{
return Math.Abs(a.x - b.x) + Math.Abs(a.y - b.y);
}
public AStarSearch(WeightedGraph graph, Location start, Location goal)
{
var frontier = new PriorityQueue();
frontier.Enqueue(start, 0);
cameFrom[start] = start;
costSoFar[start] = 0;
while (frontier.Count > 0)
{
var current = frontier.Dequeue();
if (current.Equals(goal))
{
break;
}
foreach (var next in graph.Neighbors(current))
{
double newCost = costSoFar[current]
+ graph.Cost(current, next);
if (!costSoFar.ContainsKey(next)
|| newCost < costSoFar[next])
{
costSoFar[next] = newCost;
double priority = newCost + Heuristic(next, goal);
frontier.Enqueue(next, priority);
cameFrom[next] = current;
}
}
}
}
}
public class Test
{
static void DrawGrid(SquareGrid grid, AStarSearch astar) {
// Печать массива cameFrom
for (var y = 0; y < 10; y++)
{
for (var x = 0; x < 10; x++)
{
Location id = new Location(x, y);
Location ptr = id;
if (!astar.cameFrom.TryGetValue(id, out ptr))
{
ptr = id;
}
if (grid.walls.Contains(id)) { Console.Write("##"); }
else if (ptr.x == x+1) { Console.Write("\u2192 "); }
else if (ptr.x == x-1) { Console.Write("\u2190 "); }
else if (ptr.y == y+1) { Console.Write("\u2193 "); }
else if (ptr.y == y-1) { Console.Write("\u2191 "); }
else { Console.Write("* "); }
}
Console.WriteLine();
}
}
static void Main()
{
// Создание "рисунка 4" из предыдущей статьи
var grid = new SquareGrid(10, 10);
for (var x = 1; x < 4; x++)
{
for (var y = 7; y < 9; y++)
{
grid.walls.Add(new Location(x, y));
}
}
grid.forests = new HashSet
{
new Location(3, 4), new Location(3, 5),
new Location(4, 1), new Location(4, 2),
new Location(4, 3), new Location(4, 4),
new Location(4, 5), new Location(4, 6),
new Location(4, 7), new Location(4, 8),
new Location(5, 1), new Location(5, 2),
new Location(5, 3), new Location(5, 4),
new Location(5, 5), new Location(5, 6),
new Location(5, 7), new Location(5, 8),
new Location(6, 2), new Location(6, 3),
new Location(6, 4), new Location(6, 5),
new Location(6, 6), new Location(6, 7),
new Location(7, 3), new Location(7, 4),
new Location(7, 5)
};
// Выполнение A*
var astar = new AStarSearch(grid, new Location(1, 4),
new Location(8, 5));
DrawGrid(grid, astar);
}
} 4 Optimizations
When creating the code for the article, I focused on simplicity and applicability, rather than performance. Make the code work first, then optimize the speed. Many of the optimizations that I used in real projects are specific to the project, so instead of demonstrating the optimal code, I will give you some ideas that you can implement in your own project:
4.1 Count
The biggest optimization you can make is reducing the number of nodes. Recommendation number 1: if you use a map from grids, then try to apply a path search graph not based on grids . This is not always possible, but this option is worth considering.
If the graph has a simple structure (for example, a grid), then calculate the neighbors in the function. If it has a more complex structure (without grids, or a grid with a large number of walls, as in a maze), then store the neighbors in the data structure.
You can also save copy operations by reusing the array of neighbors. Instead of performing a return each time, select it once in the search code and pass it to the graph's neighbors method.
4.2 Queue
The breadth-first search uses the regular queue, rather than the priority queue used in other algorithms. Queues are faster and easier than priority queues. Other algorithms examine fewer nodes. For most game cards, reducing the number of nodes studied is worth the slowdown of other algorithms. However, there are cards in which you can’t save a lot, and therefore it is better to use the width search in them.
For queues, use the deque array instead. deque provides the ability to quickly insert and delete from either side, while the array is fast from only one end. In Python, you should use collections.deque ; in C ++, consider the deque container. However, a breadth-first search does not even need a queue: you can use two vectors in it, switching between them when one of them is empty.
For a priority queue, use a binary heap, not an array or sorted array. The binary heap provides the ability to quickly insert and delete, while the array is fast in just one thing. In Python, I recommend using heapq ; in C ++ try the priority_queue container .
In Python, the Queue and PriorityQueue classes I showed above are so simple that you can embed methods in a search algorithm. I don’t know if you can win a lot on this, it’s worth testing. C ++ versions will be embedded.
Note that in Dijkstra's algorithm, the priority of the priority queue is saved twice, once in the priority queue, the second in
cost_so_far, so you can write a priority queue that receives priority from anywhere. I don't know if it's worth it. The standard Dijkstra algorithm implementation uses priority changes in the priority queue. However, what happens if you do not change the priority? As a result, duplicate elements will appear there. But the algorithm still works.He will re-visit some points more than necessary. The priority queue will have more elements than necessary, which slows down, but data structures that support changing the priority also slow down due to the presence of more elements. See the research “Priority Queues and Dijkstra's Algorithm” by Chen, Chaudhery, Ramachandran, Lan Roche, and Tonga. This study also recommends consideration of pairing heaps and other data structures.
If you are thinking of using something instead of a binary heap, first measure the size of the border and how often the priorities change. Profile the code and see if the priority queue is a bottleneck.
I feel that grouping data is a promising area. Just like block sorting and bitwise sorting can be useful alternatives to quicksort when the keys are integer values, in the case of Dijkstra and A * algorithms the situation is even better. Priorities in Dijkstra's algorithm are incredibly low . If the lowest element in the queue has priority
f, then the highest element has priority f+e, where eis the maximum weight of the edge. In the forest example, we have the weights of edges 1 and 5. This means that all priorities in the queue will be between fand f+5. Since they are all integer, there are six different priorities.. You can use six blocks or not sort anything at all! A * creates a wider range of priorities, but it's still worth considering. And there are more interesting grouping approaches that can handle a wider range of situations. I have another article on priority queue data structures .
4.3 Search
Heuristics increases CPU complexity and time consumption. However, the goal here is to investigate fewer nodes. In some maps (for example, in mazes), heuristics may not add much information, and it may be better to use a simpler algorithm without heuristics.
If your graph as points using integer values, then consider the possibility of using
cost_so_far, visited, came_frometc. a simple array, not a hash table. Since it visitedis a boolean array, a bit vector can be used. Initialize the bit vector for all identifiers, but leave cost_so_farit came_fromuninitialized (if the language allows it). Then initialize them only at the first visit.If you only perform one search at a time, you can statically extract and reuse data structures from one call in the next. Instead of initializing them at the input, reset them at the output. You can use the array to track the points that are changing, and then only change them. For example, if you use an array
visited[]initialized for 1000 nodes, but most search processes visit less than 100 nodes, then you can change the index array, and then change only these 100 nodes when you exit the function, instead of reinitializing all 1000 nodes when you enter the function. Some people use unacceptable A * to speed up their search.(overestimating) heuristics. That seems reasonable. However, I did not carefully consider these implementations. I believe (but I don’t know for sure) that some elements already visited need to be visited again, even if they are already removed from the border.
In some implementations, a new node is always inserted into the open set , even if it is already there. This way you can avoid the potentially costly step of checking whether the node is already in the open set. But at the same time, the open set becomes larger / slower and as a result, you will have to evaluate more nodes than necessary. If checking an open set proves to be costly, then perhaps this approach should be used. However, in the code I presented, I made the check cheap, and I do not use this approach.
In some implementationsit does not check if the new node is better than the existing one in the open set. This avoids the potentially costly verification. However, this can lead to an error . On some types of cards you will not find the shortest path if you skip this check. In the code I presented, I perform this check (
new_cost < cost_so_far). This check is cheap because I did a cost_so_farcheap search .5 Troubleshooting
5.1 Incorrect paths
If you do not get the shortest path, try the following checks:
- Does the priority queue work correctly? Try stopping the search and remove all items from the queue. They should go in order.
- Переоценивает ли эвристика истинное расстояние?
priorityнового узла никогда не должен быть ниже приоритета его родителя, если вы не переоцениваете расстояние (это можно сделать, но вы больше не получите кратчайшего пути). - В языке со статической типизацией значения стоимости, эвристики и приоритетов должны иметь совместимые типы. Код примера в этой статье работает и с целочисленными типами, и с типами с плавающей запятой, но не все графы и эвристики ограничены целочисленными значениями. Поскольку приоритеты являются суммой стоимости и эвристики, то приоритеты должны иметь тип с плавающей запятой, если или стоимость, или эвристика имеют тип с плавающей запятой.
5.2 Некрасивые пути
Most often, when performing A * on grids, they ask me a question: why don't the paths look straight? If we tell A * that all movements along the grid have equal cost, then we get many shortest paths of the same length, and the algorithm arbitrarily selects one of them. The path is short , but it does not look good.
- One solution would be to straighten the paths after the algorithm using the “string pulling” algorithm.
- Another solution is to guide the way in the right direction by regulating heuristics. There are several cheap tricks that do not work in all situations, here you can read more about this .
- Третье решение — не использовать сетку. Сообщайте A* только места, в которых можно поворачивать, а не каждый квадрат сетки. Здесь можно прочитать об этом подробнее.
- Четвёртое решение — хак, но он работает не всегда. При итерации по соседям вместо использования одинакового порядка (например: север, восток, юг, запад), изменяйте порядок в «нечётных» узлах сетки (в которых (x+y) % 2 == 1). Я использую этот трюк в своих статьях.
6 Дополнительное чтение
- В учебниках алгоритмов часто используется математическая запись с однобуквенными именами переменных. В своих статьях я старался использовать более понятные имена переменных. Соответствия:
costиногда записывается как w or d или l или lengthcost_so_farusually written as g or d or distanceheuristicusually written as hpriorityin A * it is usually written as f , where f = g + hcame_fromsometimes written as π or parent or previous or prevfrontiercommonly called OPENvisitedIs pairing OPEN and CLOSED- point, for example,
currentandnextwritten letters u , v
- Links to Wikipedia: