---
title: "Comparison of Different Grid Abstractions for Pathfinding on Maps"
authors:
  - "Yngvi Björnsson"
  - "Markus Enzenberger"
  - "Robert C. Holte"
  - "Jonathan Schaeffer"
  - "Peter Yap"
doi: ""
url: "https://ijcai.org/proceedings/2003/254"
pdf: "https://ijcai.org/proceedings/2003/0254.pdf"
venue: "Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence"
year: 2003
pages: "1511-1511"
track: ""
keywords:
---

# Comparison of Different Grid Abstractions for Pathfinding on Maps

Yngvi Björnsson, Markus Enzenberger, Robert C. Holte, Jonathan Schaeffer, Peter Yap

*Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence*, pages 1511-1511.

## Abstract

Pathfinding on a map is a fundamental problem in many applications, including robotics and computer games. Typically a grid is superimposed over the map where each cell in the grid forms a unique state. A state-space-based search algorithm, such as A* or IDA* , is then used for finding the optimal (shortest) path. In this paper we analyze the search behavior of both A* and IDA* using different grid representations, providing various new insights via analytical and empirical results.