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
|
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class AStarPathfinder
{
public const int Straight_Cost = 10;
public const int Diagonal_Cost = 14;
private int mapWidth;
private int mapHeight;
/// <summary>
/// 默认地图左下角坐标为(0,0)，分别由(x,y)表示，x向右为正，y向上为正
/// </summary>
private AStarNode[,] nodes;
public AStarPathfinder(int mapWidth, int mapHeight) {
this.mapWidth = mapWidth;
this.mapHeight = mapHeight;
nodes = new AStarNode[mapWidth, mapHeight];
//x必须对应mapWidth, y必须对应mapHeight, 此处按列遍历
for (int x = 0; x < mapWidth; x++) {
for (int y = 0; y < mapHeight; y++) {
nodes[x, y] = new AStarNode(new IntVector2(x, y), true);
}
}
}
private List<AStarNode> GetNeighbours(AStarNode node) {
List<AStarNode> list = new List<AStarNode> ();
for (int i = -1; i <= 1; i++) {
for (int j = -1; j <= 1; j++) {
// 如果是自己，则跳过
if (i == 0 && j == 0)
continue;
int x = node.index.x + i;
int y = node.index.y + j;
// 判断是否越界
if (x < mapWidth && x >= 0 && y < mapHeight && y >= 0) {
list.Add (nodes[x, y]);
}
}
}
return list;
}
private bool CanWalkToNeighbour (AStarNode current, AStarNode neighbour) {
//斜向行走，被夹住时不允许穿越
if (current.index.x != neighbour.index.x && current.index.y != neighbour.index.y) {
if (!nodes [current.index.x, neighbour.index.y].walkable
&& !nodes [neighbour.index.x, current.index.y].walkable) {
return false;
}
}
return neighbour.walkable;
}
private int GetNodeDistance(AStarNode a, AStarNode b) {
int dx = Mathf.Abs (a.index.x - b.index.x);
int dy = Mathf.Abs (a.index.y - b.index.y);
// 斜方向，判断到底是那个轴相差的距离更远
int totalCost = 0;
if (dx > dy) {
totalCost = Diagonal_Cost * dy + Straight_Cost * (dx - dy);
} else {
totalCost = Diagonal_Cost * dx + Straight_Cost * (dy - dx);
}
return totalCost;
}
public void SetWalkable (IntVector2 point, bool walkable) {
if (point.x >= 0 && point.x < mapWidth && point.y >= 0 && point.y < mapHeight) {
nodes [point.x, point.y].walkable = walkable;
}
}
public List<IntVector2> FindPath(IntVector2 startPoint, IntVector2 endPoint) {
AStarNode startNode = nodes[startPoint.x, startPoint.y];
AStarNode endNode = nodes[endPoint.x, endPoint.y];
List<AStarNode> openList = new List<AStarNode> ();
List<AStarNode> closedList = new List<AStarNode> ();
openList.Add (startNode);
while (openList.Count > 0) {
//如果是优先级队列，就不需要从open列表中查找最优节点
AStarNode currentNode = openList[0];
for (int i = 0; i < openList.Count; i++) {
if (openList[i].fCost <= currentNode.fCost && openList[i].hCost < currentNode.hCost) {
currentNode = openList[i];
}
}
//先移出最优节点
openList.Remove(currentNode);
closedList.Add(currentNode);
//找到目标
if (currentNode == endNode) {
return GetPath (startNode, endNode);
}
//判断周围节点，选择一个最优节点
foreach (var item in GetNeighbours(currentNode)) {
//如果不可走或者已经在关闭列表中
if (!CanWalkToNeighbour(currentNode, item) || closedList.Contains(item))
continue;
//计算与开始节点的距离
int newCost = currentNode.gCost + GetNodeDistance(currentNode, item);
//如果距离更小，或者不在开始列表中
if (newCost < item.gCost || !openList.Contains(item)) {
item.gCost = newCost;
item.hCost = GetNodeDistance(item, endNode);
item.parentNode = currentNode;
if (!openList.Contains(item)) {
openList.Add(item);
}
}
}
}
return GetPath (startNode, null);
}
private List<IntVector2> GetPath(AStarNode startNode, AStarNode endNode) {
List<IntVector2> path = new List<IntVector2>();
if (endNode != null) {
AStarNode temp = endNode;
while (temp != startNode) {
path.Add (temp.index);
temp = temp.parentNode;
}
path.Reverse ();
}
return path;
}
private class AStarNode
{
public AStarNode parentNode;
public IntVector2 index;
public bool walkable;
public int gCost;
public int hCost;
public int fCost { get { return gCost + hCost; } }
public AStarNode(IntVector2 index, bool walkable) {
this.index = index;
this.walkable = walkable;
}
}
}
public struct IntVector2
{
public int x;
public int y;
public IntVector2(int x, int y) {
this.x = x;
this.y = y;
}
}
|