A* 알고리즘은 잘 알려진 길찾기 알고리즘이다. 그러나 많은 상호 작용이 있거나 많은 장애물들이 있는 맵에서 A* 알고리즘을 실시간에 사용하는데 한계가 있을 수 있다. 그래서 게임에서는 최단의 경로를 찾는 대신에 게임 플레이어에게 자연스럽게 보이는 경로를 빠르게 찾을 필요가 있다. 본 논문에서는 경로 정보를 사용하는 새로운 휴리스틱 함수를 제안하고, 제안한 휴리스틱 함수를 이용한 길찾기 알고리즘이 다양한 그리드 맵에서 A* 알고리즘보다 상당히 빠르게 경로를 찾을 수 있다는 것을 보여준다.

A* algorithm is a well known pathfinding algorithm. However, there may be a limit to use A* algorithm in real-time in a map where many interactions occur between objects or many obstacles exist. Therefore, it may be necessary to find a naturally looking path quickly instead of finding a shortest path in games. In this paper, we propose a new heuristic function to exploit path information in a map. We also show that the pathfinding algorithm based on the proposed heuristic function can find a good path much faster than A* algorithm on several grid maps.

• 조성현 | Cho, Sung Hyun