저번에는 Behavior Tree 를 사용해서 간단한 적을 구현해봤습니다.
이번 목표는 길찾기 알고리즘을 통해서 던전 안에서 움직이는 적을 만들어 보겠습니다.
길찾기 알고리즘이라 하면 A* 알고리즘이 가장 먼저 떠오릅니다.
개요
A* 알고리즘에 대해서는 이 링크를 보시면 잘 설명되어 있습니다.
시작 위치부터 주변의 모든 칸들을 전부 검사하고 총 예상 비용을 비교해서 가장 빠른 길을 찾습니다.
여기서, 총 예상 비용을 구할 때 휴리스틱이라는 개념이 사용됩니다.
휴리스틱
휴리스틱이란 어림짐작으로 문제를 해결하는 것을 말합니다.
휴리스틱을 이용한 총 예상 비용은 다음과 같습니다.
총 예상 비용 f(n) = 시작점 부터 해당 위치까지의 거리 g(n) + 목적지까지 거리의 추정치 h(n)
길을 찾아다니고 있는 와중에는 목적지까지의 거리를 정확히 알 수 없습니다.
따라서, 추정치를 아래 그림과 같이 구합니다.
1.414를 float 자료형으로 계산하면 복잡해질 수 있습니다.
따라서, 각각 10을 곱한 10과 14를 사용하여 벽을 무시하고 직선과 대각선의 비용을 구합니다.
A* 알고리즘은 게임에 보편적으로 사용되는 길찾기 알고리즘으로 알려져 있지만, 주변의 모든 칸을 전부 검사하기 때문에, 맵이 넓다면 실행 시간이 늦어질 수 있습니다.
이보다 더 빠르게 길을 찾기 위해서 사용하는 알고리즘이 JPS 알고리즘 입니다.
JPS Algorithm
JPS(Jump Point Search) 알고리즘의 동작 방식은 A* 알고리즘과 유사합니다.
하지만, 주변 모든 칸을 전부 확인하는 A* 알고리즘과 다르게 JPS는 장애물의 코너를 기준으로 검사하여, 한 칸씩 이동하는게 아니라 점프를 하기 때문에 붙여진 이름입니다.
아래 그림을 보겠습니다.
시작점인 빨간색 점 부터 도착점인 파란색 점까지 최소비용으로 가기위한 길을 초록색으로 그렸습니다.
장애물을 피해서 최단거리로 도착점에 도달하기 위해서는 빨간색 원으로 표시한 부분을 지나가야 합니다.
어떻게 적절한 코너를 찾을 수 있는지 알아보겠습니다.
알고리즘
일단, 변수부터 설명드리겠습니다.
openList는 우선순위 큐로, 목적지까지의 예상 비용이 가장 적은 노드를 뽑기에 용이합니다.
closedList는 사용될 수 있지만 이미 탐색이 끝난 노드들을 넣고 중복 탐색을 방지합니다.
closedList에 있는 각 노드들은 자식 노드들의 .parent 로만 접근합니다.
우선, 시작 노드를 openList 에 넣은 후에 openList 가 빌 때까지 아래 항목들을 반복합니다.
-
openList에서 예상 비용이 가장 적은 노드를 ClosedList에 넣고 가져옵니다. -
직선 탐색
Forced Neighbor를 찾으며 벽이나 목적지를 찾을때까지 진행합니다.
Forced Neighbor를 찾으면openList에 넣습니다.
-
대각선 탐색
Forced Neighbor를 찾으며 진행합니다. 만약 해당 칸에서 Forced Neighbor를 찾지못할 경우, 보조 탐색을 진행합니다.
직선 탐색과 동일하게, 발견하면openList에 넣습니다. -
보조 탐색
예를 들어, 위-오른쪽을 향하는 대각선의 경우, 해당 위치에서부터 위, 오른쪽 직선 탐색을 각각 실행합니다.
각 탐색을 어떻게 적용하는지 위의 예시를 구체화 해봤습니다.
우선 코드로 구현하기 전에 핵심적인 개념 두 가지를 먼저 알아보겠습니다.
Pruning
Node x is currently being expanded. The arrow indicates the direction of travel from its parent, either straight or diagonal. In both cases we can immediately prune all grey neighbours as these can be reached optimally from the parent of x without ever going through node x.
-harablog
Pruning, 즉 가지치기를 통해 연산을 줄이는 것이 중요합니다.
직선과 대각선을 따로 확인해보겠습니다.
오른쪽 위를 탐색한다고 가정했을 때, 보조탐색도 같이 진행하기 때문에 벽이 없다면 시작 노드를 기준으로 한 사분면에 해당하는 부분을 탐색할 수 있습니다.
이 때, 직선 탐색과 보조 탐색을 살펴보겠습니다.
A* 알고리즘은 한 노드에서 주변 노드의 휴리스틱을 전부 계산해서 그 중 최솟값을 찾는데,
JPS 알고리즘 에서는 보조탐색에 의해 위/아래가 전부 탐색되기 때문에 직선 및 보조 탐색은 벽이 나오기 전까지 1자로 탐색하기만 하면 됩니다.
이렇게 부모로부터 도달하는게 최적인 부분들 ( 위의 사진의 회색부분 ) 을 탐색하지 않는 것을 가지치기라 합니다.
당연한 얘기같지만, 벽이 나오게 되면 다르게 처리를 해주어야 합니다.
Forced Neighbor
In the Jump Point Search paper, this is is called a forced neighbor because we’re forced to consider it when we would have otherwise ignored it.
-zerowidth positive lookahead
Forced Neighbor 는 어떻게 구하는지 알아보겠습니다.
먼저, 직선의 경우입니다.
오른쪽 직선 탐색을 하고있다고 할 때 위에 벽이 있다면, 벽 뒤의 빈 부분은 직선/보조 탐색이 탐색하지 못합니다. 따라서, 바로 위에 벽이 있고 오른쪽 위에 이동 가능한 빈 칸이 있다면 그 곳을 Forced Neightbor 라고 간주하고 그곳을 탐색해야 합니다.
이 때 탐색은 대각선 탐색으로 해야 벽 뒤를 확실하게 검사할 수 있습니다.
대각선의 경우를 보겠습니다.
위쪽 보조 탐색은 벽이 없기 때문에 정상적으로 실행되지만, 오른쪽은 벽떄문에 막혀서 탐색하지 못합니다. 이런 경우에 직선과 같이 오른쪽 아래 방향을 대각선 탐색 해주어야 합니다.
혹시라도, 이해가 아직 되지 않으신다면 이 링크 에서 JPS 알고리즘을 사용해볼 수 있으니 감 잡으시는데 도움이 되시길 바랍니다.
구현
public List<Vector2Int> PathFind(Vector2Int sp, Vector2Int ep)
{
// Initialize
// ...
// Exception Handling
// ...
// 시작점
AddToOpenList(new JPSNode(null, startPoint, JPSDir.None, 0, CalcHeuri(startPoint, endPoint)));
while (openList.Count > 0)
{
JPSNode curNode = openList.First();
closedList.Add(curNode);
openList.Remove(curNode);
// 목적지를 찾은 경우
if (curNode.pos.x == endPoint.x && curNode.pos.y == endPoint.y)
{
while (curNode != null)
{
ans.Add(new Vector2Int(curNode.pos.x, curNode.pos.y));
curNode = curNode.parent;
}
ans.Reverse();
return ans;
}
// 시작점은 8방향 전부 검사
if (curNode.dir == JPSDir.None)
{
SearchLine(curNode, curNode.pos, JPSDir.Up);
SearchLine(curNode, curNode.pos, JPSDir.Right);
SearchLine(curNode, curNode.pos, JPSDir.Left);
SearchLine(curNode, curNode.pos, JPSDir.Down);
SearchLine(curNode, curNode.pos, JPSDir.UpRight);
SearchLine(curNode, curNode.pos, JPSDir.UpLeft);
SearchLine(curNode, curNode.pos, JPSDir.DownRight);
SearchLine(curNode, curNode.pos, JPSDir.DownLeft);
}
else
SearchLine(curNode, curNode.pos, curNode.dir);
}
// 목적지를 못찾은 경우 빈 List 반환
return new List<Vector2Int>();
}전체적인 알고리즘은 이렇습니다.
위에서 설명한 대로, 첫 시작점을 openList 에 넣고 리스트가 비거나 목적지를 찾을때까지 반복합니다.
JPSNode 는 부모, 방향, 위치, 걸린 비용, 걸릴 비용을 가지는 클래스입니다.
그 외의 기본적인 연산 함수들은 생략했습니다.
이제 각 함수를 확인해보겠습니다.
SearchLine
private bool SearchLine(JPSNode parentNode, Vector2Int pos, JPSDir dir)
{
//
// ...
//
case JPSDir.Right:
for (int i = pos.x + 1; i < map.GetLength(0); i++)
{
checkPoint = pos + new Vector2Int(i - pos.x, 0);
check = JPCheck(parentNode, checkPoint, dir, out destDir);
if (check == 1)
{
AddToOpenList(new JPSNode(parentNode, checkPoint, destDir, parentNode.GetPassedCost() + CalcHeuri(parentNode.pos, checkPoint), CalcHeuri(checkPoint, endPoint)));
return true;
}
else if (check == -1) return false;
}
break;
//
// other straight cases
// ...
case JPSDir.UpRight:
SecondarySearch(parentNode, pos, JPSDir.Up, JPSDir.Right);
for (int i = 1; ; i++)
{
checkPoint = pos + new Vector2Int(i, i);
check = JPCheck(parentNode, checkPoint, dir, out destDir);
if (check == 1)
{
found = true;
AddToOpenList(new JPSNode(parentNode, checkPoint, destDir, parentNode.GetPassedCost() + CalcHeuri(parentNode.pos, checkPoint), CalcHeuri(checkPoint, endPoint)));
}
else if (check == 0)
{
JPSNode tmpNode = new JPSNode(parentNode, checkPoint, dir, parentNode.GetPassedCost() + CalcHeuri(parentNode.pos, checkPoint), CalcHeuri(checkPoint, endPoint));
if (SecondarySearch(tmpNode, checkPoint, JPSDir.Up, JPSDir.Right))
closedList.Add(tmpNode);
}
else break;
}
return found;
//
// other diagonal cases
// ...
}SearchLine함수는 각 방향을 탐색하는 함수로, 8방향에 대한 구현을 switch 문 안에 전부 구현했습니다.
위는 직선, 대각선 탐색 각각 한 case씩 가져온 것입니다.
오른쪽 직선 탐색부터 보겠습니다.
- 반복문을 통해서 현재 위치부터 배열 끝까지 확인하면서
JPCheck함수를 통해 Forced Neighbor를 찾습니다. check가 1이면 Forced Neighbor 를 찾았으므로,openList에 해당 노드를 넣고 return 합니다.check가 -1이면 해당 노드는 벽이거나 배열 범위를 벗어났으므로 return 합니다.
대각선 탐색도 비슷하게 살펴보겠습니다.
- 반복문으로 대각선 방향을 확인합니다.
JPCheck에서 범위를 확인해주므로 조건문은 생략했습니다. check가 1이면 Forced Neighbor 를 찾았으므로,openList에 노드를 넣습니다. return을 하지 않는 이유는 현재 탐색 방향과openList에 넣은 노드의 탐색 방향이 다르기 때문입니다.check가 0이면 보조 탐색을 진행합니다. 보조 탐색을 통해 Forced Neighbor를 발견하면 현재 노드를closedList에 넣어줍니다.check가 -1이면 루프를 끝냅니다.
JPCheck
private int JPCheck(JPSNode node, Vector2Int pos, JPSDir dir, out JPSDir destDir)
{
//
// BoundCheck
// Init
// ...
if (pos.x == endPoint.x && pos.y == endPoint.y)
{
destDir = dir;
AddToOpenList(new JPSNode(node, pos, dir, 0, 0));
return 1;
}
// Check Forced Neighbor
switch (dir)
{
case JPSDir.Right:
if (IsMovable(pos + new Vector2Int(1, 1)) && map[pos.x, pos.y + 1] == (int)Define.GridType.None)
{
destDir = JPSDir.UpRight;
return 1;
}
if (IsMovable(pos + new Vector2Int(1, -1)) && map[pos.x, pos.y - 1] == (int)Define.GridType.None)
{
destDir = JPSDir.DownRight;
return 1;
}
break;
//
// other directions
// ...
}
return 0;
}
처음에 BoundCheck를 통해 해당 위치가 벽이거나 배열 범위를 넘어섰으면 -1을 리턴합니다.
또한, 목적지라면 openList 에 비용을 0, 0으로 둬서 다음 While문 에서 바로 목적지를 뽑도록 합니다.
예외처리가 끝났다면 switch~case 문으로 방향마다 Forced Neighbor를 찾아줍니다.
찾았다면 1을 return하고 destDir을 앞으로 탐색해야하는 방향으로 바꿔줍니다.
아무것도 찾지 못했다면 0을 return합니다.
아래는 실행화면입니다.
잘 되는걸 확인했으니, 이제 이 경로대로 적을 움직이도록 해보겠습니다.
마무리
경로대로 잘 따라가는 것을 확인할 수 있습니다.
하지만 코너를 돌 때 collider 때문에 가끔씩 걸리는 모습이 보입니다.
다음에는 이런 부분을 개선하고 Behavior Tree 와 합쳐서 Enemy AI를 완성해보겠습니다.
주의할 점
- 해당 코드에서는
openList를SortedSet<JPSNode>로 만들고 priority queue 처럼 사용했습니다.
Comparer를 만들 때 return이 0이면 집합에서는 중복값을 허용하지 않기 때문에 해당 노드를 삭제시킵니다. 따라서, 비용 말고도 위치나 방향까지 비교하시기 바랍니다. - switch-case 를 주의해야 합니다.
각 case 마다 루프나 Forced Neighbor 를 찾기 때문에 실수할 가능성이 높습니다.
예를 들어 저는 벡터를 뺄 때, 벡터의 원소도 음수로 설정해서 몇 시간동안 해맸습니다.
저는 위 두 문제 때문에 시간을 많이 잡아먹었습니다. 맵을 랜덤적으로 생성해서 디버깅하기가 더 어려웠습니다.
이 글을 보시는 분들은 같은 실수를 하지 않으셨으면 좋겠습니다.
참고자료
https://en.wikipedia.org/wiki/A*_search_algorithm
https://harablog.wordpress.com/2011/09/07/jump-point-search/
https://zerowidth.com/2013/a-visual-explanation-of-jump-point-search/
