JPS 알고리즘에 대해 알아보자.

앞서서 우리는 A* 알고리즘에 대해 배웠다.

A* Algorithm

하지만 A알고리즘의 속도로 만족하지 못하는 경우가 있다! 일단 우선적으로 A는 잔가지로 뻗쳐나오는 경우를 모두 비교해보고, 그 중에서 가장 작은 경로를 찾아야한다.

즉 어떻게 보면 부분적으로는 완전탐색을 한다고도 생각이 드는데, 조금 더 최적화된 방법을 사용할 수 있지 않을까? 해서 나온 게 JPS알고리즘이다.

#JPS 알고리즘이란?

JPS알고리즘에서 가장 중요한 키워드는 ‘장애물’이다. a*알고리즘도 그렇고, 여타 알고리즘이 그렇듯이 장애물을 적극적으로 배제한다. 하지만 JPS알고리즘은 장애물을 가장 중요한 요소로 본다.

내가 왜 이런 말을 하였는지 보도록 하자.

S가 시작점이고 E가 도착점이다. S에서 E로 가는데 가장 빠른 경로는 무엇이겠는가? 당연히 최단 경로는 장애물을 터닝 포인터로 잡아서 이동하는 것이다.

그래서 조금 더 사전적으로 말하자면 JPS는 ‘모서리’를 찾아내어, 유망한 노드를 줄이는 것에 특화되어 있는 알고리즘이다.

JPS는 Jump Point Search 알고리즘으로 노드에 대한 계산을 Jump할 수 있는 Point를 Search하는 알고리즘이다.

경로 탐색

간단한 그림을 통해서 설명하겠다.

일단 일직선으로 쭉 나아가며 탐색한다. 장애물이 있거나 범위 밖이면 탐색을 종료한다. 또, 대각선으로 나아가고 거기서도 일직선으로 쭉 나아가며 반복한다.

그런데, 일직선으로 나아가던 대각선으로 가던 도중에 장애물이 스쳐지나가는 부분이 있을 것이다.

그 부분이 바로 JPS의 알고리즘에서 중요시 하는 ‘모서리’이다.

기본적인 알고리즘의 토대는 A알고리즘하고 똑같다. 아직 A알고리즘에 대해 이해하지 못한 사람은 위의 링크를 따라 공부하고 오자.

JPS 알고리즘

(1) 4번에서 X로 이동한다는 처음 조건을 두자. 우리가 가야하는 곳은 3이다.

(2) 2번에 장애물이 있는 경우, 장애물이 없는 경우를 일단 테스트해보자.

(3) 2번에 장애물이 없으면 X를 거치지 않아도 4 -> 2 -> 3으로 이동할 수 있다.

(4) 2번이 장애물이라면 X를 거쳐서 4 -> X -> 3으로 이동하는 절차가 된다.

(5) 따라서 3으로 가는 경로. 다르게 말하자면 3이라는 노드는 장애물에 따라 노드의 경로가 바뀌게 된다. 이러한 노드를 Forces Neighbour이라고 한다.

(6) Forced Neighbour이 무조건 지나쳐야 하는(그래야 최적인) 노드를 Jump Point라고 하고, 이걸 이용해서 A*로 길을 찾는다.

추가적으로 Jump Point를 찾는 과정을 Grid Scanning이라고 부른단다.

밑에는 내가 구현한 JPS알고리즘의 시연 영상과 그에 따른 깃허브 링크이다.

전부 예전 팀프로젝트에서 만들어뒀던 소스라서 소스코드만 올려놓을 예정이니… 물어보실 게 있다면 eyiuta1@gmail.com으로 연락을 주시면 되겠다.

https://youtu.be/z193WeTCxUY

https://github.com/HyangRim/JPS_TEST

레퍼런스

https://velog.io/@jellypower/%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B0%80-%EA%B8%B8%EC%9D%84-%EC%B0%BE%EB%8A%94-%EB%8D%94-%EB%B9%A0%EB%A5%B8-%EB%B0%A9%EB%B2%95JPS%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%98-%EC%9E%91%EB%8F%99%EB%B0%A9%EC%8B%9D

https://www.youtube.com/watch?v=rfOgaPXCADQ

Algorithm 카테고리 내 다른 글 보러가기