A* 寻路学习

启发式搜索:启发式搜索就是在状态空间中的搜索.对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标．这样可以省略大量无谓的搜索路径，提高了效率．在启发式搜索中，对位置的估价是十分重要的，采用了不同的估价可以有不同的效果

在启发式搜索中,对位置的估价是十分重要的.采用了不同的估价可以有不同的效果

估价函数:从当前节点移动到目标节点的预估费用:这个估计就是启发式的.在寻路问题和迷宫问题中,我们通常用曼哈顿(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

　　　　　　重新设置其父节点为当前点

　　　　如果相邻点不在开启集合中

　　　　　　添加相邻点到开启集合中

 1 /*
 2 脚本名称:
 3 脚本作者:
 4 建立时间:
 5 脚本功能:
 6 版本号:
 7 */
 8 using UnityEngine;
 9 using System.Collections;
10 
11 namespace VoidGame {
12 
13     /// <summary>
14     /// 节点,寻路的最小单位
15     /// </summary>
16     public class Node {
17         /// <summary>
18         /// 节点是否可以通过
19         /// </summary>
20         public bool m_canWalk;
21         /// <summary>
22         /// 节点的位置
23         /// </summary>
24         public Vector3 m_position;
25         /// <summary>
26         /// 节点在网格行(x轴)中的位置
27         /// </summary>
28         public int m_gridX;
29         /// <summary>
30         /// 节点在网格列(z轴)中的位置
31         /// </summary>
32         public int m_gridY;
33 
34         /// <summary>
35         /// 从起始点当前节点的距离
36         /// </summary>
37         public int m_gCost;
38         /// <summary>
39         /// 从当前节点到目标节点的预估距离
40         /// </summary>
41         public int m_hCost;
42         /// <summary>
43         /// f = g + h
44         /// </summary>
45         public int m_fCost {
46             get {
47                 return m_gCost + m_hCost;
48             }
49         }
50 
51         /// <summary>
52         /// 父节点
53         /// </summary>
54         public Node m_nodeParent;
55 
56 
57         public Node(bool canWalk,Vector3 position,int x,int y) {
58             m_canWalk = canWalk;
59             m_position = position;
60             m_gridX = x;
61             m_gridY = y;
62         }
63 
64     }
65 }

Node

  1 /*
  2 脚本名称:
  3 脚本作者:
  4 建立时间:
  5 脚本功能:
  6 版本号:
  7 */
  8 using UnityEngine;
  9 using System.Collections;
 10 using System.Collections.Generic;
 11 
 12 namespace VoidGame {
 13     /// <summary>
 14     /// 节点组成的网格
 15     /// </summary>
 16     public class Grid : MonoBehaviour {
 17         /// <summary>
 18         /// 节点网格数组
 19         /// </summary>
 20         private Node[,] m_nodeGrid;
 21         /// <summary>
 22         /// 整个网格的大小
 23         /// </summary>
 24         public Vector2 m_gridSize;
 25         /// <summary>
 26         /// 网格行(x轴)包含的节点数量
 27         /// </summary>
 28         public int m_gridNodeCountX;
 29         /// <summary>
 30         /// 网格列(z轴)包含的节点数量
 31         /// </summary>
 32         public int m_gridNodeCountY;
 33         /// <summary>
 34         /// 节点半径
 35         /// </summary>
 36         public float m_nodeRadius;
 37         /// <summary>
 38         /// 节点直径
 39         /// </summary>
 40         private float m_nodeDiameter;
 41 
 42         /// <summary>
 43         /// 节点不可走的层
 44         /// </summary>
 45         public LayerMask m_unWalkableLayer;
 46 
 47         /// <summary>
 48         /// 玩家
 49         /// </summary>
 50         public Transform m_startTransform;
 51 
 52         /// <summary>
 53         /// 从起点到终点的路径节点列表
 54         /// </summary>
 55         public List<Node> m_pathNodeList = new List<Node>();
 56 
 57 
 58         private void Start() {
 59             //计算节点直径
 60             m_nodeDiameter = m_nodeRadius * 2;
 61             //计算网格行(x轴)中的节点数量
 62             m_gridNodeCountX = Mathf.RoundToInt(m_gridSize.x / m_nodeDiameter);
 63             //计算网格列(z轴)中的节点数量
 64             m_gridNodeCountY = Mathf.RoundToInt(m_gridSize.y / m_nodeDiameter);
 65             //设置节点网格数组的大小
 66             m_nodeGrid = new Node[m_gridNodeCountX,m_gridNodeCountY];
 67 
 68             CreateNodeGrid();
 69         }
 70 
 71         private void Update() {
 72 
 73         }
 74 
 75         private void OnDrawGizmos() {
 76             
 77             //画节点网格包围框
 78             Gizmos.DrawWireCube(transform.position,new Vector3(m_gridSize.x,1,m_gridSize.y));
 79             //节点网格为空,直接返回
 80             if(m_nodeGrid == null) {
 81                 return;
 82             }
 83 
 84             //遍历节点网格数组
 85             foreach(var node in m_nodeGrid) {
 86                 //可以行走的网格颜色为白色,不可行走的网格颜色为红色
 87                 Gizmos.color = node.m_canWalk == true ? Color.white : Color.red;
 88                 //Gizmos视图中用比节点稍小的cube表示一个节点,便于观察
 89                 Gizmos.DrawCube(node.m_position,Vector3.one * (m_nodeDiameter - 0.1f));
 90             }
 91 
 92             //获取起始节点
 93             Node m_startNode = GetNodeFromPosition(m_startTransform.position);
 94 
 95             //如果路径列表不为空
 96             if(m_pathNodeList != null) {
 97                 //画出路线
 98                 foreach(var node in m_pathNodeList) {
 99                     Gizmos.color = Color.black;
100                     Gizmos.DrawCube(node.m_position,Vector3.one * (m_nodeDiameter - 0.1f));
101                 }
102             }
103 
104             //如果起始节点不为空并且起始节点可以走
105             if(m_startNode != null && m_startNode.m_canWalk) {
106                 Gizmos.color = Color.cyan;
107                 Gizmos.DrawCube(m_startNode.m_position,Vector3.one * (m_nodeDiameter - 0.1f));
108             }
109         }
110 
111         /// <summary>
112         /// 创建节点网格
113         /// </summary>
114         private void CreateNodeGrid() {
115             //获取起始点,为网格的左下
116             Vector3 startPosition = new Vector3(transform.position.x - m_gridSize.x / 2,0,transform.position.y - m_gridSize.y / 2);
117             //从左到右,从下到上生成节点
118             for(int i = 0;i < m_gridNodeCountY;i++) {
119                 for(int j = 0;j < m_gridNodeCountX;j++) {
120                     Vector3 nodePosition = new Vector3(startPosition.x + i * m_nodeDiameter + m_nodeRadius,0,startPosition.z + j * m_nodeDiameter + m_nodeRadius);
121                     //检测以节点半径为半径的球形范围内是否有属于m_unWalkableLayer的物体
122                     bool canWalk = !Physics.CheckSphere(nodePosition,m_nodeRadius,m_unWalkableLayer);
123                     //根据检测的结果节点是否为可走
124                     m_nodeGrid[i,j] = new Node(canWalk,nodePosition,i,j);
125                 }
126             }
127         }
128 
129         /// <summary>
130         /// 根据所在位置获得位置所在的节点
131         /// </summary>
132         /// <param name="position">所在位置</param>
133         /// <returns></returns>
134         public Node GetNodeFromPosition(Vector3 position) {
135             //获取位置所在网格行(x轴)上的比例
136             float percentX = (position.x + m_gridSize.x / 2) / m_gridSize.x;
137             //获取位置所在网格列(z轴)上的比例
138             float percentY = (position.z + m_gridSize.y / 2) / m_gridSize.y;
139             //确保行百分比和列百分比在0-1之间
140             percentX = Mathf.Clamp01(percentX);
141             percentY = Mathf.Clamp01(percentY);
142 
143             //四舍五入网格行上的比例,获得在网格行中的节点位置
144             int x = Mathf.RoundToInt((m_gridNodeCountX - 1) * percentX);
145             //四舍五入网格列上的比例,获得在网格列中的节点位置
146             int y = Mathf.RoundToInt((m_gridNodeCountY - 1) * percentY);
147             
148             //通过行位置和列位置确定要返回的节点
149             return m_nodeGrid[x,y];
150         }
151 
152         /// <summary>
153         /// 获取节点的邻居
154         /// </summary>
155         /// <param name="node">节点</param>
156         /// <returns></returns>
157         public List<Node> GetNeighbors(Node node) {
158             List<Node> neighbourNodeList = new List<Node>();
159             for(int i = -1;i <= 1;i++) {
160                 for(int j = -1;j <= 1;j++) {
161                     //i==0&&j==0 表示是自身,不添加
162                     if(i == 0 && j == 0) {
163                         continue;
164                     }
165                     //从左到右
166                     int tempX = node.m_gridX + j;
167                     //从下到上
168                     int tempY = node.m_gridY + i;
169                     //限制x,0 < x < m_gridNodeCountX
170                     //限制y,0 < y < m_gridNodeCountY
171                     //满足以上条件,将节点周围的8个节点添加到节点的邻居节点列表
172                     if(tempX > 0 && tempX < m_gridNodeCountX && tempY > 0 && tempY < m_gridNodeCountY) {
173                         neighbourNodeList.Add(m_nodeGrid[tempX,tempY]);
174                     }
175                 }
176             }
177 
178             return neighbourNodeList;
179         }
180     }
181 }

Grid

  1 /*
  2 脚本名称:
  3 脚本作者:
  4 建立时间:
  5 脚本功能:
  6 版本号:
  7 */
  8 using UnityEngine;
  9 using System.Collections;
 10 using System.Collections.Generic;
 11 
 12 namespace VoidGame {
 13 
 14     public class FindPath : MonoBehaviour {
 15         /// <summary>
 16         /// 起点
 17         /// </summary>
 18         public Transform m_start;
 19         /// <summary>
 20         /// 目标
 21         /// </summary>
 22         public Transform m_target;
 23 
 24         /// <summary>
 25         /// 要寻路的网格
 26         /// </summary>
 27         private Grid m_grid;
 28 
 29         private void Start() {
 30             m_grid = GetComponent<Grid>();
 31         }
 32 
 33         private void Update() {
 34             FindingPath(m_start.position,m_target.position);
 35         }
 36 
 37         /// <summary>
 38         /// 寻路
 39         /// </summary>
 40         /// <param name="startPosition">起始位置</param>
 41         /// <param name="endPosition">结束位置</param>
 42         private void FindingPath(Vector3 startPosition,Vector3 endPosition) {
 43             //起始节点
 44             Node startNode = m_grid.GetNodeFromPosition(startPosition);
 45             //结束节点
 46             Node endNode = m_grid.GetNodeFromPosition(endPosition);
 47 
 48             //待检查的节点列表
 49             List<Node> openlist = new List<Node>();
 50             //已检查的节点列表
 51             HashSet<Node> closeList = new HashSet<Node>();
 52 
 53             //添加起始节点到待检查的列表
 54             openlist.Add(startNode);
 55 
 56             //如果待检查的列表的数量大于0
 57             while(openlist.Count > 0) {
 58                 //设置当前节点为待检查节点列表的第一个节点
 59                 Node currentNode = openlist[0];
 60 
 61                 //遍历待检查的列表
 62                 for(int i = 0;i < openlist.Count;i++) {
 63                     //如果 待检查节点的f小于当前节点的f 或者
 64                     //     待检查节点的f等于当前节点的f并且待检查节点的h小于当前节点的h
 65                     //将当前节点设置为待检查节点
 66                     if(openlist[i].m_fCost < currentNode.m_fCost ||
 67                         openlist[i].m_fCost == currentNode.m_fCost && openlist[i].m_hCost < currentNode.m_hCost) {
 68                         currentNode = openlist[i];
 69                     }
 70                 }
 71 
 72                 //从待检查列表中移除当前节点
 73                 openlist.Remove(currentNode);
 74                 //添加当前节点到已检查节点列表
 75                 closeList.Add(currentNode);
 76 
 77                 //如果当前节点等于终端节点,生成从当前节点到终端节点的路径
 78                 if(currentNode == endNode) {
 79                     GeneratePath(startNode,endNode);
 80                 }
 81 
 82                 //遍历当前节点的邻居节点
 83                 foreach(var node in m_grid.GetNeighbors(currentNode)) {
 84                     //如果邻居节点不能走或者待检查列表里包含邻居节点,不处理
 85                     if(!node.m_canWalk || closeList.Contains(node)) {
 86                         continue;
 87                     }
 88 
 89                     //获得新的g.为当前节点的g + 当前节点到邻居节点的距离
 90                     int newgCost = currentNode.m_gCost + GetDistanceBetweenNodes(currentNode,node);
 91 
 92                     //如果新g 小于 邻居节点的g 或者 待检查列表不包括邻居节点
 93                     if(newgCost < node.m_gCost || !openlist.Contains(node)) {
 94                         //邻居节点的g等于新的g
 95                         node.m_gCost = newgCost;
 96                         //邻居节点的h等于邻居节点到终端节点的距离
 97                         node.m_hCost = GetDistanceBetweenNodes(node,endNode);
 98                         //设置邻居节点的父节点为当前节点
 99                         node.m_nodeParent = currentNode;
100                         //如果待检查节点列表不包括当前节点
101                         if(!openlist.Contains(currentNode)) {
102                             //添加邻居节点到待检查节点列表
103                             openlist.Add(node);
104                         }
105                     }
106                 }
107 
108             }
109         }
110 
111         /// <summary>
112         /// 获取两个节点之间的距离
113         /// </summary>
114         /// <param name="nodeA">节点a</param>
115         /// <param name="nodeB">节点b</param>
116         /// <returns></returns>
117         private int GetDistanceBetweenNodes(Node nodeA,Node nodeB) {
118             //获取节点a和节点b之间在网格行(x轴)上的间隔的节点数量
119             int countX = Mathf.Abs(nodeA.m_gridX - nodeB.m_gridX);
120             //获取节点a和节点b之间在网格列(z轴)上的间隔的节点数量
121             int countY = Mathf.Abs(nodeA.m_gridY - nodeB.m_gridY);
122 
123             //如果网格行上的间隔节点数量大于网格列上的间隔节点数量
124             if(countX > countY) {
125                 return 14 * countY + 10 * (countX - countY);
126             //否则
127             } else {
128                 return 14 * countX + 10 * (countY - countX);
129             }
130         }
131 
132         /// <summary>
133         /// 生成最终路径
134         /// </summary>
135         /// <param name="startNode">起始节点</param>
136         /// <param name="endNode">终端节点</param>
137         private void GeneratePath(Node startNode,Node endNode) {
138             List<Node> tempPath = new List<Node>();
139             Node tempNode = endNode;
140 
141             //从终端节点回溯直到起始节点
142             while(tempNode != startNode) {
143                 tempPath.Add(tempNode);
144                 tempNode = tempNode.m_nodeParent;
145             }
146 
147             //倒转从终端节点到开始节点的列表.获得从开始节点到终端节点的列表
148             tempPath.Reverse();
149 
150             m_grid.m_pathNodeList = tempPath;
151         }
152     }
153 }

FindPath

项目:https://pan.baidu.com/s/1mi2TSxU