New Ideas in Pathfinding

Artificial Intelligence and Interactive Entertainment II

Volume

Papers from the 2002 AAAI Spring Symposium

Contents

Pathfinding is a computationally expensive component of many computer games. Typically, a (rectangular) tile grid is superimposed over the region, then some sort of graph search is used to find the optimal path. In this paper, we mathematically prove and empirically show that the hexagonal grid is superior to the conventional tile grid for IDA*. Pathfinding using a hexagonal grid will generate smoother and shorter paths. Furthermore, searching on a hexagonal grid instead of a tile grid will result in exponentially faster searches. Although the hexagonal grid is better than the tile grid in many ways, it is difficult to implement in practise. Consequently, we introduce the tex grid which retains the advantages of a hexagonal grid but is easier to implement.