TRANSIT routing on video game maps

Leonid Antsfeld, Daniel Harabor, Toby Walsh

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearch

14 Citations (Scopus)


TRANSIT (Bast, Funke, and Matijevic 2006) is a fast and optimal technique for computing shortest path costs in road networks. It is attractive for its usually modest memory requirements and impressive running times. In this paper we give a first analysis of TRANSIT routing on a set of popular grid-based video-game benchmarks taken from the AI pathfinding literature. We show that in the presence of path symmetries, which are inherent to most grids but normally not road networks, TRANSIT is strongly and negatively impacted, both in terms of performance and memory requirements. We address this problem by developing a new general symmetry breaking technique which adds small random ε- values to edges in the search graph, reducing the size of the TRANSIT network by up to 4 times while preserving optimality. Using our enhancements TRANSIT achieves up to four orders of magnitude speed improvement vs. A* search and uses in many cases only a small (≤ 10MB) or modest (≤ 50MB) amount of memory. We also compare TRANSIT with CPDs, a recent and very fast database-driven pathfinding approach. We find the algorithms have complementary strengths but also identify a class of problems for which TRANSIT is up to two orders of magnitude faster than CPDs using a comparable amount of memory.

Original languageEnglish
Title of host publicationProceedings of the 8th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2012
Subtitle of host publicationOctober 8–12, 2012, Stanford, California
EditorsMark Riedl, Gita Sukthankar
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages6
ISBN (Print)9781577355823
Publication statusPublished - 2012
Externally publishedYes
EventAAAI Conference on Artificial Intelligence and Interactive Digital Entertainment 2012 - Stanford, United States of America
Duration: 8 Oct 201212 Oct 2012
Conference number: 8th (Proceedings)


ConferenceAAAI Conference on Artificial Intelligence and Interactive Digital Entertainment 2012
Abbreviated titleAIIDE 2012
CountryUnited States of America
Internet address

Cite this