Fast A* With Iterative Resolution for Navigation

Document Type

Article

Publication Date

2-1-2010

Department

Computing

School

Computing Sciences and Computer Engineering

Abstract

We argue that A*, the popular technique for path-finding for NPCs in games, suffers from three limitations that are pertinent to game worlds: ( a) the grid maps often restrict the optimality of the paths, (b) A* paths exhibit wall-hugging behavior, and ( c) optimal paths are more predictable. We present a new algorithm, VRA*, that varies map-resolution as needed, and repeatedly calls A*. We also present an extension of an existing post-smoothing technique, and show that these two techniques together produce more realistic looking paths than A*, that overcome the above limitations, while using significantly less memory and time than A*.

Publication Title

International Journal on Artificial Intelligence Tools

Volume

19

Issue

1

First Page

101

Last Page

119

Link to Full Text

Find in your library

Share

COinS