Unity中的A*寻路算法

Posted by 许瑞政 on 2020-11-28

Unity中的A*寻路算法

1.什么是A*寻路算法

这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。常用于游戏中的NPC(Non-Player-ControlledCharacter)的移动计算,或线上游戏的BOT(ROBOT)的移动计算上。该算法像Dijkstra算法一样,可以找到一条最短路径;也像BFS一样,进行启发式的搜索。
A*算法是一种启发式搜索算法,启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径,提高了效率。
简单来说:A星算法=Dijkstra算法+启发式搜索。

2.为什么选择A*寻路算法

A*是静态网格中求解最短路最有效的方法。也是耗时的算法,不适合寻路频繁的场合。一般来说适合精度需求高的场合。

合适的场景

策略游戏的策略搜索
方格化游戏中的寻路

3.A*寻路算法的实现

寻路区域数据化

要进行寻路,首先需要把寻路的区域进行数据化。将待搜索的区域简化成一个个小方格,最终找到的路径就是一些小方格的组合。

核心公式

F = G + H

F - 方块的总移动代价

G - 开始点到当前方块的移动代价

H - 当前方块到结束点的预估移动代价

概述算法步骤

(1)将初始节点放入到open列表中。

(2)判断open列表。如果为空,则搜索失败。如果open列表中存在目标节点,则搜索成功。

(3)从open列表中取出F值最小的节点作为当前节点,并将其加入到close列表中。

(4)计算当前节点的相邻的所有可到达节点,生成一组子节点。对于每一个子节点:

如果该节点在close列表中,则丢弃它

如果该节点在open列表中,则检查其通过当前节点计算得到的F值是否更小,如果更小则更新其F值,并将其父节点设置为当前节点。

如果该节点不在open列表中,则将其加入到open列表,并计算F值,设置其父节点为当前节点。

(5)转到2步骤

进一步解释

F值是一个估计值,用F(n) = G(n) + H(n) 表示,其中G(n)表示由起点到节点n的预估消耗,H(n)表示节点n到终点的估计消耗。H(n)的计算方式有很多种,比如曼哈顿H(n) = x + y,或者欧几里得式H(n) = sqrt(x^2 + y^2)。本实例采用曼哈顿式。

4.A*寻路算法实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254

using System;
using System.Collections;
using System.Collections.Generic;
using System.Drawing;
using TMPro;
using UnityEngine;
using UnityEngine.PlayerLoop;
public enum nodeType { Walkable, Obstacle };
/// <summary>
/// 节点
/// </summary>
public class Node
{
//是否为障碍物
public nodeType nodetype;
//位置
public Vector2 pos;
//格子坐标
public int x, y;
//父节点
public Node parent;
//F=G+H
public int G, H;
public int F { get { return G + H; } }

public Node(nodeType nodetype, Vector2 pos, int x, int y)
{
this.nodetype = nodetype;
this.pos = pos;
this.x = x;
this.y = y;
}
public Node() { }
}
public class ASTAR : MonoBehaviour
{
public Vector2 origin;
public bool isMoving = true;
public float speed = 0.1f;
public float stopDistance = 0.1f;
public float updateTime = 1f;
public Vector2 target;

public List<Node> path = new List<Node>();
List<Node> openList = new List<Node>();
List<Node> closeList = new List<Node>();
//地图中心
public Vector2 mapCenter;
//高宽
public float height, width;
//墙体层级
public LayerMask WhatLayer;
// 节点半径
[Range(0.002f, 1f)]
public float NodeRadius = 0.2f;
public Node[,] nodes;
public bool arrive;
public int H_Manhattan(Node node, Node end)
{
return 10 * ((int)(Math.Abs(node.x - end.x)) + (int)(Math.Abs(node.y - end.y)));
}

/// <summary>
/// 初始化地图
/// </summary>
public void InitMap()
{
nodes = new Node[(int)(width / NodeRadius / 2), (int)(height / NodeRadius / 2)];
for (int i = 0; i < (int)(width / NodeRadius / 2); i++)
{
for (int j = 0; j < (int)(height / NodeRadius / 2); j++)
{
Vector2 center = new Vector2(mapCenter.x + NodeRadius + 2 * NodeRadius * (i - width / NodeRadius / 4),
mapCenter.y - NodeRadius + 2 * NodeRadius * (height / NodeRadius / 4 - j));
bool isWall = Physics2D.OverlapCircle(center, NodeRadius - 0.001f, WhatLayer);
nodes[i, j] = new Node(
isWall ? nodeType.Obstacle : nodeType.Walkable, center, i, j
);
}
}

}
public void FindPath(Vector2 startPos, Vector2 endPos)
{
if (startPos.x < mapCenter.x - width / 2 ||
startPos.x > mapCenter.x + width / 2 ||
startPos.y > mapCenter.y + height / 2 ||
startPos.y < mapCenter.y - height / 2 ||
endPos.x < mapCenter.x - width / 2 ||
endPos.x > mapCenter.x + width / 2 ||
endPos.y > mapCenter.y + height / 2 ||
endPos.y < mapCenter.y - height / 2)
{
path.Clear();
return;
}

Node start = getNode(startPos);

Node end = getNode(endPos);

if (end.nodetype == nodeType.Obstacle)
{
path.Clear();
return;
}
closeList.Clear();
openList.Clear();

start.parent = null; start.G = 0; start.H = H_Manhattan(start, end);
openList.Add(start);
for (int i = -1; i <= 1; i++)
{
for (int j = -1; j <= 1; j++)
{
// 如果是自己,则跳过
if (i == 0 && j == 0)
continue;
int g = (i * j) != 0 ? 14 : 10;
FindNearNode(start.x + i, start.y + j, g, start, end);
}
}
while (openList.Count > 0)
{
Node curnode = openList[0];
for (int i = 0; i < openList.Count; i++)
{
if (openList[i].F <= curnode.F && openList[i].H <= curnode.H)
curnode = openList[i];
}
openList.Remove(curnode);
closeList.Add(curnode);

if (curnode == end)
{
generatePath(start, end);
return;
}
for (int i = -1; i <= 1; i++)
{
for (int j = -1; j <= 1; j++)
{
// 如果是自己,则跳过
if (i == 0 && j == 0)
continue;
int g = (i * j) != 0 ? 14 : 10;
FindNearNode(curnode.x + i, curnode.y + j, g, curnode, end);
}
}
}
generatePath(start, end);
}
private void generatePath(Node start, Node end)
{
path.Clear();
if (end != null)
{
Node temp = end;
while (temp != start)
{
path.Add(temp);
temp = temp.parent;
}
path.Reverse();
}
}

public Node getNode(Vector2 pos)
{
Vector2 t;
t.x = (pos.x - mapCenter.x - NodeRadius) / (2 * NodeRadius) + width / NodeRadius / 4;
t.y = -((pos.y - mapCenter.y + NodeRadius) / (2 * NodeRadius) - height / NodeRadius / 4);

return nodes[(int)t.x, (int)t.y];
}
private void FindNearNode(int x, int y, int g, Node parent, Node end)
{
if (x < 0 || x >= (int)(width / NodeRadius / 2) ||
y < 0 || y >= (int)(height / NodeRadius / 2))
return;
Node node = nodes[x, y];
if (node == null ||
node.nodetype == nodeType.Obstacle ||
closeList.Contains(node) ||
openList.Contains(node))
return;
node.parent = parent;
node.G = parent.G + g;
node.H = H_Manhattan(node, end);
openList.Add(node);
}
IEnumerator Move()
{
int count = 0;
while (count < path.Count)
{
while (Vector2.Distance(path[count].pos, transform.position) > stopDistance)
{
transform.position = Vector3.Lerp(transform.position, path[count].pos, speed);
Vector3 temp = transform.localScale;
//右侧
if (transform.position.x > path[count].pos.x)
{
temp.x = -Math.Abs(temp.x);
}
else
{
temp.x = Math.Abs(temp.x);
}
transform.localScale = temp;
yield return null;
}
count++;
}
arrive = true;
}
public void startMove(Vector2 target)
{
if (path.Count == 0)
{
InitMap();
}
StopCoroutine("Move");
isMoving = true;
arrive = false;
FindPath(transform.position, target);
if (path.Count == 0)
{
stopMove();
}
else
{
this.target = target;
StartCoroutine("Move");
}
}
public void stopMove()
{
StopCoroutine("Move");
isMoving = false;
}
public void NodeChange(Vector2 vector,nodeType nodeType)
{
getNode(vector).nodetype = nodeType;
}
private void Start()
{
InitMap();
}
}