이번 글에서는 저번글에서 약속했던것과 같이 Jump Point Search(이하 JPS)를 다뤄볼 예정입니다.
저번 시간에는 A* 알고리즘을 통해서 휴리스틱 추정값을 통해서 탐색해나갈 방향성에 대해서 제시를 했었는데요.
우리가 일반적으로 알고리즘에서 느리다고 하는 부분은 기본적으로 정렬, 삽입, 삭제, 탐색 등이 있습니다.
하지만 A*의 경우에는 priority queue를 써야하기 때문에 정렬은 빠질수가 없습니다.
혹은 pq가 아니라 리스트를 써서 매번 가장 F값이 작은걸 골라 낸다고 하더라도 그만큼의 시간 소요는 없어서는 안되는 것이라는 거죠.
그렇다면 우리가 줄일수 있는것은 중간에 거쳐가는 노드의 생성을 줄이는 겁니다.
물론 노드의 생성을 줄인다는게 메모리 풀링을 통해 동적으로 할당과 반환을 줄이는 방법도 존재하겠지만(제가 예전에 메모리풀에 대해서 남긴 글이있기때문에...) 지금의 케이스는 그건 아닙니다.
지금의 경우에는 그냥 노드 생성의 숫자를 줄여보자 이겁니다.
그러면 시작해보도록 하겠습니다.
AStar의 비효율
A*의 가장 큰 단점이라고 꼽히는 부분은 내가 가는 모든 곳에 노드가 생성된다는 점입니다.
물론 다익스트라도 마찬가지입니다.
내가 방문하는 모든 노드 즉 open list에서 하나를 꺼낼때마다 그 주변의 노드 최대 8개가 생성이 될 수있습니다.
당연히 길찾기와 같은 알고리즘은 그 알고리즘 자체만으로도 시간을 많이 잡아먹습니다.
매번 모든방향에 대한 확인과 오픈리스트에 대한 확인, 없으면 새로 생성 및 오픈리스트에 삽입 이 과정을 오픈리스트가 빌때까지 수행해야 하기 때문입니다.
그렇기 때문에 매우 느립니다.
그 와중에 new, malloc과 같이 런타임에 메모리를 할당해주는 함수들까지 사용해버린다면 길찾기 알고리즘 한번에 수 ms가 나와버리는것 또한 순식간입니다.
new도 그렇고 정렬도 그렇고 8방향 탐색도 그렇고 A*를 구현하기 위해서 어느 하나 빠질 수 없습니다.
모두 필요한 부분이기 때문입니다.
그러므로 우리는 여기서 사람의 길찾기 방식을 일부 모방해서 사용할 예정입니다.
A*알고리즘의 경우 매 한걸음마다 좌우를 살피며 어디로 가야하는지 확인하는 작업을 거쳤습니다.
반면 오늘 소개할 알고리즘인 JPS의 경우는 한걸음은 조금 너무 과하지 않느냐 하는 고민에서부터 시작되었습니다.
사람이 길을 찾을때와 마찬가지로 코너가 나오면 좌우를 둘러보고 그 때 갈길을 정해서 다음 코너가 나오기 전까지 직진하겠다는 방식으로 바뀌게 되는것입니다.
정리하면 매 스텝마다 노드의 생성이 되는게 아니라 코너가 없는 직진구간이라면 노드 생성이 없이 직진을 하고 커브 구간에만 노드를 생성해 다음 방향을 둘러보겠다는 의미가됩니다.
이는 빈번하게 발생하는 노드의 동적할당을 최소화시킨다는 의미가 있습니다.
동적할당을 최소화 시킨다면 부하도 줄어들 것이고 메모리에대한 걱정도 줄어듦으로 여러모로 편리할 것 같습니다.
하지만 마냥 JPS알고리즘이 A*보다 뛰어나다고는 할 수 없습니다.
A*의 경우 맵이 넓고 가야할 거리가 좁다면 상당한 이득을 볼 수 있는 구조입니다.
반면 JPS의 경우 코너가 나올때까지 계속 가야하므로 가지 않아도 되는 모든 구간을 다 탐색하게 되므로 맵이 넓고 가야할 거리가 짧은경우에는 오히려 비효율일 수도 있습니다.
그러므로 적절한 순간에 적절한 알고리즘을 사용하는게 가장 좋은 방법이겠지만, 일반적으로 A*와 JPS의 성능을 놓고보면 JPS의 성능이 조금더 좋지 않을까 하는게 하는게 필자의 생각입니다
그럼 다시 본론으로 돌아와서 구현에 대한 언급을 해보려고합니다.
JPS를 이루는 큰 로직덩어리, 원리는 A*와 크게 다르지 않습니다.
다만 약간의 차이가 몇가지 있습니다.
1. 직진한다는 개념을 넣어야합니다. 2. 코너라는 개념을 넣어야합니다.
그럼 직진한다는 개념을 먼저 정리하고 넘어가겠습니다.
크게 어려운것은 없습니다.
x좌표든 y좌표든 증가(감소)를 반복하며 코너가 나오는 지점까지 간다입니다.
JPS에서 중요하게 언급되어야하는 부분이 코너에 대한 정의라고 생각합니다.
위의 그림중 1번은 코너입니다, 그리고 2번은 코너가 아닙니다.
1번은 코너입니다.
진행방향을 거쳐오면서 좌우를 확인할 수 없었고 진행방향이 끝나는 지점인 구간에 다달아서야 좌우를 확인할 수 있기 때문입니다.
2번은 코너가 아닙니다
진행방향을 거쳐오면서 좌우를 확인할 수 있었기 때문에 열려있는 길이라고 봐야할겁니다.
이런 단순한 원리를 이용해서 어떤 경우 노드가 생성되는지 그림으로 표현하겠습니다.
위의 경우는 오른쪽으로 진행하는 방향에 코너가 존재하는 케이스입니다.
위의 경우에는 N을 지나는 지점이 코너이기 때문에 N지점에 노드를 생성하면 되는것입니다.
왼쪽 위쪽 아래쪽도 다 동일합니다.
그림을 회전해서 보면 모두 동일한 상황이기 때문에 다른 방향에서의 그림은 생략하도록 하겠습니다.
대각선의 경우 상하좌우의 그림보다는 약간 꼬인듯한 모습을 보여줍니다.
수평과 수직 방향의 코너가 시작되는 경우 실제 코너라고 할수있는 구간 바로 직전 진행구간에 노드를 생성했었습니다.
하지만 대각선의 경우 코너가 시작되는 그 자리를 코너라고 할것이고 그 구간에 노드를 생성할것입니다.
이 경우도 사진 회전을 통해 4가지 상황 모두를 설명할 수 있으므로 다른 방향에 대한 그림은 생략하겠습니다.
아마 지금까지 그림을 제대로 이해하셨다면 감이 오셨을겁니다.
그리고 지금부터는 방향에 따른 탐색 진행이 또 조건으로 걸리게 됩니다.
만약 이전 노드가 오른쪽으로 진행하고 있었다면 그 노드의 왼쪽은 이미 이전 노드에 의해 검사가 되었을겁니다.
굳이 돌아갈 필요가 없는 구간이라는 의미입니다.
갔던 구간을 다시 가는 경우는 다른 방향으로 접근한 노드가 똑같은 구간으로 들어갔을 경우를 제외하면 없습니다.
그래서 수평 수직으로 진행할 경우에는 이런 룰이 붙습니다.
1. 가던 방향을 확인(즉 parent로 부터 나와의 방향) -> 필수 2. 가는 방향 기준 왼쪽에 코너라면 가는방향 기준 왼쪽 대각선 확인 -> 조건에따라 3. 가는 방향 기준 오른쪽에 코너라면 가는방향 기준 오른쪽 대각선 확인 -> 조건에따라
이렇게 되는겁니다. 그러면 대각선일 경우에는요?
아직 대각선이 어떻게 진행되는지는 말씀을 안드렸지만... 대략 감이 오실겁니다.
대각선도 그냥 1씩 증가 혹은 감소시켜 가면서 찾으면 됩니다.
라고 말하면 안되겠죠
이유를 보여드리죠
그냥 대각선과 수평 수직만 탐색했을 경우에는 빨간 구간만이 체크가 됩니다.
하지만 파란부분에 대한 체크가 이뤄지지 않았으므로 이 구간은 대각선을 체크하는 구간에서 함께 체크해줍니다.
그러므로 대각선을 체크할 때에는 대각선으로부터 파생되는 가로와 세로구간을 확인하는 보조적인 함수가 필요합니다.
대각으로 진행하는 상황에서는 다음과 같은 규칙들이 필요할겁니다.
진행방향은 오른쪽 위쪽 방향으로 가정합니다.
1. 가던 방향을 확인(즉 parent로 부터 나와의 방향) -> 필수 2. 위쪽 방향 확인(진행방향이 왼쪽 위기때문에 왼쪽과 위쪽을 확인해야됩니다.) -> 필수 3. 오른쪽 방향 확인(진행방향이 왼쪽 위기때문에 왼쪽과 위쪽을 확인해야됩니다.) -> 필수 4. 왼쪽 위로 코너라면 왼쪽위 확인-> 조건에따라 5. 오른쪽 아래로 코너라면 오른쪽 아래 확인 -> 조건에따라
아마 눈치가 빠르신 분은 캐치하셨을것 같습니다.
이미 가로와 세로를 확인해서 그 위치가 코너임을 알게 되었는데 그 지점에 노드를 생성하지 않고, 대각 지점에 노드를 생성하는지가 의문이신 분이 계실것으로 판단됩니다.
물론 그 자리에 바로 노드를 생성해도 문제가 되지 않습니다.
오히려 노드를 덜 생성하기때문에 클로즈 리스트에 추가되지 않고 검사할 필요가 없다는 부분에서 성능면에서 개선 사항이 존재할 수도 있습니다.
하지만 저는 JPS의 기본적인 직진을하다 방향전환을 해야할 때 노드를 생성한다라는 규칙을 지키기 위해, 보조노드를 추가로 할당하는 방식을 채택했고, 이런 방식이 조금더 직관적이었기 때문에 이 방법을 선택했습니다.
위에서 언급한 내용대로 코드를 구현하신다면 JPS를 완벽하게 구현하실 수 있을겁니다.
사실 여기까지만 해도 JPS를 사용하는데는 지장이 없지만 아름답지 않습니다.
아직은 JPS를 완성했다고 하기에는 조금 아쉬움이 남습니다.
물론 JPS로직이 완성이 되지 않았다고 하는것이 아닙니다.
JPS를 조금더 깔끔하고 멋있게 만들어줄 추가적인 로직에 대한 언급을 하려고하는겁니다.
JPS의 최대 단점으로는 노드와 노드를 연결하는 것이고, 노드는 코너 구간에만 만들어지기 때문에, 코너가 있다고 판단되는 지점에는 직선임에도 불구하고 노드를 생성하는점과, 코너가 있다고 판단되는 지점간의 연결을 하려다 보니 직선으로 연결이 가능함에도 불구하고 각이 져있는 부분은 상당히 부자연스럽고 아쉬움이 남는부분입니다.
이를 해결하기 위해서 두 좌표사이의 직선을 그려주는 클래스를 만들었고 각 노드와 노드간 스킵이 가능한 노드가 있다면 스킵가능한 노드를 제외한 두 노드를 묶어주는 방법을 선택했습니다.
위와같은 그림입니다.
눈으로 봤을때 직선같아 보이진 않지만 저 타일맵 안에서는 최선의 직선입니다.
모니터와 실제 픽셀간 해상도 차이때문에 직선은 아닌것 같지만 저 해상도 내에서 뽑아낼 수 있는 최선의 직선인겁니다.
모니터도 확대가 가능한만큼 확대해서 본다면 픽셀단위의 저런 점들이 모여서 직선을 이루고 있는 것 처럼 보일겁니다.
노드와 노드 사이에 직선을 그어서 8방향 이동이 아니라 좀더 자연스럽게 8방향이 아니라 전방향 이동이 가능한 것 처럼 보이게 하기위해서 만들었습니다.
직선을 그려주는 클래스를 이용해서 타일 좌표로 줄을 그을 수 있게 되었습니다.
노드0과 노드2가 직선으로 연결되는 과정에 중간에 벽이 없다고 한다면 둘은 직접 연결 가능한 노드이고, 노드 1을 거쳐가는것 보다 더 빠르기 때문에 직접 연결을 해주는 코드를 넣었습니다.
결과는 다음과 같습니다.
원래의 JPS알고리즘이라면 0 -> 1 -> 2가 되겠지만
실제 가장 빠른 경로라고 하면 분홍색 라인이 될겁니다.
그러므로 1번 노드를 스킵하고 바로 연결해주는 코드해 더 빠른 경로를 얻어냈습니다.
복잡해져도 동일하게 작동합니다.
스킵이 되는 노드들은 생성되서는 안되는 노드들이지만, 우선 시각적으로 보여야하므로 스킵하는 코드를 따로 안넣은 상태로 실행시킨 모습입니다.
이전 그림보다 더 체감이 되실겁니다.
심지어 충돌처리는 서버의 영역입니다. 클라에서 살짝 걸렸다고 해서 못지나간다면... 길찾기 알고리즘을 왜합니까??..
길찾기 알고리즘을 통해 나온 경로는 무조건 믿고 가는겁니다. 추가로 그동안의 충돌검사는 하지 않는겁니다. 물론 동적으로 움직이는 맵이라던가 몬스터와의 충돌이 필수적이라면 이 알고리즘과 별개로 다른 레이어에서 충돌체크를 해줘야 할겁니다. 우선은 몬스터나 동적인 맵이 존재하지 않을것이기 때문에 이렇게 만들었습니다...
그럼 오늘의 포스팅을 마치도록 하겠습니다.
오늘도 긴 글 읽어주셔서 감사드립니다.
이번 내용을 준비한다고 사실 2주일 정도 걸린건 아니었지만,
어쩌다 보니 A* JPS한다고 2주를 날려먹었습니다.
심지어 아직 해야될게 하나 더있는 상황인데...
이녀석이 계속 안되는 바람에 아직 완성을 못해서 그거 다되고 나면 다시 돌아올것 같습니다.
