어제부터 길 찾기 알고리즘의 업그레이드 버전을 알아보겠습니다.
지난 시간에는 Dijkstra, A 알고리즘에 대해 소개해보았습니다. 이 두 알고리즘 같은 경우는 워낙 유명한 알고리즘이기도 하고, 간단하기도 해서 이미 알고 계신 분이 많았을 것이라고 생각합니다.
반면 오늘 다룰 D 알고리즘과 JPS 알고리즘의 경우 생소하기도 하고, 처음 들어보시는 분이 있을 수도 있습니다.
저 역시 옛날에 A* 알고리즘을 처음 접한 후 바로 하이테크 버전이라는 JPS 알고리즘을 공부해보았는데, 참...이해하기 힘들어서 고생했던 기억이 있습니다.
길 찾기 알고리즘에 대한 기초적인 설명은 이전 글에서 해 놓은 관계로, 바로 알고리즘 소개부터 시작하도록 하겠습니다!
메모리를 제물로 바치는 D* 알고리즘
Dynamic A 알고리즘, 즉 D 알고리즘은 이동 도중에 맵에 변화가 생겼을 때 처음부터 서치 할 필요 없이 기존의 정보를 바탕으로 경로를 수정하는 알고리즘입니다.
동작 방식부터 한번 살펴 봅시다.
사전 지식으로, A 알고리즘과 마찬가지로 D 알고리즘에는 열린 목록과 닫힌 목록이 존재합니다. 열린 목록은 탐색이 아직 필요한 지형을 나타내고, 닫힌 목록은 탐색이 더 이상 필요하지 않은 지형을 의미합니다.
여기에 RAISE, LOWER, NEW의 개념이 등장하게 되는데
NEW는 open 목록에 포함되지 않았음을 의미합니다. closed의 경우 '더 이상 open 목록에 들어가지 않음' 을 의미하기에, 약간 차이가 있습니다.
RAISE는 open 목록에 마지막에 존재했을 때보다 cost가 높아졌음을 의미합니다.
Lower는 open 목록에 마지막에 존재했을 때보다 cost가 낮아졌음을 의미합니다.
D* 알고리즘의 비용 함수는
h(X) = h(Y) + c(Y, X)
c(Y, X) = A(Y, X) + I(X)
로 정의됩니다.
h(X) 는 X 위치까지 도달하는데 소요되는 총 경로 비용을 의미합니다.
Y는 X 지형에 도달하기 바로 직전의 위치를 의미합니다.
c(X, Y)는 근접 경로 비용으로, 이전 위치 Y로 부터 X까지의 비용을 의미합니다.
I(X)는 장애물을 고려한 비용을 의미합니다. (고정된 장애물, 이동하는 장애물 포함)
D* 알고리즘은 다음과 같은 순서로 진행됩니다.
초기 경로 계산: 초기 경로 계산은 A나 다른 경로 탐색 알고리즘을 사용하여 진행됩니다. 즉, A 알고리즘은 D* 알고리즘에 있어서 일종의 부품처럼 이용된다고 볼 수 있습니다.
환경 변화 감지: 장애물이 생성되는 등 환경이 변화하면 최적 경로도 바뀌겠죠. D* 알고리즘은 이것을 감지해 경로를 바로 업데이트해줍니다.
역 방향 업데이트: 환경 변화가 감지되면, D* 알고리즘은 변경이 발생한 지점에서 역방향으로 경로를 업데이트합니다.
순 방향 업데이트: 역방향 업데이트 후, 새로운 경로에 따라 순 방향으로 경로를 업데이트 합니다.
반복: 환경이 변화할 때마다 역 방향, 순 방향 업데이트를 번갈아가며 지속적으로 최적화를 수행합니다.
D* 알고리즘의 장점은 실시간 응용이 가능하고, 동적 환경에 대응할 수 있다 이고, 단점으로는 메모리 효율성이 떨어진다입니다.
그렇다면, 지난 시간 플레이어의 길막을 인식하고 좌 우로 경로를 수정하려 한 AI는 D* 알고리즘으로 구현된 것이겠군요! 플레이어를 장애물로 보고 경로를 수정하려 했으니까요.
사실 그렇지는 않을 겁니다. D* 알고리즘은 데이터 저장 공간을 타 알고리즘에 비해 많이 요구하기 때문에, 게임에는 적합하지 않다가 중론 이거든요. 제가 너무 들이대서 콜라이더 오류를 일으켰다가 정설입니다.
D 알고리즘의 경우 동작 방식에 대한 정보가 인터넷 상에 확실히 적은 것 같습니다. 어느새 알고리즘의 갈라파고스까지 도달한 것일까요? 제 개인적으로, D 알고리즘은 그 개념만 알아두는 것이 좋을 것 같습니다. 직접 구현할 일은 많지 않아 보여요.
이 글을 읽으시고 연결이 잘 안된다, 그래서 cost function은 왜 나온 건데? 그래서 LOWER, RAISE, NEW 상태는 뭔데? 라는 의문을 가지신다면...
제가 이해를 완벽하게 수행하지 못해서 그렇습니다. D*를 이해할 필요가 없다고 글에서 굳이 설명하고 있는 것도 변명이 맞습니다. 이 부분은 보충 학습을 수행하고, 향후 업데이트를 진행하겠습니다.
그리고 그런 의문까지 가지셨다면 글을 정말 열심히 읽어주신 것 같네요.
감사합니다.
Jump point search (JPS)
D를 만만히 보고 빠르게 작성하려다 크게 데이고, JPS 먼저 작성하게 되었습니다.
D는 길 찾기 알고리즘...보다는 '길 찾기 알고리즘인 A* 알고리즘을 응용해 동적으로 변화하는 환경에 적용해 본 시스템' 에 더 어울리지 않을까요?
<JPS의 탐색 방향성. 참으로 dynamic하다...>
이 장에서 소개하는 JPS는 Dijkstra 알고리즘과 A 알고리즘이 너무 느리다고 느끼시는 분에게 어울리는 '엄청 빠른 길 찾기' 알고리즘 입니다.
시간 복잡도는 굳이 논하지 않겠습니다.
그것을 논하는 것이 Fun 하고 Cool 하고 Sexy하지 않네요.
아무튼 A보다 목적지에 빨리 도착하기 때문에 빠릅니다.
자 이제 바로 JPS의 동작 방식을 살펴봅시다!
JPS 알고리즘의 핵심은 코너를 찾는 것입니다.
위풍당당 빈고-킹이 위로 이동하고 있습니다. 이 때, 코너란 빨간색으로 표시된 두 위치를 의미합니다. 좌 우가 막혀있다가 갑자기 좌상단, 우상단에 막히지 않은 위치가 나왔죠.
대각선의 경우는 다음과 같습니다.
빈고-킹이 이동하는 길의 좌측, 하단이 막혀있다가 좌 상단, 우 하단이 막히지 않는 위치가 나왔죠.
이것은 빈고-킹이 이동할 수 있는 8 방향으로 돌려가며 모든 방향에 적용하는 것이 가능합니다.
이렇게 코너를 발견하면, 빈고-킹은 움직일 수 있는 방향을 살펴보고 다음 코너를 찾아 나섭니다.
다만, 대각선으로 움직일 때는 코너만 찾는 것이 아니라, 파란색 화살표의 보조 적인 탐색을 함께 수행합니다. 이 때 보조적인 탐색을 진행하다가 코너를 발견하면, 보조 탐색을 뿌린 대각선 위치에서 다시 탐색을 시작합니다.
위 그림의 경우 파란색 화살표의 보조 탐색을 수행하다 빨간색 코너를 발견했고, 녹색의 위치에서 다시 탐색을 이어나갈 것입니다.
탐색 과정을 정리하면 다음과 같습니다!
시작 노드를 바탕으로 8 방향 탐색
시작 노드를 닫힌 목록에 넣는다.
열린 목록에서 가장 낮은 cost를 가진 노드 pop 한다.(priority queue)
열린 목록이 비었다 --> target까지 닿을 수 없음 (탐색 종료)
pop 되었던 노드를 닫힌 목록에 넣는다.
pop 되었던 노드가 목적지라면 (탐색 완료)
pop 된 노드 이전 parent node의 방향에 따라 코너를 찾는 탐색을 수행
코너를 발견하면, 위 코너 탐색에 따라 탐색을 진행할 위치를 열린 목록에 넣는다.
위 일련의 과정을 반복하면서 탐색을 진행합니다.
JPS 알고리즘의 cost function은 A 알고리즘과 동일합니다. 결국 jump point를 찾아가며 중간의 위치를 스킵할 수 있다는 점이 JPS와 A의 차이를 만드는 것입니다.
결론
업그레이드 길 찾기 알고리즘은 정말 어렵네요.
그래도 한 때 어렵게 느꼈던 JPS 알고리즘을 다시 복습해보고, 이해한 것은 의미 있는 경험이었던 것 같습니다.
Fun하고 Cool하고 Sexy하지 않은 tmi
A* 알고리즘의 시간 복잡도는 O(b^d) 입니다. 여기서 b는 각 위치에서 이동 가능한 branch의 수이며, d는 출발 지점에서 목적지까지 최단 경로의 길이입니다.
JPS의 시간 복잡도는 O(dn^1/2)를 가집니다. n은 그래프의 노드의 수, d는 출발 지점에서 목적지까지 최단 경로의 길이입니다.
JPS의 경우 jump point를 미리 찾아내는 방법으로 탐색 과정을 압축하기 때문에, 더 효율적인 시간 복잡도를 갖고 있습니다.
neolgu
commented
9 months ago
길을 찾는 다양한 알고리즘들 (2) (작성중)
서론
19 길을 찾는 알고리즘들 (1) 에 이어서 작성된 내용입니다.
어제부터 길 찾기 알고리즘의 업그레이드 버전을 알아보겠습니다. 지난 시간에는 Dijkstra, A 알고리즘에 대해 소개해보았습니다. 이 두 알고리즘 같은 경우는 워낙 유명한 알고리즘이기도 하고, 간단하기도 해서 이미 알고 계신 분이 많았을 것이라고 생각합니다. 반면 오늘 다룰 D 알고리즘과 JPS 알고리즘의 경우 생소하기도 하고, 처음 들어보시는 분이 있을 수도 있습니다. 저 역시 옛날에 A* 알고리즘을 처음 접한 후 바로 하이테크 버전이라는 JPS 알고리즘을 공부해보았는데, 참...이해하기 힘들어서 고생했던 기억이 있습니다.
길 찾기 알고리즘에 대한 기초적인 설명은 이전 글에서 해 놓은 관계로, 바로 알고리즘 소개부터 시작하도록 하겠습니다!
메모리를 제물로 바치는 D* 알고리즘
Dynamic A 알고리즘, 즉 D 알고리즘은 이동 도중에 맵에 변화가 생겼을 때 처음부터 서치 할 필요 없이 기존의 정보를 바탕으로 경로를 수정하는 알고리즘입니다.
동작 방식부터 한번 살펴 봅시다. 사전 지식으로, A 알고리즘과 마찬가지로 D 알고리즘에는 열린 목록과 닫힌 목록이 존재합니다. 열린 목록은 탐색이 아직 필요한 지형을 나타내고, 닫힌 목록은 탐색이 더 이상 필요하지 않은 지형을 의미합니다.
여기에 RAISE, LOWER, NEW의 개념이 등장하게 되는데
D* 알고리즘의 비용 함수는
로 정의됩니다. h(X) 는 X 위치까지 도달하는데 소요되는 총 경로 비용을 의미합니다. Y는 X 지형에 도달하기 바로 직전의 위치를 의미합니다. c(X, Y)는 근접 경로 비용으로, 이전 위치 Y로 부터 X까지의 비용을 의미합니다. I(X)는 장애물을 고려한 비용을 의미합니다. (고정된 장애물, 이동하는 장애물 포함)
D* 알고리즘은 다음과 같은 순서로 진행됩니다.
D* 알고리즘의 장점은 실시간 응용이 가능하고, 동적 환경에 대응할 수 있다 이고, 단점으로는 메모리 효율성이 떨어진다입니다.
그렇다면, 지난 시간 플레이어의 길막을 인식하고 좌 우로 경로를 수정하려 한 AI는 D* 알고리즘으로 구현된 것이겠군요! 플레이어를 장애물로 보고 경로를 수정하려 했으니까요.
사실 그렇지는 않을 겁니다. D* 알고리즘은 데이터 저장 공간을 타 알고리즘에 비해 많이 요구하기 때문에, 게임에는 적합하지 않다가 중론 이거든요. 제가 너무 들이대서 콜라이더 오류를 일으켰다가 정설입니다.
D 알고리즘의 경우 동작 방식에 대한 정보가 인터넷 상에 확실히 적은 것 같습니다. 어느새 알고리즘의 갈라파고스까지 도달한 것일까요? 제 개인적으로, D 알고리즘은 그 개념만 알아두는 것이 좋을 것 같습니다. 직접 구현할 일은 많지 않아 보여요.
이 글을 읽으시고 연결이 잘 안된다, 그래서 cost function은 왜 나온 건데? 그래서 LOWER, RAISE, NEW 상태는 뭔데? 라는 의문을 가지신다면...
제가 이해를 완벽하게 수행하지 못해서 그렇습니다. D*를 이해할 필요가 없다고 글에서 굳이 설명하고 있는 것도 변명이 맞습니다. 이 부분은 보충 학습을 수행하고, 향후 업데이트를 진행하겠습니다.
그리고 그런 의문까지 가지셨다면 글을 정말 열심히 읽어주신 것 같네요. 감사합니다.
Jump point search (JPS)
D를 만만히 보고 빠르게 작성하려다 크게 데이고, JPS 먼저 작성하게 되었습니다. D는 길 찾기 알고리즘...보다는 '길 찾기 알고리즘인 A* 알고리즘을 응용해 동적으로 변화하는 환경에 적용해 본 시스템' 에 더 어울리지 않을까요?
<JPS의 탐색 방향성. 참으로 dynamic하다...>
이 장에서 소개하는 JPS는 Dijkstra 알고리즘과 A 알고리즘이 너무 느리다고 느끼시는 분에게 어울리는 '엄청 빠른 길 찾기' 알고리즘 입니다. 시간 복잡도는 굳이 논하지 않겠습니다. 그것을 논하는 것이 Fun 하고 Cool 하고 Sexy하지 않네요. 아무튼 A보다 목적지에 빨리 도착하기 때문에 빠릅니다.
자 이제 바로 JPS의 동작 방식을 살펴봅시다! JPS 알고리즘의 핵심은 코너를 찾는 것입니다.
위풍당당 빈고-킹이 위로 이동하고 있습니다. 이 때, 코너란 빨간색으로 표시된 두 위치를 의미합니다. 좌 우가 막혀있다가 갑자기 좌상단, 우상단에 막히지 않은 위치가 나왔죠.
대각선의 경우는 다음과 같습니다.
빈고-킹이 이동하는 길의 좌측, 하단이 막혀있다가 좌 상단, 우 하단이 막히지 않는 위치가 나왔죠.
이것은 빈고-킹이 이동할 수 있는 8 방향으로 돌려가며 모든 방향에 적용하는 것이 가능합니다.
이렇게 코너를 발견하면, 빈고-킹은 움직일 수 있는 방향을 살펴보고 다음 코너를 찾아 나섭니다.
다만, 대각선으로 움직일 때는 코너만 찾는 것이 아니라, 파란색 화살표의 보조 적인 탐색을 함께 수행합니다. 이 때 보조적인 탐색을 진행하다가 코너를 발견하면, 보조 탐색을 뿌린 대각선 위치에서 다시 탐색을 시작합니다.
위 그림의 경우 파란색 화살표의 보조 탐색을 수행하다 빨간색 코너를 발견했고, 녹색의 위치에서 다시 탐색을 이어나갈 것입니다.
탐색 과정을 정리하면 다음과 같습니다!
위 일련의 과정을 반복하면서 탐색을 진행합니다.
JPS 알고리즘의 cost function은 A 알고리즘과 동일합니다. 결국 jump point를 찾아가며 중간의 위치를 스킵할 수 있다는 점이 JPS와 A의 차이를 만드는 것입니다.
결론
업그레이드 길 찾기 알고리즘은 정말 어렵네요. 그래도 한 때 어렵게 느꼈던 JPS 알고리즘을 다시 복습해보고, 이해한 것은 의미 있는 경험이었던 것 같습니다.
참고자료
https://en.wikipedia.org/wiki/D* https://joonleestudio.tistory.com/28