A Project on Any-Angle Path-Planning for Computer Games
for "Introduction to Artificial Intelligence" Classes

Sven Koenig, Kenny Daniel, Alex Nash
Department of Computer Science
University of Southern California
{skoenig,kfdaniel,anash}@ usc.edu

Summary This standalone path-planning project for an undergraduate or graduate artificial intelligence class is part of our effort to motivate students via computer games. This project allows students to implement computer game technologies without having to use complex game engines. Heuristic search and, in particular, A* are among the most widely used search techniques and thus are good candidates for artificial intelligence projects. In this project, the students need to code A* and then extend it to Theta*. Theta* is an any-angle path-planning algorithm which plans paths for game characters in known gridworlds. Theta*, like A*, propagates information along the edges of the gridworld (to achieve a short runtime) but, unlike A*, does not constrain paths to be formed by grid edges (to find short "any-angle" paths). This project requires that students develop a thorough understanding of A* and heuristics in order to answer questions that are not yet covered in textbooks. For example, Theta* and A* have many different properties despite their similarities. Exploring the differences between Theta* and A* helps students to improve their understanding of A*. The project is versatile since it allows for both theoretical and implementation questions. We list a variety of possible project choices, including easy and hard questions. The project text and additional support material (such as pointers to the literature) can be found at http://idm-lab.org/gameai.
Topics Search; Heuristic Search; Any-Angle Heuristic Search; Computer Games; Path Planning
Audience The intended audience of this assignment is students in an undergraduate or graduate artificial intelligence class. It is well-suited for two different kinds of audience: those who want to understand A* and those who want to learn about recently proposed extensions of A*.
Difficulty This project is versatile since it allows for both theoretical and implementation questions. The difficulty level of the implementation questions is comparable to implementing A*. The difficulty level of the theoretical questions varies from easy to hard. We recommend that instructors give the students at least two weeks to complete the assignment.
Strengths
  • Instructors can easily incorporate this assignment in their course syllabus since it extends a commonly taught algorithm, namely A*.
  • Instructors can tailor the difficulty of this assignment by choosing questions from a pool of questions with varying levels of difficulty.
  • This assignment is inspired by computer games, which we believe motivate and interest students.
  • This assignment exposes students to recent research results, namely Theta*.
  • Students cannot search for answers to the questions in this assignment on the web since the questions are not in standard textbooks.
Weaknesses
  • Some of the implementation questions of the assignment are esssential to the project, and thus instructors unfortunately cannot tailor their difficulty.
  • No sample solutions are available.
Dependencies
  • This assignment requires that the students understand A*. The assignment briefly re-introduces A* in two pages and contains many examples to help students understand this assignment.
  • This assignment requires that the students be familiar with a programming language since they need to code A* and extend it. However, it is language and platform independent.
Variants Instructors can vary the assignment as follows:
  • Choose different questions from a pool of questions with varying levels of difficulty.
  • Create and use different randomly generated input files.
  • Extend the assignment by choosing one of the three extra credit questions.
Links