길찾기

이미지 없음

길찾기

전략 시물레이션은 길찾기 알고리즘으로 시작한다고 해도 과언이 아니다.
전략시물레이션의 특성상 실시간 정보를 바탕으로 길을 찾고자 하는데,
그중에서 JPS는 놀라운 성능을 내지만, JPS 만으로도 1024x1024 크기의 미로형태의 맵에서는 성능이 만족스럽지 않았다.
물론 hierarchical A* 등등을 말하고 있지만 그렇게 지형을 구조적으로 관리하지 않고 직접 A* 알고리즘처럼 찾고 싶었고, 꼭 구현하고 싶었다. 
수많은 알고리즘을 R&D 하였고 JPS의 다른형태들을 합성하기 시작하였다.

Boundary Lookup JPS + Block-basedSymmetryBreaking JPS 알고리즘의 합성으로 완성을 하였다.
1024x1024 이상 훨씬 큰 맵에서도 A* 알고리즘에서 5초정도의 길찾기 시도가 3 ms 이내로 줄어들었고, 일반적인 길찾기는 1ms 미만의 거의 미미한 시간이 걸리게되었다. 
이 알고리즘의 완성으로 전략시뮬레이션 및 전쟁게임의 이동라인및 이동시간연산에도 사용이되어지며, 기존의 AI 및 길찾기를 위한 지형저장관리와 구조들을 제거하게 되었다.