Bikramjit Banerjee's Publications

• Selected Publications • All Sorted by Date • All Classified by Publication Type •

Fast A* with iterative resolution for navigation

Kyle Walsh and Bikramjit Banerjee. Fast A* with iterative resolution for navigation. International Journal on Artificial Intelligence Tools, 19(1):101–119, World Scientific Publishing, 2010.

Download

[PDF] 

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*.

BibTeX

@Article{Walsh10:Fast,
  author =       {Kyle Walsh and Bikramjit Banerjee},
  title =        {Fast {A}* with iterative resolution for navigation},


  journal =      {International Journal on Artificial Intelligence Tools},
  year =         {2010},
  volume =       {19},
  number =       {1},
  pages =        {101--119},
  publisher = {World Scientific Publishing},
  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*.},
}

---

Generated by bib2html.pl (written by Patrick Riley ) on Sat May 29, 2021 15:48:22