Abstract
This study evaluates the impact of grid topologies—specifically tiles, octiles, hexes, and a novel square-based hex representation called "texes"—on the performance of pathfinding algorithms such as A and IDA. By analyzing branching factors and search depths across synthetic and real-world game maps, the research identifies that octile grids (8-way squares) frequently offer the highest efficiency for A* searches on realistic terrains. The findings suggest that while hexagonal grids offer theoretical advantages, implementation details and map characteristics significantly shift the optimal choice for developers.
Introduction
Pathfinding is a fundamental computational challenge in robotics and video games, particularly in Real-Time Strategy (RTS) and Role-Playing Game (RPG) genres. Most implementations superimpose a grid over a map to discretize the search space, using algorithms like A* to find the shortest path. However, the choice of grid topology significantly influences the "branching factor" (the number of nodes expanded at each step) and the "search depth" (the number of steps to the goal). This paper provides a systematic comparison of these abstractions to determine the most efficient configurations for common search algorithms.
Grid Topologies
The researchers compared four distinct grid topologies, each offering different trade-offs between movement naturalism and memory efficiency:
- Tiles: Standard 4-way square movement (North, South, East, West).
- Octiles: 8-way square movement, including diagonals.
- Hexes: 6-way movement on a hexagonal grid, offering more equidistant neighbors than 4-way tiles.
- Texes: A novel "square-based" representation of a hexagonal grid. This allows developers to leverage the mathematical benefits of hex grids while maintaining the efficient memory layout of a standard square array.
Search Optimizations and Branching Factors
A critical contribution of this work is the application of the "Parent-Neighbor" optimization. When moving from a "last" node to a "current" node, neighbors shared by both nodes do not need to be expanded. In unit-cost terrain, it is always more efficient (or equal) to have reached those shared neighbors directly from the "last" node.
This optimization significantly reduces the effective branching factor. For hexes and texes, the factor drops to 3 (matching 4-way tiles), despite having more adjacent cells. For octiles, the effective branching factor drops to approximately 4.2. Additionally, topology affects search depth; a hex grid reduces search depth to 81% of a tile grid's depth for the same physical distance, while an octile grid reduces it to roughly 71%.
Experimental Methodology
The study utilized a robust testing framework across three map categories:
- Obstacle-free maps: To establish a theoretical baseline.
- Randomly placed obstacles: A standard synthetic benchmark.
- Real-world game maps: 120 maps extracted from the classic RPG Baldur’s Gate II by BioWare.
The researchers conducted 48,000 searches across these maps (sizes ranging from 50x50 to 300x300) using A and a memory-enhanced version of IDA (Iterative Deepening A*) that utilizes a simplified transposition table to avoid redundant state searches.
Results and Analysis
The experimental results revealed distinct winners depending on the algorithm used. For A*, octile grids expanded the fewest nodes across all map types, making 8-way square movement the superior choice for standard implementations.
Surprisingly, while hex/tex grids are theoretically better for standard IDA, the memory-enhanced IDA performed best on simple tile grids. A significant finding was the performance gap between synthetic and real-world maps. IDA expanded an order of magnitude more nodes on Baldur’s Gate II maps than on random maps, highlighting the limitations of synthetic benchmarks for game development. While IDA expands more nodes than A*, its lower overhead per node made it faster in total run-time on simpler maps.
Conclusion
While hexagonal grids offer theoretical advantages for certain search algorithms, octile grids prove most efficient for A* on realistic game maps. The "Tex" representation provides a valuable implementation bridge for developers seeking hex-like movement on square memory structures. Future work should address the impact of variable terrain costs and more complex heuristics on these findings, as the current study assumes uniform unit costs.
Summary updated