A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。公式表示为：f(n)=g(n)+h(n)，其中f(n)是节点n从初始点到目标点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。

算法比较

Dijkstra算法从物体所在的初始点开始，访问图中的结点。它迭代检查待检查结点集中的结点，并把和该结点最靠近的尚未检查的结点加入待检查结点集。该结点集从初始结点向外扩展，直到到达目标结点。Dijkstra算法保证能找到一条从初始点到目标点的最短路径，只要所有的边都有一个非负的代价值。（我说“最短路径”是因为经常会出现许多差不多短的路径。）在下图中，粉红色的结点是初始结点，蓝色的是目标点，而类菱形的有色区域（注：原文是teal areas）则是Dijkstra算法扫描过的区域。颜色最淡的区域是那些离初始点最远的，因而形成探测过程（exploration）的边境（frontier）：

对于有障碍物的情况下，Dijkstra算法运行得较慢，但确实能保证找到一条最短路径：

最佳优先搜索（BFS）算法按照类似的流程运行，不同的是它能够评估（称为启发式的）任意结点到目标点的代价。与选择离初始结点最近的结点不同的是，它选择离目标最近的结点。BFS不能保证找到一条最短路径。然而，它比Dijkstra算法快的多，因为它用了一个启发式函数（heuristic function）快速地导向目标结点。例如，如果目标位于出发点的南方，BFS将趋向于导向南方的路径。在下面的图中，越黄的结点代表越高的启发式值（移动到目标的代价高），而越黑的结点代表越低的启发式值（移动到目标的代价低）。这表明了与Dijkstra 算法相比，BFS运行得更快。

对于有障碍物的情况，BFS运行得较快，但是它找到的路径明显不是一条好的路径：

A * Algorithm

1968年发明的A star算法就是把启发式方法（heuristic approaches）如BFS，和常规方法如Dijsktra算法结合在一起的算法。有点不同的是，类似BFS的启发式方法经常给出一个近似解而不是保证最佳解。然而，尽管A star基于无法保证最佳解的启发式方法，A star却能保证找到一条最短路径。

在简单的情况中，它和BFS一样快,在凹型障碍物的例子中，A*找到一条和Dijkstra算法一样好的路径.

A star把Dijkstra算法（靠近初始点的结点）和BFS算法（靠近目标点的结点）的信息块结合起来。在讨论A star的标准术语中，g(n)表示从初始结点到任意结点n的代价，h(n)表示从结点n到目标点的启发式评估代价（heuristic estimated cost）。在上图中，yellow(h)表示远离目标的结点而teal(g)表示远离初始点的结点。当从初始点向目标点移动时，A star权衡这两者。每次进行主循环时，它检查f(n)最小的结点n，其中f(n) = g(n) + h(n)。

启发函数

启发式函数h(n)告诉A*从任意结点n到目标结点的最小代价评估值。选择一个好的启发式函数是重要的。

• 一种极端情况，如果h(n)是0，则只有g(n)起作用，此时A演变成Dijkstra算法，这保证能找到最短路径。
• 如果h(n)经常都比从n移动到目标的实际代价小（或者相等），则A保证能找到一条最短路径。h(n)越小，A扩展的结点越多，运行就得越慢。
• 如果h(n)精确地等于从n移动到目标的代价，则A star将会仅仅寻找最佳路径而不扩展别的任何结点，这会运行得非常快。尽管这不可能在所有情况下发生，你仍可以在一些特殊情况下让它们精确地相等（译者：指让h(n)精确地等于实际值）。只要提供完美的信息，A star会运行得很完美，认识这一点很好。
• 如果h(n)有时比从n移动到目标的实际代价高，则A star不能保证找到一条最短路径，但它运行得更快。
• 另一种极端情况，如果h(n)比g(n)大很多，则只有h(n)起作用，A star演变成BFS算法。

算法流程

OPEN = priority queue containing START
CLOSED = empty set
while lowest rank in OPEN is not the GOAL:
  current = remove lowest rank item from OPEN
  add current to CLOSED
  for neighbors of current:
    cost = g(current) + movementcost(current, neighbor)
    if neighbor in OPEN and cost less than g(neighbor):
      remove neighbor from OPEN, because new path is better
    if neighbor in CLOSED and cost less than g(neighbor): ⁽²⁾
      remove neighbor from CLOSED
    if neighbor not in OPEN and neighbor not in CLOSED:
      set g(neighbor) to cost
      add neighbor to OPEN
      set priority queue rank to g(neighbor) + h(neighbor)
      set neighbor's parent to current

reconstruct reverse path from goal to start
by following parent pointers

图解算法

下面通过图解的方式解释A star 算法的工作流程。

如图所示，绿色点为start设为A，红色点为goal设为B，蓝色点为不可通过的障碍物，黑色点为自由区域。目标是规划从A到B的路径。

开始

1. 搜索的从A点开始，首先将A点加入开启列表，此时取开启列表中的最小值，初始阶段开启列表中只有A一个节点，因此将A点从开启列表中取出，将A点加入关闭列表。

2. 取出A点的相邻点，将相邻点加入开启列表。如图所示，此时A点即为相邻点的父节点。图中箭头指向父节点。将相邻点与A点加入追溯表中。

计算评分

对相邻点，一次计算每一点的g，h，最后得到f = g + h。如图，节点的右下角为g值，左下角为h值，右上角为f。

选最小值，再次搜索

1. 选出开启列表中的F值最小的节点，将此节点设为当前节点，移出开启列表，同时加入关闭列表。如图所示。
2. 取出当前点的相邻点，当相邻点为关闭点或者墙时，不操作。此外，查看相邻点是否在开启列表中，如不在开启列表中将相邻点加入开启列表。如相邻点已经在开启列表中，则需要进行G值判定

G值判定

对于相邻点在开启列表中的，计算相邻点的G值，计算按照当前路径的G值与原开启列表中的G值大小。如果当前路径G值小于原开启列表G值，则相邻点以当前点为父节点，将相邻点与当前点加入追溯表中。同时更新此相邻点的H值。如果当前路径G值大于等于原开启列表G值，则相邻点按照原开启列表中的节点关系，H值不变。因为图示中，当前点G值比原开启列表G值大，因此节点关系按照原父子关系和F值。

计算耗费评分，选最小值

此时计算开启列表中F值最小的点，将此节点设为当前节点，并列最小F值的按添加开启列表顺序，以最新添加为佳。

重复搜索判定工作

直到当goal点B加入开启列表中，则搜索完成。此时事实上生成的路径并一定是最佳路径，而是最快计算出的路径。若判定标准改为当goal点B加入关闭列表中搜索完成，则得出路径是最佳路径，但此时计算量较前者大。

当没有找到goal点，同时开启列表已空，则搜索不到路径。结束搜索。

生产路径

由goal点B向上逐级追溯父节点，追溯至起点A，此时各节点组成的路径即使A*算法生成的最优路径。

官方的实现

/*
Sample code from https://www.redblobgames.com/pathfinding/a-star/
Copyright 2014 Red Blob Games <redblobgames@gmail.com>

Feel free to use this code in your own projects, including commercial projects
License: Apache v2.0 <http://www.apache.org/licenses/LICENSE-2.0.html>
*/

#include <iostream>
#include <iomanip>
#include <map>
#include <set>
#include <array>
#include <vector>
#include <utility>
#include <queue>
#include <tuple>
#include <algorithm>
#include <cstdlib>
#include <functional>

struct SimpleGraph {
    std::map<char, std::vector<char> > edges;

    std::vector<char> neighbors(char id) {
        return edges[id];
    }
};

SimpleGraph example_graph{ {
    { 'A',{ 'B' } },
    { 'B',{ 'A', 'C', 'D' } },
    { 'C',{ 'A' } },
    { 'D',{ 'E', 'A' } },
    { 'E',{ 'B' } }
    } };

struct GridLocation {
    int x, y;
};

struct SquareGrid {
    static std::array<GridLocation, 4> DIRS;

    int width, height;
    std::set<GridLocation> walls;

    SquareGrid(int width_, int height_)
        : width(width_), height(height_) {}

    bool in_bounds(GridLocation id) const {
        return 0 <= id.x && id.x < width
            && 0 <= id.y && id.y < height;
    }

    bool passable(GridLocation id) const {
        return walls.find(id) == walls.end();
    }

    std::vector<GridLocation> neighbors(GridLocation id) const {
        std::vector<GridLocation> results;

        for (GridLocation dir : DIRS) {
            GridLocation next{ id.x + dir.x, id.y + dir.y };
            if (in_bounds(next) && passable(next)) {
                results.push_back(next);
            }
        }

        if ((id.x + id.y) % 2 == 0) {
            // aesthetic improvement on square grids
            std::reverse(results.begin(), results.end());
        }

        return results;
    }
};

std::array<GridLocation, 4> SquareGrid::DIRS =
{ GridLocation{ 1, 0 }, GridLocation{ 0, -1 }, GridLocation{ -1, 0 }, GridLocation{ 0, 1 } };

// Helpers for GridLocation

bool operator == (GridLocation a, GridLocation b) {
    return a.x == b.x && a.y == b.y;
}

bool operator != (GridLocation a, GridLocation b) {
    return !(a == b);
}

bool operator < (GridLocation a, GridLocation b) {
    return std::tie(a.x, a.y) < std::tie(b.x, b.y);
}

std::basic_iostream<char>::basic_ostream& operator<<(std::basic_iostream<char>::basic_ostream& out, const GridLocation& loc) {
    out << '(' << loc.x << ',' << loc.y << ')';
    return out;
}

// This outputs a grid. Pass in a distances map if you want to print
// the distances, or pass in a point_to map if you want to print
// arrows that point to the parent location, or pass in a path vector
// if you want to draw the path.
template<class Graph>
void draw_grid(const Graph& graph, int field_width,
    std::map<GridLocation, double>* distances = nullptr,
    std::map<GridLocation, GridLocation>* point_to = nullptr,
    std::vector<GridLocation>* path = nullptr) {
    for (int y = 0; y != graph.height; ++y) {
        for (int x = 0; x != graph.width; ++x) {
            GridLocation id{ x, y };
            std::cout << std::left << std::setw(field_width);
            if (graph.walls.find(id) != graph.walls.end()) {
                std::cout << std::string(field_width, '#').c_str();
            }
            else if (point_to != nullptr && point_to->count(id)) {
                GridLocation next = (*point_to)[id];
                if (next.x == x + 1) { std::cout << "> "; }
                else if (next.x == x - 1) { std::cout << "< "; }
                else if (next.y == y + 1) { std::cout << "v "; }
                else if (next.y == y - 1) { std::cout << "^ "; }
                else { std::cout << "* "; }
            }
            else if (distances != nullptr && distances->count(id)) {
                std::cout << (*distances)[id];
            }
            else if (path != nullptr && find(path->begin(), path->end(), id) != path->end()) {
                std::cout << '@';
            }
            else {
                std::cout << '.';
            }
        }
        std::cout << '\n';
    }
}

void add_rect(SquareGrid& grid, int x1, int y1, int x2, int y2) {
    for (int x = x1; x < x2; ++x) {
        for (int y = y1; y < y2; ++y) {
            grid.walls.insert(GridLocation{ x, y });
        }
    }
}

SquareGrid make_diagram1() {
    SquareGrid grid(30, 15);
    add_rect(grid, 3, 3, 5, 12);
    add_rect(grid, 13, 4, 15, 15);
    add_rect(grid, 21, 0, 23, 7);
    add_rect(grid, 23, 5, 26, 7);
    return grid;
}

struct GridWithWeights : SquareGrid {
    std::set<GridLocation> forests;
    GridWithWeights(int w, int h) : SquareGrid(w, h) {}
    double cost(GridLocation from_node, GridLocation to_node) const {
        return forests.find(to_node) != forests.end() ? 5 : 1;
    }
};

GridWithWeights make_diagram4() {
    GridWithWeights grid(10, 10);
    add_rect(grid, 1, 7, 4, 9);
    typedef GridLocation L;
    grid.forests = std::set<GridLocation>{
        L{ 3, 4 }, L{ 3, 5 }, L{ 4, 1 }, L{ 4, 2 },
        L{ 4, 3 }, L{ 4, 4 }, L{ 4, 5 }, L{ 4, 6 },
        L{ 4, 7 }, L{ 4, 8 }, L{ 5, 1 }, L{ 5, 2 },
        L{ 5, 3 }, L{ 5, 4 }, L{ 5, 5 }, L{ 5, 6 },
        L{ 5, 7 }, L{ 5, 8 }, L{ 6, 2 }, L{ 6, 3 },
        L{ 6, 4 }, L{ 6, 5 }, L{ 6, 6 }, L{ 6, 7 },
        L{ 7, 3 }, L{ 7, 4 }, L{ 7, 5 }
    };
    return grid;
}

template<typename T, typename priority_t>
struct PriorityQueue {
    typedef std::pair<priority_t, T> PQElement;
    std::priority_queue<PQElement, std::vector<PQElement>,
        std::greater<PQElement>> elements;

    inline bool empty() const {
        return elements.empty();
    }

    inline void put(T item, priority_t priority) {
        elements.emplace(priority, item);
    }

    T get() {
        T best_item = elements.top().second;
        elements.pop();
        return best_item;
    }
};

template<typename Location, typename Graph>
void dijkstra_search
(Graph graph,
    Location start,
    Location goal,
    std::map<Location, Location>& came_from,
    std::map<Location, double>& cost_so_far)
{
    PriorityQueue<Location, double> frontier;
    frontier.put(start, 0);

    came_from[start] = start;
    cost_so_far[start] = 0;

    while (!frontier.empty()) {
        Location current = frontier.get();

        if (current == goal) {
            break;
        }

        for (Location next : graph.neighbors(current)) {
            double new_cost = cost_so_far[current] + graph.cost(current, next);
            if (cost_so_far.find(next) == cost_so_far.end()
                || new_cost < cost_so_far[next]) {
                cost_so_far[next] = new_cost;
                came_from[next] = current;
                frontier.put(next, new_cost);
            }
        }
    }
}

template<typename Location>
std::vector<Location> reconstruct_path(
    Location start, Location goal,
    std::map<Location, Location> came_from
) {
    std::vector<Location> path;
    Location current = goal;
    while (current != start) {
        path.push_back(current);
        current = came_from[current];
    }
    path.push_back(start); // optional
    std::reverse(path.begin(), path.end());
    return path;
}

inline double heuristic(GridLocation a, GridLocation b) {
    return std::abs(a.x - b.x) + std::abs(a.y - b.y);
}

template<typename Location, typename Graph>
void a_star_search
(Graph graph,
    Location start,
    Location goal,
    std::map<Location, Location>& came_from,
    std::map<Location, double>& cost_so_far)
{
    PriorityQueue<Location, double> frontier;
    frontier.put(start, 0);

    came_from[start] = start;
    cost_so_far[start] = 0;

    while (!frontier.empty()) {
        Location current = frontier.get();

        if (current == goal) {
            break;
        }

        for (Location next : graph.neighbors(current)) {
            double new_cost = cost_so_far[current] + graph.cost(current, next);
            if (cost_so_far.find(next) == cost_so_far.end()
                || 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;
            }
        }
    }
}



int main(int argc, const char **argv)
{
    GridWithWeights grid = make_diagram4();
    GridLocation start{ 1, 4 };
    GridLocation goal{ 8, 5 };
    std::map<GridLocation, GridLocation> came_from;
    std::map<GridLocation, double> cost_so_far;
    a_star_search(grid, start, goal, came_from, cost_so_far);
    draw_grid(grid, 2, nullptr, &came_from);
    std::cout << '\n';
    draw_grid(grid, 3, &cost_so_far, nullptr);
    std::cout << '\n';
    std::vector<GridLocation> path = reconstruct_path(start, goal, came_from);
    draw_grid(grid, 3, nullptr, nullptr, &path);
    return 0;
}

---

Reference

http://theory.stanford.edu/~amitp/GameProgramming/

http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

https://blog.csdn.net/DinnerHowe/article/details/79380317

https://code.google.com/p/mycodeplayground/

https://www.cnblogs.com/zhoug2020/articles/3468167.html

https://www.cnblogs.com/kanego/archive/2011/08/30/2159070.html http://qiao.github.io/PathFinding.js/visual/ https://github.com/qiao/PathFinding.js