启发式搜索:启发式搜索就是在状态空间中的搜索.对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标．这样可以省略大量无谓的搜索路径，提高了效率．在启发式搜索中，对位置的估价是十分重要的，采用了不同的估价可以有不同的效果
在启发式搜索中,对位置的估价是十分重要的.采用了不同的估价可以有不同的效果
估价函数:从当前节点移动到目标节点的预估费用:这个估计就是启发式的.在寻路问题和迷宫问题中,我们通常用曼哈顿(manhattan)估价函数预计费用
A*算法的特点:A*算法在理论伤是时间最优的,但是也有缺点:它的空间增长是指数级别的.(优化:二叉堆)
开启列表:待检查方格的集合列表，寻找周围可以达到的点，加入到此表中， 并保存中心点为父节点
关闭列表:列表中保存不需要再次检查的方格
G 从起始节点到当前节点的距离
H 从当前节点到目标节点的估计距离
F = G + H
F,G和H的评分被写在每个方格里.正如在紧挨起始格右侧的方格所表示的,F被打印中间,G在左上角,H则在右上角
搜索过程:
1:把起始格添加到开启列表(openlist)
2:寻找起点周围所有可到达或者可通过的方格,把他们加入开启列表.
3:从开启列表中删除点A,把它加入到一个关闭列表(closedlist),列表中保存所有不需要再次检查的方格.
4:把当前格子从开启列表中删除,然后添加到关闭列表中.
5:检查所有相邻格子.跳过那些已经在关闭列表中的或者不可通过的,把他们添加进开启列表.把选中的方格作为新的方格的父节点.
6:如果某个相邻格已经在开启列表里了,检查现在的这条路径G值是否会更低一些.如果新的G值更低,那就把相邻方格的父节点改为目前选中的方格,重新计算F和G的值。
步骤总结:
1:把起始格添加到开启列表.
2:重复如下的工作:
a) 寻找开启列表中F值最低的格子.我们称它为当前格.
b) 把它切换到关闭列表.
c) 对相邻的格中的每一个
* 如果它不可通过或者已经在关闭列表中,略过它.反之如下.
* 如果它不在开启列表中,把它添加进去.把当前格作为这一格的父节点.记录从起始点经过当前格的这一格的G,H,和F值.
* 如果它已经在开启列表中,用G值为参考检查新的路径是否更好.更低的G值意味着更好的路径.
如果是这样,就把这一格的父节点改成当前格,并且重新计算这一格的G和F值.
d) 停止,当你
* 把目标格添加进了关闭列表,这时候路径被找到
* 没有找到目标格,开启列表已经空了.这时候,路径不存在.
3.保存路径.从目标格开始,沿着每一格的父节点移动直到回到起始格.
算法实现:
开启集合(openlist)
关闭集合(closedlist)
添加起始点到开始集合中
循环如下步骤:
当前点=开启集合中最小F_Cost的点
将当前点移出开启集合中
将当前点添加到关闭集合中
如果当前点是目标点,结束查询
遍历当前点的每个相邻点
如果相邻点不能访问或者相邻点在关闭集合中,跳过此相邻点
如果新路径到相邻点的距离更短,或者相邻点不在开启集合中
重新设置F_Cost
重新设置其父节点为当前点
如果相邻点不在开启集合中
添加相邻点到开启集合中
/*
脚本名称:
脚本作者:
建立时间:
脚本功能:
版本号:
*/
using UnityEngine;
using System.Collections; namespace VoidGame { /// <summary>
/// 节点,寻路的最小单位
/// </summary>
public class Node {
/// <summary>
/// 节点是否可以通过
/// </summary>
public bool m_canWalk;
/// <summary>
/// 节点的位置
/// </summary>
public Vector3 m_position;
/// <summary>
/// 节点在网格行(x轴)中的位置
/// </summary>
public int m_gridX;
/// <summary>
/// 节点在网格列(z轴)中的位置
/// </summary>
public int m_gridY; /// <summary>
/// 从起始点当前节点的距离
/// </summary>
public int m_gCost;
/// <summary>
/// 从当前节点到目标节点的预估距离
/// </summary>
public int m_hCost;
/// <summary>
/// f = g + h
/// </summary>
public int m_fCost {
get {
return m_gCost + m_hCost;
}
} /// <summary>
/// 父节点
/// </summary>
public Node m_nodeParent; public Node(bool canWalk,Vector3 position,int x,int y) {
m_canWalk = canWalk;
m_position = position;
m_gridX = x;
m_gridY = y;
} }
}
Node
/*
脚本名称:
脚本作者:
建立时间:
脚本功能:
版本号:
*/
using UnityEngine;
using System.Collections;
using System.Collections.Generic; namespace VoidGame {
/// <summary>
/// 节点组成的网格
/// </summary>
public class Grid : MonoBehaviour {
/// <summary>
/// 节点网格数组
/// </summary>
private Node[,] m_nodeGrid;
/// <summary>
/// 整个网格的大小
/// </summary>
public Vector2 m_gridSize;
/// <summary>
/// 网格行(x轴)包含的节点数量
/// </summary>
public int m_gridNodeCountX;
/// <summary>
/// 网格列(z轴)包含的节点数量
/// </summary>
public int m_gridNodeCountY;
/// <summary>
/// 节点半径
/// </summary>
public float m_nodeRadius;
/// <summary>
/// 节点直径
/// </summary>
private float m_nodeDiameter; /// <summary>
/// 节点不可走的层
/// </summary>
public LayerMask m_unWalkableLayer; /// <summary>
/// 玩家
/// </summary>
public Transform m_startTransform; /// <summary>
/// 从起点到终点的路径节点列表
/// </summary>
public List<Node> m_pathNodeList = new List<Node>(); private void Start() {
//计算节点直径
m_nodeDiameter = m_nodeRadius * ;
//计算网格行(x轴)中的节点数量
m_gridNodeCountX = Mathf.RoundToInt(m_gridSize.x / m_nodeDiameter);
//计算网格列(z轴)中的节点数量
m_gridNodeCountY = Mathf.RoundToInt(m_gridSize.y / m_nodeDiameter);
//设置节点网格数组的大小
m_nodeGrid = new Node[m_gridNodeCountX,m_gridNodeCountY]; CreateNodeGrid();
} private void Update() { } private void OnDrawGizmos() { //画节点网格包围框
Gizmos.DrawWireCube(transform.position,new Vector3(m_gridSize.x,,m_gridSize.y));
//节点网格为空,直接返回
if(m_nodeGrid == null) {
return;
} //遍历节点网格数组
foreach(var node in m_nodeGrid) {
//可以行走的网格颜色为白色,不可行走的网格颜色为红色
Gizmos.color = node.m_canWalk == true ? Color.white : Color.red;
//Gizmos视图中用比节点稍小的cube表示一个节点,便于观察
Gizmos.DrawCube(node.m_position,Vector3.one * (m_nodeDiameter - 0.1f));
} //获取起始节点
Node m_startNode = GetNodeFromPosition(m_startTransform.position); //如果路径列表不为空
if(m_pathNodeList != null) {
//画出路线
foreach(var node in m_pathNodeList) {
Gizmos.color = Color.black;
Gizmos.DrawCube(node.m_position,Vector3.one * (m_nodeDiameter - 0.1f));
}
} //如果起始节点不为空并且起始节点可以走
if(m_startNode != null && m_startNode.m_canWalk) {
Gizmos.color = Color.cyan;
Gizmos.DrawCube(m_startNode.m_position,Vector3.one * (m_nodeDiameter - 0.1f));
}
} /// <summary>
/// 创建节点网格
/// </summary>
private void CreateNodeGrid() {
//获取起始点,为网格的左下
Vector3 startPosition = new Vector3(transform.position.x - m_gridSize.x / ,,transform.position.y - m_gridSize.y / );
//从左到右,从下到上生成节点
for(int i = ;i < m_gridNodeCountY;i++) {
for(int j = ;j < m_gridNodeCountX;j++) {
Vector3 nodePosition = new Vector3(startPosition.x + i * m_nodeDiameter + m_nodeRadius,,startPosition.z + j * m_nodeDiameter + m_nodeRadius);
//检测以节点半径为半径的球形范围内是否有属于m_unWalkableLayer的物体
bool canWalk = !Physics.CheckSphere(nodePosition,m_nodeRadius,m_unWalkableLayer);
//根据检测的结果节点是否为可走
m_nodeGrid[i,j] = new Node(canWalk,nodePosition,i,j);
}
}
} /// <summary>
/// 根据所在位置获得位置所在的节点
/// </summary>
/// <param name="position">所在位置</param>
/// <returns></returns>
public Node GetNodeFromPosition(Vector3 position) {
//获取位置所在网格行(x轴)上的比例
float percentX = (position.x + m_gridSize.x / ) / m_gridSize.x;
//获取位置所在网格列(z轴)上的比例
float percentY = (position.z + m_gridSize.y / ) / m_gridSize.y;
//确保行百分比和列百分比在0-1之间
percentX = Mathf.Clamp01(percentX);
percentY = Mathf.Clamp01(percentY); //四舍五入网格行上的比例,获得在网格行中的节点位置
int x = Mathf.RoundToInt((m_gridNodeCountX - ) * percentX);
//四舍五入网格列上的比例,获得在网格列中的节点位置
int y = Mathf.RoundToInt((m_gridNodeCountY - ) * percentY); //通过行位置和列位置确定要返回的节点
return m_nodeGrid[x,y];
} /// <summary>
/// 获取节点的邻居
/// </summary>
/// <param name="node">节点</param>
/// <returns></returns>
public List<Node> GetNeighbors(Node node) {
List<Node> neighbourNodeList = new List<Node>();
for(int i = -;i <= ;i++) {
for(int j = -;j <= ;j++) {
//i==0&&j==0 表示是自身,不添加
if(i == && j == ) {
continue;
}
//从左到右
int tempX = node.m_gridX + j;
//从下到上
int tempY = node.m_gridY + i;
//限制x,0 < x < m_gridNodeCountX
//限制y,0 < y < m_gridNodeCountY
//满足以上条件,将节点周围的8个节点添加到节点的邻居节点列表
if(tempX > && tempX < m_gridNodeCountX && tempY > && tempY < m_gridNodeCountY) {
neighbourNodeList.Add(m_nodeGrid[tempX,tempY]);
}
}
} return neighbourNodeList;
}
}
}
Grid
/*
脚本名称:
脚本作者:
建立时间:
脚本功能:
版本号:
*/
using UnityEngine;
using System.Collections;
using System.Collections.Generic; namespace VoidGame { public class FindPath : MonoBehaviour {
/// <summary>
/// 起点
/// </summary>
public Transform m_start;
/// <summary>
/// 目标
/// </summary>
public Transform m_target; /// <summary>
/// 要寻路的网格
/// </summary>
private Grid m_grid; private void Start() {
m_grid = GetComponent<Grid>();
} private void Update() {
FindingPath(m_start.position,m_target.position);
} /// <summary>
/// 寻路
/// </summary>
/// <param name="startPosition">起始位置</param>
/// <param name="endPosition">结束位置</param>
private void FindingPath(Vector3 startPosition,Vector3 endPosition) {
//起始节点
Node startNode = m_grid.GetNodeFromPosition(startPosition);
//结束节点
Node endNode = m_grid.GetNodeFromPosition(endPosition); //待检查的节点列表
List<Node> openlist = new List<Node>();
//已检查的节点列表
HashSet<Node> closeList = new HashSet<Node>(); //添加起始节点到待检查的列表
openlist.Add(startNode); //如果待检查的列表的数量大于0
while(openlist.Count > ) {
//设置当前节点为待检查节点列表的第一个节点
Node currentNode = openlist[]; //遍历待检查的列表
for(int i = ;i < openlist.Count;i++) {
//如果 待检查节点的f小于当前节点的f 或者
// 待检查节点的f等于当前节点的f并且待检查节点的h小于当前节点的h
//将当前节点设置为待检查节点
if(openlist[i].m_fCost < currentNode.m_fCost ||
openlist[i].m_fCost == currentNode.m_fCost && openlist[i].m_hCost < currentNode.m_hCost) {
currentNode = openlist[i];
}
} //从待检查列表中移除当前节点
openlist.Remove(currentNode);
//添加当前节点到已检查节点列表
closeList.Add(currentNode); //如果当前节点等于终端节点,生成从当前节点到终端节点的路径
if(currentNode == endNode) {
GeneratePath(startNode,endNode);
} //遍历当前节点的邻居节点
foreach(var node in m_grid.GetNeighbors(currentNode)) {
//如果邻居节点不能走或者待检查列表里包含邻居节点,不处理
if(!node.m_canWalk || closeList.Contains(node)) {
continue;
} //获得新的g.为当前节点的g + 当前节点到邻居节点的距离
int newgCost = currentNode.m_gCost + GetDistanceBetweenNodes(currentNode,node); //如果新g 小于 邻居节点的g 或者 待检查列表不包括邻居节点
if(newgCost < node.m_gCost || !openlist.Contains(node)) {
//邻居节点的g等于新的g
node.m_gCost = newgCost;
//邻居节点的h等于邻居节点到终端节点的距离
node.m_hCost = GetDistanceBetweenNodes(node,endNode);
//设置邻居节点的父节点为当前节点
node.m_nodeParent = currentNode;
//如果待检查节点列表不包括当前节点
if(!openlist.Contains(currentNode)) {
//添加邻居节点到待检查节点列表
openlist.Add(node);
}
}
} }
} /// <summary>
/// 获取两个节点之间的距离
/// </summary>
/// <param name="nodeA">节点a</param>
/// <param name="nodeB">节点b</param>
/// <returns></returns>
private int GetDistanceBetweenNodes(Node nodeA,Node nodeB) {
//获取节点a和节点b之间在网格行(x轴)上的间隔的节点数量
int countX = Mathf.Abs(nodeA.m_gridX - nodeB.m_gridX);
//获取节点a和节点b之间在网格列(z轴)上的间隔的节点数量
int countY = Mathf.Abs(nodeA.m_gridY - nodeB.m_gridY); //如果网格行上的间隔节点数量大于网格列上的间隔节点数量
if(countX > countY) {
return * countY + * (countX - countY);
//否则
} else {
return * countX + * (countY - countX);
}
} /// <summary>
/// 生成最终路径
/// </summary>
/// <param name="startNode">起始节点</param>
/// <param name="endNode">终端节点</param>
private void GeneratePath(Node startNode,Node endNode) {
List<Node> tempPath = new List<Node>();
Node tempNode = endNode; //从终端节点回溯直到起始节点
while(tempNode != startNode) {
tempPath.Add(tempNode);
tempNode = tempNode.m_nodeParent;
} //倒转从终端节点到开始节点的列表.获得从开始节点到终端节点的列表
tempPath.Reverse(); m_grid.m_pathNodeList = tempPath;
}
}
}
FindPath
项目:https://pan.baidu.com/s/1mi2TSxU