# 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
```python
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
```c++
#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