Skip to main content

Pathfinding for Games

Primary supervisor

Daniel Harabor

Pathfinding is fundamental operation in video game AI: virtual characters need to move from location A to location B in order to explore their environment, gather resources or otherwise coordinate themselves in the course of play. Though simple in principle such problems are surprisingly challenging for game developers: paths should be short and appear realistic but they must be computed very quickly, usually with limited CPU resources and using only small amounts of memory.

Student cohort

Single Semester
Double Semester

Aim/outline

In this project you will develop new and efficient pathfinding techniques for game characters operating in a 2D grid environment. There are many possibilities for you to explore. For example, you might choose to investigate a class of "symmetry breaking" pathfinding techniques which speed up search by eliminating equivalent (and thus redundant) alternative paths. Another possibility involves dynamic settings where the grid world changes (e.g. an open door becomes closed) and characters must re-plan their routes. A third possibility is multi-agent pathfinding such as cooperative settings where groups of characters move at the same time or where one character tries to evade another. Successful projects may lead to publication and/or entry to the annual Grid-based Path Planning Competition.

Required knowledge

Students interested in this project should be enthusiastic about programming. They should also have some understanding of AI Search and exposure to the C and/or C++ programming language.