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
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351 | using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class PathNode
{
// 길찾기용 맵 데이터 좌표 X,Z 이다. 그러나 실제 월드 블록 배열 X,Z 평면값과 동일한 의미로 쓰이기도 하니,
// 이 값을 실제 길을 찾아가는 오브젝트가 월드 좌표 (x, z)값으로 사용 가능하다.
private int _pathMapDataX;
public int pathMapDataX
{
set { _pathMapDataX = value; }
get { return _pathMapDataX; }
}
private int _pathMapDataY;
public int pathMapDataY
{
set { _pathMapDataY = value; }
get { return _pathMapDataY; }
}
private int _worldCoordY;
public int worldCoordY
{
set { _worldCoordY = value; }
get { return _worldCoordY; }
}
private bool _isJumped;
public bool isJumped
{
set { _isJumped = value; }
get { return _isJumped; }
}
private PathNode _parentNode;
public PathNode parentNode
{
set { _parentNode = value; }
get { return _parentNode; }
}
private bool _isGoalNode;
public bool isGoalNode
{
set { _isGoalNode = value; }
get { return _isGoalNode; }
}
private int _gValue;
public int gValue
{
get { return _gValue; }
}
public void Calc_G_Value()
{
if (_parentNode == null)
{
_gValue = 0;
return;
}
int x = _pathMapDataX - _parentNode.pathMapDataX;
int y = _pathMapDataY - _parentNode.pathMapDataY;
int absX = 0;
int absY = 0;
// 대각선 이동.
if (((x == -1) && (y == 1))
|| ((x == 1) && (y == 1))
|| ((x == -1) && (y == -1))
|| ((x == 1) && (y == -1)))
{
absX = Mathf.Abs(x);
absY = Mathf.Abs(y);
_gValue = (absX + absY) * 14 + _parentNode.gValue;
}
else
{
absX = Mathf.Abs(x);
absY = Mathf.Abs(y);
_gValue = (absX + absY) * 10 + _parentNode.gValue;
}
}
private int _hValue;
public int hValue
{
get { return _hValue; }
}
// 대각선 이동, 장애물들을 모두 무시한채 목표지점간의 x, y 이동값에 대한 결과를 구한다.
public void Calc_H_Value(PathNode goal)
{
int x = Mathf.Abs(goal.pathMapDataX - _pathMapDataX);
int y = Mathf.Abs(goal.pathMapDataY - _pathMapDataY);
_hValue = (x + y) * 10;
}
}
public class Astar : MonoBehaviour
{
private int MAP_SIZE_X = 4;
private int MAP_SIZE_Y = 4;
private PathNode[,] pathFindMapData;
private List<PathNode> openList = new List<PathNode>();
private List<PathNode> closedList = new List<PathNode>();
private List<Vector2> eightDir = new List<Vector2>();
private PathNode curNode;
private PathNode goalNode;
private Transform moveObject;
private Stack<PathNode> navigatePath = new Stack<PathNode>();
public Astar(Transform _moveObject, int mapSizeX, int mapSizeY)
{
MAP_SIZE_X = mapSizeX;
MAP_SIZE_Y = mapSizeY;
pathFindMapData = new PathNode[MAP_SIZE_X, MAP_SIZE_Y];
for (int x = 0; x < MAP_SIZE_X; x++)
for (int y = 0; y < MAP_SIZE_Y; y++)
{
pathFindMapData[x, y] = new PathNode();
pathFindMapData[x, y].pathMapDataX = x;
pathFindMapData[x, y].pathMapDataY = y;
pathFindMapData[x, y].parentNode = null;
pathFindMapData[x, y].isGoalNode = false;
}
moveObject = _moveObject;
InitEightDir();
}
private void ExtractNavigatePath()
{
PathNode path = goalNode;
while (path.parentNode != null)
{
navigatePath.Push(path);
path = path.parentNode;
}
}
private void InitData()
{
openList.Clear();
closedList.Clear();
navigatePath.Clear();
InitPathFindMapData();
}
public Stack<PathNode> PathFinding()
{
InitData();
SetStartPathNode();
while ((openList.Count != 0) && (!IsGoalInOpenList()))
{
SetOpenList();
PathNode selectNode = SelectLowCostPath();
if (selectNode != null) SearchAdjacentNodes(selectNode);
}
ExtractNavigatePath();
// Stack<T> 의 복사 생성자는 오리지널의 스택 순서에서 반대로 카피를 한다.
// # 1 : https://msdn.microsoft.com/en-us/library/76atxd68(v=vs.110).aspx
// # 2 : http://stackoverflow.com/questions/7391348/c-sharp-clone-a-stack
return new Stack<PathNode>(navigatePath);
}
private void SetStartPathNode()
{
int x = Mathf.RoundToInt(moveObject.position.x);
int y = Mathf.RoundToInt(moveObject.position.y);
curNode = pathFindMapData[x, y];
curNode.parentNode = null;
curNode.Calc_H_Value(goalNode);
curNode.Calc_G_Value();
openList.Add(curNode);
}
/// <summary>
/// 길찾기 시작전에 반드시 호출되어야 하는 함수.
/// 목표위치 노드를 지정해야 합니다.
/// </summary>
public void SetGoalPathNode(int worldCoordX, int worldCoordY)
{
goalNode = pathFindMapData[worldCoordX, worldCoordY];
goalNode.isGoalNode = true;
}
/// <summary>
/// 길찾기에 이용되는 맵정보 배열을 초기화 합니다.
/// 실제 월드 블록 배열의 XY평면의 범위값을 이용해 맵 정보 배열을 순회.
/// </summary>
private void InitPathFindMapData()
{
for (int x = 0; x < MAP_SIZE_X; x++)
for (int y = 0; y < MAP_SIZE_Y; y++)
{
pathFindMapData[x, y].pathMapDataX = x;
pathFindMapData[x, y].pathMapDataY = y;
pathFindMapData[x, y].worldCoordY = 0;
pathFindMapData[x, y].parentNode = null;
pathFindMapData[x, y].isGoalNode = false;
pathFindMapData[x, y].isJumped = false;
}
}
private void SearchAdjacentNodes(PathNode selectNode)
{
foreach (Vector2 pos in eightDir)
{
int searchPosX = selectNode.pathMapDataX + (int)pos.x;
int searchPosY = selectNode.pathMapDataY + (int)pos.y;
if ((searchPosX >= 0 && searchPosX < MAP_SIZE_X) && (searchPosY >= 0 && searchPosY < MAP_SIZE_Y))
{
if (!IsInClosedList(searchPosX, searchPosY))
{
if (!IsInOpenList(searchPosX, searchPosY))
{
openList.Add(pathFindMapData[searchPosX, searchPosY]);
pathFindMapData[searchPosX, searchPosY].parentNode = curNode;
pathFindMapData[searchPosX, searchPosY].Calc_H_Value(goalNode);
pathFindMapData[searchPosX, searchPosY].Calc_G_Value();
}
else
{
if ((pathFindMapData[searchPosX, searchPosY].gValue < selectNode.gValue))
{
selectNode.parentNode = pathFindMapData[searchPosX, searchPosY];
selectNode.Calc_H_Value(goalNode);
selectNode.Calc_G_Value();
}
}
}
}
}
}
private PathNode SelectLowCostPath()
{
int minCost = 0;
PathNode lowCostPath = null;
if (openList.Count > 0)
{
minCost = openList[0].gValue + openList[0].hValue;
lowCostPath = openList[0];
for (int i = 1; i < openList.Count; i++)
{
int cost = openList[i].gValue + openList[i].hValue;
if (minCost > cost)
{
minCost = cost;
lowCostPath = openList[i];
}
}
openList.Remove(lowCostPath);
closedList.Add(lowCostPath);
curNode = lowCostPath;
}
return lowCostPath;
}
private void SetOpenList()
{
foreach (Vector2 pos in eightDir)
{
int searchPosX = curNode.pathMapDataX + (int)pos.x;
int searchPosY = curNode.pathMapDataY + (int)pos.y;
if ((searchPosX >= 0 && searchPosX < MAP_SIZE_X) && (searchPosY >= 0 && searchPosY < MAP_SIZE_Y))
{
if ((!IsInClosedList(searchPosX, searchPosY)) && (!IsInOpenList(searchPosX, searchPosY)))
{
pathFindMapData[searchPosX, searchPosY].parentNode = curNode;
pathFindMapData[searchPosX, searchPosY].Calc_H_Value(goalNode);
pathFindMapData[searchPosX, searchPosY].Calc_G_Value();
openList.Add(pathFindMapData[searchPosX, searchPosY]);
}
}
}
CurNodeToClosedList();
}
private bool IsInClosedList(int searchPosX, int searchPosY)
{
return (closedList.Exists((PathNode p) =>
{
if ((p.pathMapDataX == searchPosX)
&& (p.pathMapDataY == searchPosY))
{
return true;
}
return false;
}));
}
private bool IsInOpenList(int searchPosX, int searchPosY)
{
return (openList.Exists((PathNode p) =>
{
if ((p.pathMapDataX == searchPosX)
&& (p.pathMapDataY == searchPosY))
{
return true;
}
return false;
}));
}
private bool IsGoalInOpenList()
{
return (openList.Exists((PathNode p) =>
{
if (p.isGoalNode)
{
return true;
}
return false;
}));
}
private void CurNodeToClosedList()
{
closedList.Add(curNode);
openList.Remove(curNode);
}
private void InitEightDir()
{
Vector2 north = new Vector2(0, 1);
Vector2 south = new Vector2(0, -1);
Vector2 west = new Vector2(-1, 0);
Vector2 east = new Vector2(1, 0);
Vector2 northWest = new Vector2(-1, 1);
Vector2 northEast = new Vector2(1, 1);
Vector2 southWest = new Vector2(-1, -1);
Vector2 southEast = new Vector2(1, -1);
eightDir.Add(north);
eightDir.Add(south);
eightDir.Add(west);
eightDir.Add(east);
eightDir.Add(northWest);
eightDir.Add(northEast);
eightDir.Add(southWest);
eightDir.Add(southEast);
}
}
|
