在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=)