首先說下簡(jiǎn)單的原理
image.png
如圖所示簡(jiǎn)易地圖, 其中綠色方塊的是起點(diǎn) (用 A 表示), 中間藍(lán)色的是障礙物, 紅色的方塊 (用 B 表示) 是目的地. 為了可以用一個(gè)二維數(shù)組來表示地圖, 我們將地圖劃分成一個(gè)個(gè)的小方塊.
二維數(shù)組在游戲中的應(yīng)用是很多的, 比如貪吃蛇和俄羅斯方塊基本原理就是移動(dòng)方塊而已. 而大型 游戲的地圖, 則是將各種"地貌"鋪在這樣的小方塊上.
尋路步驟
1. 從起點(diǎn) A 開始, 把它作為待處理的方格存入一個(gè)"開啟列表", 開啟列表就是一個(gè)等待檢查方格 的列表.
2. 尋找起點(diǎn) A 周圍可以到達(dá)的方格, 將它們放入"開啟列表", 并設(shè)置它們的"父方格"為 A.
3. 從"開啟列表"中刪除起點(diǎn) A, 并將起點(diǎn) A 加入"關(guān)閉列表", "關(guān)閉列表"中存放的都是不需要再 次檢查的方格
image.png
圖中淺綠色描邊的方塊表示已經(jīng)加入 "開啟列表" 等待檢查. 淡藍(lán)色描邊的起點(diǎn) A 表示已經(jīng)放入 "關(guān)閉列表" , 它不需要再執(zhí)行檢查.
從 "開啟列表" 中找出相對(duì)最靠譜的方塊, 什么是最靠譜? 它們通過公式 F=G+H 來計(jì)算.
F = G + H
G 表示從起點(diǎn) A 移動(dòng)到網(wǎng)格上指定方格的移動(dòng)耗費(fèi) (可沿斜方向移動(dòng)).
H 表示從指定的方格移動(dòng)到終點(diǎn) B 的預(yù)計(jì)耗費(fèi) (H 有很多計(jì)算方法, 這里我們?cè)O(shè)定只可以 上下左右移動(dòng)).
image.png
我們假設(shè)橫向移動(dòng)一個(gè)格子的耗費(fèi)為 10, 為了便于計(jì)算, 沿斜方向移動(dòng)一個(gè)格子耗費(fèi)是 14. 為了 更直觀的展示如何運(yùn)算 FGH, 圖中方塊的左上角數(shù)字表示 F, 左下角表示 G, 右下角表示 H. 看看是否 跟你心里想的結(jié)果一樣?
從 "開啟列表" 中選擇 F 值最低的方格 C (綠色起始方塊 A 右邊的方塊), 然后對(duì)它進(jìn)行如下處 理:
4. 把它從 "開啟列表" 中刪除, 并放到 "關(guān)閉列表" 中.
5. 檢查它所有相鄰并且可以到達(dá) (障礙物和 "關(guān)閉列表" 的方格都不考慮) 的方格. 如果這
些方格 還不在 "開啟列表" 里的話, 將它們加入 "開啟列表", 計(jì)算這些方格的 G, H 和 F 值
各是多少, 并設(shè)置 它們的 "父方格" 為 C.
6. 如果某個(gè)相鄰方格 D 已經(jīng)在 "開啟列表" 里了, 檢查如果用新的路徑 (就是經(jīng)過 C 的路
徑) 到 達(dá)它的話, G 值是否會(huì)更低一些, 如果新的 G 值更低, 那就把它的 "父方格" 改為目前
選中的方格 C, 然 后重新計(jì)算它的 F 值和 G 值 (H 值不需要重新計(jì)算, 因?yàn)閷?duì)于每個(gè)方塊,
H 值是不變的). 如果新的 G 值比較高, 就說明經(jīng)過 C 再到達(dá) D 不是一個(gè)明智的選擇, 因?yàn)?它需要更遠(yuǎn)的路, 這時(shí)我們什么也不做.
image.png
如圖, 我們選中了 C 因?yàn)樗?F 值最小, 我們把它從 "開啟列表" 中刪除, 并把它加入 "關(guān)閉列 表". 它右邊上下三個(gè)都是墻, 所以不考慮它們. 它左邊是起始方塊, 已經(jīng)加入到 "關(guān)閉列表" 了, 也不考 慮. 所以它周圍的候選方塊就只剩下 4 個(gè). 讓我們來看看 C 下面的那個(gè)格子, 它目前的 G 是 14, 如 果通過 C 到達(dá)它的話, G 將會(huì)是 10 + 10, 這比 14 要大, 因此我們什么也不做. 然后我們繼續(xù)從 "開啟列表" 中找出 F 值最小的, 但我們發(fā)現(xiàn) C 上面的和下面的同時(shí)為 54, 這 時(shí)怎么辦呢? 這時(shí)隨便取哪一個(gè)都行, 比如我們選擇了 C 下面的那個(gè)方塊 D.
image.png
image.png
那么什么時(shí)候停止呢? —— 當(dāng)我們發(fā)現(xiàn) "開始列表" 里出現(xiàn)了目標(biāo)終點(diǎn)方塊的時(shí)候, 說明路徑已經(jīng) 被找到.
如何找回路徑
image.png
如上圖所示, 除了起始方塊, 每一個(gè)曾經(jīng)或者現(xiàn)在還在 "開啟列表" 里的方塊, 它都有一個(gè) "父方 塊", 通過 "父方塊" 可以索引到最初的 "起始方塊", 這就是路徑.
代碼實(shí)現(xiàn)
public class Point
{
public Point ParentPoint { get; set; }
public float F { get; set; }
public float G { get; set; }
public float H { get; set; }
public int X { get; set; }
public int Y { get; set; }
public bool IsWall { get; set; }
public Point(int x, int y, Point parent = null)
{
this.X = x;
this.Y = y;
this.ParentPoint = parent;
IsWall = false;
}
public void UpdataParent(Point parent, float g)
{
this.ParentPoint = parent;
this.G = g;
F = G + H;
}
}
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class AStar : MonoBehaviour
{
const int mapWith = 8;
const int mapHeight = 6;
private Point[,] map = new Point[mapWith, mapHeight];
// Use this for initialization
void Start()
{
InitMap();
Point start = map[3, 3];
Point end = map[7, 3];
FindPath(start, end);
ShowPath(start, end);
}
void Update()
{
}
void InitMap()
{
for (int x = 0; x < mapWith; x++)
{
for (int y = 0; y < mapHeight; y++)
{
map[x, y] = new Point(x, y);
}
}
map[5, 2].IsWall = true;
map[5, 3].IsWall = true;
map[5, 4].IsWall = true;
}
void ShowPath(Point start,Point end)
{
Point temp = end;
while (true)
{
Debug.Log(temp.X + "," + temp.Y);
Color c = Color.gray;
if (temp == start) c = Color.green;
if (temp == end) c = Color.red;
CreateCube(temp.X,temp.Y,c);
if (temp.ParentPoint == null) break;
temp = temp.ParentPoint;
}
for (int x = 0; x < mapWith; x++)
{
for (int y = 0; y < mapHeight; y++)
{
if (map[x, y].IsWall)
{
CreateCube(x,y,Color.blue);
}
}
}
}
void CreateCube(int x,int y,Color color)
{
GameObject go = GameObject.CreatePrimitive(PrimitiveType.Cube);
go.transform.position = new Vector3(x,y,0);
go.GetComponent<MeshRenderer>().material.color = color;
}
void FindPath(Point start, Point end)
{
List<Point> openList = new List<Point>();
List<Point> closeList = new List<Point>();
openList.Add(start);
while (openList.Count > 0)
{
Point point = FindMinFOfPoint(openList);
openList.Remove(point);
closeList.Add(point);
List<Point> SurroundPoints = GetSurroundPoints(point);
PointsFilter(SurroundPoints,closeList);
foreach (Point SurroundPoint in SurroundPoints)
{
if (openList.IndexOf(SurroundPoint) > -1)
{
float nowG = CalcG(SurroundPoint, point);
if (nowG < SurroundPoint.G)
{
SurroundPoint.UpdataParent(point, nowG);
}
}
else
{
SurroundPoint.ParentPoint = point;
CalcF(SurroundPoint, end);
openList.Add(SurroundPoint);
}
}
if (openList.IndexOf(end) > -1)
break;
}
// start.CalcF();
}
void PointsFilter(List<Point> src, List<Point> closePoint)
{
foreach (Point p in closePoint)
{
if (src.IndexOf(p) > -1)
{
src.Remove(p);
}
}
}
List<Point> GetSurroundPoints(Point point)
{
Point left=null, up=null, down=null, right=null;
Point lu = null, ru = null, ld = null, rd = null;
if (point.Y < mapHeight - 1) up = map[point.X, point.Y + 1];
if (point.Y > 0) down = map[point.X, point.Y - 1];
if (point.X > 0) left = map[point.X-1, point.Y];
if (point.X < mapWith - 1) right = map[point.X + 1, point.Y];
if(up!=null&&left!=null)
lu = map[point.X - 1, point.Y+1];
if (up != null && right != null)
ru = map[point.X + 1, point.Y + 1];
if (down != null && left != null)
ld = map[point.X - 1, point.Y - 1];
if (down != null && right != null)
rd = map[point.X + 1, point.Y - 1];
List<Point> list = new List<Point>();
if (down != null && down.IsWall == false)
list.Add(down);
if (up != null && up.IsWall == false)
list.Add(up);
if (left != null && left.IsWall == false)
list.Add(left);
if (right != null && right.IsWall == false)
list.Add(right);
if(lu!=null&&lu.IsWall==false&&left.IsWall==false&&up.IsWall==false)
list.Add(lu);
if (ru != null && ru.IsWall == false && right.IsWall == false && up.IsWall == false)
list.Add(ru);
if (ld != null && ld.IsWall == false && left.IsWall == false && down.IsWall == false)
list.Add(ld);
if (rd != null && rd.IsWall == false && right.IsWall == false && down.IsWall == false)
list.Add(rd);
return list;
}
Point FindMinFOfPoint(List<Point> openList)
{
float f = float.MaxValue;
Point temp = null;
foreach (Point p in openList)
{
if (p.F < f)
{
temp = p;
f = p.F;
}
}
return temp;
}
float CalcG(Point now,Point parent)
{
return Vector2.Distance(new Vector2(now.X, now.Y), new Vector2(parent.X, parent.Y)) + parent.G;
}
public void CalcF(Point now, Point end)
{
float h = Mathf.Abs(end.X - now.X) + Mathf.Abs(end.Y - now.Y);
float g = 0;
if (now.ParentPoint == null)
{
g = 0;
}
else
{
g = Vector2.Distance(new Vector2(now.X, now.Y), new Vector2(now.ParentPoint.X, now.ParentPoint.Y)) + now.ParentPoint.G;
}
float f = g + h;
now.F = f;
now.G = g;
now.H = h;
}
}
運(yùn)行后，綠色代表起點(diǎn)，紅色代表終點(diǎn)，藍(lán)色是障礙物，灰色就是最短路徑了。
image.png
相關(guān)插件:A* Pathfinding Project
