在遊戲中，有一個很常見地需求，就是要讓一個角色從A點走向B點，我們期望是讓角色走最少的路。嗯，大家可能會說，直線就是最短的。沒錯，但大多數時候，A到B中間都會出現一些角色無法穿越的東西，比如牆、坑等障礙物。這個時候怎麼辦呢？ 是的，我們需要有一個算法來解決這個問題，算法的目标就是計算出兩點之間的最短路徑，而且要能避開障礙物。
百度百科：
A*搜尋算法俗稱A星算法。這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的算法。常用于遊戲中的NPC的移動計算，或線上遊戲的BOT的移動計算上。
簡化搜尋區域
要實作尋路，第一步我們要把場景簡化出一個易于控制的搜尋區域。
怎麼處理要根據遊戲來決定了。例如，我們可以将搜尋區域劃分成像素點，但是這樣的劃分粒度對于一般的遊戲來說太高了(沒必要)。
作為代替，我們使用格子(一個正方形)作為尋路算法的單元。其他的形狀類型也是可能的(比如三角形或者六邊形)，但是正方形是最簡單并且最常用的。
比如地圖的長是w=2000像索，寬是h=2000像索，那麼我們這個搜尋區域可以是二維數組 map[w, h], 包含有400000個正方形，這實在太多了，而且很多時候地圖還會更大。
現在讓我們基于目前的區域，把區域劃分成多個格子來代表搜尋空間(在這個簡單的例子中，20*20個格子 = 400 個格子， 每個格式代表了100像索)：
既然我們建立了一個簡單的搜尋區域，我們來讨論下A星算法的工作原理吧。我們需要兩個清單 (Open和Closed清單)：
一個記錄下所有被考慮來尋找最短路徑的格子(稱為open 清單)
一個記錄下不會再被考慮的格子(成為closed清單)
首先在closed清單中添加目前位置(我們把這個開始點稱為點 “A”)。然後，把所有與它目前位置相鄰的可通行格子添加到open清單中。
現在我們要從A出發到B點。
在尋路過程中，角色總是不停從一個格子移動到另一個相鄰的格子，如果單純從距離上講，移動到與自身斜對角的格子走的距離要長一些，而移動到與自身水準或垂直方面平行的格子，則要近一些。
為了描述這種差別，先引入二個概念：
節點(Node)：每個格子都可以稱為節點。
代價(Cost)：描述角色移動到某個節點時所走的距離(或難易程度)。
如上圖，如果每水準或垂直方向移動相鄰一個節點所花的代價記為1，則相鄰對角節點的代碼為1.4(即2的平方根--勾股定理)
通常尋路過程中的代價用f,g,h來表示
g代表(從指定節點到相鄰)節點本身的代價--即上圖中的1或1.4
h代表從指定節點到目标節點(根據不同的估價公式--後面會解釋估價公式)估算出來的代價。
而 f = g + h 表示節點的總代價
///
/// 尋路節點
///
public class NodeItem {
// 是否是障礙物
public bool isWall;
// 位置
public Vector3 pos;
// 格子坐标
public int x, y;
// 與起點的長度
public int gCost;
// 與目标點的長度
public int hCost;
// 總的路徑長度
public int fCost {
get {return gCost + hCost; }
}
// 父節點
public NodeItem parent;
public NodeItem(bool isWall, Vector3 pos, int x, int y) {
this.isWall = isWall;
this.pos = pos;
this.x = x;
this.y = y;
}
}
注意：這裡有二個新的東東 isWall 和 parent。
通常障礙物本身也可以看成是由若幹個不可通過的節點所組成，是以 isWall 是用來标記該節點是否為障礙物(節點)。
另外：在考查從一個節點移動到另一個節點時，總是拿自身節點周圍的8個相鄰節點來說事兒，相對于周邊的節點來講，自身節點稱為它們的父節點(parent).
前面一直在提“網格，網格”，幹脆把它也封裝成類Grid.cs
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
public class Grid : MonoBehaviour {
public GameObject NodeWall;
public GameObject Node;
// 節點半徑
public float NodeRadius = 0.5f;
// 過濾牆體所在的層
public LayerMask WhatLayer;
// 玩家
public Transform player;
// 目标
public Transform destPos;
///
/// 尋路節點
///
public class NodeItem {
// 是否是障礙物
public bool isWall;
// 位置
public Vector3 pos;
// 格子坐标
public int x, y;
// 與起點的長度
public int gCost;
// 與目标點的長度
public int hCost;
// 總的路徑長度
public int fCost {
get {return gCost + hCost; }
}
// 父節點
public NodeItem parent;
public NodeItem(bool isWall, Vector3 pos, int x, int y) {
this.isWall = isWall;
this.pos = pos;
this.x = x;
this.y = y;
}
}
private NodeItem[,] grid;
private int w, h;
private GameObject WallRange, PathRange;
private List pathObj = new List ();
void Awake() {
// 初始化格子
w = Mathf.RoundToInt(transform.localScale.x * 2);
h = Mathf.RoundToInt(transform.localScale.y * 2);
grid = new NodeItem[w, h];
WallRange = new GameObject ("WallRange");
PathRange = new GameObject ("PathRange");
// 将牆的資訊寫入格子中
for (int x = 0; x < w; x++) {
for (int y = 0; y < h; y++) {
Vector3 pos = new Vector3 (x*0.5f, y*0.5f, -0.25f);
// 通過節點中心發射圓形射線，檢測目前位置是否可以行走
bool isWall = Physics.CheckSphere (pos, NodeRadius, WhatLayer);
// 建構一個節點
grid[x, y] = new NodeItem (isWall, pos, x, y);
// 如果是牆體，則畫出不可行走的區域
if (isWall) {
GameObject obj = GameObject.Instantiate (NodeWall, pos, Quaternion.identity) as GameObject;
obj.transform.SetParent (WallRange.transform);
}
}
}
}
// 根據坐标獲得一個節點
public NodeItem getItem(Vector3 position) {
int x = Mathf.RoundToInt (position.x) * 2;
int y = Mathf.RoundToInt (position.y) * 2;
x = Mathf.Clamp (x, 0, w - 1);
y = Mathf.Clamp (y, 0, h - 1);
return grid [x, y];
}
// 取得周圍的節點
public List getNeibourhood(NodeItem node) {
List list = new List ();
for (int i = -1; i <= 1; i++) {
for (int j = -1; j <= 1; j++) {
// 如果是自己，則跳過
if (i == 0 && j == 0)
continue;
int x = node.x + i;
int y = node.y + j;
// 判斷是否越界，如果沒有，加到清單中
if (x < w && x >= 0 && y < h && y >= 0)
list.Add (grid [x, y]);
}
}
return list;
}
// 更新路徑
public void updatePath(List lines) {
int curListSize = pathObj.Count;
for (int i = 0, max = lines.Count; i < max; i++) {
if (i < curListSize) {
pathObj [i].transform.position = lines [i].pos;
pathObj [i].SetActive (true);
} else {
GameObject obj = GameObject.Instantiate (Node, lines [i].pos, Quaternion.identity) as GameObject;
obj.transform.SetParent (PathRange.transform);
pathObj.Add (obj);
}
}
for (int i = lines.Count; i < curListSize; i++) {
pathObj [i].SetActive (false);
}
}
}
在尋路的過程中“條條道路通羅馬”，路徑通常不止一條，隻不過所花的代價不同而已。
是以我們要做的事情，就是要盡最大努力找一條代價最小的路徑。
但是，即使是代價相同的最佳路徑，也有可能出現不同的走法。
用代碼如何估算起點與終點之間的代價呢？
//曼哈頓估價法
private function manhattan(node:Node):Number
{
return Math.abs(node.x - _endNode.x) * _straightCost + Math.abs(node.y + _endNode.y) * _straightCost;
}
//幾何估價法
private function euclidian(node:Node):Number
{
var dx:Number=node.x - _endNode.x;
var dy:Number=node.y - _endNode.y;
return Math.sqrt(dx * dx + dy * dy) * _straightCost;
}
//對角線估價法
private function diagonal(node:Node):Number
{
var dx:Number=Math.abs(node.x - _endNode.x);
var dy:Number=Math.abs(node.y - _endNode.y);
var diag:Number=Math.min(dx, dy);
var straight:Number=dx + dy;
return _diagCost * diag + _straightCost * (straight - 2 * diag);
}
上面的代碼給出了三種基本的估價算法(也稱估價公式)，其算法示意圖如下：
如上圖，對于“曼哈頓算法”最貼切的描述莫過于孫燕姿唱過的那首成名曲“直來直往”，筆直的走，然後轉個彎，再筆直的繼續。
“幾何算法”的最好解釋就是“勾股定理”，算出起點與終點之間的直線距離，然後乘上代價因子。
“對角算法”綜合了以上二種算法，先按對角線走，一直走到與終點水準或垂直平行後，再筆直的走。
這三種算法可以實作不同的尋路結果，我們這個例子用的是“對角算法”：
// 擷取兩個節點之間的距離
int getDistanceNodes(Grid.NodeItem a, Grid.NodeItem b) {
int cntX = Mathf.Abs (a.x - b.x);
int cntY = Mathf.Abs (a.y - b.y);
// 判斷到底是那個軸相差的距離更遠 ， 實際上，為了簡化計算，我們将代價*10變成了整數。
if (cntX > cntY) {
return 14 * cntY + 10 * (cntX - cntY);
} else {
return 14 * cntX + 10 * (cntY - cntX);
}
}
好吧，下面直接貼出全部的尋路算法 FindPath.cs:
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
public class FindPath : MonoBehaviour {
private Grid grid;
// Use this for initialization
void Start () {
grid = GetComponent ();
}
// Update is called once per frame
void Update () {
FindingPath (grid.player.position, grid.destPos.position);
}
// A*尋路
void FindingPath(Vector3 s, Vector3 e) {
Grid.NodeItem startNode = grid.getItem (s);
Grid.NodeItem endNode = grid.getItem (e);
List openSet = new List ();
HashSet closeSet = new HashSet ();
openSet.Add (startNode);
while (openSet.Count > 0) {
Grid.NodeItem curNode = openSet [0];
for (int i = 0, max = openSet.Count; i < max; i++) {
if (openSet [i].fCost <= curNode.fCost &&
openSet [i].hCost < curNode.hCost) {
curNode = openSet [i];
}
}
openSet.Remove (curNode);
closeSet.Add (curNode);
// 找到的目标節點
if (curNode == endNode) {
generatePath (startNode, endNode);
return;
}
// 判斷周圍節點，選擇一個最優的節點
foreach (var item in grid.getNeibourhood(curNode)) {
// 如果是牆或者已經在關閉清單中
if (item.isWall || closeSet.Contains (item))
continue;
// 計算目前相領節點現開始節點距離
int newCost = curNode.gCost + getDistanceNodes (curNode, item);
// 如果距離更小，或者原來不在開始清單中
if (newCost < item.gCost || !openSet.Contains (item)) {
// 更新與開始節點的距離
item.gCost = newCost;
// 更新與終點的距離
item.hCost = getDistanceNodes (item, endNode);
// 更新父節點為目前標明的節點
item.parent = curNode;
// 如果節點是新加入的，将它加入打開清單中
if (!openSet.Contains (item)) {
openSet.Add (item);
}
}
}
}
generatePath (startNode, null);
}
// 生成路徑
void generatePath(Grid.NodeItem startNode, Grid.NodeItem endNode) {
List path = new List();
if (endNode != null) {
Grid.NodeItem temp = endNode;
while (temp != startNode) {
path.Add (temp);
temp = temp.parent;
}
// 反轉路徑
path.Reverse ();
}
// 更新路徑
grid.updatePath(path);
}
// 擷取兩個節點之間的距離
int getDistanceNodes(Grid.NodeItem a, Grid.NodeItem b) {
int cntX = Mathf.Abs (a.x - b.x);
int cntY = Mathf.Abs (a.y - b.y);
// 判斷到底是那個軸相差的距離更遠
if (cntX > cntY) {
return 14 * cntY + 10 * (cntX - cntY);
} else {
return 14 * cntX + 10 * (cntY - cntX);
}
}
}
運作效果圖：
紅色區域是辨別出來的不可以行走區域。(代碼中對兩個點的定位有點小小的問題，不過不影響算法的示範，我也就懶得改了)
![android a*算法尋路,A*尋路算法的簡單實作[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)