그리드 기반 맵에서 꼭지점 정보를 이용한 휴리스틱의 설계 (Design of Heuristics Using Vertex Information in a Grid-based Map)

서지정보

· 발행기관 : 한국컴퓨터정보학회
· 수록지 정보 : 한국컴퓨터정보학회논문지 / 20권 / 1호 / 85 ~ 92페이지
· 저자명 : 김지혜, 정예원, 유견아

초록

컴퓨터 게임 배경이 정교하게 표현되면서 그리드 기반으로 표현된 게임 맵에서 A* 알고리즘을 이용한 경로 찾기는 전체 게임 성능을 저해하는 요인이 되고 있다. 셀 단위의 세밀한 표현으로 상태 공간이 커져 탐색 시간이 증가하기 때문이다. 본 논문에서는 정규 그리드로 표현된 컴퓨터 게임 배경을 꼭지점 리스트로 된 다각형 기반 맵으로 변환하고 다각형의 꼭지점에 대한 가시성 정보를 이용하여 효율적인 경로 찾기가 가능하게 하는 방법을 제안한다. 다각형 기반 맵으로의 변환은 오프라인으로 전처리하여 실시간 쿼리에는 영향을 미치지 않도록 하며 꼭지점의 가시성정보를 이용하는 휴리스틱을 설계함으로서 추정의 정확도를 높여 경로 탐색 시에 방문하는 노드수를 획기적으로 감소시키도록 한다. 시뮬레이션에서는 제안한 방법들이 그리드 기반 방식의 장점을 유지하면서 탐색 공간과 탐색 시간을 효율적으로 감소시킴을 확인한다.

영어초록

As computer game maps get more elaborate, path-finding by using A* algorithm in grid-based gamemaps becomes bottlenecks of the overall game performance. It is because the search space becomes largeas the number of nodes increases with detailed representation in cells. In this paper we propose anefficient pathfinding method in which the computer game maps in a regular grid is converted into thepolygon-based representation of the list of vertices and then the visibility information about vertices ofpolygons can be utilized. The conversion to the polygon-based map does not give any effect to thereal-time query process because it is preprocessed offline. The number of visited nodes during search can be reduced dramatically by designing heuristics using visibility information of vertices that make theaccuracy of the estimation enhanced. Through simulations, we show that the proposed methods reduce thesearch space and the search time effectively while maintaining the advantages of the grid-based method.

참고자료

· 없음