CSC17 Final Programming Assignment. Due Tuesday December 9th, 2014 (ABSOLUTE) You are to implement the A* search algorithm as described in class and in the handout. I've provided you with enough code so you can concentrate on the basic algorithm. First, download all relevant files, including animated gifs from the homepage. Examine the files astar.java and coord.java carefully. 1. In the astar class, code has already been written to generate a random map. There are also other functions you might find useful. STUDY THEM. The map is represented by a 2D array int[][] M. There are ROWS rows and COLS columns. The value of each array element represents a terrain type. For the this assignment, the values is either 0 for OPEN and 3 for WATER. You are to write a subclass myastar extends astar. A template has been created in myastar.java. You must call the subclass myastar because that's referred to in patherfinder.java, which contains main (run the program with java pathfinder). In your myastar class you need to override the "search" method in astar.java. This method should find the best path from the source coordinate sy,sx to the destination ty,tx. It will return a "coord" object representing the path (see below). It returns null if there is no possible path. ****************** CHOICE ********************* For this assignment you have the choice of either making water completely impassable, or giving it a higher cost than OPEN land. HOWEVER, if you give it a cost value, you must be able to change the value as a simple parameter. Hint: in astar.java you see that there are predefined constants for each type of terrain (only two are used in my basic version). You can define: int[] CostOf = {1,0,0,8}; // open field has cost of 1 and water has cost 8 2. coord.java defines the coord class, which represents "nodes" in our search tree. Study this class CAREFULLY: public class coord implements Comparable { int y, x; int cost; // estimated cost, including heuristic int dist; // distance from source node coord prev; // pointer to previous coordinate on path (forms tree) coord(int a, int b) {y=a; x=b;} public boolean equals(Object oc) // conforms to old java specs { if (oc==null || !(oc instanceof coord)) return false; coord c = (coord)oc; return (x==c.x && y==c.y); } public int compareTo(coord c) // compares cost { return c.cost - cost; // note: reverses relationship } } // coord * y,x are represents a current map coordinate * .dist should represent the distance of the coord (y,x) from the source. This value DOES incorporate the terrain cost: if you are two water sectors away from the source, the dist value will be 16 (if each water costs 8). * .cost should represent dist + estimated distance to the target. The estimated distance can just be the discrete distance (see ddist function in astar class). However, if you want the figure to move in more than 4 directions, you should use the Euclidean distance function. * .prev points to the previous coord object, towards the root. When your "search" function returns a coord object, we can follow the "prev" pointers back to the origin. **** * equals(coord c): this method overrides the equals method of "Object". Two coord objects are equal if their x,y coordinates are equal. This is useful if you use another data structure such as a TreeSet or ArrayList. * compareTo(coord c): this method implements the interface Comparable. It compares the cost (exact distance to source + estimated distance to target) between this and c. NOTE THAT it returns a positive value if c.cost is greater than this.cost, so it will actually sort in REVERSE order. This is because of the way I defined the "heap" data structure. This will allow a heap to have the SMALLEST value on top. NOTE ALSO that this function is not compatible with equals: A.compareTo(B)==0 if coords A and B have the same cost measure, but A.equals(B)==true if A, B have the same x,y values. * constructor simply initializes object with y,x coords (in that order). ------------------------------ To write the search function. You need to first decide what data structures should be used to represent the Interior and Frontier regions of the search tree. Keep in mind the following: a. You need to be able to add new coords to each structure b. You need to check if there's already a coord with values y,x in both strucutures (using the "equals" method defined above). c. You need to be able to locate and delete the item with the lowest cost value from the Frontier list. Using a simple linked list (ArrayList) is not recommended (why?). The recommended way is to do the following: 1. Define a parallel array coord[][] that points to coord objects that you've created. That way, given a y,x coordinate you can immediately determine if there's already a coord object for it (it will be null if there is no object). Each coord object has a status variable indicating whether it's open (frontier) or closed (interior), with default open. 2. Use a Priority Heap (pheap) to represent the coordinates on the frontier (open) list. This will give us O(log n) operation. Thus, the interior is only represented by those coordinates with status set to the interior: there's no need to traverse any structure. The frontier is represented by a combination of the Status array and the priority heap: to determine if a coord is in the frontier we only need to consult the Status array, but to insert and take the top element, we use the heap. ****** The coord object that the search function should return should be the last node generated in your search tree, that is, a node that represents the target coordinate: y==ty, x==tx. The prev pointer will indicate the path to take. null should be returned if there is no possible path. --------------------------------------------------------------------------- Pseudocode outline: Given: int M[ROWS][COLS] representing the map. // do not redefine this! The value of M[i][j] either OPEN or WATER coord search(int sy, int sx, int ty, int tx) { coord current; setup interior and frontier representations insert new coord(sy,sx) which is the start node into the frontier set boolean var stop to false; this controls when loop should exit. while (!stop and fontier is not empty) { set current to frontier coord with lowest cost delete current from fontier and move it to interior. for each neighbor north south east west of current: add neighbor to frontier (and calculate dist and cost) if it's not already in either frontier or interior, and if it's OPEN if water is impassable. For example, if current has coordiates i, j, then the NORTH neighbor will be at M[i-1][j], so you'll have code that looks like: coord neighbor = new coord(i-1,j); if ( i>0 && M[i-1][j]== OPEN && neighbor is not on interior or frontier ) { set neighbor.dist as (cost of terrain) + current.dist calculate neighbor.cost using neighbor.dist and heuristic. set neighbor.prev to current to record path followed add neighbor to the frontier. if i==ty and j==tx, then target found, so set stop to true. } } // while } // THIS PSEUDOCODE DOES NOT IMPLEMENT FULL A* - for that, if a node is already // on the frontier, you'll need to compare its cost value with the cost of // the new route that you've just found. -------------------------------------------- For EXTRA CREDIT, you must modify the program to include all four types of terrain (OPEN, FOREST, DESERT, WATER). Each type of terrain should have a different cost, but each is passable at some cost. In other words, you need to implement Dijkstra's algorithm in full: including replacing an entry on the Frontier with one of better cost value. This option will also require you to rewrite the code that generates a random map since you'll have different types of terrain. You'll also need to extend some of the graphics code in pathfinder.java. In particular, you should understand the way that the vectors "imageof" and "imagechar" works. Find your own appropriate gifs.