<-- Back to the main page

A* shortest-path finder

Screenshot of A* solution with proximity heuristic (click for full-size) The same basic framework that I use in my CS2 course as an example of interacting classes and data structure choice serves as a lovely starting point for a discussion of search heuristics and the A* algorithm in an introduction to AI or CS262c-type course. I present a complete solution to the CS2 version as a starting point for this one, partly because most (but not all) of my students will have done that assignment already in CS2; but also to keep the length of the project a little shorter and give me time for other things. (Also, it gives them some practice reading code, which is always a good thing.) It would be easy enough to fold that in, though, and at this level, the students should be able to build it quickly enough anyway).

The screenshot (click to enlarge) is of my reference implementation that has found a path using the "proximity" heuristic---which evaluates to the Manhattan distance to the target if that is less than 8, or 8 otherwise. This simulates a robot or whatever that doesn't know what direction the target is or how far away it is until it gets relatively close to it. Note that the displayed grid is an important test case: an incorrectly-implemented A* will find the (slightly longer) path that first goes straight down and then hooks around the bottom leg of the L.

Assignment materials


This page is too easily googlable, so I don't want to post it here, but I'm happy to email the solution to any CS teacher. Just email me at dblaheta@knox.edu. Preferably, email from your school email account, and if possible include a link to some official school website that includes your name on faculty/staff (so I can verify that this is on the up-and-up).