[게임 AI] A* 알고리즘 vs JPS 알고리즘 성능 비교

개요

에이스타 알고리즘과 JPS 알고리즘의 상황별 성능차이를 알아보자

테스트 조건

가로 세로 100x100, 200x200 타일에 장애물을 랜덤 한 위치에 설치한다.

각 길찾기 알고리즘으로 경로를 탐색한다.

경로 탐색에 성공한 경우 발생한 시간을 모두 더하고 경로 탐색을 한 수만큼 나눠 평균 속도를 계산한다.

테스트 기기 : 맥북 M1 Air 기본형

테스트 횟수는 기기의 한계로 인해 각각 1000번, 100번 수행했다.

100x100 타일에서의 테스트(1000번 테스트)

장애물의 수	에이스타 알고리즘	JPS 알고리즘
100개	8ms	1ms
500개	26ms	1ms
1000개	41ms	2ms
2000개	63ms	2ms

 

에이스타 알고리즘은 장애물의 수가 증가하는 만큼 눈에 띄게 비례하여 상승하였지만, JPS 알고리즘은 장애물의 개수가 증가하여도 크게 변화하지 않았다.
무엇보다 연산 속도가 JPS 알고리즘이 압도적으로 빠른것이 눈에 띈다.

차이를 더 명확히 보기 위해 맵의 크기를 늘렸다.

 

200x200 타일에서의 테스트(100번 테스트)

장애물의 수	에이스타 알고리즘	JPS 알고리즘
100개	47ms	10ms
500개	121ms	14ms
1000개	202ms	15ms
2000개	353ms	15ms
5000개	695ms	17ms

맵의 크기를 늘리자 정말 놀라운 결과가 나왔다. 장애물이 얼마나 늘어나든 JPS 알고리즘의 탐색 속도가 크게 변화하지 않았다.
특히 장애물이 500개일때와 2000개일때의 결과가 크게 차이나지 않는다는점이 놀라웠다.

마치며

예전에 JPS(B) 알고리즘을 도입해서 포트폴리오를 만든적이 있었다.
 R&D를 제대로 하지 않고 사용했기 때문에 면접에서 '얼마나 차이 나는가?'라는 질문에서 모른다고 대답했었다.
그때가 생각나서 시작한 포스팅이었는데, 이렇게 하나하나 눈으로 보니 R&D가 얼마나 중요한지 알게 되었다. 앞으로 무언가 새로운 시도를 할 때 명확하게 분석하고 사용하는 습관을 들여야겠다.