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-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

2017-07-24 22:29:33 qq_35957011 阅读数 4972
  • 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);
        }
    }


}
复制代码

 

运行效果图:

 

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

2019-05-17 14:18:42 qq_37770855 阅读数 197
  • Unity 值得看的500+ 技术内容列表

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