컴퓨터 게임 환경에서 일반화 가시성 그래프를 이용한 경로찾기

• 영문명: Path-finding by using generalized visibility graphs in computer game environments
• 발행기관: 한국시뮬레이션학회
• 저자명: 유견아(Kyeonah Yu) 전현주(Hyunjoo Jeon)
• 간행물 정보: 『한국시뮬레이션학회 논문지』제14권 제3호, 21~31쪽, 전체 11쪽
• 주제분류: 공학 > 기타공학
• 파일형태: PDF
• 발행일자: 2005.09.30

영문 초록

In state-of-the-art games, characters can move in a goal-directed manner so that they can move to the goal position without colliding obstacles. Many path-finding methods have been proposed and implemented for these characters and most of them use the A* search algorithm. When the map is represented with a regular grid of squares or a navigation mesh, it often takes a long time for the A* to search the state space because the number of cells used in the grid or the mesh increases for higher resolution. Moreover the A* search on the grid often causes a zigzag effect, which is not optimal and realistic. In this paper we propose to use visibility graphs to improve the search time by reducing the search space and to find the optimal path. We also propose a method of taking into account the size of moving characters in the phase of planning to prevent them from colliding with obstacles as they move. Simulation results show that the proposed method performs better than the grid-based A* algorithm in terms of the search time and space and that the resulting paths are more realistic.

목차

1. 서론

2. 관련 연구

3. 일반화 가시성 그래프(Generalized Visibility Graph, GVgraph)

4. 구현 및 시뮬레이션

5. 결론

참고문헌

키워드

Game path-finding visibility graph grid-based A* algorithm configuration space