KJCKorea
Journal Central

@article{ART001958401},
author={김지혜 and 정예원 and Kyeonah Yu},
title={Design of Heuristics Using Vertex Information in a Grid-based Map},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2015},
volume={20},
number={1},
pages={85-92}

TY - JOUR
AU - 김지혜
AU - 정예원
AU - Kyeonah Yu
TI - Design of Heuristics Using Vertex Information in a Grid-based Map
JO - Journal of The Korea Society of Computer and Information
PY - 2015
VL - 20
IS - 1
PB - The Korean Society Of Computer And Information
SP - 85
EP - 92
SN - 1598-849X
AB - 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.
KW - Path-finding;Heuristics for A* algorithm;Grid-based maps
DO -
UR -
ER -

김지혜, 정예원 and Kyeonah Yu. (2015). Design of Heuristics Using Vertex Information in a Grid-based Map. Journal of The Korea Society of Computer and Information, 20(1), 85-92.

김지혜, 정예원 and Kyeonah Yu. 2015, "Design of Heuristics Using Vertex Information in a Grid-based Map", Journal of The Korea Society of Computer and Information, vol.20, no.1 pp.85-92.

김지혜, 정예원, Kyeonah Yu "Design of Heuristics Using Vertex Information in a Grid-based Map" Journal of The Korea Society of Computer and Information 20.1 pp.85-92 (2015) : 85.

김지혜, 정예원, Kyeonah Yu. Design of Heuristics Using Vertex Information in a Grid-based Map. 2015; 20(1), 85-92.

김지혜, 정예원 and Kyeonah Yu. "Design of Heuristics Using Vertex Information in a Grid-based Map" Journal of The Korea Society of Computer and Information 20, no.1 (2015) : 85-92.

김지혜; 정예원; Kyeonah Yu. Design of Heuristics Using Vertex Information in a Grid-based Map. Journal of The Korea Society of Computer and Information, 20(1), 85-92.

김지혜; 정예원; Kyeonah Yu. Design of Heuristics Using Vertex Information in a Grid-based Map. Journal of The Korea Society of Computer and Information. 2015; 20(1) 85-92.

김지혜, 정예원, Kyeonah Yu. Design of Heuristics Using Vertex Information in a Grid-based Map. 2015; 20(1), 85-92.

김지혜, 정예원 and Kyeonah Yu. "Design of Heuristics Using Vertex Information in a Grid-based Map" Journal of The Korea Society of Computer and Information 20, no.1 (2015) : 85-92.