初步了解了一些寻路算法后,本以为dijstra是比较合适的寻路算法,今天仔细看了关于A星寻路算法的教程和视频后,我认为A星寻路算法很适合战棋游戏。由于我的项目是仿照小小合金的玩法,所以是只需要上下左右寻路的正方形格子地图。
A星寻路的原理和教程我就不班门弄斧了,百度前几个都是大神写的。对着前辈的教程,我简单修改了一部分代码后做了一个简单的demo,又花了一个晚上将跑通的demo的脚本移植到项目了,在博客里就只贴出demo里的脚本了,作为我的学习记录。
其中有一部分不是很懂,写的注释(理解)可能是错的,以后有时间会重新学习和修改的。
Point类,存储着每一个点的各种属性,父点、F、G、H值,x、z坐标
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 Z { get; set; } public bool IsObstacle { get; set; } public Point(int x, int z, Point parent = null) { this.X = x; this.Z = z; this.ParentPoint = parent; } public void UpdateParent(Point parent,float g) { this.ParentPoint = parent; this.G = g; F = G + H; } }
AStar类,根据需要能得到移动路径点列表、移动所需要的步数、障碍物(不能走的格子)
public class AStar : MonoBehaviour { private const int mapWith = 5; private const int mapHeight = 5; private Point[,] map; Point start; Point end; public GameObject player; List<Point> pointList = new List<Point>(); Vector3 targetPos; int step; void Update () { if (pointList.Count == 0) return; Move(); } void InitPath(int row,int column) { map = new Point[row, column]; InitMap(); start = map[0, 0];//起始坐标 end = map[1, 2];//目标点坐标 FindPath(start, end); SetPathByParent(start, end); } //移动方法 void Move() { for (int i = pointList.Count; i > 0; i--) { Vector3 pointPos = new Vector3(pointList[i - 1].X, player.transform.position.y, pointList[i - 1].Z); if (player.transform.position == pointPos) { pointList.Remove(pointList[i - 1]); break; } if (i == pointList.Count) { targetPos = pointPos; break; } } player.transform.position = Vector3.MoveTowards(player.transform.position, targetPos, 1 * Time.deltaTime); } //将通过父点,将路径点添加进列表 private void SetPathByParent(Point start, Point end) { Point temp = end; pointList.Add(temp); while (true) { if (temp.ParentPoint == null) break; temp = temp.ParentPoint; step++; pointList.Add(temp); } Debug.Log(step); } //点过滤方法,关闭列表里存在的点——其本身,在周围能走的点列表里移除该点 private void PointsFilter(List<Point> src, List<Point> closeList) { foreach (Point p in closeList) { if (src.IndexOf(p) > -1) { src.Remove(p); } } } //初始化格子坐标和属性 private void InitMap() { for (int x = 0; x < mapWith; x++) { for (int z = 0; z < mapHeight; z++) { map[x, z] = new Point(x, z); } } //设置某点为障碍物 map[0, 1].IsObstacle = true; } //寻找路径方法,传入起始点和结束点, private void FindPath(Point start, Point end) { //声明开启列表和结束列表,将起始点添加进开启列表 List<Point> openList = new List<Point>(); List<Point> closeList = new List<Point>(); openList.Add(start); //如果开启列表数量不为0 while (openList.Count > 0) { //找到开启列表里最小F值的点,将该点移除开启列表,添加进关闭列表 Point point = FindMinFOfPoint(openList); openList.Remove(point); closeList.Add(point); //得到该点的周围的点,并将关闭列表里最小F值的点从中移除 List<Point> surroundPoints = GetSurroundPoints(point); PointsFilter(surroundPoints, closeList); //遍历周围能走的点列表,第一次循环结束后,开启列表里最小F值的点为所以周围的点的父点,并且周围的点都添加进了开启列表 foreach (Point surroundPoint in surroundPoints) { //如果周围的点在开启列表里,计算当前遍历到的周围的点的G值 if (openList.IndexOf(surroundPoint) > -1) { float nowG = CalcG(surroundPoint, point); if (nowG < surroundPoint.G) { surroundPoint.UpdateParent(point, nowG); } } //不在开启列表里,将当前点设为周围能走的点的父点,计算周围点的F、H、G值,将其添加进开启列表 else { surroundPoint.ParentPoint = point; CalcF(surroundPoint, end); openList.Add(surroundPoint); } } //如果开启列表为空,跳出循环 if (openList.IndexOf(end) > -1) { break; } } } //得到周围点方法 private List<Point> GetSurroundPoints(Point point) { //默认点有四个方向,上下左右四个点,由地图大小判断四个点是否存在 Point up = null, down = null, left = null, right = null; //Point lu = null, ru = null, ld = null, rd = null; if (point.Z < mapHeight - 1) { up = map[point.X, point.Z + 1]; } if (point.Z > 0) { down = map[point.X, point.Z - 1]; } if (point.X > 0) { left = map[point.X - 1, point.Z]; } if (point.X < mapWith - 1) { right = map[point.X + 1, point.Z]; } //判断上下左右点是否为障碍物点,返回存储能走的点的list List<Point> list = new List<Point>(); if (down != null && down.IsObstacle == false) { list.Add(down); } if (up != null && up.IsObstacle == false) { list.Add(up); } if (left != null && left.IsObstacle == false) { list.Add(left); } if (right != null && right.IsObstacle == false) { list.Add(right); } return list; } //在开启列表里寻找最小F值的点,并返回该点 private Point FindMinFOfPoint(List<Point> openList) { //初始化f值为最大值,遍历开启列表,判断开启列表里F值最小的点,即为最合适的点 float f = float.MaxValue; Point temp = null; foreach (Point p in openList) { if (p.F < f) { temp = p; f = p.F; } } return temp; } //返回由父点计算得到的当前点的G值 private float CalcG(Point now, Point parent) { return Vector2.Distance(new Vector2(now.X, now.Z), new Vector2(parent.X, parent.Z))+parent.G; } //计算F值,传入当前点和结束点 private void CalcF(Point now,Point end) { //得到当前点和结束点的x、z两坐标值之差的绝对值之和为h值,g初始化为0 float h = Mathf.Abs(end.X-now.X) + Mathf.Abs(end.Z-now.Z); float g = 0; //如果当前点没有父点,说明为起始点,g值为0 if (now.ParentPoint == null) g = 0; //如果有父点,则计算当前点到父点的距离加上父点的g值就为当前点的g值 else g = Vector2.Distance(new Vector2(now.X, now.Z), new Vector2(now.ParentPoint.X, now.ParentPoint.Z))+ now.ParentPoint.G; float f = g + h; now.F = f; now.G = g; now.H = h; } }