[게임 AI] JPS(Jump Point Search) 알고리즘

개요

---

에이스타 알고리즘을 확장한 길 찾기 알고리즘인 JPS 알고리즘에 대해 알아보자.

JPS 알고리즘이란?

출발 지점부터 목표지점까지 탐색 과정 중간중간에 포인트를 찍어가며 경로를 찾아내는 알고리즘이다.
에이스타 알고리즘을 확장한 알고리즘으로, 성능이 상대적으로 뛰어나다.

구현

---

JPS의 구성

JPS 알고리즘은 어떻게 구성되어 있는지 알아보자

JPS 알고리즘은 에이스타와 길을 찾아내는 방법에서 차이가 있을 뿐이지, 노드의 구성과 일부 규칙은 에이스타와 동일하다. 따라서 이해를 위해선 에이스타 알고리즘을 먼저 이해하고 오길 바란다.

JPS 알고리즘의 길찾기 수행

JPS 알고리즘이 어떤 과정을 통해 길을 찾아내는지 알아보자

JPS 알고리즘이 길을 찾아가는 방식은 체스 게임 속 퀸의 이동방식을 예시로 들어 설명할 수 있다.
퀸은 상하좌우, 대각선 중 한 방향으로 나아갈 수 있다. 하지만 길을 막고 있는 장애물이 있거나 한 번에 도달할 수 없는 경로인 경우 여러 번에 나눠서 이동해야 한다. 즉, 모든 위치로 한 번에 이동할 수는 없다.

퀸이 이동할 수 있는 방향은 다음과 같다.
위에서 설명했듯, 상하좌우 그리고 대각선으로 이동할 수 있다.

하늘색 타일이 목적지처럼 한 번에 이동할 수 없는 목적지는 두 번에 걸쳐서 이동해야 한다.

이처럼 목적지까지 이동하기 위해 경유해야하는 위치를 찾아내는 것이 JPS 알고리즘의 핵심이다. 이 경유해야 하는 노드를 포인트라고 부른다.
에이스타는 점진적으로 출발지에서부터 목적지까지의 모든 타일을 하나하나 검색하지만, JPS는 포인트만 빠르게 찾아내어 나아가기 때문에 속도에서 차이가 난다.

이 포인트를 찾아내는 규칙을 알아보자

포인트를 찾는 규칙

JPS 알고리즘이 경유해야 할 위치인 포인트를 찾는 방법을 알아보자.
본 포스팅에서 설명하는 규칙은, 대각선 이동시 벽을 타고 넘어갈 수 없도록 규칙을 수정했기 때문에 다른 글에서 보여주는 내용과는 조금 다르다.

JPS 알고리즘에서 지형을 탐색하는 과정은 다음과 같다.
대각선 탐색을 할 때 직선 탐색을 추가로 하는것에 유의해야 한다.

포인트를 찾기 위해서 가장 먼저 알아야 하는 것은 가지치기이다.

가지치기는, 불필요 하다고 느껴지는 방향은 탐색하지 않는 것이다.
가지치기는 직선으로 탐색할때와 대각선으로 탐색할 때 차이가 있으며, 이마저도 장애물의 유무에 따라 조금씩 달라진다.

직선으로 탐색할때 가지치기를 하는 모습은 다음과 같다.

마름모형태가 그려진 타일은 부모 노드이며, 동그라미가 그려진 노드는 현재 노드이다.
하얀색 타일은 탐색을 하는 타일이고, 회색 타일은 탐색을 하지 않는 타일이다.
부모 노드가 현재 노드의 좌측에 있으므로 우측으로 탐색을 하는 과정이며, 그 외의 방향으로는 탐색하지 않는다.

대각선으로 탐색할때 가지치기를 하는 모습은 다음과 같다.

대각선 탐색 뿐 아니라 위아래 방향도 추가로 탐색한다.

직선으로 탐색할때 특정 위치에 장애물이 있으면 탐색 범위가 넓어지기도 한다.

탐색을 진행중인 방향 기준 좌측 하단 혹은 우측 하단에 장애물이 있을 때이다.
검은색 타일이 장애물인 타일이다.
우측 이동중이라면, 좌측 상단과 좌측 하단이 장애물이 있어야 할 위치이다.

장애물이 양측에 있으면 양쪽으로 탐색범위가 넓어진다.

가지치기를 했다면, 포인트가 되는 규칙을 알아야 한다.
포인트를 찾는 규칙으로는 네 가지가 있다.

첫 번째 규칙은 상하좌우로 탐색할때를 기준으로 한다.
상하좌우 방향으로 탐색을 하다가 탐색 방향 기준으로 좌측 하단 혹은 우측 하단에 장애물이 있고, 장애물의 앞에 장애물이 없다면 그곳을 탐색한 지점에 포인트를 찍는다.

위의 설명을 예시를 통해 확인해보자.
다음은 우측으로 탐색중일 때의 모습이다. 파란색 타일은 장애물이고 하얀색은 지나갈 수 있는 영역이며, 동그라미는 현재 노드이다.

우측으로 탐색 중이기 때문에, 현재 노드의 좌측 상단에 장애물이 있으며 상단에 장애물이 없거나, 좌측 하단에 장애물이 있으며 하단에 장애물이 없는 위치를 찾아야 한다.

X표시가 있는 타일이 바로 그곳이다. X표시의 좌측 상단 타일은 장애물이지만 상단 타일(붉은색으로 표시)은 장애물이 아니다.
여기에서 잘 보아야 하는 것은 X표시가 생기는 위치이다. 탐색하는 도중 첫 번째 조건에 맞는 상황이라면 탐색을 한 지점에 X표시가 생긴다.

두 번째 규칙은 대각선으로 탐색할 때를 기준으로 한다.
대각선 방향으로 탐색을 하다가 탐색 방향 기준 좌측 하단에 장애물이 있고, 좌측은 장애물이 없거나, 우측 하단에 장애물이 있고, 우측은 장애물이 없다면 포인트를 찍는다.

마찬가지로 예시를 보며 알아보자.
대각선 방향으로 탐색을 하다가 탐색 방향 기준으로 좌측에 장애물이 있으며 좌측 상단엔 장애물이 없거나, 우측에 장애물이 있으며 우측 상단엔 장애물이 없다면 그곳을 탐색한 지점에 포인트를 찍는다.
우측 상단으로 탐색중일 때의 모습이다. 파란색 타일은 장애물이며, 하얀색 타일은 지나갈 수 있는 타일이다.

우측 상단으로 탐색 중이기 때문에, 현재 노드의 좌측 상단에 장애물이 있으며 상단에 장애물이 없거나, 우측 하단에 장애물이 있으며 우측에 장애물이 없으면 중단점을 찍어야 한다.
위의 조건을 만족하는 지점을 찾았다면 포인트를 찍어야 한다. X표시가 있는 타일이 포인트가 찍힌 지점이다.

세 번째 규칙은 두 번째 규칙과 마찬가지로 대각선으로 탐색할 때를 기준으로 한다.
진행방향 기준 좌측 상단 혹은 우측 상단이 장애물인 경우 포인트를 찍는다.

예시를 보면 우측 상단으로 탐색을 하고 있다.

우측 상단 탐색을 기준으로는 상단 혹은 우측에 장애물이 있으면 포인트를 찍어야 한다.
X표시가 있는 타일은 상단이 장애물이기 때문에 포인트를 찍은 모습이다.

네 번째 규칙은 대각선으로 탐색할 때 추가로 탐색하는 보조 탐색을 기준으로 한다.
보조 탐색은 대각선 탐색 중 포인트를 찾지 못했을 때 추가로 하는 탐색이다. 대각선 방향에서 좌우측으로 뻗어나간다.

보조탐색이 포인트를 찾는 규칙은 첫 번째 규칙과 동일하지만, 포인트를 찍는 위치가 다르다.
포인트가 찍히는 위치가 보조 탐색을 시작한 지점에 찍히게 된다.

네 가지의 포인트를 찾는 규칙에서 공통적으로 적용되는 규칙이 두 가지가 있다.

첫 번째는 맵의 끝에 다다랐거나, 장애물로 인해 더 이상 탐색이 불가능한 경우 종료된다. 이때 중단점은 찍지 않는다.

두 번째는 탐색도중 목적지를 발견했다면, 포인트를 찍은 후, 탐색을 종료한다.

이제, 위의 규칙대로 탐색했을 때 잘 동작하는지 검증해 보자.

JPS 알고리즘의 동작

---

JPS 알고리즘이 Astar 알고리즘을 확장한 알고리즘이기 때문에 기본 구조는 동일하다.
F, G, H에 대한 설명은 에이스타 알고리즘 설명에서 했으므로 추가로 하진 않겠다.

붉은색 타일은 출발지이고, 푸른색 타일은 목적지이며, 회색 타일은 장애물이다.

출발지에서부터 주변 지형을 탐색하게 된다. 출발지는 Close 상태가 되며, 부모노드가 없기 때문에 8방향 모두 탐색한다.

우측 상단 대각선을 탐색하는 도중 포인트를 찍는 세 번째 조건에 맞았기 때문에 포인트를 찍고, Open 상태로 변경된다.
이때 OpenList에 들어가는 것은 포인트뿐이고, F, G, H값이 계산되는 것도 포인트뿐인 점을 주의 깊게 봐야 한다.

또, 대각선 검사에서 포인트를 찾았으므로 보조 검색을 추가로 하지 않는다.

좌측 하단 노드가 부모노드이고 가지치기 조건으로 인해 상단, 우측, 우측상단으로 검사를 해야 하지만 우측과 우측 상단으로 가는 경로가 막혀있으므로 상단만 검사한다.

11번 인덱스가 포인트를 찍는 첫 번째 조건에 맞았기 때문에 포인트를 찍는다.

가지치기로 인해 11번 인덱스에서부터 상단, 우측, 우측 상단 탐색을 한다.
우측 탐색 중 첫 번째 조건을 만족하여 13번 인덱스의 노드는 포인트가 된다.
우측 상단 대각선 탐색 중 네 번째 조건에서 목적지를 탐색했으므로 17번 인덱스의 노드는 포인트가 된다.

17번 노드와 13번 노드 중 17번 노드의 F값이 더 낮으므로 17번 인덱스에서 탐색을 시작한다.
가지치기로 인해 우측 탐색만 이루어지며, 우측 탐색 중 목적지를 발견하였으므로 포인트를 찍고 탐색을 종료한다.

19번 인덱스에서부터 부모 노드를 타고 0번 인덱스까지 이동한 후에 모든 노드들을 이으면 경로가 나타난다.

마치며

---

JPS 알고리즘은 Astar 알고리즘에 비해 이해하기가 까다로웠다. 특히 JPS 알고리즘은 직선으로 이동하는 중 좌측 혹은 우측에 장애물이 있어도 대각선 이동이 가능하게 되어있는데, 필자는 그런 경우엔 대각선 이동을 못하는 게 맞다고 생각해서 기존 알고리즘을 수정하느라 구현이 오래 걸렸다.
하지만 그 덕에 어떻게 동작하는지 완벽하게 이해할 수 있게 되었다. 만약 시간이 된다면 육각타일에서 JPS 알고리즘을 적용할 수 있게끔 해보는 것도 좋은 경험이 될 것 같다.