Efficient path finding for 2D tile-based games

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

[img] PDF

Download (368kB)


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.

Item Type: Technical report
Uncontrolled Keywords: pathfinding, A*, astar, path searching, heuristics, path, AI, artificial intelligence
Subjects: Computing methodologies > Artificial intelligence
Date Deposited: 31 Oct 2012
Last Modified: 10 Oct 2019 15:33
URI: http://pubs.cs.uct.ac.za/id/eprint/815

Actions (login required)

View Item View Item