CSC17 Final Programming Assignment. You are to implement the A* search algorithm on a hexagon grid as described in class. I've provided you with enough code so you can concentrate on the basic algorithm. First, download all relevant files, including gifs and jpeg images from the homepage into a separate folder. Please don't be distracted by the graphics: focus on the algorithm. **You need to understand carefully certain parts of the coord.java file and the astar.java file. 0. myastar.java This is the skeleton class that you need to complete: ALL your code must go into this class (subclass of astar). In particular, you need to @Override public coord search(int sy, int sx, int ty, int tx) 1. astar.java: In the astar class, code has already been written (in the constructor) to generate a random map containing land (grassy texture), water and fire. You shouldn't have to touch this unless you add another type of terrain (see optional challenges). However, it's also possible to load a saved map configuration (see below). These are the structures defined in the astar class that you will inherit in your subclass and will need to refer to: int M[][]; // the map itself, value=terrain type int ROWS, COLS; // size of map in array coords The map is represented by the 2D array M. This array is instantiated in the constructor (do not recreate it). There are ROWS rows and COLS columns. The value of each array element represents a terrain type. For the basic program, the values used are 0 for open land, 3 for water and 2 for fire. Values 1 and others are not currently used. public static int[] DY = Hexagon.DY; public static int[][] DX = Hexagon.DX; Although the map is a 2D array, each array cell is treated as a hexagon which means that it has six immediate neighbors. The Hexagon class (in Hexagon.java) extends java.awt.Polygon, and so inherits everything that can be done with polygons (graphical rendering). The neighbors are designated in order west, northwest, northeast, east, southeast, and southwest. The vector DY defines the row coordinate displacement: so given current row coordinate y, y+DY[5] will give the row coordinate of its southwest neighbor. The column (DX) displacement is more complicated because it's different for even and odd rows. Therefore DX is defined as a 2D int[][] array with two vectors: the first (0th) vector is to be used if the current row number is 0 or even, and the second (1st) vector is to be used if the current row number is odd. For example, if the current row is y and the current column is x, then x+DX[y%2][5] will give the column coordinate of the southwest neighbor. **As usual, you must always check if y,x stay within bounds (ROLS, COLS). The DX and DY vectors are copied into the astar class, and so are also inherited by your class. int[] costof = {1,0,8000,8}; // cost vector public void setcosts(int l, int d, int f, int w) // call to change costs This vector indicates the cost of each type of terrain. This means, for example, that the cost of land is 1 and the cost of water is 8. The cost of going to a map coordinate y,x is costof[M[y][x]]. A cost of -1 means that the terrain type is impassable. With impassable types of terrain there may be no path at all to the destination, in which case your search function must return null. Use the setcosts function to change the values of the vector. public static int hexdist(int y1, int x1, int y2, int x2) {...} This function conservatively estimate the shortest distance between two coordinates in the hexagonal grid. This function can be used to calculate the heuristic estimate that's part of algorithm A*. public coord makeneighbor(coord p, int y, int x, int ty, int tx) This is a convenient function that you might find useful, but you need to study carefully how it works in order to use it in the right way. 2. coord.java. The coord class represents "nodes" in our search tree. Study this class CAREFULLY. You are going to build a "spanning tree" using coord objects. public class coord implements HeapVal { int y, x; int estcost; // total cost, including knowndist and estimate int knowndist; // distance (cost) from source node, excluding estimate boolean interior = false; coord prev; // pointer to previous coordinate on path. coord(int a, int b) {y=a; x=b;} public void copy(coord B) // replace information with those from coord B { // but retain heap index info y = B.y; x = B.x; estcost = B.estcost; knowndist = B.knowndist; interior = B.interior; prev = B.prev; }//copy 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 estcost - c.estcost; } // for HeapVal interface, allows repositioning once estcost changes protected int Hi; // index in heap (for HeapAware interface) public int getIndex() { return Hi; } public void setIndex(int i) { Hi=i; } } // coord It's very important that you understand that: * knowndist represents the cost accumulated so far on the path from the source coord to the current coord (y,x). * estcost should represent knowndist + estimated cost to the target. The suggested way to estimate is to use the hexdist function (in astar class) * 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. * compareTo(coord c): this method implements the interface Comparable. It compares the .estcost between 'this' and c. NOTE ALSO that this function is not compatible with equals: A.compareTo(B)==0 if coords A and B have the same estcost measure, but A.equals(B)==true if A, B have the same x,y values. * interior boolean flag indicates if node belongs to the interior or frontier "lists". * the method 'copy' copies info from a coord object into 'this' object, but does not copy the HeapValue index, so we can change its position in a priority heap that has the ability to 'requeue.' Your search method needs to return a coord object with y,x=ty,tx, and with prev pointers set that leads back to a coord with y,x=sy,sx. ------------------------------ ***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: public coord search(int sy, int sx, int ty, int tx) This method should find an optimal path from the source coordinate sy,sx to the destination ty,tx. It should return a "coord" object with y,x=ty,tx, and with a prev pointer that will lead back to the source (back to the root, which is a coord object with y,x=sy,sx). If there is no path (because some terrain types have cost -1), then the function should return null. My pathfinder program will then use this information to produce the animation. **The animation doesn't run until you have found the entire path. You need to implement the A* algorithm as an O(n*log n) algorithm. To do this you need to select appropriate data structures and know how to use them. Keep in mind that you need to perform the following operations: 1. insert into both interior and frontier "lists" 2. search for items in at least the interior list 3. determine and remove the least estcost element from the frontier list. 4. two coord objects may have the same cost measure (estcost), so your data structure will need to handle *duplicate* values. Here are two data structures that I recommend: 1. A Priority Heap with the ability to reposition entries when their priorities change. You can use my HeapValue interface and BinHeap + FlexQueue implementation, or use your own if you trust it enough. The .requeue(T x) method of my FlexHeap allows a HeapValue-compatible object x inside the heap to be repositioned in O(log n) time. You can call .insert(T x) and .dequeue() on the Heap. However, you will also need to call .changeCmp to change the Comparator because my Heap places the largest value on top, whereas this algorithm requries the smallest value on top. This can be done more easily by calling one of the constructors of FlexQueue with the second argument set to true: FlexQueue Frontier = new FlexQueue(100,true); // 100 is the initial capacity of the queue, true inverts the comparator. 2. Use another array parallel to the array M of terrain types, define a coord[][] Status; Given y,x coordinates, Status[y][x] can be null if this coord was never visited before. If it does point to a coord object, then the boolean variable 'interior' inside the object will tell us if it's on the frontier or interior (since it's not a protected variable, you can access and change it directly: coordobject.interior=true, etc..). This array gives you instantaneous ability to determine if a coordinate is on the frontier, interior, or never seen before. You should use it in conjunction with the priority heap (the coord objects ill be pointed to by both data structure). When you remove the min-cost coord from the Heap, you need to change its status from frontier to interior. --------------------------------------------------------------------------- Pseudocode outline (without modifying coord costs): Given: int M[ROWS][COLS] representing the map. The value of M[i][j] is either OPEN or WATER or FIRE public 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 estcost (poll) move current from fontier to interior. stop if current.y==ty && current.x==tx. for each of the six neighbors of the current node: add neighbor to frontier (and calculate cost, dist) if it's not already in interior (NEW). For example, if current have coordiates i, j, then each neighbor k (0<=k<6) will have coordinates i2=i+DY[k], j2=j+DX[i%2][k]. ALWAYS REMEMBER TO CHECK BOUNDS, x>=0 && x