A* Pathfinding Project Asset - Grid Graph에서 갈 수 없는 노드 체크하기

현재 진행 중인 프로젝트에서 A* Pathfinding Project 에셋을 이용하여 유닛으로 부터 특정 범위 안에서 클릭한 목적지로 이동하도록 구현을 하고 있습니다.

 

https://arongranberg.com/astar/

A* Pathfinding Project

 

여기서 요구되는 기능이 만약 클릭한 destination이 

 

AstarPath의 maxNearestNodeDistance는 온전히 Seeker의 node로부터 얼마나 떨어진 거리까지 search할 수 있는가를 의미하므로 용도에 적합하지 않았습니다.

 

 

분명 PathUtilities.BFS를 이용하여 위와 같은 그래프에서 울타리(?) 안쪽 부분과 바깥 부분을 각각 찍어봤을 때, 반환되는 List<GraphNode>로 봤을 때는 BFS로 탐색한 결과 리스트를 잘 반환하길래

GraphNode node1 =
	m_AstarPath.GetNearest(SelectedUnit.transform.position).node;
GraphNode node2 = 
	m_AstarPath.GetNearest(click_block.transform.position).node;

if (PathUtilities.BFS(node2, 100).Contains(node1))
{
	Debug.LogError("포함");
}
	else Debug.LogError("미포함");

위와 같은 코드로 테스트를 했는데 로그가 미포함이 찍혔습니다... 

왜 그런가 싶어 IDE로 디버그를 돌려보니 아니나 다를까 제가 유닛이 위치한 노드는 Graph Scan시 unwalkable Node로 나온다는 사실을 깜박하고 있었던 문제였어요.

 

위 사진을 예로 들자면 세로로 6칸이기에 각 인덱스를 445~450이라고 한다면 node1에서는 유닛이 위치한 인덱스 449가 나왔지만 BFS로 탐색한 울타리 내의 노드들에는 449를 제외한 walkable node인 445, 446, 447, 448, 450만이 있더군요.

 

물론 프로젝트에서 유닛이 위치한 노드는 갈 수 없는 지형으로 하는 것이 맞습니다. (다른 유닛이 막고있는 것을 밀어버리고 가버릴 순 없기에...)

단지 유닛이 위치한 노드에서 가장 가까운 walkable node를 찾아서 그 노드가 BFS 상 탐지된 리스트 안에 포함되는지 확인해야겠군요.

 

제가 한 방법은 unwalkable node인 node1의 상하좌우 노드의 그래프 상 좌표를 구하였고, 구한 4방향의 좌표 중 destination node좌표로부터 BFS로 탐색한 위치에 포함되는 것이 있으면 이동할 수 있는 경로 인지시키는 방법으로 진행하였습니다.

 

사용하였던 코드는 아래와 같습니다.

GraphNode node1 = m_AstarPath.GetNearest(SelectedUnit.transform.position).node;
GraphNode node2 = m_AstarPath.GetNearest(click_block.transform.position).node;
List<GraphNode> destinationBFS = PathUtilities.BFS(node2, 100);
List<GraphNode> surroundNodes = new List<GraphNode>();
List<List<int>> xz = new List<List<int>>
{
    new List<int>{1,0},
    new List<int>{0,1},
    new List<int>{-1,0},
    new List<int>{0,-1},
};
foreach (var _xz in xz)
    surroundNodes.Add(m_AstarPath.data.gridGraph.GetNode(
        ((GridNode)node1).XCoordinateInGrid + _xz[0],
        ((GridNode)node1).ZCoordinateInGrid + _xz[1]));
surroundNodes = surroundNodes.Where(node => destinationBFS.Contains(node)).ToList();
if (surroundNodes.Count > 0)
{
    Debug.LogError("포함");
}
    else Debug.LogError("미포함");

GraphNode가 아니라 GridNode란 클래스가 있어서 보니, GraphNode를 상속받고 있는 하위개념의 클래스더군요. 그래서 그냥 다형성으로 처리해주었습니다.

 

위와 같이 진행하고 나니

안쪽을 목적지로 했을 때

바깥쪽을 목적지로 했을 때

제대로 나오지만 바깥쪽(유닛이 이동할 수 없는 곳)을 목적지로 하여서 갈 수 없는 경우 이동하지 못하도록 설정해주어야 겠군요.