/*            CSC 155 Final Assignment: A* Treasure Hunt.

   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.

*/

using namespace std;
#include<cstdlib>
#include<math.h>
#include "heaps.cpp"

/*****  Terrain Values (in my program, only OPEN and WATER are used)  *****/

#define OPEN 0
#define FORREST 1
#define DESERT 2
#define WATER 3


/*****  Size of map  - you can change these constants (but only these!) *****/

#define ROWS 32
#define COLS 44

/////  used by genmap:
#define NFACTOR 0.1
#define GENS 12

// object to represent each cell of the matrix.  You may add extra elements
// to the class if you wish, but the following must be here, especially the
// prev pointer.  Your Astar procedure must set this pointer correctly.  A
// value of NULL for this pointer means that no path exists.
class cell
{
public:
  cell * prev;  // previous cell in path  *****************
  int x, y;     // coordinates - should coorespond with matrix coords
  int terrain;  // terrain type - OPEN or WATER

  cell(int y0, int x0) 
   { terrain = OPEN;
     x=x0; y=y0;
     prev = NULL;
   }
};   // class cell



// function to return distance between two coords:
  double dist(int y1, int x1, int y2, int x2)
  {
    double dx2 = (x1-x2) * (x1-x2);
    double dy2 = (y1-y2) * (y1-y2);
    return sqrt(dx2+dy2);
  }



class playground
{
public:
  cell *M[ROWS][COLS];   // The matrix

  // constructor initializes playground:
  playground()
  {
    int i, j;
    for(i=0;i<ROWS;i++) for(j=0;j<COLS;j++)
      M[i][j] = new cell(i,j);
  } // constructor

  void genmap()  // generate random map
  { int i, j;  double p;   double r;
    int generation;
    for(generation=0;generation<GENS;generation++)
      {
	for(i=0;i<ROWS;i++) for(j=0;j<COLS;j++)
	  {
	     p = 0.005; // base probability factor
	     if (i>0 && M[i-1][j]->terrain==WATER) p += NFACTOR;
	     if (i<ROWS-1 && M[i+1][j]->terrain==WATER) p+=NFACTOR;
	     if (j>0 && M[i][j-1]->terrain==WATER) p+=NFACTOR;
	     if (j<COLS-1 && M[i][j+1]->terrain==WATER) p+=NFACTOR;

	     r = (random() % 10000) / 10000.0;
	     if (r<=p) M[i][j]->terrain = WATER;
	  } // for each cell
      } // for each generation
  } // genmap
  

  /*************** Here's what you have to implement: *******************/

  // generate (reverse) path from coordinate sy,sx to ty,tx.
  // It should terminate if no path exists.
  void Astar(int sy, int sx, int ty, int tx);

}; // class playground