The Effective Pathfinding Algorithm for Gaming Maps Using Systemized Iterative Deepening A
Abhilash Sreeramaneni · The Journal of Korean Institute of Information Technology · 2015
IDA* 알고리즘은 상태공간 탐색 문제의 다양성을 위한 상태공간과 시간에 대해 유용하지만, 그러나 검색트리의 좌-우 탐색의 노드의 반복적인 방문의 탐색 공간에서 CPU 사이클 타임의 문제가 있다. 이의 해결을 위해 플린지 탐색 알고리즘을 사용한다. 이것은 A*나 IDA*와 같은 반복처리를 하지만, 현재의 반복처리에 관련이 없는 노드 방문의 결점이 있다. 본 논문에서, 플린지 탐색 알고리즘과 A* 알고리즘의 특성을 갖지만 플린지 알고리즘의 단점을 교정하여 시스템화 된 알고리즘인 SIDA*를 제안한다. 게이밍 맵 응용에서, 정적 곳선 트랙에서 회피를 위하여 곡률 반경 정보를 추가하여 사고 우발적인 장해물을 위한 온 트랙 전략을 적용한다. 실험결과로 카 레이싱 게임에서 다른 알고리즘에 비해 빠른 처리를 보였고, 우발적인 장해물 회피를 위해 본 논문에서 제안한 온 트랙 전략이 효과적임을 보였다. 장벽이 있는 경우와 없는 경우의 두 가지 플랫폼에 대한 실험결과 A*알고리즘에 비하여 종합적으로 15%, 35%의 성능향상을 보였다.