본문 바로가기
  • Home

Design of Heuristics Using Vertex Information in a Grid-based Map

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2015, 20(1), pp.85-92
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

김지혜 1 정예원 1 Kyeonah Yu 1

1덕성여자대학교

Accredited

ABSTRACT

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.

Citation status

* References for papers published after 2023 are currently being built.