Memory-Efficient Abstractions for Pathfinding

Nathan R. Sturtevant

From an academic perspective there has been a lot of work on using state abstraction to speed path planning. But, this work often does not directly address the needs of the game development community, specifically for mechanisms that will fit the limited memory budget of most commercial games. In this paper we bring together several related pieces of work on using abstraction for pathfinding, showing how the ideas can be implemented using a minimal amount of memory. Our techniques use about 3% additional storage to compute complete paths up to 100 times faster than A*.

Subjects: 15.7 Search 1. Applications

Submitted: Mar 27, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.