A* 搜索演算法
- Ⅰ 前言
- Ⅱ 演算法決議
- Ⅲ 如何實作游戲尋路問題
- Ⅳ 總結
Ⅰ 前言
你可能玩過魔獸世界，仙劍奇俠和英雄聯盟這類 MMRPG 游戲，在這些游戲中，有一個非常重要的功能，就是人物角色自動尋路，當人物處于游戲地圖中的某個位置的時候，我們用滑鼠點擊另外一個相對較遠的位置，人物就會自動地繞過障礙物走過去，那么這個功能是如何實作的呢？這篇文章我們就來探索一下這個功能，
Ⅱ 演算法決議
實際上，這是一個非常典型的搜索問題，人物的起點就是他當下所在的位置，終點就是滑鼠點擊的位置，我們需要在地圖中，找一條從起點到終點的路徑，這條路徑要繞過地圖中所有障礙物，并且看起來要是一種非常聰明的走法，所謂聰明，籠統地解釋就是，走的路不能太繞，理論上講，最短路徑顯然是最聰明的走法，是這個問題的最優解，
但是，在前面圖的最短路徑的講解中，我說過，如果圖非常大，那 Dijkstra 最短路徑演算法的執行耗時會很多，在真實的軟體開發中，我們面對的是超級大的地圖和海量的尋路請求，演算法的執行效率太低，這顯然是無法接受的，
【資料結構與演算法】-＞演算法-＞地圖軟體的最優路線是如何計算的？
實際上，像出行路線規劃、游戲尋路，這些真實軟體開發中的問題，一般情況下，我們都不需要非得求最優解（也就是最短路徑），在權衡路線規劃質量和執行效率的情況下，我們只需要尋求一個次優解就足夠了，那如何快速找出一條接近于最短路線的次優路線呢？
這個快速的路徑規劃演算法，就是我們這篇文章要講的 A 演算法*，實際上，A* 演算法是對 Dijkstra 演算法的優化和改造，如何將 Dijkstra 演算法改造成 A* 演算法呢？我們逐步來看一下，如果你對 Dijkstra 演算法 不熟悉，可以先跳轉到我上面鏈接的文章中看一下，
Dijkstra 演算法其實是有點類似 BFS 演算法 ，它每次找到跟起點最近的頂點，往外擴展，這種擴展的思路，其實有些盲目，為什么盲目呢？我用下圖的例子來說明，假設下圖對應著一個真實的地圖，每個頂點在圖中的位置，我們用一個二維坐標 (x, y) 來表示，其中 x，y 分別表示橫坐標和縱坐標，
在 Dijkstra 演算法的實作思路中，我們用一個優先級佇列，來記錄已經遍歷到的頂點以及這個頂點與起點的路徑長度，頂點與起點路徑長度越小，就越先被從優先級佇列中取出來擴展，從圖中舉的例子可以看出，盡管我們找的是從 s 到 t 的路線，但是最先被搜索到的頂點依次是 1，2，3，通過肉眼來觀察，這個搜索方向跟我們期望的路線方向（s 到 t 是自西向東）是反著的，路線搜索到的方向明顯跑偏了，
之所以會跑偏，是因為我們是按照頂點與起點的路徑長度的大小，來安排出佇列順序的，與起點越近的頂點，就會越早出佇列，我們并沒有考慮到這個頂點到終點的距離，所以，在地圖中，盡管 1，2，3 三個頂點離起始頂點最近，但離終點卻越來越遠，
那么，如果我們綜合更多的因素，把這個頂點到終點可能還要走多遠，也考慮進去，綜合來判斷哪個頂點該先出佇列，那是不是就可以避免跑偏呢？
當我們遍歷到某個頂點的時候，從起點走到這個頂點的路徑長度是確定的，我們記作 g(i) （i 表示頂點編號），但是，從這個頂點到終點的路徑長度，我們是未知的，雖然確切的值無法提前知道，但是我們可以用其他估計值來替代，
這里我們可以通過這個頂點跟終點之間的直線距離，也就是歐幾里得距離，來近似地估計這個頂點跟終點的路徑長度（直線距離和路徑長度不是一個概念），我們把這個距離記作 h(i)（i 表示頂點編號），專業的叫法叫是啟發函式（heuristic function），因為歐幾里得距離的計算公式，會涉及到比較耗時的開根號計算，所以我們一般用另外一種更加簡單的計算距離的公式，叫作曼哈頓距離（Manhattan distance），曼哈頓距離是兩點之間橫縱坐標的距離之和，計算的程序只涉及加減法和符號位反轉，所以比歐幾里得距離更加高效，
private int hManhattan(Vertex v1, Vertex v2) {
return Math.abs(v1.x - v2.x) + Math.abs(v1.y - v2.y);
}
原來只是單純地通過頂點與起點之間的路徑長度 g(i)，來判斷誰先出佇列，現在有了頂點到終點的路徑長度估計值，我們通過兩者之和 f(i) = g(i) + h(i)，來判斷哪個頂點該最先出佇列，綜合兩部分，我們就能有效避免前面說的跑偏，這里 f(i) 的專業叫法叫做 估價函式（evaluation function），
經過上面的描述，我們可以發現，A* 演算法就是對 Dijkstra 演算法的簡單改造，實際上，在代碼實作上，我們也只需要改動幾個地方就可以了，
在 A* 演算法的代碼實作中，頂點 Vertex 類的定義，跟 Dijkstra 演算法中的定義，稍微有點區別，多了 x, y 坐標，以及剛剛提到的 f(i) 值，圖 Graph 類的定義跟 Dijkstra 演算法中的定義一樣，我還是將完整代碼貼出來，具體的講解大家可以看我的將 Dijkstra 演算法的文章—— Dijkstra 演算法 ，
首先是 Vertex 頂點類
package com.tyz.astar.core;
/**
* 構造一個頂點
* @author Tong
*/
public class Vertex {
int id; //頂點編號
int distance; //從起始點到這個頂點的距離
int f; //f(i) = g(i) + h(i)
int x; //頂點在地圖中的橫坐標
int y; //頂點在地圖中的縱坐標
Vertex(int id, int x, int y) {
this.id = id;
this.x = x;
this.y = y;
this.f = Integer.MAX_VALUE;
this.distance = Integer.MAX_VALUE;
}
}
邊的構造
package com.tyz.astar.core;
/**
* 構造邊
* @author Tong
*/
public class Edge {
private int start; //邊的起始頂點編號
private int end; //邊的終止頂點編號
private int weight; //邊的權重
public Edge() {
}
public Edge(int start, int end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
public int getStart() {
return start;
}
public void setStart(int start) {
this.start = start;
}
public int getEnd() {
return end;
}
public void setEnd(int end) {
this.end = end;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
}
優先級佇列（小頂堆）
package com.tyz.astar.core;
/**
* 實作一個優先級佇列（小頂堆）
* @author Tong
*/
class PriorityQueue {
private Vertex[] nodes;
private int count;
public PriorityQueue(int vertex) {
this.nodes = new Vertex[vertex+1];
this.count = 0;
}
/**
* 隊首元素出佇列
* @return 隊首元素
*/
Vertex poll() {
Vertex vertex = this.nodes[1];
this.nodes[1] = this.nodes[this.count--];
heapifyUpToDown(1);
return vertex;
}
/**
* 添加元素并按優先級堆化
* @param vertex
*/
void add(Vertex vertex) {
this.nodes[++this.count] = vertex;
vertex.id = this.count;
heapifyDownToUp(count);
}
/**
* 更新佇列中元素的distance值
* @param vertex
*/
void update(Vertex vertex) {
this.nodes[vertex.id].distance = vertex.distance;
heapifyDownToUp(vertex.id);
}
boolean isEmpty() {
return this.count == 0;
}
void clear() {
this.count = 0;
}
/**
* 自上而下堆化
* @param index
*/
private void heapifyUpToDown(int index) {
while (index <= this.count) {
int maxPos = index;
if (index * 2 <= this.count &&
this.nodes[maxPos].distance > this.nodes[index*2].distance) {
maxPos = 2 * index;
} else if ((index * 2 + 1) <= count &&
this.nodes[maxPos].distance > this.nodes[index*2+1].distance) {
maxPos = index * 2 + 1;
} else if (maxPos == index) {
break;
}
swap(index, maxPos);
index = maxPos;
}
}
/**
* 自下而上堆化
* @param index
*/
private void heapifyDownToUp(int index) {
while (index / 2 > 0 &&
this.nodes[index].distance < this.nodes[index / 2].distance) {
swap(index, index / 2);
index /= 2;
}
}
/**
* 交換兩個元素對應的下標的值
* @param index
* @param maxPos
*/
private void swap(int index, int maxPos) {
this.nodes[index].id = maxPos; //下標交換記錄
this.nodes[maxPos].id = index;
Vertex temp = this.nodes[index];
this.nodes[index] = this.nodes[maxPos];
this.nodes[maxPos] = temp;
}
}
A* 演算法的代碼實作和 Dijkstra 演算法的代碼實作，主要有三點區別：
- 優先級佇列構建的方式不同，A* 演算法是根據 f 值（即 f(i) = g(i) + h(i) ），來構建優先級佇列，而 Dijkstra 演算法是根據 distance 值（也就是 g(i) ）來構建優先級佇列；
- A* 演算法在更新頂點 distance 值的時候，會同步更新 f 值；
- 回圈結束的條件也不一樣， Dijkstra 演算法是在終點出佇列的時候才結束，A* 演算法是一旦遍歷到終點就結束，
代碼實作如下👇
package com.tyz.astar.core;
import java.util.LinkedList;
/**
* A*演算法實作有向有權圖的兩點間路徑查找
* @author Tong
*/
public class Graph {
private LinkedList<Edge>[] adj; //鄰接表
private int vertex; //頂點個數
private Vertex[] vertexs;
@SuppressWarnings("unchecked")
public Graph(int vertex) {
this.vertex = vertex;
this.vertexs = new Vertex[this.vertex];
this.adj = new LinkedList[vertex];
for (int i = 0; i < vertex; i++) {
this.adj[i] = new LinkedList<Edge>();
}
}
/**
* 添加頂點
* @param id
* @param x
* @param y
*/
public void addVetex(int id, int x, int y) {
this.vertexs[id] = new Vertex(id, x, y);
}
public void addEdge(int start, int end, int weight) {
this.adj[start].add(new Edge(start, end, weight));
}
/**
* 用A*演算法求strat頂點到end頂點之間的最短距離
* @param start 起始頂點
* @param end 終止頂點
*/
public void astar(int start, int end) {
int[] predecessor = new int[this.vertex]; //用來還原最短路徑
//按照頂點的f值來構建小頂堆
PriorityQueue queue = new PriorityQueue(this.vertex); //小頂堆
boolean[] inqueue = new boolean[this.vertex];
inqueue[start] = true;
this.vertexs[start].distance = 0;
this.vertexs[start].f = 0;
queue.add(this.vertexs[start]);
inqueue[start] = true;
while (!queue.isEmpty()) {
Vertex minVertex = queue.poll(); //取堆頂元素并從佇列中將其從佇列中洗掉
for (int i = 0; i < this.adj[minVertex.id].size(); i++) {
Edge edge = this.adj[minVertex.id].get(i);
Vertex nextVertex = this.vertexs[edge.getEnd()];
if (nextVertex.distance > minVertex.distance + edge.getWeight()) {
nextVertex.distance = minVertex.distance + edge.getWeight();
nextVertex.f = nextVertex.distance +
hManhattan(nextVertex, this.vertexs[end]);
predecessor[nextVertex.id] = minVertex.id;
if (inqueue[nextVertex.id] == true) {
queue.update(nextVertex);
} else {
queue.add(nextVertex);
inqueue[nextVertex.id] = true;
}
}
if (nextVertex.id == end) { //只要到達終點就可以停下了
queue.clear(); //將queue狀態變成empty才能跳出回圈
break;
}
}
}
//輸出路徑
System.out.print(start);
print(start, end, predecessor);
}
private int hManhattan(Vertex v1, Vertex v2) {
return Math.abs(v1.x - v2.x) + Math.abs(v1.y - v2.y);
}
/**
* 遞回列印路徑
* @param start
* @param end
* @param predecessor
*/
private void print(int start, int end, int[] predecessor) {
if (start == end) {
return;
}
print(start, predecessor[end], predecessor);
System.out.println("->" + end);
}
}
盡管 A* 演算法可以更加快速地找到從起點到終點的路線，但是它并不是像 Dijkstra 演算法那樣，找到最短路線，這是為什么呢？
要找出起點 s 到終點 t 的最短路徑，最簡單的方法是，通過回溯窮舉所有從 s 到 t 的不同路徑，然后對比找出最短的那個，不過很顯然，回溯演算法的執行效率非常低，是指數級的，
Dijkstra 演算法在此基礎上，利用動態規劃的思想，對回溯搜索進行了剪枝，只保留起點到某個頂點的最短路徑，繼續往外擴展搜索，動態規劃相較于回溯搜索，只是換了一個實作思路，但它實際上也考察到了所有從起點到終點的路線，所以才能得到最優解，
A* 演算法之所以不能像 Dijkstra 演算法那樣，找到最短路徑，主要原因是兩者的 while 回圈結束條件不一樣，前面我們說過，Dijkstra 演算法是在終點出佇列的時候才結束，A* 演算法是一旦遍歷到終點就結束，對于 Dijkstra 演算法來說，當終點出佇列的時候，終點的 distance 值是優先級佇列中所有頂點的最小值，即便再運行下去，終點的 distance 值也不會再被更新了，對于 A* 演算法來說，一旦遍歷到終點，我們就結束 while 回圈，這個時候，終點的 dist 值未必是最小值，
A* 演算法利用貪心演算法的思路，每次都找 f 值最小的頂點出佇列，一旦搜索到終點就不再繼續考察其他頂點和路線了，所以，它并沒有考察所有的路線，也就不可能找到最短路徑了，
Ⅲ 如何實作游戲尋路問題
要利用 A* 演算法解決游戲尋路的問題，我們只需要將地圖抽象成圖就可以了，不過，游戲中的地圖和一般的地圖是不一樣的，因為游戲中的地圖并不像我們現實生活中那樣，存在規劃非常清晰的道路，更多的是寬闊的荒野、草坪等，所以，我們沒辦法用普通的抽象方法，把岔路口抽象成頂點，把道路抽象成邊，
實際上，我們可以換一種抽象的思路，把整個地圖分割成一個一個的小方塊，在某一個方塊上的人物，只能往上下左右四個方向的方塊上移動，我們可以把每個方塊看作一個頂點，兩個方塊相鄰，我們就在它們之間，連兩條有向邊，并且邊的權值都是 1，所以，這個問題就轉化成了，在一個有向有權圖中，找某一個頂點到另一個頂點的路徑問題，將地圖抽象成邊權值為 1 的有向圖之后，我們就可以套用 A* 演算法，來實作游戲中人物的自動尋路功能了，
Ⅳ 總結
這篇文章我們說的 A* 演算法屬于一種啟發式搜索演算法（Heuristically Search Algorithm），實際上，啟發式搜索演算法并不僅僅只有 A* 演算法，還有很多其他演算法，比如 IDA* 演算法，蟻群演算法，遺傳演算法，模擬退火演算法等等，大家有興趣可以再去看看，
啟發式搜索演算法利用估價函式，避免跑偏，貪心地朝著最有可能到達終點的方向前進，這種演算法找出的路線，并不是最短路線，但是，實際的軟體開發中的路線規劃問題，我們往往并不需要非得找出最短路線，所以，鑒于啟發式搜索演算法能很好地平衡路線質量和執行效率，它在實際的軟體開發中的應用更加廣泛，
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/112343.html
標籤：其他
上一篇：Codeforces Round #671 (Div. 2)A-E題解
下一篇：3D游戲編程與設計--第二次作業