a星插件 unity3d

2013-12-27 23:54:35 aisajiajiao 阅读数 15595
  • 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 阅读数 7710
  • 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 } 
2019-04-21 21:00:38 xiumang 阅读数 831
  • Unity 值得看的500+ 技术内容列表

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

Unity3D 简易细节层次插件 Simple LOD
http://www.idoubi.net/unity3d/tool/3764.html
Unity3D 物体表面贴花喷漆插件 Easy Decal Easy Decal v1.6.8
http://www.idoubi.net/unity3d/tool/4060.html
Unity3D 汽车底盘传动模拟插件 Kinematic Car Suspension – Offroad Car
http://www.idoubi.net/unity3d/tool/3162.html
Unity3D A星寻路插件 A* Pathfinding Project Pro
http://www.idoubi.net/unity3d/tool/1538.html
Unity3D 山洞制作插件 MicroSplat – Terrain Holes v2.54
http://www.idoubi.net/uncategorized/3154.html
Unity3D 动态骨骼插件 Dynamic Bone
http://www.idoubi.net/unity3d/tool/3733.html
Unity3D 高级输入输出控制插件 Rewired v1.1.22.3
http://www.idoubi.net/unity3d/tool/3785.html
Unity3D 体积光和雾气制作插件 Aura 2
http://www.idoubi.net/unity3d/tool/3769.html
Unity3D 网格地形制作插件 Grids Pro
http://www.idoubi.net/unity3d/tool/3426.html
Unity3D 视图捕捉插件 Offline Render v1.0
http://www.idoubi.net/unity3d/tool/3580.html
Unreal 战争迷雾效果资源包 Fog of War
http://www.idoubi.net/unreal/blueprints/2899.html
Unity3D魔幻英雄角色编辑器 Fantasy Heroes- Character Editor [PRO]
http://www.idoubi.net/unity3d/tool/3449.html
Unity3D 用于Facebook的简单的排行榜 Easy Leaderboard (Facebook + PlayFab) v2.0.1
http://www.idoubi.net/unity3d/tool/2525.html
Unity3D Youtobe视频播放器 Youtube video player
http://www.idoubi.net/unity3d/tool/2629.html
Unity3D 完美的角色编辑器 Fantasy Heroes: Character Editor [PRO]
http://www.idoubi.net/unity3d/tool/2668.html
Unity3D 安卓视频播放插件 WRP Android Video Player Pro
http://www.idoubi.net/unity3d/tool/2620.html
Unity3D 网页图片链接插件 Web Image Links
http://www.idoubi.net/unity3d/tool/2602.html
Unity3D 简便的排行榜功能 Easy Leaderboard (Facebook + PlayFab) v2.0.1
http://www.idoubi.net/unity3d/tool/2585.html
Unity3D MMORPG 拍卖行系统 Auction House for uMMORPG
http://www.idoubi.net/unity3d/tool/2553.html
Unity3D PlayMaker NGUI脚本插件 PlayMaker NGUI Scripts
http://www.idoubi.net/unity3d/tool/2352.html
Unity3D 场景序列帧编辑器 Flux v2.1.5
http://www.idoubi.net/unity3d/tool/2366.html

2015-05-28 16:05:28 green_tea_great 阅读数 4016
  • Unity 值得看的500+ 技术内容列表

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

原文地址:http://t-machine.org/index.php/2014/08/10/debugging-a-pathfinding-in-unity/

说明:在文章中有时出现A星有时出现A*,都是一个东西,要是不理解,可以先看看原作者推荐的那几篇文章……

正文:

我的项目需要一个快速、高效、强大和适应性强的寻路系统。我的角色要飞、走、爬、瞬移穿过一个程序生成的陆地。完成这个要求有些复杂,但是过程却很有趣。

我想要一个模块,它能智能的引导障碍周围的怪物,并选择比较容易走的路,而不是从悬崖边走过去(反之亦然,比如巨型蜘蛛)。就像这样:


Unity Asset Store

Unity里要做任何事,访问Asset Store都应该是第一步。

我搜索排名靠前的几个寻路资源包,并且测试了有webPlayer或者免费版本的demo。

其中有些挺好,但是总的来说让人失望。性能不错,其中大部分都用了协程或者后台线程来控制CPU的使用,这很不错!(相对容易自己实现,话说这是A*的两大特性之一)

……但是用户接口很糟糕(我理解不了……)或者代码很难写,或者丢失了A星的核心元素的设置(比如动态边界dynamic edge:在游戏里使用A*的另一个原因)。

如果只是简单用用,它们很多都不错。24小时热卖资源里有一个看起来很好,由一个大团队维护——但是他们很精明(只能在你购买后才能看到文档!)而且看上去代码相对难写。

最后,我放弃了,于是我想:


也许……每个创新的游戏都需要你重新实现A*算法,来保证你的游戏独一无二的特点?

(A*不难实现,有很多选择方式,也许在这件事上重复造轮子是一件好事)。

A星是什么,如何工作?如何实现?

我推荐以下几篇文章:

这几篇文章留给我们一个基本算法:

OPEN = priority queue containing START
CLOSED = empty set
while lowest rank in OPEN is not the GOAL:
  current = remove lowest rank item from OPEN
  add current to CLOSED
  for neighbors of current:
    cost = g(current) + movementcost(current, neighbor)
    if neighbor in OPEN and cost less than g(neighbor):
      remove neighbor from OPEN, because new path is better
    if neighbor in CLOSED and cost less than g(neighbor): **
      remove neighbor from CLOSED
    if neighbor not in OPEN and neighbor not in CLOSED:
      set g(neighbor) to cost
      add neighbor to OPEN
      set priority queue rank to g(neighbor) + h(neighbor)
      set neighbor's parent to current

reconstruct reverse path from goal to start
by following parent pointers

在Unity里用C#实现

首先:Unity在使用C#语法时有些问题。泛泛的说,一些C#代码在Unity里会引起问题——最常见的例子:多维数组。你可以给Unity打补丁修复它,但是这么做不太常规。替代方法是简单粗暴的实现一个更底层的结构(很烂,但是实用)。

其次:微软C#/.NET标准库有一个内置的SortedList,我直说吧它名字起错了。你在每个位置只能有一个元素(这是sorted Map或者Set-sorted List,不是sorted List)。在我们的例子里这是一个错误的数据结构,虽然你可以通过定制它让它工作(让每个物品一个List,把节点从List移到另一个List)——哎呦,复杂!

还是一样:很烂,但是实用。我个人写了我自己的SortedList。

Node类

可能你游戏里已经有类似的结构了:

public class Node
{
public int x, int y;
}

graph / grid类

举个例子:

public class Grid
{
public Node[] allNodes;
public int nodesAcross, nodesDown; // needed to workaround Unity bugs
public Node NodeAt( int x, int y ) // needed to workaround Unity bugs
{
return allNodes[ x + y*nodesAcross];
}
public void SetNodeAt( int x, int y, Node n ) // needed to workaround Unity bugs
{
allNodes[ x + y*nodesAcross] = n;
}

写一个自己的SortedList

超简单,但是第一次写的时候我绕进去了,因为我不熟悉C#内部的foreach循环里如何保持整洁。我认为你也可能有类似的问题。对于A*你只需要一个包含以下方法的类:

public class MySortedList<T> where T: class
{
	public MySortedList();
	public int Count();
	public T GetFirst();
	public T RemoveFirst();
	public void RemoveItem( T victimItem );
	public bool Contains( T searchItem );
	public int AddWithValue( T newItem, float newValue );
}

检查你的算法

这是一个数据敏感的算法,我们创建了一些数据结构(不太危险)和一个自定义的容器(恩,危险!容易出错)。

我强烈建议你给MySortedList写单元测试。我没有这么做(我还没找到一个适用于Unity的好的单元测试框架),而且很后悔。特别关注以下几点:

  1. 测试Contains方法是否正确
  2. 测试Remove方法是否真的移除了对象

省略上面的任何一项,A星有可能陷入死循环,因为它持续添加节点到列表里。尤其是对Contains的测试,确保为你的自定义类实现了Equals和GetHashcode!

调试你的算法

现在到有趣的部分了,这是一个重度数据的算法:在真正的游戏中,它会处理成千上万的节点,以及数以万计的边界。调试它简直就是下地狱,千万别那么做啊。

你第一步的思考可能是:

我可以给调试A星弄个界面吗?这样调试它就变得又快又容易?

我的思路:

  1. 做个Calculate A Path的组件
    1. 把开始节点和结束节点放进去
    2. 写一个编辑器类,增加一个按钮“Calculate Path”
  2. A星输出一个Path对象
  3. Calculate A Path组件持有这个对象
    1. 创建一个新的GameObject
    2. 把Path对象作为它的子对象
    3. 给它附加一个PathVisualizer组件
  4. PathVisualizer组件实现了OnGizmos()
    1. 在每个节点都绘制一个立方体
    2. 在开始和结束节点的立方体和其他立方体颜色不同
    3. 在节点之间通过线段连接

需要注意的事:

因为每个路径都附加到一个GameObject上,你可以微调一下你的A*实现,在编辑器里重新跑一下,对比一下输出的2条路径,看看是否符合你修改的初衷。

我不需要我的Nodes和Paths类继承MonoBehaviours,因为我创建了一个可视化behaviour,而不是保存了一个需要可视化的路径的引用。(我也没懂)

本文的第一张图就是我的第一版可视化寻路。

可视化图和代价

我同时也做了一些可视化地图的工作:

以及代价的可视化。我实现了“双重”的代价:下坡比上坡更容易,因此每个边界都有两种颜色,一种是上坡的代价,一种是下坡的代价:

编辑器优化

没有优化的情况下,你的A星算法在很短的时间内运行完,它可能要计算成千上万的节点,这是即时的。

但是,当你有bug时,A*会陷入死循环,Unity会卡住(Unity对于代码死循环基本没有什么措施)。

因此从实用性的角度讲,你会想把计算放到协程里,并且在出错时,在编辑器里显示一些信息。我计划添加一个进度条给Open和Close表,显示它们的容量。我知道节点的总数量,两个列表都不能超过节点的总数量,我可以这样显示:

编辑器里的协程

可悲的是,虽然Unity允许在编辑器里使用协程(Unity的员工在4.5里这样用过),你这样用却不行。

但是Unity实现协程很简单,自己写也很简单。使用类似这样的类你就可以自己做协程。

我也这样做了(把你自己的回调添加到update里,手动运行IEnumerator),但是我添加了一些东西重绘GUI(经常但是不频繁)和其他一些小的特性。

断言和异常

让我们回顾前文:

这是一个重度数据的算法:在真正的游戏中,它会处理成千上万的节点,以及数以万计的边界。调试它简直就是下地狱,千万别那么做啊。

断言(Assertions)是我们的朋友。许多牛b的游戏开发者都喜欢它,尤其是在控制台上(一些机器运行不起来单元测试,断言能帮你在这种机器上完成单元测试)。

我修改了代码的实现,增加了下面的断言:

  1. 从一个节点到另一个节点,代价不能是负的
    1. 这应该是不可能的,即使你想在游戏里实现点特别的东西,你也不可能想要这个结果
    2. 因为A*会滥用这个,在你的“负”边界上来回跑一跑,会发现总的路径代价因为它们而减少
    3. 你可能想要0代价的边界——比如一个传送点——但是小心:它们也可能引起无限循环的问题
    4. 一般来讲当你读到一个边界代价<=0f时应该断言(Assert)
  2. 伪代码的核心循环的最后一行,把当前节点作为相邻节点的父节点。如果这个节点已经指向相邻节点了,就不要这么做!
    1. 再说一下:这个情况不会发生,如果算法正确,它就是绝对错误的
    2. (0或者负的代价会导致这个情况)
    3. 更糟糕的是:一个链表里包含多个相同节点,这会在后面导致死循环
    4. 我增加了一个断言:当给一个链表的末尾添加了一个节点,确保这个节点之前不在链表里
  3. 不要允许open表里的节点数超过总节点数
    1. 应该不可能!不能包含相同的节点!
  4. close表也一样(我把close表用集合实现了,但是如果你的Equals方法有bug,用标准库里的set也不管用)
2017-07-24 22:29:33 qq_35957011 阅读数 4944
  • Unity 值得看的500+ 技术内容列表

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

在游戏中,有一个很常见地需求,就是要让一个角色从A点走向B点,我们期望是让角色走最少的路。嗯,大家可能会说,直线就是最短的。没错,但大多数时候,A到B中间都会出现一些角色无法穿越的东西,比如墙、坑等障碍物。这个时候怎么办呢? 是的,我们需要有一个算法来解决这个问题,算法的目标就是计算出两点之间的最短路径,而且要能避开障碍物。

 原文地址:http://www.cnblogs.com/yangyxd/articles/5447889.html点击打开链接!

百度百科:

A*搜寻算法俗称A星算法。这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。常用于游戏中的NPC的移动计算,或线上游戏的BOT的移动计算上。

 

简化搜索区域

 

要实现寻路,第一步我们要把场景简化出一个易于控制的搜索区域。

怎么处理要根据游戏来决定了。例如,我们可以将搜索区域划分成像素点,但是这样的划分粒度对于一般的游戏来说太高了(没必要)。

作为代替,我们使用格子(一个正方形)作为寻路算法的单元。其他的形状类型也是可能的(比如三角形或者六边形),但是正方形是最简单并且最常用的。

比如地图的长是w=2000像索,宽是h=2000像索,那么我们这个搜索区域可以是二维数组 map[w, h], 包含有400000个正方形,这实在太多了,而且很多时候地图还会更大。

现在让我们基于目前的区域,把区域划分成多个格子来代表搜索空间(在这个简单的例子中,20*20个格子 = 400 个格子, 每个格式代表了100像索):

 

 

 

 

既然我们创建了一个简单的搜索区域,我们来讨论下A星算法的工作原理吧。

我们需要两个列表 (Open和Closed列表)

  •     一个记录下所有被考虑来寻找最短路径的格子(称为open 列表)
  •     一个记录下不会再被考虑的格子(成为closed列表)


首先在closed列表中添加当前位置(我们把这个开始点称为点 “A”)。然后,把所有与它当前位置相邻的可通行格子添加到open列表中。

 

现在我们要从A出发到B点。

在寻路过程中,角色总是不停从一个格子移动到另一个相邻的格子,如果单纯从距离上讲,移动到与自身斜对角的格子走的距离要长一些,而移动到与自身水平或垂直方面平行的格子,则要近一些。

为了描述这种区别,先引入二个概念:

 

节点(Node):每个格子都可以称为节点。

代价(Cost):描述角色移动到某个节点时所走的距离(或难易程度)。

 

 

 

 

如上图,如果每水平或垂直方向移动相邻一个节点所花的代价记为1,则相邻对角节点的代码为1.4(即2的平方根--勾股定理)

 

通常寻路过程中的代价用f,g,h来表示

 

g代表(从指定节点到相邻)节点本身的代价--即上图中的1或1.4

 

h代表从指定节点到目标节点(根据不同的估价公式--后面会解释估价公式)估算出来的代价。

而 f = g + h 表示节点的总代价

 

复制代码
    /// <summary>
    /// 寻路节点
    /// </summary>
    public class NodeItem {
        // 是否是障碍物
        public bool isWall;
        // 位置
        public Vector3 pos;
        // 格子坐标
        public int x, y;

        // 与起点的长度
        public int gCost;
        // 与目标点的长度
        public int hCost;

        // 总的路径长度
        public int fCost {
            get {return gCost + hCost; }
        }

        // 父节点
        public NodeItem parent;

        public NodeItem(bool isWall, Vector3 pos, int x, int y) {
            this.isWall = isWall;
            this.pos = pos;
            this.x = x;
            this.y = y;
        }
    }
复制代码

 

注意:这里有二个新的东东 isWall 和 parent

通常障碍物本身也可以看成是由若干个不可通过的节点所组成,所以 isWall  是用来标记该节点是否为障碍物(节点)。

另外:在考查从一个节点移动到另一个节点时,总是拿自身节点周围的8个相邻节点来说事儿,相对于周边的节点来讲,自身节点称为它们的父节点(parent).

前面一直在提“网格,网格”,干脆把它也封装成类Grid.cs

 

复制代码
using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class Grid : MonoBehaviour {
    public GameObject NodeWall;
    public GameObject Node;

    // 节点半径
    public float NodeRadius = 0.5f;
    // 过滤墙体所在的层
    public LayerMask WhatLayer;

    // 玩家
    public Transform player;
    // 目标
    public Transform destPos;


    /// <summary>
    /// 寻路节点
    /// </summary>
    public class NodeItem {
        // 是否是障碍物
        public bool isWall;
        // 位置
        public Vector3 pos;
        // 格子坐标
        public int x, y;

        // 与起点的长度
        public int gCost;
        // 与目标点的长度
        public int hCost;

        // 总的路径长度
        public int fCost {
            get {return gCost + hCost; }
        }

        // 父节点
        public NodeItem parent;

        public NodeItem(bool isWall, Vector3 pos, int x, int y) {
            this.isWall = isWall;
            this.pos = pos;
            this.x = x;
            this.y = y;
        }
    }

    private NodeItem[,] grid;
    private int w, h;

    private GameObject WallRange, PathRange;
    private List<GameObject> pathObj = new List<GameObject> ();

    void Awake() {
        // 初始化格子
        w = Mathf.RoundToInt(transform.localScale.x * 2);
        h = Mathf.RoundToInt(transform.localScale.y * 2);
        grid = new NodeItem[w, h];

        WallRange = new GameObject ("WallRange");
        PathRange = new GameObject ("PathRange");

        // 将墙的信息写入格子中
        for (int x = 0; x < w; x++) {
            for (int y = 0; y < h; y++) {
                Vector3 pos = new Vector3 (x*0.5f, y*0.5f, -0.25f);
                // 通过节点中心发射圆形射线,检测当前位置是否可以行走
                bool isWall = Physics.CheckSphere (pos, NodeRadius, WhatLayer);
                // 构建一个节点
                grid[x, y] = new NodeItem (isWall, pos, x, y);
                // 如果是墙体,则画出不可行走的区域
                if (isWall) {
                    GameObject obj = GameObject.Instantiate (NodeWall, pos, Quaternion.identity) as GameObject;
                    obj.transform.SetParent (WallRange.transform);
                }
            }
        }

    }

    // 根据坐标获得一个节点
    public NodeItem getItem(Vector3 position) {
        int x = Mathf.RoundToInt (position.x) * 2;
        int y = Mathf.RoundToInt (position.y) * 2;
        x = Mathf.Clamp (x, 0, w - 1);
        y = Mathf.Clamp (y, 0, h - 1);
        return grid [x, y];
    }

    // 取得周围的节点
    public List<NodeItem> getNeibourhood(NodeItem node) {
        List<NodeItem> list = new List<NodeItem> ();
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                // 如果是自己,则跳过
                if (i == 0 && j == 0)
                    continue;
                int x = node.x + i;
                int y = node.y + j;
                // 判断是否越界,如果没有,加到列表中
                if (x < w && x >= 0 && y < h && y >= 0)
                    list.Add (grid [x, y]);
            }
        }
        return list;
    }

    // 更新路径
    public void updatePath(List<NodeItem> lines) {
        int curListSize = pathObj.Count;
        for (int i = 0, max = lines.Count; i < max; i++) {
            if (i < curListSize) {
                pathObj [i].transform.position = lines [i].pos;
                pathObj [i].SetActive (true);
            } else {
                GameObject obj = GameObject.Instantiate (Node, lines [i].pos, Quaternion.identity) as GameObject;
                obj.transform.SetParent (PathRange.transform);
                pathObj.Add (obj);
            }
        }
        for (int i = lines.Count; i < curListSize; i++) {
            pathObj [i].SetActive (false);
        }
    }
}
复制代码

 

在寻路的过程中“条条道路通罗马”,路径通常不止一条,只不过所花的代价不同而已。

所以我们要做的事情,就是要尽最大努力找一条代价最小的路径。

但是,即使是代价相同的最佳路径,也有可能出现不同的走法。

用代码如何估算起点与终点之间的代价呢?

 

 

复制代码
//曼哈顿估价法
private function manhattan(node:Node):Number
{
    return Math.abs(node.x - _endNode.x) * _straightCost + Math.abs(node.y + _endNode.y) * _straightCost;
}
 
//几何估价法
private function euclidian(node:Node):Number
{
    var dx:Number=node.x - _endNode.x;
    var dy:Number=node.y - _endNode.y;
    return Math.sqrt(dx * dx + dy * dy) * _straightCost;
}
 
//对角线估价法
private function diagonal(node:Node):Number
{
    var dx:Number=Math.abs(node.x - _endNode.x);
    var dy:Number=Math.abs(node.y - _endNode.y);
    var diag:Number=Math.min(dx, dy);
    var straight:Number=dx + dy;
    return _diagCost * diag + _straightCost * (straight - 2 * diag);
}
复制代码

 

 

上面的代码给出了三种基本的估价算法(也称估价公式),其算法示意图如下:

 

 

如上图,对于“曼哈顿算法”最贴切的描述莫过于孙燕姿唱过的那首成名曲“直来直往”,笔直的走,然后转个弯,再笔直的继续。

“几何算法”的最好解释就是“勾股定理”,算出起点与终点之间的直线距离,然后乘上代价因子。

“对角算法”综合了以上二种算法,先按对角线走,一直走到与终点水平或垂直平行后,再笔直的走。

 

这三种算法可以实现不同的寻路结果,我们这个例子用的是“对角算法”:

复制代码
    // 获取两个节点之间的距离
    int getDistanceNodes(Grid.NodeItem a, Grid.NodeItem b) {
        int cntX = Mathf.Abs (a.x - b.x);
        int cntY = Mathf.Abs (a.y - b.y);
        // 判断到底是那个轴相差的距离更远 , 实际上,为了简化计算,我们将代价*10变成了整数。
        if (cntX > cntY) {
            return 14 * cntY + 10 * (cntX - cntY);
        } else {
            return 14 * cntX + 10 * (cntY - cntX);
        }
    }
复制代码

 

好吧,下面直接贴出全部的寻路算法 FindPath.cs:

复制代码
using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class FindPath : MonoBehaviour {
    private Grid grid;

    // Use this for initialization
    void Start () {
        grid = GetComponent<Grid> ();
    }
    
    // Update is called once per frame
    void Update () {
        FindingPath (grid.player.position, grid.destPos.position);
    }

    // A*寻路
    void FindingPath(Vector3 s, Vector3 e) {
        Grid.NodeItem startNode = grid.getItem (s);
        Grid.NodeItem endNode = grid.getItem (e);

        List<Grid.NodeItem> openSet = new List<Grid.NodeItem> ();
        HashSet<Grid.NodeItem> closeSet = new HashSet<Grid.NodeItem> ();
        openSet.Add (startNode);

        while (openSet.Count > 0) {
            Grid.NodeItem curNode = openSet [0];

            for (int i = 0, max = openSet.Count; i < max; i++) {
                if (openSet [i].fCost <= curNode.fCost &&
                    openSet [i].hCost < curNode.hCost) {
                    curNode = openSet [i];
                }
            }

            openSet.Remove (curNode);
            closeSet.Add (curNode);

            // 找到的目标节点
            if (curNode == endNode) {
                generatePath (startNode, endNode);
                return;
            }

            // 判断周围节点,选择一个最优的节点
            foreach (var item in grid.getNeibourhood(curNode)) {
                // 如果是墙或者已经在关闭列表中
                if (item.isWall || closeSet.Contains (item))
                    continue;
                // 计算当前相领节点现开始节点距离
                int newCost = curNode.gCost + getDistanceNodes (curNode, item);
                // 如果距离更小,或者原来不在开始列表中
                if (newCost < item.gCost || !openSet.Contains (item)) {
                    // 更新与开始节点的距离
                    item.gCost = newCost;
                    // 更新与终点的距离
                    item.hCost = getDistanceNodes (item, endNode);
                    // 更新父节点为当前选定的节点
                    item.parent = curNode;
                    // 如果节点是新加入的,将它加入打开列表中
                    if (!openSet.Contains (item)) {
                        openSet.Add (item);
                    }
                }
            }
        }

        generatePath (startNode, null);
    }

    // 生成路径
    void generatePath(Grid.NodeItem startNode, Grid.NodeItem endNode) {
        List<Grid.NodeItem> path = new List<Grid.NodeItem>();
        if (endNode != null) {
            Grid.NodeItem temp = endNode;
            while (temp != startNode) {
                path.Add (temp);
                temp = temp.parent;
            }
            // 反转路径
            path.Reverse ();
        }
        // 更新路径
        grid.updatePath(path);
    }

    // 获取两个节点之间的距离
    int getDistanceNodes(Grid.NodeItem a, Grid.NodeItem b) {
        int cntX = Mathf.Abs (a.x - b.x);
        int cntY = Mathf.Abs (a.y - b.y);
        // 判断到底是那个轴相差的距离更远
        if (cntX > cntY) {
            return 14 * cntY + 10 * (cntX - cntY);
        } else {
            return 14 * cntX + 10 * (cntY - cntX);
        }
    }


}
复制代码

 

运行效果图:

 

红色区域是标识出来的不可以行走区域。(代码中对两个点的定位有点小小的问题,不过不影响算法的演示,我也就懒得改了)