UCT CS Research Document Archive

Efficient path finding for 2D tile-based games

Mapaila, Masilo (2012) Efficient path finding for 2D tile-based games. Technical Report CS12-08-00, Department of Computer Science, University of Cape Town.

Full text available as:
PDF - Requires Adobe Acrobat Reader or other PDF viewer.

Abstract

In this paper we investigate different heuristics used in an A* (A Star) algorithm. This algorithm can be used to achieve efficient path finding within tile-based games. Path finding is a computationally expensive problem that is solved by searching. We investigate different optimisation techniques and further develop techniques which can be incorporated within the existing algorithm. These techniques make path finding for 2D static and dynamic environments faster with less use of memory.

EPrint Type:Departmental Technical Report
Keywords:pathfinding, A*, astar, path searching, heuristics, path, AI,
artificial intelligence
Subjects:I Computing Methodologies: I.2 ARTIFICIAL INTELLIGENCE
ID Code:815
Deposited By:Mapaila, Masilo
Deposited On:31 October 2012