Breaking path symmetries on 4-connected grid maps

Daniel Harabor, Adi Botea

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

28 Citations (Scopus)

Abstract

Pathfinding systems that operate on regular grids are common in the AI literature and often used in real-Time video games. Typical speed-up enhancements include reducing the size of the search space using abstraction, and building more informed heuristics. Though effective each of these strategies has shortcomings. For example, pathfinding with abstraction usually involves trading away optimality for speed. Meanwhile, improving on the accuracy of the well known Manhattan heuristic usually requires significant extra memory. We present a different kind of speedup technique based on the idea of identifying and eliminating symmetric path segments in 4-connected grid maps (which allow straight but not diagonal movement). Our method identifies rectangular rooms with no obstacles and prunes all interior nodes, leaving only a boundary perimeter. This process eliminates many symmetric path segments and results in grid maps which are often much smaller and consequently much faster to search than the original. We evaluate our technique on a range of different grid maps including a well known set from the popular video game Baldur's Gate II. On our test data, A* can run up to 3.5 times faster on average. We achieve this without using any significant extra memory or sacrificing solution optimality.

Original languageEnglish
Title of host publicationAAAI Conference on Artificial Intelligence for Interactive Digital Entertainment
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages33-38
Number of pages6
ISBN (Print)9781577354789
Publication statusPublished - 2010
Externally publishedYes
EventAAAI Conference on Artificial Intelligence and Interactive Digital Entertainment 2010 - Stanford, United States of America
Duration: 11 Oct 201013 Oct 2010
Conference number: 6th

Conference

ConferenceAAAI Conference on Artificial Intelligence and Interactive Digital Entertainment 2010
Abbreviated titleAIIDE 2010
Country/TerritoryUnited States of America
CityStanford
Period11/10/1013/10/10

Cite this