a星 unity3d

2019-11-01 20:08:53 xhugleixin123 阅读数 99
  • Unity 值得看的500+ 技术内容列表

    Unity3D是由Unity Technologies开发的一个让玩家轻松创建诸如三维视频游戏、建筑可视化、实时三维动画等类型互动内容的多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

A星算法

算法分析

在这里插入图片描述

  • Node的属性
    • gCost
    • 利用currentNode来来计算
    • 从起点到currentNode再到neighbourNode的距离=gCost
    • hCost
    • 网格到targetNode的距离
    • fCost
    • fCost = gCost + hCost
    • parent
    • neighbourNode的parent就是使其gCost最短的Node
    • neighbourNode不在openlist中,则parent = currentNode

  • openList
    • 可查找的序列,用来遍历最小的fCost的序列数组
    • 每次查找neighbourNode时,都会把不在openList中的neighbourNode添加进去

  • closeList

    • 选择最大的fCost的Node作为currentNode,并把currentNode从openList从openlist移除,并放入closeList中
  • findPath过程

    1.startTarget加入openlist,遍历openlist中fCost最小的Node作为currentNode(此时只有startNode)
    2.将currentNode从openList中移除,并加入closeList
    3.遍历出currentNode的neighbourNode,并计算neighbourNode的gCost和hCost,若gCost变小,则parent为currentNode,如果neighbourNode不在openList中,则将neighbourNode加入到openlist中,并且parent为currentNode。
    4.查找openlist中fCost最小的Node,循环到步骤1重新开始
    直到将targetNode添加入openList中,遍历结束。

    路径:

targetNode
targetNode.parent
targetNode.parent.parent
...
startNode
  • 距离计算
    在这里插入图片描述

    • dis = 14y + 10( x - y )
    • 其中x,y为Node的下标
  • 总结

    • 每个Node的parent都是从startNode到parent再到Node的距离最短
    • 每个current都是fCost最小,有同样的parent的Node到targetNode的距离也最短
    • 可以理解为每个Node到起点的距离最短,到终点的距离也最短,故总的距离最短
2013-12-27 23:54:35 aisajiajiao 阅读数 15602
  • Unity 值得看的500+ 技术内容列表

    Unity3D是由Unity Technologies开发的一个让玩家轻松创建诸如三维视频游戏、建筑可视化、实时三维动画等类型互动内容的多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

这篇文章翻译自Unity 4.x Game AI Programming这本书第七章

在本章中,我们将在Unity3D环境中使用C#实现A*算法.尽管有很多其他算法,像Dijkstra算法,但A*算法以其简单性和有效性而广泛的应用于游戏和交互式应用中.我们之前在第一章AI介绍中短暂的涉及到了该算法.不过现在我们从实现的角度来再次复习该算法.

A*算法复习

在我们进入下一部分实现A*之前,我们再次复习一下A*算法.首先,我们将需要用可遍历的数据结构来表示地图.尽管可能有很多结构可实现,在这个例子中我们将使用2D格子数组.我们稍后将实现GridManager类来处理这个地图信息.我们的类GridManager将记录一系列的Node对象,这些Node对象才是2D格子的主题.所以我们需要实现Node类来处理一些东西,比如节点类型,他是是一个可通行的节点还是障碍物,穿过节点的代价和到达目标节点的代价等等.

我们将用两个变量来存储已经处理过的节点和我们要处理的节点.我们分别称他们为关闭列表和开放列表.我们将在PriorityQueue类里面实现该列表类型.我们现在看看它:

  1. 首先,从开始节点开始,将开始节点放入开放列表中.
  2. 只要开放列表中有节点,我们将进行一下过程.
  3. 从开放列表中选择第一个节点并将其作为当前节点(我们将在代码结束时提到它,这假定我们已经对开放列表排好序且第一个节点有最小代价值).
  4. 获得这个当前节点的邻近节点,它们不是障碍物,像一堵墙或者不能穿越的峡谷一样.
  5. 对于每一个邻近节点,检查该邻近节点是否已在关闭列表中.如果不在,我们将为这个邻近节点计算所有代价值(F),计算时使用下面公式:F = G + H,在前面的式子中,G是从上一个节点到这个节点的代价总和,H是从当前节点到目的节点的代价总和.
  6. 将代价数据存储在邻近节点中,并且将当前节点保存为该邻近节点的父节点.之后我们将使用这个父节点数据来追踪实际路径.
  7. 将邻近节点存储在开放列表中.根据到他目标节点的代价总和,以升序排列开放列表.
  8. 如果没有邻近节点需要处理,将当前节点放入关闭列表并将其从开放列表中移除.
  9. 返回第二步
一旦你完成了这个过程,你的当前节点将在目标节点的位置,但只有当存在一条从开始节点到目标节点的无障碍路径.如果当前节点不在目标节点,那就没有从目标节点到当前节点的路径.如果存在一条正确的路径我们现在所能做的就是从当前节点的父节点开始追溯,直到我们再次到达开始节点.这样我们得到一个路径列表,其中的节点都是我们在寻路过程中选择的,并且该列表从目标节点排列到开始节点.之后我们翻转这个路径列表,因为我们需要知道从开始节点到目标节点的路径.

这就是我们将在Unity3D中使用C#实现的算法概览.所以,搞起吧.

实现

我们将实现我们之前提到过的基础类比如Node类,GridManager类和PriorityQueue类.我们将在后续的主AStar类里面使用它们.

Node

Node类将处理代表我们地图的2D格子中其中的每个格子对象,一下是Node.cs文件.
using UnityEngine;
using System.Collections;
using System;

public class Node : IComparable {
	public float nodeTotalCost;
	public float estimatedCost;
	public bool bObstacle;
	public Node parent;
	public Vector3 position;
	
	public Node() {
		this.estimatedCost = 0.0f;
		this.nodeTotalCost = 1.0f;
		this.bObstacle = false;
		this.parent = null;
	}
	
	public Node(Vector3 pos) {
		this.estimatedCost = 0.0f;
		this.nodeTotalCost = 1.0f;
		this.bObstacle = false;
		this.parent = null;
		this.position = pos;
	}
	
	public void MarkAsObstacle() {
		this.bObstacle = true;
	}
Node类有其属性,比如代价值(G和H),标识其是否是障碍物的标记,和其位置和父节点. nodeTotalCost是G,它是从开始节点到当前节点的代价值,estimatedCost是H,它是从当前节点到目标节点的估计值.我们也有两个简单的构造方法和一个包装方法来设置该节点是否为障碍物.之后我们实现如下面代码所示的CompareTo方法:
	public int CompareTo(object obj)
	{
		Node node = (Node) obj;
		//Negative value means object comes before this in the sort order.
		if (this.estimatedCost < node.estimatedCost)
				return -1;
		//Positive value means object comes after this in the sort order.
		if (this.estimatedCost > node.estimatedCost)
				return 1;
		return 0;
	}
}
这个方法很重要.我们的Node类继承自ICompare因为我们想要重写这个CompareTo方法.如果你能想起我们在之前算法部分讨论的东西,你会注意到我们需要根据所有预估代价值来排序我们的Node数组.ArrayList类型有个叫Sort.Sort的方法,该方法只是从列表中的对象(在本例中是Node对象)查找对象内部实现的CompareTo方法.所以,我们实现这个方法并根据estimatedCost值来排序Node对象.你可以从以下资源中了解到更多关于.Net framework的该特色.

PriorityQueue

PriorityQueue是一个简短的类,使得ArrayList处理节点变得容易些,PriorityQueue.cs展示如下:
using UnityEngine;
using System.Collections;
public class PriorityQueue {
	private ArrayList nodes = new ArrayList();
	
	public int Length {
		get { return this.nodes.Count; }
	}
	
	public bool Contains(object node) {
		return this.nodes.Contains(node);
	}
	
	public Node First() {
		if (this.nodes.Count > 0) {
			return (Node)this.nodes[0];
		}
				return null;
	}
	
	public void Push(Node node) {
		this.nodes.Add(node);
		this.nodes.Sort();
	}
	
	public void Remove(Node node) {
		this.nodes.Remove(node);
		//Ensure the list is sorted
		this.nodes.Sort();
	}
}
上面的代码很好理解.需要注意的一点是从节点的ArrayList添加或者删除节点后我们调用了Sort方法.这将调用Node对象的CompareTo方法,且将使用estimatedCost值来排序节点.

GridManager

GridManager类处理所有代表地图的格子的属性.我们将GridManager设置单例,因为我们只需要一个对象来表示地图.GridManager.cs代码如下:
using UnityEngine;
using System.Collections;
public class GridManager : MonoBehaviour {
	private static GridManager s_Instance = null;
	public static GridManager instance {
		get {
			if (s_Instance == null) {
				s_Instance = FindObjectOfType(typeof(GridManager)) 
						as GridManager;
				if (s_Instance == null)
					Debug.Log("Could not locate a GridManager " +
							"object. \n You have to have exactly " +
							"one GridManager in the scene.");
			}
			return s_Instance;
		}
	}
我们在场景中寻找GridManager对象,如果找到我们将其保存在s_Instance静态变量里.
public int numOfRows;  
public int numOfColumns;  
public float gridCellSize;  
public bool showGrid = true;  
public bool showObstacleBlocks = true;  
private Vector3 origin = new Vector3();  
private GameObject[] obstacleList;  
public Node[,] nodes { get; set; }  
public Vector3 Origin {  
	get { return origin; }
}
紧接着我们声明所有的变量;我们需要表示我们的地图,像地图行数和列数,每个格子的大小,以及一些布尔值来形象化(visualize)格子与障碍物.此外还要向下面的代码一样保存格子上存在的节点:
	void Awake() {
		obstacleList = GameObject.FindGameObjectsWithTag("Obstacle");
		CalculateObstacles();
	}
	// Find all the obstacles on the map
	void CalculateObstacles() {
		nodes = new Node[numOfColumns, numOfRows];
		int index = 0;
		for (int i = 0; i < numOfColumns; i++) {
			for (int j = 0; j < numOfRows; j++) {
				Vector3 cellPos = GetGridCellCenter(index);
				Node node = new Node(cellPos);
				nodes[i, j] = node;
				index++;
			}
		}
		if (obstacleList != null && obstacleList.Length > 0) {
			//For each obstacle found on the map, record it in our list
			foreach (GameObject data in obstacleList) {
				int indexCell = GetGridIndex(data.transform.position);
				int col = GetColumn(indexCell);
				int row = GetRow(indexCell);
				nodes[row, col].MarkAsObstacle();
			}
		}
	}
我们查找所有标签为Obstacle的游戏对象(game objects)并将其保存在我们的obstacleList属性中.之后在CalculateObstacles方法中设置我们节点的2D数组.首先,我们创建具有默认属性的普通节点属性.在这之后我们查看obstacleList.将其位置转换成行,列数据(即节点是第几行第几列)并更新对应索引处的节点为障碍物.

GridManager有一些辅助方法来遍历格子并得到对应格子的对局.以下是其中一些函数(附有简短说明以阐述它们的是做什么的).实现很简单,所以我们不会过多探究其细节.
GetGridCellCenter方法从格子索引中返回世界坐标系中的格子位置,代码如下:
	public Vector3 GetGridCellCenter(int index) {
		Vector3 cellPosition = GetGridCellPosition(index);
		cellPosition.x += (gridCellSize / 2.0f);
		cellPosition.z += (gridCellSize / 2.0f);
		return cellPosition;
	}
	public Vector3 GetGridCellPosition(int index) {
		int row = GetRow(index);
		int col = GetColumn(index);
		float xPosInGrid = col * gridCellSize;
		float zPosInGrid = row * gridCellSize;
		return Origin + new Vector3(xPosInGrid, 0.0f, zPosInGrid);
	}
GetGridIndex方法从给定位置返回格子中的格子索引:
	public int GetGridIndex(Vector3 pos) {
		if (!IsInBounds(pos)) {
			return -1;
		}
		pos -= Origin;
		int col = (int)(pos.x / gridCellSize);
		int row = (int)(pos.z / gridCellSize);
		return (row * numOfColumns + col);
	}
	public bool IsInBounds(Vector3 pos) {
		float width = numOfColumns * gridCellSize;
		float height = numOfRows* gridCellSize;
		return (pos.x >= Origin.x &&  pos.x <= Origin.x + width &&
				pos.x <= Origin.z + height && pos.z >= Origin.z);
	}
GetRow和GetColumn方法分别从给定索引返回格子的行数和列数.
	public int GetRow(int index) {
		int row = index / numOfColumns;
		return row;
	}
	public int GetColumn(int index) {
		int col = index % numOfColumns;
		return col;
	}
另外一个重要的方法是GetNeighbours,它被AStar类用于检索特定节点的邻接点.
public void GetNeighbours(Node node, ArrayList neighbors) {
	Vector3 neighborPos = node.position;
	int neighborIndex = GetGridIndex(neighborPos);
	int row = GetRow(neighborIndex);
	int column = GetColumn(neighborIndex);
	//Bottom
	int leftNodeRow = row - 1;
	int leftNodeColumn = column;
	AssignNeighbour(leftNodeRow, leftNodeColumn, neighbors);
	//Top
	leftNodeRow = row + 1;
	leftNodeColumn = column;
	AssignNeighbour(leftNodeRow, leftNodeColumn, neighbors);
	//Right
	leftNodeRow = row;
	leftNodeColumn = column + 1;
	AssignNeighbour(leftNodeRow, leftNodeColumn, neighbors);
	//Left
	leftNodeRow = row;
	leftNodeColumn = column - 1;
	AssignNeighbour(leftNodeRow, leftNodeColumn, neighbors);
}

void AssignNeighbour(int row, int column, ArrayList neighbors) {
	if (row != -1 && column != -1 && 
		row < numOfRows && column < numOfColumns) {
	  Node nodeToAdd = nodes[row, column];
	  if (!nodeToAdd.bObstacle) {
		neighbors.Add(nodeToAdd);
	  }
	}
  }
首先,我们在当前节点的左右上下四个方向检索其邻接节点.之后,在AssignNeighbour方法中,我们检查邻接节点看其是否为障碍物.如果不是我们将其添加neighbours中.紧接着的方法是一个调试辅助方法用于形象化(visualize)格子和障碍物.
void OnDrawGizmos() {
		if (showGrid) {
			DebugDrawGrid(transform.position, numOfRows, numOfColumns, 
					gridCellSize, Color.blue);
		}
		Gizmos.DrawSphere(transform.position, 0.5f);
		if (showObstacleBlocks) {
			Vector3 cellSize = new Vector3(gridCellSize, 1.0f,
				gridCellSize);
			if (obstacleList != null && obstacleList.Length > 0) {
				foreach (GameObject data in obstacleList) {
					Gizmos.DrawCube(GetGridCellCenter(
							GetGridIndex(data.transform.position)), cellSize);
				}
			}
		}
	}
	public void DebugDrawGrid(Vector3 origin, int numRows, int
		numCols,float cellSize, Color color) {
		float width = (numCols * cellSize);
		float height = (numRows * cellSize);
		// Draw the horizontal grid lines
		for (int i = 0; i < numRows + 1; i++) {
			Vector3 startPos = origin + i * cellSize * new Vector3(0.0f,
				0.0f, 1.0f);
			Vector3 endPos = startPos + width * new Vector3(1.0f, 0.0f,
				0.0f);
			Debug.DrawLine(startPos, endPos, color);
		}
			// Draw the vertial grid lines
		for (int i = 0; i < numCols + 1; i++) {
			Vector3 startPos = origin + i * cellSize * new Vector3(1.0f,
				0.0f, 0.0f);
			Vector3 endPos = startPos + height * new Vector3(0.0f, 0.0f,
				1.0f);
			Debug.DrawLine(startPos, endPos, color);
		}
	}
}
Gizmos在编辑器场景视图中可以用于绘制可视化的调试并建立辅助.OnDrawGizmos在每一帧都会被引擎调用.所以,如果调试标识showGrid和showObstacleBlocks被勾选我们就是用线条绘制格子使用立方体绘制障碍物.我们就不讲DebugDrawGrid这个简单的方法了.
注意:你可以从Unity3D参考文档了解到更多有关gizmos的资料

AStar

类AStar是将要使用我们目前所实现的类的主类.如果你想复习这的话,你可以返回算法部分.如下面AStar.cs代码所示,我们先声明我们的openList和closedList,它们都是PriorityQueue类型.

using UnityEngine;
using System.Collections;
public class AStar {
	public static PriorityQueue closedList, openList;
接下来我们实现一个叫HeursticEstimatedCost方法来计算两个节点之间的代价值.计算很简单.我们只是通过两个节点的位置向量相减得到方向向量.结果向量的长度便告知了我们从当前节点到目标节点的直线距离.

	private static float HeuristicEstimateCost(Node curNode, 
			Node goalNode) {
		Vector3 vecCost = curNode.position - goalNode.position;
		return vecCost.magnitude;
	}
接下来使我们主要的FindPath方法:

	public static ArrayList FindPath(Node start, Node goal) {
		openList = new PriorityQueue();
		openList.Push(start);
		start.nodeTotalCost = 0.0f;
		start.estimatedCost = HeuristicEstimateCost(start, goal);
		closedList = new PriorityQueue();
		Node node = null;
我们初始化开放和关闭列表.从开始节点开始,我们将其放入开放列表.之后我们便开始处理我们的开放列表.

		while (openList.Length != 0) {
			node = openList.First();
			//Check if the current node is the goal node
			if (node.position == goal.position) {
				return CalculatePath(node);
			}
			//Create an ArrayList to store the neighboring nodes
			ArrayList neighbours = new ArrayList();
			GridManager.instance.GetNeighbours(node, neighbours);
			for (int i = 0; i < neighbours.Count; i++) {
				Node neighbourNode = (Node)neighbours[i];
				if (!closedList.Contains(neighbourNode)) {
					float cost = HeuristicEstimateCost(node,
							neighbourNode);
					float totalCost = node.nodeTotalCost + cost;
					float neighbourNodeEstCost = HeuristicEstimateCost(
							neighbourNode, goal);
					neighbourNode.nodeTotalCost = totalCost;
					neighbourNode.parent = node;
					neighbourNode.estimatedCost = totalCost + 
							neighbourNodeEstCost;
					if (!openList.Contains(neighbourNode)) {
						openList.Push(neighbourNode);
					}
				}
			}
			//Push the current node to the closed list
			closedList.Push(node);
			//and remove it from openList
			openList.Remove(node);
		}
		if (node.position != goal.position) {
			Debug.LogError("Goal Not Found");
			return null;
		}
		return CalculatePath(node);
	}
这代码实现类似于我们之前讨论过的算法,所以如果你对特定的东西不清楚的话可以返回去看看.

  1. 获得openList的第一个节点.记住每当新节点加入时openList都需要再次排序.所以第一个节点总是有到目的节点最低估计代价值.
  2. 检查当前节点是否是目的节点,如果是推出while循环创建path数组.
  3. 创建数组列表保存当前正被处理的节点的临近节点.使用GetNeighbours方法来从格子中检索邻接节点.
  4. 对于每一个在邻接节点数组中的节点,我们检查它是否已在closedList中.如果不在,计算代价值并使用新的代价值更新节点的属性值,更新节点的父节点并将其放入openList中.
  5. 将当前节点压入closedList中并将其从openList中移除.返回第一步.
如果在openList中没有更多的节点,我们的当前节点应该是目标节点如果路径存在的话.之后我们将当前节点作为参数传入CalculatePath方法中.

	private static ArrayList CalculatePath(Node node) {
		ArrayList list = new ArrayList();
		while (node != null) {
			list.Add(node);
			node = node.parent;
		}
		list.Reverse();
		return list;
	}
}
CalculatePath方法跟踪每个节点的父节点对象并创建数组列表.他返回一个从目的节点到开始节点的ArrayList.由于我们需要从开始节点到目标节点的路径,我们简单调用一下Reverse方法就ok.

这就是我们的AStar类.我们将在下面的代码里写一个测试脚本来检验所有的这些东西.之后创建一个场景并在其中使用它们.

TestCode Class

代码如TestCode.cs所示,该类使用AStar类找到从开始节点到目的节点的路径.

using UnityEngine;
using System.Collections;
public class TestCode : MonoBehaviour {
	private Transform startPos, endPos;
	public Node startNode { get; set; }
	public Node goalNode { get; set; }
	public ArrayList pathArray;
	GameObject objStartCube, objEndCube;
	private float elapsedTime = 0.0f;
	//Interval time between pathfinding
	public float intervalTime = 1.0f;
首先我们创建我们需要引用的变量.pathArray用于保存从AStar的FindPath方法返回的节点数组.

	void Start () {
		objStartCube = GameObject.FindGameObjectWithTag("Start");
		objEndCube = GameObject.FindGameObjectWithTag("End");
		pathArray = new ArrayList();
		FindPath();
	}
	void Update () {
		elapsedTime += Time.deltaTime;
		if (elapsedTime >= intervalTime) {
			elapsedTime = 0.0f;
			FindPath();
		}
	}
在Start方法中我们寻找标签(tags)为Start和End的对象并初始化pathArray.如果开始和结束的节点位置变了我们将尝试在每一个我们所设置的intervalTime属性时间间隔里找到我们的新路径.之后我们调用FindPath方法.

	void FindPath() {
		startPos = objStartCube.transform;
		endPos = objEndCube.transform;
		startNode = new Node(GridManager.instance.GetGridCellCenter(
				GridManager.instance.GetGridIndex(startPos.position)));
		goalNode = new Node(GridManager.instance.GetGridCellCenter(
				GridManager.instance.GetGridIndex(endPos.position)));
		pathArray = AStar.FindPath(startNode, goalNode);
	}
因为我们在AStar类中实现了寻路算法,寻路现在变得简单多了.首先,我们获得开始和结束的游戏对象(game objects).之后,我们使用GridManager的辅助方法创建新的Node对象,使用GetGridIndex来计算它们在格子中对应的行列位置.一旦我们将开始节点和目标节点作为参数调用了AStar.FindPath方法并将返回的数组保存在pathArray属性中.接下我们实现OnDrawGizmos方法来绘制并形象化(draw and visualize)我们找到的路径.

	void OnDrawGizmos() {
		if (pathArray == null)
			return;
		if (pathArray.Count > 0) {
			int index = 1;
			foreach (Node node in pathArray) {
				if (index < pathArray.Count) {
					Node nextNode = (Node)pathArray[index];
					Debug.DrawLine(node.position, nextNode.position,
						Color.green);
					index++;
				}
			}
		}
	}
}
我们检查了我们的pathArray并使用Debug.DrawLine方法来绘制线条连接起pathArray中的节点.当运行并测试程序时我们就能看到一条绿线从开始节点连接到目标节点,连线形成了一条路径.

Scene setup

我们将要创建一个类似于下面截图所展示的场景:


Sample test scene

我们将有一个平行光,开始以及结束游戏对象,一些障碍物,一个被用作地面的平面实体和两个空的游戏对象,空对象身上放置GridManager和TestAstar脚本.这是我们的场景层级图.


Scene hierarchy

创建一些立方体实体并给他们加上标签Obstacle,当运行我们的寻路算法时我们需要寻找带有该标签的对象.


Obstacle nodes

创建一个立方体实体并加上标签Start


Start node

创建另一个立方体实体并加上标签End


End node

现在创建一个空的游戏对象并将GridManager脚本赋给它.将其名字也设置回GridManager因为在我们的脚本中使用该名称寻找GridManager对象.这里我们可以设置格子的行数和列数和每个格子的大小.


GridManager script

Testing

我们点击Play按钮实打实的看下我们的A*算法.默认情况下,一旦你播放当前场景Unity3D将会切换到Game视图.由于我们的寻路形象化(visualization)代码是为我编辑器视图中的调试绘制而写,你需要切换回Scene视图或者勾选Gizmos来查看找到的路径.


现在在场景中尝试使用编辑器的移动工具移动开始和结束节点.(不是在Game视图中,而是在Scene视图中)


如果从开始节点到目的节点有合法路径,你应该看到路径会对应更新并且是动态实时的更新.如果没有路径,你会在控制窗口中得到一条错误信息.

总结

在本章中,我们学习了如何在Unity3D环境中实现A*寻路算法.我们实现了自己的A*寻路类以及我们自己的格子类,队列类和节点类.我们学习了IComparable接口并重写了CompareTo方法.我们使用调试绘制功能(debug draw functionalities)来呈现我们的网格和路径信息.有了Unity3D的navmesh和navagent功能你可能不必自己实现寻路算法.不管怎么样,他帮助你理解实现背后的基础算法.

在下一章中,我们将查看如何扩展藏在A*背后的思想看看导航网格(navigation meshes).使用导航网格,在崎岖的地形上寻路将变得容易得多.

2015-01-31 12:41:30 huangyushi 阅读数 7720
  • Unity 值得看的500+ 技术内容列表

    Unity3D是由Unity Technologies开发的一个让玩家轻松创建诸如三维视频游戏、建筑可视化、实时三维动画等类型互动内容的多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

 转载:http://www.gopedu.com/article/735

因为项目需要做一个 A 星寻路的功能,但是又不想用 Unity3D 中的 A 星寻路插件,因为感觉插件感觉不够灵活,不能符合自己的设计,还好以前就保留了一位前辈的高效 A 星寻路链接,不过作者是用的 ActionScript 编写的,所以我就整理成了 C# 版本的了。

      

       最终效果图如下:

 

 

       测试代码如下(TestWorld.cs):

 


using UnityEngine; 

002 using System.Collections.Generic; 

003   

004 public class TestWorld : MonoBehaviour  

005 { 

006     public GameObject cubeObject; 

007     public GameObject pathObject; 

008   

009     public Camera mainCamera; 

010     public SceneGrid sceneGrid; 

011   

012     private AStarUtils aStarUtils; 

013   

014     private AStarNode beginNode; 

015   

016     private int cols = 20; 

017     private int rows = 20; 

018   

019     private IList<GameObject> pathList; 

020   

021     void Awake() 

022     { 

023         this.pathList = new List<GameObject> (); 

024         this.aStarUtils = new AStarUtils (this.cols, this.rows); 

025   

026         // cols 

027         for(int i = 0; i < this.cols; i++) 

028         { 

029             // rows 

030             for(int j = 0; j < this.rows; j++) 

031             { 

032                 AStarUnit aStarUnit = new AStarUnit(); 

033   

034                 if(i != 0 && j != 0 && Random.Range(1, 10) <= 3) 

035                 { 

036                     aStarUnit.isPassable = false; 

037   

038                     GameObject gameObject = (GameObject)Instantiate(cubeObject); 

039                     if(gameObject != null) 

040                     { 

041                         gameObject.transform.localPosition = new Vector3(i - this.cols * 0.5f + 0.5f, 0f, j - this.cols * 0.5f + 0.5f); 

042                     } 

043   

044                 }else{ 

045                     aStarUnit.isPassable = true; 

046                 } 

047   

048                 this.aStarUtils.GetNode(i,j).AddUnit(aStarUnit); 

049             } 

050         } 

051     } 

052   

053     private void FindPath(int x, int y) 

054     { 

055         AStarNode endNode = this.aStarUtils.GetNode(x, y); 

056   

057         if (this.beginNode == null)  

058         { 

059             this.beginNode = endNode; 

060             return; 

061         } 

062   

063         if (this.pathList != null && this.pathList.Count > 0)  

064         { 

065             foreach (GameObject xxObject in this.pathList)  

066             { 

067                 Destroy(xxObject); 

068             } 

069         } 

070           

071         if(endNode != null && endNode.walkable) 

072         { 

073             System.DateTime dateTime = System.DateTime.Now; 

074   

075             IList<AStarNode> pathList = this.aStarUtils.FindPath(this.beginNode, endNode); 

076   

077             System.DateTime currentTime = System.DateTime.Now; 

078   

079             System.TimeSpan timeSpan = currentTime.Subtract(dateTime); 

080   

081             Debug.Log(timeSpan.Seconds + "秒" + timeSpan.Milliseconds + "毫秒"); 

082   

083             if(pathList != null && pathList.Count > 0) 

084             { 

085                 foreach(AStarNode nodeItem in pathList) 

086                 { 

087                     GameObject gameObject = (GameObject)Instantiate(this.pathObject); 

088                     this.pathList.Add(gameObject); 

089                     gameObject.transform.localPosition = new Vector3(nodeItem.nodeX - this.cols * 0.5f + 0.5f, 0f, nodeItem.nodeY - this.cols * 0.5f + 0.5f); 

090                 } 

091             } 

092             this.beginNode = endNode; 

093         } 

094     } 

095       

096     void Update() 

097     { 

098         if (Input.GetMouseButtonDown (0))  

099         { 

100             Ray ray = this.mainCamera.ScreenPointToRay(Input.mousePosition); 
101   

102             RaycastHit raycastHit = new RaycastHit(); 

103             if(Physics.Raycast(ray, out raycastHit)) 

104             { 

105                 if(raycastHit.collider.gameObject.tag == "Plane") 

106                 { 

107                     Vector3 pointItem = this.sceneGrid.transform.InverseTransformPoint(raycastHit.point) * 2f; 

108   

109                     pointItem.x = this.cols * 0.5f + Mathf.Ceil(pointItem.x) - 1f; 

110                     pointItem.z = this.cols * 0.5f + Mathf.Ceil(pointItem.z) - 1f; 

111   

112                     this.FindPath((int)pointItem.x, (int)pointItem.z); 

113                 } 

114             } 

115         } 

116     } 

117 } 

SceneGrid.cs 





1 using UnityEngine; 

2 using System.Collections; 

3   

4 public class SceneGrid : MonoBehaviour  

5 { 

6   

7 } 

A 星类库代码如下(AStarCallback.cs): 



01 using UnityEngine; 

02 using System.Collections; 

03   

04 public class AStarCallback 

05 { 

06     // 

07     public delegate void IsPassableChangeCallback(); 

08   

09     //  

10     public delegate void HeuristicCallback(AStarNode aStarNode); 

11   

12     public event HeuristicCallback OnHeuristic; 

13   

14     public event IsPassableChangeCallback OnIsPassableChange; 

15   

16     public void InvokeHeuristic(AStarNode callAStarNode) 

17     { 

18         if (this.OnHeuristic != null)  

19         { 

20             this.OnHeuristic(callAStarNode); 

21         } 

22     } 

23       

24     public void InvokeIsPassableChange() 

25     { 

26         if (this.OnIsPassableChange != null)  

27         { 

28             this.OnIsPassableChange(); 

29         } 

30     } 

31 } 

AtarDiagonalHeuristic.cs 






01 using UnityEngine; 

02 using System.Collections; 

03   

04 public class AStarDiagonalHeuristic : IAStarHeuristic 

05 { 

06     public int Heuristic(int x1, int y1, int x2, int y2) 

07     { 

08         int dx = x1 > x2 ? x1 - x2 : x2 - x1; 

09         int dy = y1 > y2 ? y1 - y2 : y2 - y1; 

10           

11         return dx > dy ? AStarUtils.DIAG_COST * dy + AStarUtils.STRAIGHT_COST * (dx - dy) : AStarUtils.DIAG_COST * dx + AStarUtils.STRAIGHT_COST * (dy - dx); 

12     } 

13 } 

AStarLinkNode.cs 







01 using UnityEngine; 

02 using System.Collections; 

03   

04 /// <summary> 

05 /// 邻节点 

06 /// </summary> 

07 public class AStarLinkNode 

08 { 

09     /// <summary> 

10     /// 节点 

11     /// </summary> 

12     public AStarNode node; 

13   

14     /// <summary> 

15     /// 花费代价 

16     /// </summary> 

17     public int cost; 

18       

19     public AStarLinkNode(AStarNode node, int cost) 

20     { 

21         this.node = node; 

22         this.cost = cost; 

23     } 

24 } 

AStarManhattanHeuristic.cs 







01 using UnityEngine; 

02 using System.Collections; 

03   

04 public class AStarManhattanHeuristic : IAStarHeuristic  

05 { 

06     public int Heuristic(int x1, int y1, int x2, int y2) 

07     { 

08         return ( 

09             (x1 > x2 ? x1 - x2 : x2 - x1) 

10             + 

11             (y1 > y2 ? y1 - y2 : y2 - y1) 

12             ) * AStarUtils.STRAIGHT_COST; 

13     } 

14 } 

AStarNode.cs 







001 using UnityEngine; 

002 using System.Collections.Generic; 

003   

004 public class AStarNode 

005 { 

006     /// <summary> 

007     /// 坐标 x 

008     /// </summary> 

009     public int nodeX; 

010       

011     /// <summary> 

012     /// 坐标 y 

013     /// </summary> 

014     public int nodeY; 

015       

016     /// <summary> 

017     /// 父节点 

018     /// </summary> 

019     public AStarNode parentNode; 

020       

021     /// <summary> 

022     /// 二叉堆节点 

023     /// </summary> 

024     public BinaryHeapNode binaryHeapNode; 

025       

026     /// <summary> 

027     /// 与此节点相邻的可通过的邻节点 

028     /// </summary> 

029     public IList<AStarLinkNode> links; 

030       

031     /// <summary> 

032     /// 搜索路径的检查编号(确定是否被检查过) 

033     /// </summary> 

034     public int searchPathCheckNum; 

035       

036     /// <summary> 

037     /// 可移动范围的检查编号(确定是否被检查过) 

038     /// </summary> 

039     public int walkableRangeCheckNum; 

040       

041     /// <summary> 

042     /// 是否能被穿越 

043     /// </summary> 

044     public bool walkable; 

045       

046     /// <summary> 

047     /// 从此节点到目标节点的代价(A星算法使用) 

048     /// </summary> 

049     public int f; 

050       

051     /// <summary> 

052     /// 从起点到此节点的代价 

053     /// </summary> 

054     public int g; 

055       

056     /// <summary> 

057     /// 在此节点上的单位 

058     /// </summary> 

059     private IList<IAStarUnit> units; 

060   

061     /// <summary> 

062     /// 通过回调函数 

063     /// </summary> 

064     private AStarCallback aStarCallback = new AStarCallback (); 

065   

066     /// <summary> 

067     /// 回调函数参数 

068     /// </summary> 

069     private AStarNode aStarNodeParam; 

070   

071     public int unitCount 

072     { 

073         get { return this.units.Count; } 

074     } 

075       

076     /// <summary> 

077     /// 添加穿越代价被修改后的回调函数 

078     /// </summary> 

079     /// <param name="callback">Callback.</param> 

080     /// <param name="aStarNodeParam">A star node parameter.</param> 

081     public void AddHeuristic(AStarCallback.HeuristicCallback callback, AStarNode aStarNodeParam) 

082     { 

083         this.aStarNodeParam = aStarNodeParam; 

084         this.aStarCallback.OnHeuristic += callback; 

085     } 

086       

087     /// <summary> 

088     /// 移除穿越代价被修改后的回调函数 

089     /// </summary> 

090     /// <param name="callback">Callback.</param> 

091     public void RemoveHeuristic(AStarCallback.HeuristicCallback callback) 

092     { 

093         this.aStarCallback.OnHeuristic -= callback; 

094     } 

095       

096     /// <summary> 

097     /// 刷新穿越代价 

098     /// </summary> 

099     private void RefreshPassCost() 

100     { 

101         foreach(IAStarUnit unit in this.units) 

102         { 

103             if(!unit.isPassable) 

104             { 

105                 if(this.walkable) 

106                 { 

107                     this.walkable = false; 

108                     this.aStarCallback.InvokeHeuristic(this.aStarNodeParam); 

109                 } 

110                 return; 

111             } 

112         } 

113     } 

114   

115     /// <summary> 

116     /// 单位的 isPassable 属性被改变 

117     /// </summary> 

118     /// <returns><c>true</c> if this instance is passable change; otherwise, <c>false</c>.</returns> 

119     /*private void IsPassableChange() 

120     { 

121         this.RefreshPassCost(); 

122     }*/ 

123       

124     /// <summary> 

125     /// 添加单位 

126     /// </summary> 

127     /// <returns><c>true</c>, if unit was added, <c>false</c> otherwise.</returns> 

128     /// <param name="unit">Unit.</param> 

129     public bool AddUnit(IAStarUnit unit) 

130     { 

131         if(this.walkable) 

132         { 

133             if(this.units.IndexOf(unit) == -1) 

134             { 

135                 //unit.AddIsPassableChange(this.IsPassableChange); 

136                 this.units.Add(unit); 

137                 RefreshPassCost(); 

138                 return true; 

139             } 

140         } 

141         return false; 

142     } 

143       

144     /// <summary> 

145     /// 移除单位 

146     /// </summary> 

147     /// <returns><c>true</c>, if unit was removed, <c>false</c> otherwise.</returns> 

148     /// <param name="unit">Unit.</param> 

149     public bool RemoveUnit(IAStarUnit unit) 

150     { 

151         int index = this.units.IndexOf(unit); 

152         if(index != -1) 

153         { 

154             //unit.RemoveIsPassableChange(this.IsPassableChange); 

155             this.units.RemoveAt(index); 

156             this.RefreshPassCost(); 

157             return true; 

158         } 

159         return false; 

160     } 

161       

162     /// <summary> 

163     /// 地图节点 

164     /// </summary> 

165     /// <param name="nodeX">Node x.</param> 

166     /// <param name="nodeY">Node y.</param> 

167     public AStarNode(int nodeX, int nodeY) 

168     { 

169         this.nodeX = nodeX; 

170         this.nodeY = nodeY; 

171           

172         this.walkable = true; 

173         this.units = new List<IAStarUnit> (); 

174     } 

175 } 

AStarUnit.cs 






01 using UnityEngine; 

02 using System.Collections; 

03   

04 public class AStarUnit : IAStarUnit  

05 { 

06     /// <summary> 

07     /// 是否可以通过 

08     /// </summary> 

09     private bool _isPassable; 

10   

11     private AStarCallback aStarCallback = new AStarCallback(); 

12   

13     /// <summary> 

14     /// 添加通过回调函数 

15     /// </summary> 

16     /// <param name="callback">Callback.</param> 

17     public void AddIsPassableChange(AStarCallback.IsPassableChangeCallback callback) 

18     { 

19         this.aStarCallback.OnIsPassableChange += callback; 

20     } 

21   

22     /// <summary> 

23     /// 移除通过回调函数 

24     /// </summary> 

25     /// <param name="callback">Callback.</param> 

26     public void RemoveIsPassableChange(AStarCallback.IsPassableChangeCallback callback) 

27     { 

28         this.aStarCallback.OnIsPassableChange -= callback; 

29     } 

30   

31     /// <summary> 

32     /// 是否可以通过 

33     /// </summary> 

34     /// <value>true</value> 

35     /// <c>false</c> 

36     public bool isPassable  

37     {  

38         get { return this._isPassable; }  

39         set 

40         {  

41             if(this._isPassable != value) 

42             { 

43                 this._isPassable = value; 

44                 this.aStarCallback.InvokeIsPassableChange(); 

45             } 

46         }  

47     } 

48 } 

AStarUtils.cs 




001 using UnityEngine; 

002 using System.Collections.Generic; 

003   

004 /// <summary> 

005 /// A 星算法,公式:f = g + h; 

006 /// </summary> 

007 public class AStarUtils : MonoBehaviour  

008 { 

009     /// <summary> 

010     /// 直角移动的 g 值 

011     /// </summary> 

012     public const int STRAIGHT_COST = 10; 

013       

014     /// <summary> 

015     /// 对角移动的 g 值 

016     /// </summary> 

017     public const int DIAG_COST = 14; 

018       

019     /// <summary> 

020     /// 地图节点 

021     /// </summary> 

022     private Dictionary<string, AStarNode> nodes; 

023       

024     /// <summary> 

025     /// 地图的宽度(列数) 

026     /// </summary> 

027     private int numCols; 

028       

029     /// <summary> 

030     /// 地图的高度(行数) 

031     /// </summary> 

032     private int numRows; 

033       

034     /// <summary> 

035     /// 当前节点到结束节点的估价函数 

036     /// </summary> 

037     private IAStarHeuristic iAStarHeuristic; 

038       

039     /// <summary> 

040     /// 当前的寻路编号  

041     /// </summary> 

042     private int searchPathCheckNum; 

043       

044     /// <summary> 

045     /// 当前查找可移动范围的编号 

046     /// </summary> 

047     private int walkableRangeCheckNum; 

048       

049     /// <summary> 

050     /// 是否是四向寻路,默认为八向寻路 

051     /// </summary> 

052     private bool isFourWay; 

053       

054     /// <summary> 

055     /// 存放 "openList" 的最小二叉堆 

056     /// </summary> 

057     private BinaryHeapUtils binaryHeapUtils; 

058   

059     /// <summary> 

060     /// 获取节点 

061     /// </summary> 

062     /// <returns>The node.</returns> 

063     /// <param name="nodeX">Node x.</param> 

064     /// <param name="nodeY">Node y.</param> 

065     public AStarNode GetNode(int nodeX, int nodeY) 

066     { 

067         string nodeKey = this.GetNodeKey (nodeX, nodeY); 

068         if (this.nodes.ContainsKey (nodeKey))  

069         { 

070             return this.nodes[nodeKey]; 

071         } 

072         return null; 

073     } 

074   

075     /// <summary> 

076     /// 组装 Star Key 

077     /// </summary> 

078     /// <returns>The node key.</returns> 

079     /// <param name="nodeX">Node x.</param> 

080     /// <param name="nodeY">Node y.</param> 

081     private string GetNodeKey(int nodeX, int nodeY) 

082     { 

083         return nodeX + ":" + nodeY; 

084     } 

085       

086     /// <summary> 

087     /// 获取节点的相邻节点 

088     /// </summary> 

089     /// <returns>The adjacent nodes.</returns> 

090     /// <param name="node">Node.</param> 

091     private IList<AStarNode> GetAdjacentNodes(AStarNode node) 

092     { 
093         IList<AStarNode> adjacentNodes = new List<AStarNode> (); 

094           

095         int startX = 0; 

096         int endX = 0; 

097         int startY = 0; 

098         int endY = 0; 

099           

100         startX = Mathf.Max(0, node.nodeX - 1); 

101         endX = Mathf.Min(this.numCols - 1, node.nodeX + 1); 

102           

103         startY = Mathf.Max(0, node.nodeY - 1); 

104         endY = Mathf.Min(this.numRows - 1, node.nodeY + 1); 

105           

106         AStarNode varNode = null; 

107         for(int i = startX; i <= endX; i++) 

108         { 

109             for(int j = startY; j <= endY; j++) 

110             { 

111                 varNode = this.nodes[this.GetNodeKey(i, j)]; 

112                 if(varNode != node) 

113                 { 

114                     if(this.isFourWay) 

115                     { 

116                         if(!(i == node.nodeX || j == node.nodeY)) 

117                         { 

118                             continue; 

119                         } 

120                     } 

121                     adjacentNodes.Add(varNode); 

122                 } 

123             } 

124         } 

125         return adjacentNodes; 

126     } 

127       

128     /// <summary> 

129     /// 刷新节点的 links 属性 

130     /// </summary> 

131     /// <param name="node">Node.</param> 

132     private void RefreshNodeLinks(AStarNode node) 

133     { 

134         IList<AStarNode> adjacentNodes = this.GetAdjacentNodes(node); 

135           

136         int cost = 0; 

137         List<AStarLinkNode> links = new List<AStarLinkNode> (); 

138         foreach(AStarNode nodeItem in adjacentNodes) 

139         { 

140             if(nodeItem.walkable) 

141             { 

142                 if(node.nodeX != nodeItem.nodeX && node.nodeY != nodeItem.nodeY) 

143                 { 

144                     if(!this.nodes[this.GetNodeKey(node.nodeX, nodeItem.nodeY)].walkable || !this.nodes[this.GetNodeKey(nodeItem.nodeX, node.nodeY)].walkable) 

145                     { 

146                         continue; 

147                     }else 

148                     { 

149                         cost = DIAG_COST; 

150                     } 

151                 }else 

152                 { 

153                     cost = STRAIGHT_COST; 

154                 } 

155                 links.Add(new AStarLinkNode(nodeItem, cost)); 

156             } 

157         } 

158   

159         node.links = links; 

160     } 

161   

162     /// <summary> 

163     /// 刷新节点的相邻节点的 links 属性 

164     /// </summary> 

165     /// <param name="node">Node.</param> 

166     private void RefreshLinksOfAdjacentNodes(AStarNode node) 

167     { 

168         IList<AStarNode> adjacentNodes = this.GetAdjacentNodes(node); 

169         foreach(AStarNode adjacentNode in adjacentNodes) 

170         { 

171             this.RefreshNodeLinks(adjacentNode); 

172         } 

173     } 

174       

175     /// <summary> 

176     /// 刷新所有节点的 links 属性 

177     /// </summary> 

178     private void RefreshLinksOfAllNodes() 

179     { 

180         for(int i = 0; i < this.numCols; i++) 

181         { 

182             for(int j = 0; j < this.numRows; j++) 

183             { 

184                 this.RefreshNodeLinks(this.nodes[this.GetNodeKey(i, j)]); 

185             } 

186         } 

187     } 

188       

189     /// <summary> 

190     /// 搜索路径 

191     /// </summary> 

192     /// <returns><c>true</c>, if base binary heap was searched, <c>false</c> otherwise.</returns> 

193     /// <param name="startNode">Start node.</param> 

194     /// <param name="endNode">End node.</param> 

195     /// <param name="nowCheckNum">Now check number.</param> 

196     private bool SearchBaseBinaryHeap(AStarNode startNode, AStarNode endNode, int nowCheckNum) 

197     { 

198         int STATUS_CLOSED = nowCheckNum + 1; 

199   

200         this.binaryHeapUtils.Reset (); 

201           

202         startNode.g = 0; 

203         startNode.f = startNode.g + this.iAStarHeuristic.Heuristic(startNode.nodeX, startNode.nodeY, endNode.nodeX, endNode.nodeY); 

204         startNode.searchPathCheckNum = STATUS_CLOSED; 

205   

206         int g = 0; 

207         AStarNode node = startNode; 

208         AStarNode nodeItem; 

209   

210         while(node != endNode) 

211         { 

212             IList<AStarLinkNode> links = node.links; 

213             foreach(AStarLinkNode link in links) 

214             { 

215                 nodeItem = link.node; 

216                 g = node.g + link.cost; 

217   

218                 // 如果已被检查过 

219                 if(nodeItem.searchPathCheckNum >= nowCheckNum) 

220                 { 

221                     if(nodeItem.g > g) 

222                     { 

223                         nodeItem.f = g + this.iAStarHeuristic.Heuristic(nodeItem.nodeX, nodeItem.nodeY, endNode.nodeX, endNode.nodeY); 

224                         nodeItem.g = g; 

225                         nodeItem.parentNode = node; 

226                         if(nodeItem.searchPathCheckNum == nowCheckNum) 

227                         { 

228                             this.binaryHeapUtils.ModifyNode(nodeItem.binaryHeapNode); 

229                         } 

230                     } 

231                 }else{ 

232                     nodeItem.f = g + this.iAStarHeuristic.Heuristic(nodeItem.nodeX, nodeItem.nodeY, endNode.nodeX, endNode.nodeY); 

233                     nodeItem.g = g; 

234                     nodeItem.parentNode = node; 

235                       

236                     nodeItem.binaryHeapNode = this.binaryHeapUtils.InsertNode(nodeItem); 

237                     nodeItem.searchPathCheckNum = nowCheckNum; 

238                 } 

239             } 

240             if(this.binaryHeapUtils.headNode != null) 

241             { 

242                 node = this.binaryHeapUtils.PopNode(); 

243   

244                 node.searchPathCheckNum = STATUS_CLOSED; 

245             }else 

246             { 

247                 return false; 

248             } 

249         } 

250         return true; 

251     } 

252       

253     /// <summary> 

254     /// 寻路 

255     /// </summary> 

256     /// <returns>The path.</returns> 

257     /// <param name="startNode">Start node.</param> 

258     /// <param name="endNode">End node.</param> 

259     public IList<AStarNode> FindPath(AStarNode startNode, AStarNode endNode) 

260     { 

261         this.searchPathCheckNum += 2; 

262         if(this.SearchBaseBinaryHeap(startNode, endNode, searchPathCheckNum)) 

263         { 

264             AStarNode currentNode = endNode; 

265             IList<AStarNode> pathList = new List<AStarNode>(){ 

266                 startNode 

267             }; 

268             while(currentNode != startNode) 

269             { 

270                 currentNode = currentNode.parentNode; 

271                 pathList.Add(currentNode); 

272             } 

273   

274             return pathList; 

275         } 

276         return null; 

277     } 

278       

279     /// <summary> 

280     /// 返回节点在指定的代价内可移动的范围 

281     /// </summary> 

282     /// <returns>The range.</returns> 

283     /// <param name="startNode">Start node.</param> 

284     /// <param name="costLimit">Cost limit.</param> 

285     public IList<AStarNode> WalkableRange(AStarNode startNode, int costLimit) 

286     { 

287         this.walkableRangeCheckNum ++; 

288   

289         int maxStep = (int)(costLimit / STRAIGHT_COST); 

290           

291         int startX = Mathf.Max(startNode.nodeX - maxStep, 0); 

292         int endX = Mathf.Min(startNode.nodeX + maxStep, this.numCols - 1); 

293         int startY = Mathf.Max(startNode.nodeY - maxStep, 0); 

294         int endY = Mathf.Min(startNode.nodeY + maxStep, this.numRows - 1); 

295           

296         IList<AStarNode> rangeList = new List<AStarNode> (); 

297         for(int i = startX; i <= endX; i++) 

298         { 

299             for(int j = startY; j <= endY; j++) 

300             { 

301                 AStarNode nodeItem = this.nodes[this.GetNodeKey(i, j)]; 

302                 if(nodeItem.walkable && nodeItem.walkableRangeCheckNum != walkableRangeCheckNum) 

303                 { 

304                     IList<AStarNode> pathList = this.FindPath(startNode, nodeItem); 

305                     if(pathList != null && pathList[pathList.Count - 1].f <= costLimit) 

306                     { 

307                         foreach(AStarNode node in pathList) 

308                         { 

309                             if(node.walkableRangeCheckNum != walkableRangeCheckNum) 

310                             { 

311                                 node.walkableRangeCheckNum = walkableRangeCheckNum; 

312                                 rangeList.Add(node); 

313                             } 

314                         } 

315                     } 

316                 } 

317             } 

318         } 

319         return rangeList; 

320     } 

321   

322     public AStarUtils(int numCols, int numRows, bool isFourWay = false) 

323     { 

324         this.numCols = numCols; 

325         this.numRows = numRows; 

326         this.isFourWay = isFourWay; 

327         this.iAStarHeuristic = new AStarManhattanHeuristic (); 

328         //this.iAStarHeuristic = new AStarDiagonalHeuristic (); 

329           

330         AStarNode node = null; 

331         this.nodes = new Dictionary<string, AStarNode> (); 

332         for(int i = 0; i < this.numCols; i++) 

333         { 

334             for(int j = 0; j < this.numRows; j++) 

335             { 

336                 node = new AStarNode(i, j); 

337                 node.AddHeuristic(this.RefreshLinksOfAdjacentNodes, node); 

338                 this.nodes.Add(this.GetNodeKey(i, j), node); 

339             } 

340         } 

341         this.RefreshLinksOfAllNodes(); 

342         this.binaryHeapUtils = new BinaryHeapUtils(numCols * numRows / 2); 

343     } 

344 } 
 
BinaryHeapNode.cs 




01 using UnityEngine; 

02 using System.Collections; 

03   

04 /// <summary> 

05 /// 二叉堆节点 

06 /// </summary> 

07 public class BinaryHeapNode 

08 { 

09     /// <summary> 

10     /// 父节点 

11     /// </summary> 

12     public BinaryHeapNode parentNode; 

13       

14     /// <summary> 

15     /// 左子节点 

16     /// </summary> 

17     public BinaryHeapNode leftNode; 

18       

19     /// <summary> 

20     /// 右子节点 

21     /// </summary> 

22     public BinaryHeapNode rightNode; 

23       

24     /// <summary> 

25     /// 节点数据 

26     /// </summary> 

27     public AStarNode data; 

28   

29     public BinaryHeapNode(AStarNode data, BinaryHeapNode parentNode) 

30     { 

31         this.data = data; 

32         this.parentNode = parentNode; 

33     } 

34 } 

BinaryHeapUtils.cs 





001 using UnityEngine; 

002 using System.Collections.Generic; 

003   

004 /// <summary> 

005 /// 最小二叉堆 

006 /// </summary> 

007 public class BinaryHeapUtils 

008 { 

009     /// <summary> 

010     /// 数组,用于保持树的平衡 

011     /// </summary> 

012     public IList<BinaryHeapNode> nodes; 

013       

014     /// <summary> 

015     /// 数组中正在使用的元素数目 

016     /// </summary> 

017     private int nodeLength; 

018   

019     /// <summary> 

020     /// 头节点 

021     /// </summary> 

022     public BinaryHeapNode headNode; 

023       

024     /// <summary> 

025     /// 节点对象池(缓存节点)  

026     /// </summary> 

027     private IList<BinaryHeapNode> cacheNodes = new List<BinaryHeapNode>(); 

028       

029     /// <summary> 

030     /// 获得一个节点 

031     /// </summary> 

032     /// <returns>The node.</returns> 

033     /// <param name="data">Data.</param> 

034     /// <param name="parentNode">Parent node.</param> 

035     private BinaryHeapNode GetNode(AStarNode data, BinaryHeapNode parentNode) 

036     { 

037         BinaryHeapNode binaryHeapNode = null; 

038   

039         if(this.cacheNodes.Count > 0) 

040         { 

041             binaryHeapNode = this.cacheNodes[this.cacheNodes.Count - 1]; 

042   

043             binaryHeapNode.data = data; 

044             binaryHeapNode.parentNode = parentNode; 

045   

046             this.cacheNodes.RemoveAt(this.cacheNodes.Count - 1); 

047         } 

048         else 

049         { 

050             binaryHeapNode = new BinaryHeapNode(data, parentNode); 

051         } 

052         return binaryHeapNode; 

053     } 

054       

055     /// <summary> 

056     /// 存储节点 

057     /// </summary> 

058     /// <param name="node">Node.</param> 

059     private void CacheNode(BinaryHeapNode node) 

060     { 

061         node.parentNode = node.leftNode = node.rightNode = null; 

062         node.data = null; 

063   

064         this.cacheNodes.Add (node); 

065     } 

066       

067     /// <summary> 

068     /// 向下修正节点(向树叶方向修正节点) 

069     /// </summary> 

070     /// <returns>The to leaf.</returns> 

071     /// <param name="node">Node.</param> 

072     private BinaryHeapNode ModifyToLeaf(BinaryHeapNode node) 

073     { 

074         AStarNode currentNodeData = node.data; 

075         int currentNodeValue = currentNodeData.f; 

076   

077         BinaryHeapNode leftNode = null; 

078         BinaryHeapNode rightNode = null; 

079   

080         while(true) 

081         { 

082             leftNode = node.leftNode; 

083             rightNode = node.rightNode; 

084               

085             if(rightNode != null && leftNode != null && rightNode.data.f < leftNode.data.f) 

086             { 

087                 if(currentNodeValue > rightNode.data.f) 

088                 { 

089                     node.data = rightNode.data; 

090                     node.data.binaryHeapNode = node; 

091                     node = rightNode; 

092                 } 

093                 else 

094                 { 

095                     break; 

096                 } 

097             }else if(leftNode != null && leftNode.data.f < currentNodeValue) 

098             { 

099                 node.data = leftNode.data; 

100                 node.data.binaryHeapNode = node; 

101                 node = leftNode; 

102             }else 

103             { 

104                 break; 

105             } 

106         } 

107         node.data = currentNodeData; 

108         node.data.binaryHeapNode = node; 

109   

110         return node; 

111     } 

112       

113     /// <summary> 

114     /// 向上修正节点(向树根方向修正节点) 

115     /// </summary> 

116     /// <returns>The to root.</returns> 

117     /// <param name="node">Node.</param> 

118     private BinaryHeapNode ModifyToRoot(BinaryHeapNode node) 

119     { 

120         AStarNode currentNodeData = node.data; 

121         int currentNodeValue = currentNodeData.f; 

122           

123         BinaryHeapNode parentNode = node.parentNode; 

124         while(parentNode != null) 

125         { 

126             if(currentNodeValue < parentNode.data.f) 

127             { 

128                 node.data = parentNode.data; 

129                 node.data.binaryHeapNode = node; 

130                   

131                 node = node.parentNode; 

132                 parentNode = node.parentNode; 

133             }else 

134             { 

135                 break; 

136             } 

137         } 

138         node.data = currentNodeData; 

139         node.data.binaryHeapNode = node; 

140   

141         return node; 

142     } 

143       

144     /// <summary> 

145     /// 修正节点 

146     /// </summary> 

147     /// <returns>The node.</returns> 

148     /// <param name="node">Node.</param> 

149     public BinaryHeapNode ModifyNode(BinaryHeapNode node) 

150     { 

151         if(node.parentNode != null && node.parentNode.data.f > node.data.f) 

152         { 

153             return this.ModifyToRoot(node); 

154         }else{ 

155             return this.ModifyToLeaf(node); 

156         } 

157     } 

158       

159     /// <summary> 

160     /// 添加新节点 

161     /// </summary> 

162     /// <returns>The node.</returns> 

163     /// <param name="data">Data.</param> 

164     public BinaryHeapNode InsertNode(AStarNode data) 

165     { 

166         if(this.headNode != null) 

167         { 

168             BinaryHeapNode parentNode = this.nodes[this.nodeLength >> 1]; 

169             BinaryHeapNode node = this.GetNode(data, parentNode); 

170             node.data.binaryHeapNode = node; 

171   

172             if(parentNode.leftNode == null) 

173             { 

174                 parentNode.leftNode = node; 

175             }else 

176             { 

177                 parentNode.rightNode = node; 

178             } 

179             this.nodes[this.nodeLength] = node; 

180             this.nodeLength ++; 

181             return this.ModifyToRoot(node); 

182         }else 

183         { 

184             this.nodes[1] = this.headNode = this.GetNode(data, null); 

185             this.nodes.Add(this.headNode); 

186             this.headNode.data.binaryHeapNode = this.headNode; 

187               

188             this.nodeLength = 2; 

189             return this.headNode; 

190         } 

191     } 

192       

193     /// <summary> 

194     /// 取出最小值 

195     /// </summary> 

196     /// <returns>The node.</returns> 

197     public AStarNode PopNode() 

198     { 

199         AStarNode minValue = this.headNode.data; 

200   

201         BinaryHeapNode lastNode = this.nodes[--this.nodeLength]; 

202   

203         if(lastNode != this.headNode) 

204         { 

205             BinaryHeapNode parentNode = lastNode.parentNode; 

206             if(parentNode.leftNode == lastNode) 

207             { 

208                 parentNode.leftNode = null; 

209             }else{ 

210                 parentNode.rightNode = null; 

211             } 

212             this.headNode.data = lastNode.data; 

213             this.headNode.data.binaryHeapNode = this.headNode; 

214   

215             this.ModifyToLeaf(this.headNode); 

216         }else 

217         { 

218             this.headNode = null; 

219         } 

220         this.CacheNode(this.nodes[this.nodeLength]); 

221         this.nodes[this.nodeLength] = null; 

222   

223         return minValue; 

224     } 

225       

226     /// <summary> 

227     /// 重置 

228     /// </summary> 

229     public void Reset() 

230     { 

231         for(int index = 1; index < this.nodeLength; index++) 

232         { 

233             this.CacheNode(this.nodes[index]); 

234             this.nodes[index] = null; 

235         } 

236         this.nodeLength = 1; 

237         this.headNode = null; 

238     } 

239       

240     // 小二叉堆 

241     public BinaryHeapUtils(int cacheSize) 

242     { 

243         this.nodes = new List<BinaryHeapNode> (cacheSize); 

244         for(int index = 0; index < cacheSize; index ++) 

245         { 

246             this.nodes.Add(null); 

247             this.cacheNodes.Add(new BinaryHeapNode(null, null)); 

248         } 

249     } 

250 } 

IAStarHeuristic.cs 





1 using UnityEngine; 

2 using System.Collections; 

3   

4 public interface IAStarHeuristic 

5 { 

6     int Heuristic(int x1, int y1, int x2, int y2); 

7 } 

IAStarUnit.cs 


view sourceprint?

01 using UnityEngine; 

02 using System.Collections.Generic; 

03   

04 /// <summary> 

05 /// 单位接口 

06 /// </summary> 

07 public interface IAStarUnit  

08 { 

09     /// <summary> 

10     /// 添加通过回调函数 

11     /// </summary> 

12     /// <param name="callback">Callback.</param> 

13     void AddIsPassableChange(AStarCallback.IsPassableChangeCallback callback); 

14   

15     /// <summary> 

16     /// 移除通过回调函数 

17     /// </summary> 

18     /// <param name="callback">Callback.</param> 

19     void RemoveIsPassableChange(AStarCallback.IsPassableChangeCallback callback); 

20   

21     /// <summary> 

22     /// 是否可以通过 

23     /// </summary> 

24     /// <value><c>true</c> if is passable; otherwise, <c>false</c>.</value> 

25     bool isPassable { get; set; } 

26 } 
2016-03-18 21:26:51 liu_if_else 阅读数 5494
  • Unity 值得看的500+ 技术内容列表

    Unity3D是由Unity Technologies开发的一个让玩家轻松创建诸如三维视频游戏、建筑可视化、实时三维动画等类型互动内容的多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

A星寻路原理:

略,网上可搜到
只简单说下F,G,H值
G:从起点A到当前点B的所耗费的移动距离。
H:此点到终点的移动距离(忽视障碍)。
F:F=G+H,用来寻找最优解。

通过理解A星寻路的原理可以设计出以下流程图:

这里写图片描述

Unity C#脚本实现流程图的代码:

此脚本挂在场景中任意空物体上即可实现效果,在Start()内可调整地图相关参数

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class AStar : MonoBehaviour {
    //地图节点类型
    public enum NodeType    
    {
        moveable,   //可移动
        bar,        //障碍物
        boundary,   //边界
        aStarPath   //A星路径
    }

    //A星状态
    public enum AStarState
    {
        free,
        isInOpenList,
        isInCloseList
    }

    //pos<-->node 字典
    private Dictionary<Vector2, Node> PosNodeDict;

    //地图节点
    public class Node   
    {
        public Vector2 pos; 
        public NodeType nodeType;
        public AStarState aStarState;
        public Node[] neighbourNodes;
        public Node parentNode=null;
        public float F=0;
        public float G=0;
        public float H = 0;
    }

    //地图初始化
    public Node[,] InitMap(int mapHeight,int mapLength)
    {
        Node[,] nodes = new Node[mapHeight, mapLength];
        PosNodeDict = new Dictionary<Vector2, Node>();

        for (int i = 0; i < mapHeight; i++)
        {
            for (int j = 0; j < mapLength; j++)
            {
                nodes[i, j] = new Node();
                //边界判断
                if (i == 0)
                {
                    nodes[i, j].nodeType = NodeType.boundary;
                    nodes[i, j].pos = new Vector2(j, i);
                }
                else if (j == 0)
                {
                    nodes[i, j].nodeType = NodeType.boundary;
                    nodes[i, j].pos = new Vector2(j, i);
                }
                else if (i == mapHeight - 1)
                {
                    nodes[i, j].nodeType = NodeType.boundary;
                    nodes[i, j].pos = new Vector2(j, i);
                }
                else if (j == mapLength - 1)
                {
                    nodes[i, j].nodeType = NodeType.boundary;
                    nodes[i, j].pos = new Vector2(j, i);
                }
                else
                {
                    nodes[i, j].nodeType = NodeType.moveable;
                    nodes[i, j].pos = new Vector2(j, i);
                }

                //节点加入 坐标<-->节点 字典
                nodes[i, j].aStarState = AStarState.free;
                PosNodeDict.Add(new Vector2(j, i), nodes[i, j]);
             }
        }

        //初始化相邻坐标节点数组
        for (int i=0; i < mapHeight; i++)
        {
            for(int j=0; j < mapLength; j++)
            {
                nodes[i, j].neighbourNodes = new Node[8];
                Vector2 curNeighbVec2;
                //上
                curNeighbVec2 = new Vector2(j, i + 1);
                if (PosNodeDict.ContainsKey(curNeighbVec2))
                {
                    nodes[i, j].neighbourNodes[0] = PosNodeDict[curNeighbVec2];
                }
                //下
                curNeighbVec2 = new Vector2(j, i - 1);
                if (PosNodeDict.ContainsKey(curNeighbVec2))
                {
                    nodes[i, j].neighbourNodes[1] = PosNodeDict[curNeighbVec2];
                }
                //左
                curNeighbVec2 = new Vector2(j - 1, i);
                if (PosNodeDict.ContainsKey(curNeighbVec2))
                {
                    nodes[i, j].neighbourNodes[2] = PosNodeDict[curNeighbVec2];
                }
                //右
                curNeighbVec2 = new Vector2(j + 1, i);
                if (PosNodeDict.ContainsKey(curNeighbVec2))
                {
                    nodes[i, j].neighbourNodes[3] = PosNodeDict[curNeighbVec2];
                }
                //左上
                curNeighbVec2 = new Vector2(j - 1, i + 1);
                if (PosNodeDict.ContainsKey(curNeighbVec2))
                {
                    nodes[i, j].neighbourNodes[4] = PosNodeDict[curNeighbVec2];
                }
                //右上
                curNeighbVec2 = new Vector2(j + 1, i + 1);
                if (PosNodeDict.ContainsKey(curNeighbVec2))
                {
                    nodes[i, j].neighbourNodes[5] = PosNodeDict[curNeighbVec2];
                }
                //左下
                curNeighbVec2 = new Vector2(j - 1, i - 1);
                if (PosNodeDict.ContainsKey(curNeighbVec2))
                {
                    nodes[i, j].neighbourNodes[6] = PosNodeDict[curNeighbVec2];
                }
                //右下
                curNeighbVec2 = new Vector2(j + 1, i - 1);
                if (PosNodeDict.ContainsKey(curNeighbVec2))
                {
                    nodes[i, j].neighbourNodes[7] = PosNodeDict[curNeighbVec2];
                }
            }
        }
        return nodes;
    }

    //设置障碍bar
    public void AddBar(Vector2 barPos)
    {
        if (PosNodeDict.ContainsKey(barPos)){
            print("bar added");
           PosNodeDict[barPos].nodeType = NodeType.bar;
        }
    }

    //地图具象化
    public void InstantiateMap(Node[,] nodes)
    {
        for(int i = 0; i < nodes.GetLength(0); i++)
        {
            for (int j = 0; j < nodes.GetLength(1); j++)
            {
                GameObject curCube = GameObject.CreatePrimitive(PrimitiveType.Cube);
                curCube.transform.position = new Vector3(j, i, 0);
                if (nodes[i, j].nodeType == NodeType.boundary)
                {
                    print("set boundary");
                    curCube.GetComponent<Renderer>().material.SetColor("_Color", Color.black);
                }
                else if (nodes[i, j].nodeType == NodeType.bar)
                {
                    print("set bar");
                    curCube.GetComponent<Renderer>().material.SetColor("_Color", Color.red);
                }
                else if (nodes[i, j].nodeType == NodeType.aStarPath)
                {
                    print("set path");
                    curCube.GetComponent<Renderer>().material.SetColor("_Color", Color.yellow);
                }
            }
        }
    }

    //地图具象化(并对Openlist,Closelist内节点上色)
    public void InstantiateMapBeta(Node[,] nodes){
        for (int i = 0; i < nodes.GetLength(0); i++)
        {
            for (int j = 0; j < nodes.GetLength(1); j++)
            {
                GameObject curCube = GameObject.CreatePrimitive(PrimitiveType.Cube);
                curCube.transform.position = new Vector3(j, i, 0);
                if (nodes[i, j].nodeType == NodeType.boundary)
                {
                    print("set boundary");
                    curCube.GetComponent<Renderer>().material.SetColor("_Color", Color.black);
                }
                else if (nodes[i, j].nodeType == NodeType.bar)
                {
                    print("set bar");
                    curCube.GetComponent<Renderer>().material.SetColor("_Color", Color.red);
                }
                else if (nodes[i, j].nodeType == NodeType.aStarPath)
                {
                    print("set path");
                    curCube.GetComponent<Renderer>().material.SetColor("_Color", Color.yellow);
                }
                else if(OpenList.Contains(nodes[i,j]))
                {
                    curCube.GetComponent<Renderer>().material.SetColor("_Color", Color.green);
                }
                else if(CloseList.Contains(nodes[i,j]))
                {
                    curCube.GetComponent<Renderer>().material.SetColor("_Color", Color.blue);
                }
            }
        }
    }

    //寻路相关
    private List<Node> OpenList;
    private List<Node> CloseList;
    private Vector2 globalEndPos;
    //寻路入口
    public bool PathSearch(Node[,] nodes,Vector2 startPos,Vector2 endPos)
    {
        //校验参数
        if (!PosNodeDict.ContainsKey(startPos) || !(PosNodeDict.ContainsKey(endPos)))
        {
            print("invalid para");
            return false;
        }
        if(PosNodeDict[startPos].nodeType != NodeType.moveable||PosNodeDict[endPos].nodeType!=NodeType.moveable){
            print("invalid para");
            return false;
        }

        OpenList = new List<Node>();
        CloseList = new List<Node>();
        globalEndPos = endPos;
        //算法开始
        //起点为A
        //这里有点不直观,startPos的xy要倒过来引用nodes。感谢tuyou67评论指出。
        Node A = nodes[(int)startPos.y, (int)startPos.x];	
        A.G = 0;
        A.H = Mathf.Abs(globalEndPos.x - A.pos.x) + Mathf.Abs(globalEndPos.y - A.pos.y); //Vector2.Distance(A.pos, globalEndPos);
        A.F = A.G + A.H;
        A.parentNode = null;
        CloseList.Add(A);
        A.aStarState = AStarState.isInCloseList;
        do
        {
            //遍历OpenList,寻找F值最小的节点,设为A
            if (OpenList.Count > 0)
            {
                A = OpenList[0];
            }
            for (int i = 0; i < OpenList.Count; i++)
            {
                if (OpenList[i].F < A.F)
                {
                    A = OpenList[i];
                }
            }

            Node path = AStarSearch(A);

            if (path != null)
            {
                print("path found");
                do
                {
                    path.nodeType = NodeType.aStarPath;
                    if (path.parentNode == null)
                    {
                        path = null;
                    }
                    else
                    {
                        path = path.parentNode;
                    }
                } while (path!= null);
                return true;
            }
            OpenList.Remove(A);
            CloseList.Add(A);
            A.aStarState = AStarState.isInCloseList;
        //OpenList是否还有节点
        } while (OpenList.Count > 0);
        //无到达目的地的路径
        print("path not found");
        return false;
    }

    public Node AStarSearch(Node A)
    {
        //遍历A的周边节点,当前处理节点为B
        Node B;
        for (int i = 0; i < A.neighbourNodes.Length; i++)
        {
            if (A.neighbourNodes[i] == null)
            {
                continue;
            }

            B = A.neighbourNodes[i];
            //是否是可移动节点
            if (B.nodeType != NodeType.moveable)
            {
                continue;
            }
            //是否在开放列表中
            if (B.aStarState == AStarState.isInOpenList)
            {
                //A到B的G值+A.G>B.G
                float curG = Vector2.Distance(A.pos, B.pos);
                if (B.G > curG + A.G)
                {
                    //更新B的父节点为A,并相应更新B.G,B.H
                    B.parentNode = A;
                    B.G = curG + A.G;
                    B.F = B.G + B.H;
                }
                continue;
            }
            else if(B.aStarState==AStarState.free)
            {
                //更新B的父节点为A,并相应更新B.G; 计算B.F,B.H; B加入OpenList
                B.parentNode = A;
                B.G = Vector2.Distance(A.pos,B.pos)+A.G;
                B.H = Mathf.Abs(globalEndPos.x - B.pos.x) + Mathf.Abs(globalEndPos.y - B.pos.y); //Vector2.Distance(B.pos, globalEndPos);
                B.F = B.G + B.H;
                OpenList.Add(B);
                B.aStarState = AStarState.isInOpenList;
                //B.F==0
                if (B.H <Mathf.Epsilon)
                {
                    //B的所有父节点既是路径
                    return B;
                }
                else
                {
                    //继续遍历
                    continue;
                }
            }
            else
            {
                continue;
            }
        }
        return null;
    }

    //程序入口
    // Use this for initialization
    void Start () {
        Node[,] nodes = InitMap(100, 100);

        AddBar(new Vector2(2, 2));
        AddBar(new Vector2(2, 3));
        AddBar(new Vector2(3, 2));
        AddBar(new Vector2(3, 3));
        AddBar(new Vector2(4, 4));
        AddBar(new Vector2(3, 4));
        AddBar(new Vector2(4, 3));
        AddBar(new Vector2(4, 5));
        AddBar(new Vector2(5, 4));
        AddBar(new Vector2(4, 6));
        AddBar(new Vector2(4, 7));
        AddBar(new Vector2(1, 7));
        AddBar(new Vector2(2, 7));
        AddBar(new Vector2(3, 7));

        PathSearch(nodes, new Vector2(1, 3), new Vector2(2,12));

        InstantiateMapBeta(nodes);
    }
}


效果图:

红色方块为障碍物,黑色方块为边界,灰色方块为空地,绿色方块为OpenList内节点,蓝色方块为CloseList内节点,黄色方块为路径。

这里写图片描述

这里写图片描述

这里写图片描述
————————————————————————————————
维护日志:
2017-8-31:更改标题,文章分类。
2018-8-2:Review,重写了代码,流程图,并更新了效果图。
2020-5-28:修改了startPos引用nodes的bug

2015-07-03 10:28:41 qq_16013649 阅读数 4179
  • Unity 值得看的500+ 技术内容列表

    Unity3D是由Unity Technologies开发的一个让玩家轻松创建诸如三维视频游戏、建筑可视化、实时三维动画等类型互动内容的多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

首先需要确定实现A星算法的一些必要脚本:

 

Node         节点

PriorityQueue  优先级队列

GridManager   网格管理

AStar   A算法

 

我们首先将从A星算法实现前的一些准备工作开始,逐步完成整个A星寻路算法效果。

 

1.Node脚本,A星寻路算法是通过算法自动寻找出一条最短路径,然后将这条路径串联起来,那么串起来的每个点都是一个节点,因此我们需要Node这样一个脚本。

 

这些节点将会在我们的优先级队列中进行排序,所以要可以比较。因此,Node需要继承IComparable

    

/// <summary>

/// 可以比较节点的大小

/// </summary>

public int CompareTo(object obj)

 

A星算法是通过计算每个节点的成本数值来决定选择的路径,成本计算公式:C=S+H。因此Node节点中需要包含着一些基本的属性:

//节点总成本

    //估算成本

    //障碍物

    //父节点

//节点的位置

同时,除了提供给比较两个节点成本的函数外,节点的默认构造函数和含参数的构造函数用来初始化节点的位置。再提供一个设置障碍物的函数,每个节点有可能是可以走的路径,同时也可能是障碍物不可通过的路径。

 

2.PriorityQueue 脚本,优先级队列主要是为了将我们通过A星算法所计算出的点按照成本的大小进行排序,在unity中我们可以通过使用ArrayList这样的一个动态数组进行再封装。

 

我们需要提供    获取节点的个数  

 

Push  将节点放入优先级队列,并进行排序,即在数组中对节点进行比较

Remove 删除优先级队列中的节点

First 获取优先级队列中的第一个元素,也就是获取成本最小的

Contains 检查是否包含该节点

 

 

3.GridManager 网格管理

  在unity中由于A星算法来说,需要通过一个个小的节点进行不断的判断和选择,因此我们需要构建模拟一个寻路网格来实现。

 

网格管理中我们将使用单例模式,保证全局中只有一个寻路网格

 

要制作一个网格的话,我们需要制作出与坐标轴样式类似的效果。第一,要有一个原点,我们用三维向量表示为Origin。通过这个原点,我们将在unity中使用Gizmos将整个网格绘制出来,绘制w*h大小的整个网格。但是由于我们整个网格并非是需要进行寻路的全部部分,我们还需要剔除掉网格中用户设置好的障碍物,因此还需要通过对场景中的障碍物进行计算和剔除。

 

3.1计算障碍物

   计算障碍物时,我们首先要将整个W*H的网格中每一个网格设定为我们的一个Node,初始化每一个Node,都使用这个小网格中心的坐标作为Node初始化的坐标。初始化结束后,我们需要通过获取障碍物列表中的所有障碍物,然后将这些障碍物的node进行标记,设置为障碍物,也就是调用我们Node中提供的Mark函数。

 

3.2提供必要的计算网格位置的API

/// <summary>

    /// 根据物体的位置获取编号

/// </summary>

    public int GetGridIndex(Vector3 pos)

将传入的物体位置坐标首先减去初始原点坐标,获取传入物体相对于原点的相对坐标。要获取该物体在网格中的行和列就需要将该坐标的xz除以单个网格的大小,最终返回一个从原点开始标号为0计算起的网格编号。

 

    /// <summary>

    /// 根据序号计算对应中心点的位置

    /// </summary>

    /// <param name="index"></param>

    /// <returns></returns>

    public Vector3 GetGridCellCenter(int index)

 

    /// <summary>

    /// 计算网格的位置点   即计算网格左下角的位置

    /// </summary>

    /// <param name="index"></param>

    /// <returns></returns>

    public Vector3 GetGridCellPosition(int index)

 

 

    /// <summary>

    /// 获取行

    /// </summary>

    /// <param name="index"></param>

    /// <returns></returns>

    public int GetRow(int index)

 

/// <summary>

    /// 获取列

    /// </summary>

    /// <param name="index"></param>

    /// <returns></returns>

    public int GetColumn(int index)

 

3.3 计算该网格中节点的邻居节点

/// <summary>

    /// 每个节点的邻居节点

    /// </summary>

    public void GetNeighbours(Node node, ArrayList neighbors)

 

 

 

4.A星算法的实现

 

A星算法实现的关键是计算每个节点的成本数值,再通过这个节点的邻接节点的成本数值进行计算找到下一个最优节点的成本数值并记录。那么我们就需要两个动态的数组进行对已经计算过成本数值计算节点和将要进行成本数值计算的节点存储,那么就会使用一个开始列表和一个关闭列表,开始列表对将要计算成本节点进行计算,关闭列表对已经计算过节点进行计算。

 

A星算法中较为核心的就是找到一条关键路径并将该条路径记录到一个动态的数组列表之中,下面描述算法实现的步骤:

1.将起始地节点放入开始列表之中,表示寻路从该节点开始。

2.计算该节点的估计成本,也就是计算该节点和目标(终点)节点的距离。

3.初始化一个新的节点赋值为开始列表中的第一个点,也就是成本最小的点

4.如果当前节点是目标节点,跳转7,反之,继续进行

5.获取当前节点的邻居节点,只要这些邻居节点中不在关闭列表就先计算当前节点到当前邻居节点的成本,总成本=当前节点原先成本+到邻居节点的成本。当前邻居节点的成本就是邻居节点到目标节点的成本计算,并将邻居节点的父节点设置为当前节点。若当前邻居节点不在开始列表中就将当前邻居节点放入开始列表之中。并将当前节点放入关闭列表中,同时把当前节点从开始列表中移出。跳转3直到开始列表中没有元素存在为止。

6.若没有找到目标节点,则返回空,反之跳转7

7.重新初始化一个列表,只要传入的当前节点不是空,那么久将当前节点添加进入列表,并将当前节点赋值为当前节点的父级节点。通过此种方式将路径串起来。但是此时路径是从末尾目标节点到起始节点,因此再将数组反转,返回当前数组。

 

通过以上方式,我们就基本上将A星算法的基本算法实现并在unity中可以使用了。大家可以通过下面百度网盘的地址下载工程源码,里面有一个简单的应用。以后有时间的话,我会将这种方式的寻路简单介绍应用在项目之中并进行优化。

 

链接:http://pan.baidu.com/s/1c0i3VnM 密码:wjxn