在Unity中建立類A_Star，其内複制下述全文，再根據下文中講述的應用案例就可以明白如何使用了
using System.Collections.Generic;
using UnityEngine;
public class A_Star
{
/*
自己書寫的Unity可使用的A星算法(C#版)
該腳本僅針對上下左右移動，沒有做斜向移動
如果要看算法過程，可以轉到最下面，不保證說明正确或清晰
*/
/*
該腳本應用舉例：
//設定地圖stringMap，可走點1，不可走點0，比如：
string stringMap =//作為地圖資料
"0000001111" +
"0000111000" +
"0000011010" +
"0011111010" +
"0110101010" +
"1111111000";
int maxX = 9;//行從0計到9，則聲明maxX=9
int maxY = 5;//列從0計到5，則聲明maxY=5
//上方資料中，最左下角為坐标(0,0)，然後：
Vector2Int[] way;
A_Star.GetWay(new Vector2Int(1, 0), new Vector2Int(6, 4), stringMap,maxX,maxY, out way);
//就可以得到stringMap中，從坐标(0,0)到坐标(6,4)的路線way，way[0]表示起點坐标，其後元素順序與路徑上經過的各點一緻
-------------------------------------------------------------------
//或者使用int[]作為地圖資料也行，比如：
int[] intMap =
{
0,1,1,1,1
1,1,0,1,1
1,0,0,0,1
}
int maxX=4;//行從0計到4，則聲明maxX=4
int maxY=2;//列從0計到2，則聲明maxY=2
//上方資料中，最左下角為坐标(0,0)，然後：
Vector2Int[] way;
A_Star.GetWay(new Vector2Int(0,1),new Vector2Int(4,0),intMap,maxX,maxY,out way);
//就可以得到intMap中，從坐标(0,1)到坐标(4,0)的路線way，way[0]表示起點坐标，其後元素順序與路徑上經過的各點一緻
-------------------------------------------------------------------
//如果對同一個地圖使用多次A_Star尋路，那麼使用下述方式最好：
A_Star.Point[][] points=A_Star.GetPointsMatrixByStringMap(stringMap,maxX,maxY);//或根據intMap得到points
A_Star.GetWay(new VectorInt(起點1x,起點1y), new VectorInt(終點1x,終點1y), points, out way);
A_Star.GetWay(new VectorInt(起點2x,起點2y), new VectorInt(終點2x,終點2y), points, out way);
A_Star.GetWay(new VectorInt(起點3x,起點3y), new VectorInt(終點3x,終點3y), points, out way);
//...
//上述将Point[][]類型資料暫存起來，再多次使用GetWay
*/
//根據string型地圖以及起點，終點，來試圖擷取路徑(經過點的坐标數組)，傳回是否存在一條可行的路徑
public static bool GetWay(Vector2Int startPos, Vector2Int endPos, string stringMap, int maxX, int maxY, out Vector2Int[] way)
{
return GetWay(startPos, endPos, GetPointsMatrixByStringMap(stringMap, maxX, maxY), out way);
}
//根據int[]型地圖以及起點，終點，來試圖擷取路徑(經過點的坐标數組)，傳回是否存在一條可行的路徑
public static bool GetWay(Vector2Int startPos, Vector2Int endPos, int[] intMap, int maxX, int maxY, out Vector2Int[] way)
{
return GetWay(startPos, endPos, GetPointsMatrixByIntMap(intMap, maxX, maxY), out way);
}
//根據string型地圖資訊獲得Point[][]類型資料
public static Point[][] GetPointsMatrixByStringMap(string stringMap, int maxX, int maxY)
{
int[] map = GetIntMapByString(stringMap, maxX, maxY);
bool[][] boolMatrix = GetBoolMatrixByIntMap(map, maxX, maxY);
return GetPointsMatrixByBoolMatrix(boolMatrix, maxX, maxY);
}
//根據int[]型地圖資訊獲得Point[][]類型資料
public static Point[][] GetPointsMatrixByIntMap(int[] intMap, int maxX, int maxY)
{
bool[][] boolMatrix = GetBoolMatrixByIntMap(intMap, maxX, maxY);
return GetPointsMatrixByBoolMatrix(boolMatrix, maxX, maxY);
}
//根據Point[][]，以及起點和終點的資訊，獲得最終路徑(經過點的坐标數組)，傳回是否存在一條可行的路徑
public static bool GetWay(Vector2Int startPos, Vector2Int endPos, Point[][] points, out Vector2Int[] way)
{
foreach (var array in points)
{
foreach (var o in array)
{
o.fromStart = int.MaxValue;
o.toEnd = 0;
o.inClosed = false;
o.inOpen = false;
}
}
open.RemoveRange(0, open.Count);
closed.RemoveRange(0, closed.Count);
way = new Vector2Int[0];
Point start = points[startPos.x][startPos.y];
start.Refresh(0, start, endPos.x, endPos.y);
while (true)
{
if (open.Count <= 0) return false;
if (FindMinPointF().CalculateAround(points, endPos))
{
way = GetWayFromPointMatrix(points, startPos, endPos);
return true;
}
}
}
static Point FindMinPointF()
{
int where = -1;
int min = int.MaxValue;
for (int i = 0; i < open.Count; ++i)
if (open[i].F <= min)
{
where = i;
min = open[i].F;
}
return open[where];
}
static Vector2Int[] GetWayFromPointMatrix(Point[][] points, Vector2Int startPos, Vector2Int endPos)
{
List<Vector2Int> wayList = new List<Vector2Int>();
Point prePoint = points[endPos.x][endPos.y];
wayList.Add(new Vector2Int(prePoint.x, prePoint.y));
while (true)
{
if (prePoint.x == startPos.x && prePoint.y == startPos.y) break;
prePoint = prePoint.lastPoint;
wayList.Add(new Vector2Int(prePoint.x, prePoint.y));
}
Vector2Int[] way = new Vector2Int[wayList.Count];
for (int i = 0; i < wayList.Count; ++i)
way[i] = wayList[wayList.Count - 1 - i];
return way;
}
static int[] GetIntMapByString(string stringMap, int maxX, int maxY)
{
int amout = (maxX + 1) * (maxY + 1);
int[] intMap = new int[amout];
char[] cs = stringMap.ToCharArray();
for (int i = 0; i < amout; ++i)
intMap[i] = cs[i] - 48;
return intMap;
}
static bool[][] GetBoolMatrixByIntMap(int[] map, int maxX, int maxY)
{
bool[][] canTo = new bool[maxX + 1][];
for (int i = 0; i <= maxX; ++i)
canTo[i] = new bool[maxY + 1];
int tempX = maxX + 1;
int mapPos;
for (int i = 0; i <= maxX; i += 1)
for (int j = 0; j <= maxY; j += 1)
{
/*
map一行的個數是maxX+1個，一列的個數是maxY+1個
這裡舉一個例子：
這裡有個int[] map如下，其中maxX=5,maxY=3
1,0,1,1,0,1,
1,0,1,1,0,1,
1,1,0,1,0,1,
0,1,1,1,1,1
最左下角(0,0)點對應map的位置是(maxX+1)*(maxY-0)+0=18
(1,0)點對應map的位置是(maxX+1)*(maxY-0)+1=19
(1,1)點對應map的位置是(maxX+1)*(maxY-1)+1=13
(4,3)點對應map的位置是(maxX+1)*(maxY-3)+4=4
這樣就得到了規律(x,y)，x作為加數加到前式的後面，y作為maxY後面的減數
*/
mapPos = tempX * (maxY - j) + i; ;
if (map[mapPos] == 1)
canTo[i][j] = true;
else canTo[i][j] = false;
}
return canTo;
}
static Point[][] GetPointsMatrixByBoolMatrix(bool[][] canTo, int maxX, int maxY)
{
int tempX = maxX + 1, tempY = maxY + 1;
Point[][] points = new Point[tempX][];
for (int i = 0; i < tempX; i += 1)
points[i] = new Point[tempY];
for (int i = 0; i < tempX; i += 1)
for (int j = 0; j < tempY; j += 1)
points[i][j] = new Point(i, j, canTo[i][j]);
return points;
}
static List<Point> open = new List<Point>();
static List<Point> closed = new List<Point>();
public class Point
{
public int x;
public int y;
public int fromStart;//G
public int toEnd;//H
public int F;
public bool canTo;
public bool inOpen;
public bool inClosed;
public Point lastPoint;
public Point(int x, int y, bool canTo)
{
this.x = x; this.y = y; fromStart = int.MaxValue; toEnd = 0;
F = 0; this.canTo = canTo; inOpen = false; inClosed = false;
}
public void Refresh(int _fromStart, Point _lastPoint, int endX, int endY)
{
if (!inOpen)
open.Add(this);
inOpen = true;
int temp = endX - x;
if (temp < 0) temp = -temp;
toEnd += temp;
temp = endY - y;
if (temp < 0) temp = -temp;
toEnd += temp;
if (_fromStart <= fromStart)
{
fromStart = _fromStart;
F = fromStart + toEnd;
lastPoint = _lastPoint;
}
}
public void Passed()
{
closed.Add(this);
for (int i = 0; i < open.Count; ++i)
if (open[i].x == x && open[i].y == y)
{
open.RemoveAt(i);
break;
}
inOpen = false;
inClosed = true;
}
public bool CalculateAround(Point[][] points, Vector2Int endPos)
{
if (x == endPos.x && y == endPos.y)
return true;
int maxX = points.Length - 1;
int maxY = points[0].Length - 1;
if (x - 1 >= 0)
{
if (!points[x - 1][y].inClosed && points[x - 1][y].canTo)
points[x - 1][y].Refresh(fromStart + 1, this, endPos.x, endPos.y);
}
if (x + 1 <= maxX)
{
if (!points[x + 1][y].inClosed && points[x + 1][y].canTo)
points[x + 1][y].Refresh(fromStart + 1, this, endPos.x, endPos.y);
}
if (y - 1 >= 0)
{
if (!points[x][y - 1].inClosed && points[x][y - 1].canTo)
points[x][y - 1].Refresh(fromStart + 1, this, endPos.x, endPos.y);
}
if (y + 1 <= maxY)
{
if (!points[x][y + 1].inClosed && points[x][y + 1].canTo)
points[x][y + 1].Refresh(fromStart + 1, this, endPos.x, endPos.y);
}
Passed();
return false;
}
}
}
/*
包含的資料結構：
Point以及Point[][]，後者記錄整個地圖上的點
每個Point點除了含有坐标值x,y，還含有 fromStart/toEnd/F/[上一個點]/[是否在open清單中]/[是否在closed清單中]
fromStart表示從原點到該點的總路程(fromStart會動态變化)
toEnd表示從該點到目的坐标的直接路程(固定值，就是 橫坐标差(絕對值)+縱坐标差(絕對值))
F值指派為fromStart+toEnd
[上一個點]指派為上一個經過的點(下面有具體的指派方式說明)
[open清單]和[closed清單] 分别記錄 [可以走的點]和[不能再走的點]
------------------------
現在給出了地圖，然後要計算從起點到終點的一條最短路徑：
過程描述：
計算起點的fromStart(=0),toEnd,F，起點的[上一個點]可以指派為空或者自身，然後加入該起點到open清單
然後重複下列步驟，直到找到最終點，如果循環過程中，若open清單元素數量變為0，表示沒有找到一條可行的路徑
{
從open清單中選擇F最小的點記為P點(如果多個點有相同的最小值F，一般取其中最後添加進open清單的點)
然後判斷P點是否為終點，若是，則得到最終路徑(根據每一個點所記錄的[上一個點]可以得到完整路徑)并傳回，若不是，則對該點周圍(上下左右)的每個點C進行下述：
.若C沒有在open清單中，則該點的fromStart指派為P點的fromStart+1，并計算toEnd,F，以及設定C點的[上一個點]為P點，然後将C點添加到open清單，C點的[是否在open清單中]指派為true
.若C已在open清單中，則判斷P點的fromStart+1是否比目前點的fromStart更小，若更小則更新該點的fromStart,F,以及替換[上一個點]為P點
.若C在closed清單中則不計算
加入P點到closed清單(closed清單中的點不會再被計算或重新整理)，P點的[是否在closed清單中]指派為true，[是否在open清單中]指派為false
}
*/
/*
如果将上述腳本用到C#項目，需要建立類Vector2Int，如下：
public class Vector2Int
{
public int x;
public int y;
public Vector2Int(){}
public Vector2Int(int x,int y)
{
this.x=x;
this.y=y;
}
}
*/
![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)