길찾기 알고리즘 공부-2(JPS)

astar보다 빠르다는 jps관련 자료들을 찾았는데

큰 맵에서는 jps가 더 효율이 좋은데 작은 맵이라면 astar가 더 좋다는 글도 있고

jps단점을 개선해서 jps+ 와 jps(b)

jps+와 GoalBound를 합친 jps+GoalBound 도 있다고 하네요

 

참고 주소

https://harablog.wordpress.com/2011/09/07/jump-point-search/

https://www.gdcvault.com/play/1022094/JPS-Over-100x-Faster-than

https://game-dev.tistory.com/13

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=gg9494&logNo=221523868892 

https://joonleestudio.tistory.com/28

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=zzing0907&logNo=220671022815 

https://github.com/rafaelcastrocouto/PathFinding.js

 

 

출처 : https://www.gdcvault.com/play/1022094/JPS-Over-100x-Faster-than

시작 시점을 열린 목록에 넣고

열린 목록에 있는 노드들의 F의 비용이 가장 낮은 노드들 먼저 

( G 이동했던 거리 H 목표까지의 거리, F=G+H)

8방향으로 쏴서 확인합니다

 

열린 목록에 넣는 기준은 목표지점이 이거나

벽유무에 따라서 확인합니다

 

오른쪽 방향(→) 일 때는

// ↑ 벽 ,↗ 이동 가능 ( 노란색 기준으로 위쪽은 벽 오른쪽 위 이동 가능)

// ↓ 벽 ,↘ 이동 가능 (노란색 기준으로 아래는 벽 오른쪽 아래 이동 가능

 

노란색은 열린 목록에 넣을 노드 흰색은 이동 가능 나무는 벽

일 때 그 지점을 열린 목록에 넣습니다.

 

저것처럼

왼쪽 방향(←)

// ↑벽,↖이동 가능
// ↓벽,↙이동 가능

위 방향(↑)
// →벽,↗이동 가능
// ←벽,↖이동 가능

아래 방향(↓)
// →벽,↘이동 가능
// ←벽,↙이동 가능

오른쪽 위(↗)
// ←벽,↖이동 가능
// ↓벽,↘이동 가능

오른쪽 아래(↘)
// ←벽,↙이동 가능
// ↑벽,↗이동 가능

왼쪽 위(↖)
// →벽,↗이동 가능
// ↓벽,↙이동 가능

왼쪽 아래(↙)
// →벽,↘이동 가능
// ↑벽,↖이동 가능

 

여기서 대각선으로 갈 때 (↗↖↘↙)

또 그 자리에서 2방향으로 쏘아서 확인합니다

 

오른쪽 위(↗) 일 때는 위쪽 방향과 오른쪽 방향을 쏴서 확인합니다

캐릭터 방향에서 오른쪽 위(↗) 방향으로 가면서 위쪽으로 보내고 오른쪽으로 보내면서  확인하면

1번 쪽에서 2번이 열린 목록에 들어갈 조건이 맞으니 1번과 2번 노드를 열린 목록에 넣습니다.

 

한 번 더 예시를 들면 왼쪽 아래(↙)

 

아래쪽과 왼쪽을 보냅니다

 

 

 

-----------

 

왼쪽 사진은 왼쪽 위↖ 방향으로 쏴서

---

왼쪽 위(↖)
// →벽,↗이동 가능 (첫 번째 기준)
// ↓벽,↙이동 가능 (두 번째 기준)

---

첫 번째 기준이 맞으니 열린 목록에 넣습니다.

 

/////

 

오른쪽 사진은 

---

오른쪽 위(↗)
// ←벽,↖이동 가능 (첫 번째 기준)
// ↓벽,↘이동 가능 (두 번째 기준)

---

첫 번째 기준이 맞으니 또 열린 목록에 넣습니다. 

 

이런 식으로 특정 지점만 열린 목록에 넣다 보니 거리가 멀어지면 멀어질수록 가는 모든 지점을 넣는 astar보다 빠른 경로 탐색 결과를 나타냅니다.

 

열린 노드 중에 F 가 가장 낮은걸 우선으로 돌리다 보면 목표지점이 나오는 구간이 나오면 그걸 토대로 길 찾기를 하면 됩니다.

 

 

 

10개를 실시간으로 돌리는 모습

 

 

 

 

 

astar

jps

 

100x100 기준으로 한번 돌려봤습니다.

 

jps가 더 ms가 높은데 동시에 실행시키는 부분도 있고 , 벽을 많이 안 깔아 놓은 부분도 있고

실시간으로 움직이는 플레이어 충돌처리를 확인하려고 한번 실행 시 확인하는 타일에

Physics2D.OverlapCircle함수를 실행시키니까 큰맵이니까 타일 확인을 더 많이 하는 jps가 ms가 좀 더 나오더라구요

100x100 이다보니까 한방향 쭉 돌리면 100번 봐야하고 텅비어있어서 수천타일을 한번에 확인하네요

 

해당 타일이 이동 가능한 구역인지 확인하는 방법을 따로 최적화하는 방법을 찾아야겠습니다.

아니면 움직이지 않는 벽은 미리 배열에다가 넣고 확인하면 될 거 같고 움직이는 플레이어나 벽은 어쩔 수 없이 확인해야 할 거 같기도 하고 좀 더 공부를 해야겠네요

 

 

 

깃허브 주소 : https://github.com/wolstar415/Unity_Pathfinding-Algorithm