A* shortest-path finder
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
Solution?
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).
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).