回答編集履歴
1
GetNeighboursの「自分自身」の判定条件を修正、コスト計算時の隣接ノード移動コストをユークリッド距離に変更
answer
CHANGED
|
@@ -1,10 +1,9 @@
|
|
|
1
|
-
ご提示のコードを[Wikipediaの記事](https://ja.wikipedia.org/wiki/A*#%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AE%E6%B5%81%E3%82%8C)と見比べてみたのですが、ご質問者さんの隣接ノードのコスト計算やオープンリストへの追加ルールに疑問を感じ、`
|
|
1
|
+
ご提示のコードを[Wikipediaの記事](https://ja.wikipedia.org/wiki/A*#%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AE%E6%B5%81%E3%82%8C)と見比べてみたのですが、ご質問者さんの隣接ノードのコスト計算やオープンリストへの追加ルールに疑問を感じ、`Pathfinding`と`GetNeighbours`を下記のように改変してみました。これならどうでしょうか?
|
|
2
2
|
|
|
3
3
|
```C#
|
|
4
4
|
using System.Collections;
|
|
5
5
|
using System.Collections.Generic;
|
|
6
6
|
using System.Linq;
|
|
7
|
-
using System.Runtime.ConstrainedExecution;
|
|
8
7
|
using UnityEngine;
|
|
9
8
|
|
|
10
9
|
public class Astar : MonoBehaviour
|
|
@@ -190,11 +189,13 @@
|
|
|
190
189
|
//隣接するNodeのコストを計算する
|
|
191
190
|
//SetCost(GetNeighbours(n), startNode, goalNode); // ここのSetCostは意図不明だったため削除
|
|
192
191
|
|
|
193
|
-
// neighbourのHコスト、Fコストを求め...
|
|
192
|
+
// neighbourのHコスト、Fコストを求め...
|
|
194
193
|
float neighbourH = GethCost(neighbour, goalNode);
|
|
195
|
-
float neighbourF = n.gCost +
|
|
194
|
+
float neighbourF = n.gCost + Vector2.Distance(n.pos, neighbour.pos) + neighbourH;
|
|
196
195
|
|
|
196
|
+
bool openListContainsNeighbour = openList.Contains(neighbour);
|
|
197
|
+
bool closeListContainsNeighbour = closeList.Contains(neighbour);
|
|
197
|
-
if ((!
|
|
198
|
+
if ((!openListContainsNeighbour && !closeListContainsNeighbour) || (neighbourF < neighbour.fCost))
|
|
198
199
|
{
|
|
199
200
|
// neighbourがオープン・クローズリストのいずれにも存在しない新しいノードの場合、または
|
|
200
201
|
// オープンまたはクローズリストにあり、かつ以前の探索で得られたものよりも小さいFコストが得られた場合、
|
|
@@ -203,8 +204,18 @@
|
|
|
203
204
|
neighbour.hCost = neighbourH;
|
|
204
205
|
neighbour.gCost = neighbour.fCost - neighbour.hCost;
|
|
205
206
|
neighbour.parent = n;
|
|
207
|
+
|
|
208
|
+
// クローズリストにあったノードなら、リストから削除することでクローズを取り消して...
|
|
209
|
+
if (closeListContainsNeighbour)
|
|
210
|
+
{
|
|
206
|
-
|
|
211
|
+
closeList.Remove(neighbour);
|
|
212
|
+
}
|
|
213
|
+
|
|
214
|
+
// オープンリストに未追加のノードなら、リストに追加して処理対象とする
|
|
215
|
+
if (!openListContainsNeighbour)
|
|
216
|
+
{
|
|
207
|
-
|
|
217
|
+
openList.Add(neighbour);
|
|
218
|
+
}
|
|
208
219
|
}
|
|
209
220
|
|
|
210
221
|
// 以降の部分は削除
|
|
@@ -232,17 +243,19 @@
|
|
|
232
243
|
n = n.parent;
|
|
233
244
|
}
|
|
234
245
|
|
|
235
|
-
|
|
246
|
+
parentList.Reverse();
|
|
236
247
|
}
|
|
237
248
|
}
|
|
238
249
|
public List<Node> GetNeighbours(Node node)
|
|
239
250
|
{
|
|
240
251
|
List<Node> neighbours = new List<Node>();
|
|
252
|
+
int nx = (int)node.pos.x;
|
|
253
|
+
int ny = (int)node.pos.y;
|
|
241
|
-
for (int i =
|
|
254
|
+
for (int i = nx - 1; i <= nx + 1; i++)
|
|
242
255
|
{
|
|
243
|
-
for (int j =
|
|
256
|
+
for (int j = ny - 1; j <= ny + 1; j++)
|
|
244
257
|
{
|
|
245
|
-
if (i ==
|
|
258
|
+
if (i == nx && j == ny)
|
|
246
259
|
{
|
|
247
260
|
// 自分自身は近傍ノードから除外する
|
|
248
261
|
continue;
|