CSC 155 Final Assignment Due Tuesday 5/16 For the final assignment, you need to implement the A* algorithm as described in the handout I gave you. A* is acutally a more general AI algorithm that is applied to a special case here. The algorithm is an extension of Dijkstra's single-source shortest path algorithm. However, there is now a destination as well as a source. The "cost" of each choice during the construction of the search tree is determined by the cost back to the source, plus an heuristic estimate as to how much further it will be to the destination. For our problem, the cost of moving to adjacent cells is always one (so there is no need to see if better paths are found to cells that are on the frontier/open list.) The heuristic estimate value is just the strait-line distance to the destination (so the the cost value should be a double instead of int). In order for you to use my graphical program, it must observe the following setup: Basically: You need to: 1. Modify the cell class - perhaps add additional variables and methods 2. Implement the Astar procedure, which will construct a path by setting the "prev" pointers in cell objects. 3. Run my graphical test program: g++ pathfinder.cpp -o pathfinder `pkg-config gtkmm-2.0 --cflags --libs` ./pathfinder 45 (command-line arg seeds random number generator) -------------------------------------------------------- Planning Session In order to organize our thinking about how to write the program, please answer the following questions, then write in pseudocode the program you're going to follow. 0. Do you want the character to move in 4 or 8 possible directions? 1. How to compute the cost of each node. Are you going to add a variable to the cell class, or compute it on the fly using a method, or some combination of both. Careful: the cost needs to be double. Write out the prototype of the function that will calculate the cost of each node. You also have to decide where to put this function ( in cell or playground class). 2. In algorithm A*, what kind of data structure are you going to use to implemet the Interior (closed) list. What operations will you need to perform on this structure (lookup, insert/delete, verify existence, etc). 3. What about the Frontier (open) list. Since you need to take out the element with the least cost, I recommend that you consider using a heap data structure (I'm giving you a polymorphic class). However, you need to implement the comparator class very carefully. In particular (watch out!) the "eq" function should return pointer equality, not equality in cost!. And the "le" function should reverse "<" to ">" since technically in a heap data structure the *largest* element is always at the root. ----------- Please turn in written answers to these questions as part of assigment. Attendance is required during the scheduled final exam time to demonstrate your programs.