Primary supervisor
Daniel HaraborPathfinding 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
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.
URLs/references
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.