CSC17 Final Programming Assignment. Due at Scheduled Final Exam Time 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 will 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 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. 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. coord(int a, int b) {y=a; x=b;} public boolean equals(coord c) // two coords are same if x,y's are same { 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. * cost should represent dist + estimated distance to the target, which should just be the euclidean distance (function provided in astar). * 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. * 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. YOU MAY NEED TO REVERSE THE DEFINITION. 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. In my implementation, I used an ArrayList to represent the interior and a priority heap (heap) to represent the Frontier. You can choose different structures but 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. For convenience you may decide to use an ArrayList for both structures, but you will have to define a separate method that deletes the coord with the lowest cost. ****** 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 is returned if there is no possible path. --------------------------------------------------------------------------- Pseudocode outline: Given: int M[ROWS][COLS] representing the map. The value of M[i][j] either OPEN or WATER coord search(int sy, int sx, int ty, int tx) { coord current; create interior and frontier structures. 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 insert it to interior. for each neighbor north south east west of current: add neighbor to frontier (and calculate cost, dist) if it's not already in either frontier or interior, and if it's OPEN (water is impassable). For example, if current have 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 && neighbor is not on frontier ) { set neighbor.dist as 1 + 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 } -------------------------------------------- EXTRA CREDIT OPTIONS: The above description is the MINIMUM requirement of the assignment. There's only two type of terrain: OPEN and WATER. Furthermore, the cost or distance between adjacent coordinates is always one. This means that you won't have to replace an existing value on the Frontier with a better-cost option - you just need to check if a coordinate is already on the frontier. There are ROWS*COLS number of cells in the 2D matrix. Correspondingly, the sizes of the Frontier and Interior data strucutures can become very large. For each neighbor node being processed, we need to check if it's on the interior or frontier list. This can be costly. In fact, the algorithm as described above runs in O(n*n*n) time. But Dijkstra's algorithm should run in O(n*n) time. We can achive this optimization be using a variable at each matrix coordinate that records the status of that coordinate as either NEW (UNSEEN), FRONTIER, or INTERIOR. (constants 0,1,2 would do fine). We can then check or change the value of these variables directly, without having to search through the frontier/interior data structures. The Interior data structure can be completely avoided under this scheme. You still need a data structure for the Frontier however, since you still need the ability to find the *best* node on the frontier. But you nolonger need to search the frontier to see if a node is already on the frontier. One way to implement this optimization is to use a 3-dimension array: int M[][][]; ... M = new M[ROWS][COLS][2]; That is, at each coordinate y,x, M[y][x][0] will hold the terrain value (WATER, OPEN, etc...) while M[y][x][1] will hold the status (NEW, FRONTIER or INTERIOR). You will have to change all current references to M[a][b] to M[a][b][0] in BOTH astar.java and in pathfinder.java (and in alligator.java), but this isn't hard. Alternatively, you can leave M a 2-D array and use a parallel status array: int Status[][]; ---------------------------------------------- For more 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.