💾 Archived View for gem.sdf.org › s.kaplan › cheatsheets › data-structures-and-algorithms › a_star.m… captured on 2023-09-28 at 16:17:34.

-=-=-=-=-=-=-

# A* Algorithm Implementation Cheatsheet

## Overview
A* algorithm is an informed search algorithm that finds the shortest path between two given nodes on a graph. It uses a heuristic function to estimate the cost of reaching the goal from the current node. A* algorithm is guaranteed to find the shortest path if the heuristic is admissible and consistent.

## Implementation
1. Define the heuristic function that estimates the cost of reaching the goal from the current node.
2. Define the data structures to be used: `open_list`, `closed_list`, `g_score`, `h_score`, and `f_score`.
3. Add the starting node to the `open_list` with an initial `g_score` of 0 and `h_score` calculated using the heuristic function.
4. While the `open_list` is not empty, select the node with the lowest `f_score` and remove it from `open_list`.
5. If the selected node is the goal, return the path.
6. Add the selected node to the `closed_list`.
7. For each neighboring node of the selected node, calculate its tentative `g_score` and `h_score` using the heuristic function.
8. If the neighboring node is already in the `closed_list`, skip it.
9. If the neighboring node is not in the `open_list`, add it to the `open_list`.
10. If the neighboring node is already in the `open_list` and the tentative `g_score` is greater than or equal to its current `g_score`, skip it. Otherwise, update the `g_score`, `h_score`, and `f_score` of the neighboring node and add it to the `open_list`.
11. Repeat steps 4-10 until the `open_list` is empty.

## Python Example

import heapq

def heuristic(a, b):

return abs(b[0] - a[0]) + abs(b[1] - a[1])

def astar(array, start, goal):

neighbors = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)]

close_set = set()

came_from = {}

gscore = {start:0}

fscore = {start:heuristic(start, goal)}

oheap = []

heapq.heappush(oheap, (fscore[start], start))

while oheap:

current = heapq.heappop(oheap)[1]

if current == goal:

data = []

while current in came_from:

data.append(current)

current = came_from[current]

return data

close_set.add(current)

for i, j in neighbors:

neighbor = current[0] + i, current[1] + j

tentative_g_score = gscore[current] + heuristic(current, neighbor)

if 0 <= neighbor[0] < array.shape[0]:

if 0 <= neighbor[1] < array.shape[1]:

if array[neighbor[0]][neighbor[1]] == 1:

continue

else:

continue

else:

continue

if neighbor in close_set and tentative_g_score >= gscore.get(neighbor, 0):

continue

if tentative_g_score < gscore.get(neighbor, 0) or neighbor not in [i[1]for i in oheap]:

came_from[neighbor] = current

gscore[neighbor] = tentative_g_score

fscore[neighbor] = tentative_g_score + heuristic(neighbor, goal)

heapq.heappush(oheap, (fscore[neighbor], neighbor))

return None


## C++ Example

include <iostream>

include <queue>

include <vector>

include <functional>

include <utility>

include <cmath>

include <unordered_map>

include <set>

using namespace std;

typedef pair<int, int> pii;

const int INF = 1e9;

int heuristic(pii a, pii b) {

return abs(b.first - a.first) + abs(b.second - a.second);

}

vector<pii> astar(vector<vector<int>>& grid, pii start, pii goal) {

int n = grid.size(), m = grid[0].size();

vector<pii> dirs = {% raw %}{{0,1}, {0,-1}, {1,0}, {-1,0}, {1,1}, {1,-1}, {-1,1}, {-1,-1}}{% endraw %};

priority_queue<pii, vector<pii>, greater<pii>> pq;

unordered_map<int, unordered_map<int, int>> gscore;

unordered_map<int, unordered_map<int, int>> fscore;

unordered_map<int, unordered_map<int, pii>> came_from;

set<pii> closed_set;

gscore[start.first][start.second] = 0;

fscore[start.first][start.second] = heuristic(start, goal);

pq.push({fscore[start.first][start.second], (start.first << 16) | start.second});

while (!pq.empty()) {

auto curr = pq.top(); pq.pop();

int x = curr.second >> 16, y = curr.second & 0xFFFF;

if (make_pair(x, y) == goal) {

vector<pii> path;

while (x != start.first || y != start.second) {

path.push_back({x, y});

int tmp_x = x, tmp_y = y;

x = came_from[tmp_x][tmp_y].first;

y = came_from[tmp_x][tmp_y].second;

}

path.push_back({x, y});

reverse(path.begin(), path.end());

return path;

}

closed_set.insert({x, y});

for (auto dir : dirs) {

int nx = x + dir.first, ny = y + dir.second;

if (nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx][ny] == 1) continue;

if (closed_set.count({nx, ny})) continue;

int tentative_gscore = gscore[x][y] + heuristic({x, y}, {nx, ny});

if (!gscore.count(nx) || !gscore[nx].count(ny) || tentative_gscore < gscore[nx][ny]) {

came_from[nx][ny] = {x, y};

gscore[nx][ny] = tentative_gscore;

fscore[nx][ny] = tentative_gscore + heuristic({nx, ny}, goal);

pq.push({fscore[nx][ny], (nx << 16) | ny});

}

return {};

}

int main() {

vector<vector<int>> grid = {

{0, 0, 0, 0, 0},

{0, 1, 1, 1, 0},

{0, 1, 0, 0, 0},

{0, 1, 0, 1, 0},

{0, 0, 0, 1, 0}

};

pii start = {0, 0}, goal = {4, 4};

auto path = astar(grid, start, goal);

for (auto p : path) {

cout << "(" << p.first << ", " << p.second << ") ";

}

cout << endl;

return 0;

}


## Resources

- [A* Search Algorithm](https://en.wikipedia.org/wiki/A*_search_algorithm): Wikipedia page on A* algorithm
- [Introduction to A* Pathfinding](https://www.redblobgames.com/pathfinding/a-star/introduction.html): Red Blob Games tutorial on A* algorithm
- [A* Search Algorithm](https://www.geeksforgeeks.org/a-search-algorithm/): GeeksforGeeks tutorial on A* algorithm
- [Pathfinding with A*](https://theory.stanford.edu/~amitp/GameProgramming/): Amit’s A* Pages with detailed explanations and interactive examples
- [A* Pathfinding for Beginners](http://www.ai-junkie.com/astar/astar1.html): AI Junkie tutorial on A* algorithm with code samples
- [A* Pathfinding Visualization Tool](https://qiao.github.io/PathFinding.js/visual/): Pathfinding.js Visualizer for A* algorithm
- [A* Pathfinding for Beginners - Introduction to Pathfinding](https://www.youtube.com/watch?v=-L-WgKMFuhE): YouTube video tutorial on A* algorithm by Sebastian Lague