Unity A*(A-Star)アルゴリズム 挙動がおかしくなる

Question

前提・実現したいこと

経路探索を正常に動作させたい

該当のソースコード

using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.ConstrainedExecution;
using UnityEngine;

public class Astar : MonoBehaviour
{
    public int map_Width = 10;
    public int map_Height = 10;
    public GameObject[] walls;
    public GameObject currenCell;
    public class Node
    {
        public Vector2 pos;
        //スタートからゴールまでの最短距離。gCost + hCost。
        public float fCost;
        //スタートからnノードまでの最短距離
        public float gCost;
        //nノードからゴールまでの最短距離
        public float hCost;
        public bool walkable;
        public Node parent;
    }
    /// <summary>
    /// スタートからnノードまでの最短距離
    /// </summary>
    public float GetgCost(Node startNode,Node nNode)
    {
        float distance = Vector3.Distance(startNode.pos, nNode.pos);
        return distance;
    }
    /// <summary>
    /// nノードからゴールまでの最短距離
    /// </summary>
    public float GethCost(Node nNode,Node goalNode)
    {
        float distance = Vector3.Distance(nNode.pos, goalNode.pos);
        return distance;
    }
    public void SetCost(List<Node> nodeList,Node startNode,Node goalNode)
    {
        foreach(Node item in nodeList)
        {
            item.gCost = GetgCost(startNode, item);
            item.hCost = GethCost(item, goalNode);
            item.fCost = item.gCost + item.hCost;
        }
    }
    public Node GetMinNode(List<Node> nodeList)
    {
        List<float> floatList = new List<float>();
        foreach(Node item in nodeList)
        {
            floatList.Add(item.fCost);
        }
        float min = floatList.Min();
        List<Node> minNodeList = new List<Node>();
        foreach(Node item in nodeList)
        {
            if(item.fCost == min)
            {
                minNodeList.Add(item);
            }
        }
        if(minNodeList.Count == 0)
        {
            return minNodeList[0];
        }
        else
        {
            List<float> hCostList = new List<float>();
            foreach(Node item in minNodeList)
            {
                hCostList.Add(item.hCost);
            }
            float minhCost = hCostList.Min();
            foreach(Node item in minNodeList)
            {
                if(item.hCost == minhCost)
                {
                    return item;
                }
            }
        }
        return null;
    }
    public Node startNode;
    public Node goalNode;
    public List<Node> wallNodeList = new List<Node>();
    public List<Node> allNodeList = new List<Node>();
    public void SetNode()
    {
        //すべてのノードをメモリに格納
        for (int x = 0; x < map_Width; x++)
        {
            for (int y = 0; y < map_Height; y++)
            {
                Node node = new Node();
                node.pos = new Vector2(x, y);
                node.walkable = true;
                allNodeList.Add(node);
            }
        }
    }
    public Node GetNode(int x,int y)
    {
        foreach(Node item in allNodeList)
        {
            if(item.pos.x == x && item.pos.y == y)
            {
                return item;
            }
        }
        return null;
    }
    public void SetWall()
    {
        List<Vector2> list = new List<Vector2>();
        for(int i = 0; i < walls.Length; i++)
        {
            list.Add(walls[i].transform.position);
        }
        foreach(Vector2 item in list)
        {
            Node node = GetNode((int)item.x, (int)item.y);
            if(node == null)
            {
                Debug.Log("OK");
            }
            node.walkable = false;
            wallNodeList.Add(node);
        }
    }

    //OpenリストとCloseリストを設定
    List<Node> openList = new List<Node>();
    List<Node> closeList = new List<Node>();

    List<Node> parentList = new List<Node>();

    public void Pathfinding()
    {
        SetNode();
        SetWall();
        //スタート位置とゴール位置を設定
        startNode = GetNode(0,0);
        goalNode = GetNode(2,5);
        openList.Add(startNode);
        while(openList.Count != 0)
        {
            //OpenListが空になったら解なし
            if(openList == null)
            {
                break;
            }
            //コストを設定
            SetCost(openList, startNode, goalNode);
            //OpenListからfCostが最小のノードnを取得
            Node n = GetMinNode(openList);
            openList.Remove(n);
            closeList.Add(n);
            if (n == goalNode)
            {
                break;
            }
            //ノードnの移動可能な方向を調べる
            foreach(Node neighbour in GetNeighbours(n))
            {
                //隣接するNodeのコストを計算する
                SetCost(GetNeighbours(n), startNode, goalNode);
                //検索したNodeをすべてOpenListに追加する
                openList.Add(neighbour);
                //すべての隣接するセルの親Nodeを設定する
                neighbour.parent = n;
                if (!parentList.Contains(neighbour.parent))
                {
                    parentList.Add(neighbour.parent);
                }
            }
        }
    }
    public List<Node> GetNeighbours(Node node)
    {
        List<Node> neighbours = new List<Node>();
        for(int i = (int)node.pos.x - 1;i <= (int)node.pos.x + 1; i++)
        {
            for (int j = (int)node.pos.y - 1; j <= (int)node.pos.y + 1; j++)
            {
                Node nei = GetNode(i, j);
                if(nei != null && nei.walkable == true && !openList.Contains(nei) && !closeList.Contains(nei))
                {
                    neighbours.Add(nei);
                }
            }
        }
        return neighbours;
    }
    private void Start()
    {
        Pathfinding();
        parentList.Add(goalNode);
        StartCoroutine(Move());
    }

    IEnumerator Move()
    {
        foreach(Node item in parentList)
        {
            currenCell.transform.position = item.pos;
            yield return new WaitForSeconds(0.5f);
        }
    }
}

試したこと

Unityで、色々なサイトを参考にしながら、A*アルゴリズムを実装しようとしたのですが、なぜか複雑な形状になると、挙動がおかしくなってしまいます。
どこにおかしくなる原因があるのか、分からなかったため、質問しました。

Answer 1

高速化について

GetNodeで一つ一つ座標を比較してノードを探したり、先の回答のコメントで申し上げたようにGetMinNodeで複雑そうな処理を行っていたりするのを何とかしようと思い、下記のようにしてみました。

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using UnityEngine;

public class ChessboardPathFinder
{
	private static readonly Vector2Int[] Directions =
	{
		new Vector2Int(-1, -1), // 南西
		new Vector2Int(-1, 0), // 西
		new Vector2Int(-1, 1), // 北西
		new Vector2Int(0, 1), // 北
		new Vector2Int(1, 1), // 北東
		new Vector2Int(1, 0), // 東
		new Vector2Int(1, -1), // 南東
		new Vector2Int(0, -1) // 南
	};

	private readonly Node[] world;
	private readonly List<Vector2Int> path = new List<Vector2Int>();

	public ChessboardPathFinder(int width, int height)
	{
		this.Path = this.path.AsReadOnly();
		this.Width = Mathf.Max(width, 1);
		this.Height = Mathf.Max(height, 1);
		this.world = new Node[this.Width * this.Height];
	}

	public int Width { get; }
	public int Height { get; }
	public ReadOnlyCollection<Vector2Int> Path { get; }

	public void SetWallPositions(IEnumerable<Vector2Int> positions)
	{
		this.RemoveAllWalls();
		if (positions == null)
		{
			return;
		}

		foreach (var position in positions)
		{
			if (this.IsInbound(position))
			{
				this.SetWall(position);
			}
		}
	}

	public bool FindPath(Vector2Int from, Vector2Int to)
	{
		// スタート位置・ゴール位置をワールド内にクランプする
		var minPosition = Vector2Int.zero;
		var maxPosition = new Vector2Int(this.Width - 1, this.Height - 1);
		var startPosition = Vector2Int.Min(Vector2Int.Max(from, minPosition), maxPosition);
		var goalPosition = Vector2Int.Min(Vector2Int.Max(to, minPosition), maxPosition);

		// 経路探索を実行する
		var pathFound = this.FindPathInternal(startPosition, goalPosition);
		
		// 経路が見つからなければpathには手を付けずfalseを返し...
		if (!pathFound)
		{
			return false;
		}

		// 見つかればpathを更新してtrueを返す
		this.path.Clear();
		var position = goalPosition;
		var directionIndex = this.GetParent(position);
		this.path.Add(position);
		while (directionIndex >= 0)
		{
			position += Directions[directionIndex];
			directionIndex = this.GetParent(position);
			this.path.Add(position);
		}

		this.path.Reverse();
		return true;
	}

	private bool FindPathInternal(Vector2Int startPosition, Vector2Int goalPosition)
	{
		// 経路が見つかったらこのフラグを立てる
		var pathFound = false;

		// ワールド全域を最大コストで埋める
		this.CleanWorld();

		// スタート地点のコストを設定し、オープンリストを作ってスタート地点を追加する
		this.SetGScore(startPosition, 0);
		this.SetState(startPosition, NodeState.Open);
		var openSet = new SortedSet<NodeAnchor> {new NodeAnchor(Distance(startPosition, goalPosition), startPosition)};

		// オープンリストが空になるまでループ
		while (openSet.Count > 0)
		{
			// オープンリストの中でFスコアが最小のノードを取得
			var current = openSet.Min;

			// そこがゴールなら経路発見フラグを立ててループを終了
			if (current.Position == goalPosition)
			{
				pathFound = true;
				break;
			}

			// オープンリストからcurrentを除去、クローズ状態に変える
			openSet.Remove(current);
			this.SetState(current.Position, NodeState.Closed);

			// 隣接ノードの評価はGスコアをもとに行うことにする
			// 隣接ノードへの移動コストは常に1と決め打ちし、そのため隣接ノード走査中に
			// いちいち計算する必要はなくなるので、ループ前に計算してしまう
			var tentativeGScore = this.GetGScore(current.Position) + 1;

			// 隣接8方向を調べる
			for (var i = 0; i < 8; i++)
			{
				var neighborPosition = current.Position - Directions[i];

				// ワールド範囲外だったり、壁だった場合はスキップ
				if (!this.IsInbound(neighborPosition) || this.GetWall(neighborPosition))
				{
					continue;
				}

				// クローズされていればスキップ
				// https://en.wikipedia.org/wiki/A*_search_algorithm によると、ヒューリスティック関数が無矛盾である場合は
				// いったんクローズされたノードまでの経路は最適であることが保証され、より小さいコストの経路が以降の探索で
				// 見つかることはないらしい...ということはスキップしても問題ないということか?
				var neighborState = this.GetState(neighborPosition);
				if (neighborState == NodeState.Closed)
				{
					continue;
				}

				// もし計算したGスコアがそれまでのGスコアより小さいなら...
				var previousGScore = this.GetGScore(neighborPosition);
				if (tentativeGScore < previousGScore)
				{
					// スコアを記録、親を設定する
					var neighborHScore = Distance(neighborPosition, goalPosition);
					this.SetGScore(neighborPosition, tentativeGScore);
					this.SetParent(neighborPosition, i);

					// もしこの隣接ノードがオープン状態なら、古いデータをオープンリストから削除する
					if (neighborState == NodeState.Open)
					{
						openSet.Remove(new NodeAnchor(previousGScore + neighborHScore, neighborPosition));
					}

					// この隣接ノードをオープン状態にして、オープンリストに追加する
					this.SetState(neighborPosition, NodeState.Open);
					openSet.Add(new NodeAnchor(tentativeGScore + neighborHScore, neighborPosition));
				}
			}
		}

		return pathFound;
	}

	private bool IsInbound(in Vector2Int position)
	{
		return (position.x >= 0) && (position.x < this.Width) && (position.y >= 0) && (position.y < this.Height);
	}

	private void SetGScore(in Vector2Int position, in int gScore)
	{
		this.world[(position.y * this.Width) + position.x].GScore = gScore;
	}

	private void SetParent(in Vector2Int position, in int parentDirectionIndex)
	{
		this.world[(position.y * this.Width) + position.x].ParentDirectionIndex = parentDirectionIndex;
	}

	private void SetState(in Vector2Int position, in NodeState state)
	{
		this.world[(position.y * this.Width) + position.x].State = state;
	}

	private void SetWall(in Vector2Int position, in bool wall = true)
	{
		this.world[(position.y * this.Width) + position.x].IsWall = wall;
	}

	private int GetGScore(in Vector2Int position)
	{
		return this.world[(position.y * this.Width) + position.x].GScore;
	}

	private int GetParent(in Vector2Int position)
	{
		return this.world[(position.y * this.Width) + position.x].ParentDirectionIndex;
	}

	private NodeState GetState(in Vector2Int position)
	{
		return this.world[(position.y * this.Width) + position.x].State;
	}

	private bool GetWall(in Vector2Int position)
	{
		return this.world[(position.y * this.Width) + position.x].IsWall;
	}

	// 2点間の距離としてチェビシェフ距離を使うことにする
	private static int Distance(Vector2Int a, Vector2Int b)
	{
		return Mathf.Max(Mathf.Abs(a.x - b.x), Mathf.Abs(a.y - b.y));
	}

	private void CleanWorld()
	{
		for (var i = 0; i < this.world.Length; i++)
		{
			this.world[i].GScore = int.MaxValue;
			this.world[i].ParentDirectionIndex = -1;
			this.world[i].State = NodeState.None;
		}
	}

	private void RemoveAllWalls()
	{
		for (var i = 0; i < this.world.Length; i++)
		{
			this.world[i].IsWall = false;
		}
	}

	private struct Node
	{
		public int GScore;
		public int ParentDirectionIndex;
		public NodeState State;
		public bool IsWall;
	}

	private enum NodeState
	{
		None,
		Open,
		Closed
	}

	private readonly struct NodeAnchor : IComparable<NodeAnchor>, IEquatable<NodeAnchor>
	{
		public readonly int FScore;
		public readonly Vector2Int Position;

		public NodeAnchor(int fScore, Vector2Int position)
		{
			this.FScore = fScore;
			this.Position = position;
		}

		public int CompareTo(NodeAnchor other)
		{
			var fResult = this.FScore.CompareTo(other.FScore);
			if (fResult != 0)
			{
				return fResult;
			}

			var yResult = this.Position.y.CompareTo(other.Position.y);
			if (yResult != 0)
			{
				return yResult;
			}

			return this.Position.x.CompareTo(other.Position.x);
		}

		public bool Equals(NodeAnchor other)
		{
			return (this.FScore == other.FScore) && this.Position.Equals(other.Position);
		}

		public override bool Equals(object obj)
		{
			return obj is NodeAnchor other && this.Equals(other);
		}

		public override int GetHashCode()
		{
			unchecked
			{
				return (this.FScore * 397) ^ this.Position.GetHashCode();
			}
		}
	}
}

任意のグラフ構造に対してA*経路探索を行えるような汎用的なものではなく、チェス盤のような縦横のマス目の上を8方向に移動させるということに特化した作りのためChessboardPathFinderというネーミングにしました。思考の整理のため経路探索機能だけを抜き出した形にしましたので、オブジェクトにアタッチするためのスクリプトは別途用意することになります。
ご質問者さんのAsterに沿った使用例としては、たとえば下記のようになるでしょう。

using System.Collections;
using System.Linq;
using UnityEngine;

public class Astar : MonoBehaviour
{
	public int map_Width = 10;
	public int map_Height = 10;
	public GameObject[] walls;
	public GameObject currenCell;

	ChessboardPathFinder pathFinder;
	
	void Start()
	{
		// スタート位置とゴール位置
		Vector2Int startPosition = new Vector2Int(0, 0);
		Vector2Int goalPosition = new Vector2Int(2, 5);

		// まずマップのサイズを決めてパスファインダーを生成する
		// マップのサイズが変わらない限り、経路探索のたびにパスファインダーを再生成する必要はない
		pathFinder = new ChessboardPathFinder(map_Width, map_Height);
		
		// 壁を設置して...
		pathFinder.SetWallPositions(walls.Select(
			g =>
			{
				Vector3 p = g.transform.position;
				return new Vector2Int(Mathf.RoundToInt(p.x), Mathf.RoundToInt(p.y));
			}));

		// どの点からどの点までの経路を探すかを引数で与えてFindPathを実行し、経路が見つかったかどうかを受け取る
		bool pathFound = pathFinder.FindPath(startPosition, goalPosition);

		// 経路が見つかったなら移動を行う
		if (pathFound)
		{
			StartCoroutine(Move());
		}
		else
		{
			Debug.LogError("Path not found.");
		}
	}

	IEnumerator Move()
	{
		// 経路が見つかった場合、パスファインダーのPathが更新されているので
		// そこから経路を取得できる
		foreach (Vector2Int position in pathFinder.Path)
		{
			currenCell.transform.position = new Vector3(position.x, position.y, 0.0f);
			yield return new WaitForSeconds(0.5f);
		}
	}
}

ChessboardPathFinderの中で核となる経路探索作業を担当する部分はFindPathInternalと名前を付けてFindPathメソッドから分離していますが、これはさらなる改造を加えることになった場合に備えての布石です。
おそらく現状でそれなりにスピードアップしているとは思うのですが、もしまだ遅くて支障が出るようでしたら「FindPathInternalを別スレッドで実行してメインスレッドを止めないようにする」といった手が使えるんじゃないかと思うのですが...

Comments

[退会済みユーザー]

回答していただき、ありがとうございました。

Answer 2

ご提示のコードをWikipediaの記事と見比べてみたのですが、ご質問者さんの隣接ノードのコスト計算やオープンリストへの追加ルールに疑問を感じ、PathfindingとGetNeighboursを下記のように改変してみました。これならどうでしょうか?

using System.Collections;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;

public class Astar : MonoBehaviour
{
    public int map_Width = 10;
    public int map_Height = 10;
    public GameObject[] walls;
    public GameObject currenCell;
    public class Node
    {
        public Vector2 pos;
        //スタートからゴールまでの最短距離。gCost + hCost。
        public float fCost;
        //スタートからnノードまでの最短距離
        public float gCost;
        //nノードからゴールまでの最短距離
        public float hCost;
        public bool walkable;
        public Node parent;
    }
    /// <summary>
    /// スタートからnノードまでの最短距離
    /// </summary>
    public float GetgCost(Node startNode, Node nNode)
    {
        float distance = Vector3.Distance(startNode.pos, nNode.pos);
        return distance;
    }
    /// <summary>
    /// nノードからゴールまでの最短距離
    /// </summary>
    public float GethCost(Node nNode, Node goalNode)
    {
        float distance = Vector3.Distance(nNode.pos, goalNode.pos);
        return distance;
    }
    public void SetCost(List<Node> nodeList, Node startNode, Node goalNode)
    {
        foreach (Node item in nodeList)
        {
            item.gCost = GetgCost(startNode, item);
            item.hCost = GethCost(item, goalNode);
            item.fCost = item.gCost + item.hCost;
        }
    }
    public Node GetMinNode(List<Node> nodeList)
    {
        List<float> floatList = new List<float>();
        foreach (Node item in nodeList)
        {
            floatList.Add(item.fCost);
        }
        float min = floatList.Min();
        List<Node> minNodeList = new List<Node>();
        foreach (Node item in nodeList)
        {
            if (item.fCost == min)
            {
                minNodeList.Add(item);
            }
        }
        if (minNodeList.Count == 0)
        {
            return minNodeList[0];
        }
        else
        {
            List<float> hCostList = new List<float>();
            foreach (Node item in minNodeList)
            {
                hCostList.Add(item.hCost);
            }
            float minhCost = hCostList.Min();
            foreach (Node item in minNodeList)
            {
                if (item.hCost == minhCost)
                {
                    return item;
                }
            }
        }
        return null;
    }
    public Node startNode;
    public Node goalNode;
    public List<Node> wallNodeList = new List<Node>();
    public List<Node> allNodeList = new List<Node>();
    public void SetNode()
    {
        //すべてのノードをメモリに格納
        for (int x = 0; x < map_Width; x++)
        {
            for (int y = 0; y < map_Height; y++)
            {
                Node node = new Node();
                node.pos = new Vector2(x, y);
                node.walkable = true;
                allNodeList.Add(node);
            }
        }
    }
    public Node GetNode(int x, int y)
    {
        foreach (Node item in allNodeList)
        {
            if (item.pos.x == x && item.pos.y == y)
            {
                return item;
            }
        }
        return null;
    }
    public void SetWall()
    {
        List<Vector2> list = new List<Vector2>();
        for (int i = 0; i < walls.Length; i++)
        {
            list.Add(walls[i].transform.position);
        }
        foreach (Vector2 item in list)
        {
            Node node = GetNode((int)item.x, (int)item.y);
            if (node == null)
            {
                Debug.Log("OK");
            }
            node.walkable = false;
            wallNodeList.Add(node);
        }
    }

    //OpenリストとCloseリストを設定
    List<Node> openList = new List<Node>();
    List<Node> closeList = new List<Node>();

    List<Node> parentList = new List<Node>();

    public void Pathfinding()
    {
        SetNode();
        SetWall();
        //スタート位置とゴール位置を設定
        startNode = GetNode(0, 0);
        goalNode = GetNode(2, 5);

        // スタートノードのコストを設定
        startNode.gCost = 0;
        startNode.hCost = GethCost(startNode, goalNode);
        startNode.fCost = startNode.gCost + startNode.hCost;
        startNode.parent = null;

        // ゴールが見つかったらこのフラグを立てることにする
        bool goalFound = false;

        openList.Clear();
        closeList.Clear();
        openList.Add(startNode);
        while (openList.Count != 0)
        {
            // openListがnullかどうか判定する意義はなさそうだったので削除
            /*
            //OpenListが空になったら解なし
            if (openList == null)
            {
                break;
            }
            */
            //コストを設定
            //SetCost(openList, startNode, goalNode); // ここのSetCostは意図不明だったため削除
            //OpenListからfCostが最小のノードnを取得
            Node n = GetMinNode(openList);
            openList.Remove(n);
            closeList.Add(n);
            if (n == goalNode)
            {
                // ゴールが見つかったので、フラグを立ててループを終える
                goalFound = true;
                break;
            }
            //ノードnの移動可能な方向を調べる
            foreach (Node neighbour in GetNeighbours(n))
            {
                //隣接するNodeのコストを計算する
                //SetCost(GetNeighbours(n), startNode, goalNode); // ここのSetCostは意図不明だったため削除

                // neighbourのHコスト、Fコストを求め...
                float neighbourH = GethCost(neighbour, goalNode);
                float neighbourF = n.gCost + Vector2.Distance(n.pos, neighbour.pos) + neighbourH;

                bool openListContainsNeighbour = openList.Contains(neighbour);
                bool closeListContainsNeighbour = closeList.Contains(neighbour);
                if ((!openListContainsNeighbour && !closeListContainsNeighbour) || (neighbourF < neighbour.fCost))
                {
                    // neighbourがオープン・クローズリストのいずれにも存在しない新しいノードの場合、または
                    // オープンまたはクローズリストにあり、かつ以前の探索で得られたものよりも小さいFコストが得られた場合、
                    // こちらの経路の方が優れていると考えられるため経路を更新する（つまりneighbourの親をnとする）
                    neighbour.fCost = neighbourF;
                    neighbour.hCost = neighbourH;
                    neighbour.gCost = neighbour.fCost - neighbour.hCost;
                    neighbour.parent = n;

                    // クローズリストにあったノードなら、リストから削除することでクローズを取り消して...
                    if (closeListContainsNeighbour)
                    {
                        closeList.Remove(neighbour);
                    }

                    // オープンリストに未追加のノードなら、リストに追加して処理対象とする
                    if (!openListContainsNeighbour)
                    {
                        openList.Add(neighbour);
                    }
                }

                // 以降の部分は削除
                /*
                //検索したNodeをすべてOpenListに追加する
                openList.Add(neighbour);
                //すべての隣接するセルの親Nodeを設定する
                neighbour.parent = n;
                if (!parentList.Contains(neighbour.parent))
                {
                    parentList.Add(neighbour.parent);
                }
                */
            }
        }

        parentList.Clear();
        if (goalFound)
        {
            // ゴールが見つかったなら、ゴールから親を辿ってparentListを作る
            Node n = goalNode;
            while (n != null)
            {
                parentList.Add(n);
                n = n.parent;
            }

            parentList.Reverse();
        }
    }
    public List<Node> GetNeighbours(Node node)
    {
        List<Node> neighbours = new List<Node>();
        int nx = (int)node.pos.x;
        int ny = (int)node.pos.y;
        for (int i = nx - 1; i <= nx + 1; i++)
        {
            for (int j = ny - 1; j <= ny + 1; j++)
            {
                if (i == nx && j == ny)
                {
                    // 自分自身は近傍ノードから除外する
                    continue;
                }
                Node nei = GetNode(i, j);
                // オープン・クローズリストに入っているかどうかはここでは判定しない
                if (nei != null && nei.walkable == true)// && !openList.Contains(nei) && !closeList.Contains(nei))
                {
                    neighbours.Add(nei);
                }
            }
        }
        return neighbours;
    }
    private void Start()
    {
        Pathfinding();
        parentList.Add(goalNode);
        StartCoroutine(Move());
    }

    IEnumerator Move()
    {
        foreach (Node item in parentList)
        {
            currenCell.transform.position = item.pos;
            yield return new WaitForSeconds(0.5f);
        }
    }
}

結局SetCostメソッドを使っていた部分は全部削除されてしまったため、SetCostメソッド自体を削除してしまってもいいでしょう。

Comments

[退会済みユーザー]

とても分かりやすいです。いつも回答していただき、ありがとうございます。

[Bongo]

お役に立てたようで幸いです。うまく動きましたら、それをさらに効率的になるよう改修していくのも面白いかと思います。

たとえば現状のGetMinNodeではコストが最小のノードを探すのにだいぶ手間のかかる方法をとっているようですが、回答中で言及しましたWikipediaの記事に出てくる「優先度付きキュー」（https://ja.wikipedia.org/wiki/%E5%84%AA%E5%85%88%E5%BA%A6%E4%BB%98%E3%81%8D%E3%82%AD%E3%83%A5%E3%83%BC ）を使ったり、その次の節で紹介されている「ノードにオープン/クローズ状態を表す情報を持たせる」といった手を使えばスピードアップが期待できそうです。

その他気になった点として、現状ではノード間の最短距離としてユークリッド距離（https://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E8%B7%9D%E9%9B%A2 ）を使っている様子ですが、もしキャラクターの移動がチェスのキングのように8方向に制限されるのならチェビシェフ距離（https://ja.wikipedia.org/wiki/%E3%83%81%E3%82%A7%E3%83%93%E3%82%B7%E3%82%A7%E3%83%95%E8%B7%9D%E9%9B%A2 ）を使った方が自然かもしれません。とはいえ、ユークリッド距離でもWikipediaの記事で言及されている「真のゴール距離 h*(n) を上回らない」という条件は満たしていると思いますので、得られる結果は適切な経路になってくれそうです。

[Bongo]

すみません！GetNeighboursの「自分自身は近傍ノードから除外する」とコメントを入れた部分ですが、あの条件では自分自身を除外できませんね。コードを修正版に差し替えます。うっかりしていました...

それと距離としてユークリッド距離を使うのならば、neighbourFを求める際に増加させるコストは1固定とするよりも、nとneighbourのユークリッド距離を使う方が妥当だろうと思い直しまして、併せて変更しました。

もし他にも妙な動きをしていたり、「ここのコードはおかしいんじゃないか」といったところを見つけましたらコメントいただければ修正してみます。

[退会済みユーザー]

経路探索をするとき、ＦＰＳがガクッと落ちて、ゲームが１０秒くらいフリーズしてしまうのですが、どのようにすればよいでしょうか？　マップのサイズが２００×２００で、複雑な地形になっているため、計算に時間がかかっているのだと思います。マップをいくつかのチャンク（塊）に分割して、計算はチャンクごとに行う、という方法を考えましたが、他にも良い方法があれば、教えていただきたいです。

[Bongo]

スピードアップ案を検討してみました。字数制限のため別回答になってしまいますがご容赦ください...

さらに高速化するとなると、高速化というよりもむしろゲームをフリーズさせないことが主眼になりますが、回答中の末尾で申し上げたように非同期化してメインの処理を妨害しないようにする手があるかと思います。
やはり経路探索は高コストな処理ですから、たとえばNavMeshAgentだとかも目的地を設定した直後に経路を利用可能になるとは限らず、pathPendingを見て探索が完了したか確認するような方式になっていますね。ですが経路探索中でもフリーズせず、他のスクリプトがちゃんと動くのでストレスを感じにくいと思います。

ご質問者さんのおっしゃるような分割案が有効な場面もあると思います。たとえばローグ（https://ja.wikipedia.org/wiki/%E3%83%AD%E3%83%BC%E3%82%B0 ）みたいに小部屋が通路で接続されたようなマップを持つゲームでしたら、マップ全体をタイル単位で経路探索しなくても、まず通路の交差点や小部屋をノードとするグラフ構造について探索を行うことで目的オブジェクトのある部屋までの経路を求め、部屋に着いたら目的オブジェクトへ向かって詳細な経路探索を行う...といった多段階の探索方法が使えるかもしれません。

Answer 3

最短経路を求めたいなら Start から Goal に Start -> a -> b -> c -> Goal というパスがあったときに、Start -> a のコスト、 a -> b のコスト、 b -> c のコスト...とすべて求めていく必要があるわけです。しかし今のコードを見る限り、それぞれのノードについてスタートからのコストとゴールまでのコストを求めてるだけです。これでは無理です。