A*是一個比較經典的啟發式尋路算法。是基於dijkstra算法，但是加入了啟發函數，使路徑搜索效率更高。實現起來很簡單。不過要做到通用性高，比如支持各種不同類型的地圖，甚至不僅僅是地圖，而是個圖結構如解決拼圖游戲N-puzzle會用到的，就需要多花點心思。用C++實現的話，可以使用模板來適應不同的需要。也可以使用類繼承。
template <typename NodeType, typename CostType, typename Heuristic>
static vector<NodeType> search(Map<NodeType, CostType> &map,
NodeType start, NodeType goal,
Heuristic heuristic) {
map.initialize(start, goal);
map.open_node(start, 0, heuristic(start, goal), start); // Get started.
while (map.open_node_available()) {
NodeType top_node = map.close_front_open_node();
if (map.nodes_equal(top_node, goal))
return map.get_path(top_node); // Stop and return the path found.
const vector<Edge<NodeType, CostType>> &&edges = map.edges(top_node);
for (auto edge : edges) { // For each qualified edge evaluate target node.
NodeType node_to_evaluate = edge.to_;
CostType g = map.current_cost(top_node) + edge.cost_;
CostType h = heuristic(node_to_evaluate, goal);
if (map.node_unexplored(node_to_evaluate)) {
map.open_node(node_to_evaluate, g, h, top_node);
} else if (map.cost_greater(map.current_cost(node_to_evaluate), g)) {
if (map.node_open(node_to_evaluate)) {
map.increase_node_priority(node_to_evaluate, g, h, top_node);
} else { // Won't reach here if heuristic is consistent(monotone).
map.reopen_node(node_to_evaluate, g, h, top_node);
}
}
}
}
return vector<NodeType>(); // No path found. Return an empty path.
}
十多年前在大學裡迷戀於開發自己的即時戰略游戲，需要一個尋路算法。當時第一次實現這個算法是有一點小激動的。不過那個時候互聯網還不流行，很難找到相關資料，所以用現在的眼光看實現得不夠好。尤其是open列表，只是用了個有序鏈表。現在看來，可以使用一個優先隊列(priority queue)，畢竟每次從open列表只需要取第一個元素，其他元素的次序並不重要。C++的STL提供了一個優先隊列，不過很不幸，並沒有提供改變某個元素優先度的操作。所以，要麼自己實現一個優先隊列，要麼在STL的基礎上添加這個功能。如果看下STL的源代碼就會發現STL的優先隊列實際上是一個二叉堆(binary heap)。所以，只要在這個基礎上添加個函數percolate_up(）函數就可以了。當然，偷懶一點，修改元素優先度後再用std::make_heap()重新生成堆也可以替代，不過效率就差了。
// Percolate up an element at the index specified.
template<typename Container, typename ElementType, typename LessPriority>
static void percolate_up(Container &container, int index, LessPriority less_priority) {
auto value = container[index];
int hole = index;
int parent = (hole - 1) / 2;
while (hole > 0 && less_priority(container[parent], value)) {
container[hole] = container[parent];
hole = parent;
parent = (hole - 1) / 2;
}
container[hole] = value;
}
再改進一下，可以用HOT(heap on top)來優化。也就是建立一個數據結構，只在最上面使用優先隊列，而其余的元素則放在其他的容器裡，比如分成很多個bucket的vector。這樣做的好處是可以縮小優先隊列的規模，那些不大可能被open的元素則不進隊列，除非隊列已經排空需要把一個bucket轉化為新的優先隊列。
另外一項技術，就是Jump Point Search（JPS或者所謂的跳點搜索）。這是一個近年來發現的高效尋路算法。不過有一個限制就是只能在規則的格子地圖上尋路，而且圖上的點或邊不能帶權重，也就是不能有復雜的地形，只支持平坦和障礙兩種地形。其思想就是跳過矩形平坦區域的大量對稱路徑，只尋找所謂的跳躍點，作為搜索的節點。這樣做的好處是裁剪了矩形區域內大量的節點，使open list中的節點數相對較少。不過JPS有個缺點是每生成一個節點，也就是要找到一個跳躍點，相比較一般的A*算法，是比較昂貴的。幸好通常來說，得到的收益更多些。所以，在適用的情況下，還是推薦使用JPS的。
具體的實現，主要有兩部分。第一部分，從open list中取一個最佳節點，然後從幾個特定方向展開搜索，把每個方向得到的跳躍點，加入open list裡。第二部分，就是找到一個跳躍點。
對於起始點，可以向所有方向展開搜索。對於其他節點，要看父節點指向本節點的方向，向所有自然鄰居和被迫鄰居節點方向進行搜索。
例如下圖的例子，對於節點n和父節點p和障礙x，+是n的自然鄰居，也就是說從p到n到+是最佳路徑。如果x不是障礙，從p到n到-不是最佳路徑，因為從p到x到-最近。但是如果x是障礙，那麼從p到n到-就是最佳路徑了，所以這時候稱-為被迫鄰居。
- + + x n + p x -
以上是n和p對角的例子。還有種情況是n和p是直線：
x x - p n + x x -
搜尋跳躍點是遞歸進行的。首先判斷一個節點是否是跳躍點。如果這個點有被迫鄰居，那麼這個節點就是跳躍點。第二種情況，如果這個節點是目的地節點那麼也當作跳躍點。如果不是，那麼就遞歸地沿本來方向繼續搜尋下去。對於對角方向要額外多做兩步，即先對其相應的（左右兩個）直線方向進行搜索，如果找到跳躍點，就把自身也當作跳躍點返回。如果直線沒找到，那麼就一樣繼續按對角方向遞歸尋找跳躍點，並返回那個跳躍點。
以下是使用A*算法和JPS算法搜索一個10x10的格子地圖得到的結果比較（x是障礙，S是起始點，G是終點，@是最佳路徑，o是open節點，-是closed節點）
大致可以看出JPS是如何通過jump point跳過矩形區域的。
A*:
ooox-S-- oo@Gx-@-- oo@xxxx@-- o@-x--xx@- @xxx---x@- -@-x-x-x@- o-@x-x-x@- o--@@x-x@- oo---@@@-- oo-------
JPS:
x S
@Gx @
xxxx
x xx
@xxx - x
x-x-x
x x x
@@x-x@
@ @
