격자-기반 방식으로 표현된 게임에서 경로찾기를 위한 계층적 탐색의 응용 = Appling the Hierarchical Search for Path-Finding in Computer Games Represented in Grid-Based Method

국문 초록 (Abstract)

컴퓨터 게임의 캐릭터, 로봇, 아바타 등의 자율적인 이동을 위해 가장 많이 사용되는 탐색 알고리즘은 인공지능 분야의 A*이다. 최적 경로를 보장하는 성질 때문에 매력적인 경로 찾기 방법이기는 하지만 기본적으로는 오프라인 탐색 방법이므로 실시간으로 움직이는 캐릭터가 한 지점에서 가만히 최소 비용의 경로 계획에 몰두하다가 갑자기 재빠르게 계획된 경로 이동을 실행하는 모습은 자연스럽지 않다. 특히 격자-기반 표현 방식과 같이 많은 격자수 때문에 상태 공간이 커지면 전체 공간에 대해 한번에 최적 경로를 탐색하는 것은 더욱 부자연스럽다. 본 연구에서는 전체에 대해서는 가시점만을 이용하여 대략적인 경로를 찾아내고 가시점들을 서브목표로 하여 격자들의 정보를 이용한 세부 경로 계획을 시행하여 이와 같은 문제를 해결하고자 한다.

목차 (Table of Contents)

• I. 서론
• II. 관련연구
• III. 가사정보를 이용한 계층적 탐색
• IV. 시뮬레이션 및 결과
• V. 결론
• 참고문헌