* the variable "grid" is a structure with one x integer and one y integer.
* this is the "nodes" variable:
struct node{
int x_pos,y_pos;
bool OPEN,CLOSED;
void Open();
void Close();
void init();
node *parent;
int F,G,H;
};//

////////Variables///////////////////////
extern int loop1,current_x,current_y;
extern int steps_in_path,open_count;
int loop_i,loop_j;

int x_neighbour[8] = {0,2,2,2,0,-2,-2,-2};
int y_neighbour[8] = {2,2,0,-2,-2,-2,0,2};
extern int map[MAP_SIZE][MAP_SIZE];  // the array map can have one of 5 values:
//0 = not taken.  1 = unpassable. 3 = part of the path. 4 = taken by a unit.    
//5 = next to unpassable terrain.
//
int current_x, current_y;

extern grid open_list[10000];
extern grid path[500];
extern node nodes[MAP_SIZE][MAP_SIZE];

///////////////////////////  

void node :: init() ////initializes the nodes.
{
 CLOSED = FALSE;
 OPEN = FALSE;
 F = 0 ; G = 0; H = 0;//F=0//rand()%10
 //parent = NULL;
}

void node :: Open()  ////////marks a node as an "open node"
{
 OPEN = TRUE;
 CLOSED = FALSE;
}

void node :: Close()  ////////marks a node as an "closed node"
{
 OPEN = FALSE;
 CLOSED = TRUE;
}


void InitNodes()       /////////initializes the x and y positions of the nodes.
{                       /////////the MAP_SIZE is 128
  for(loop_i=0;loop_i<MAP_SIZE;loop_i++)    ///
  for(loop_j=0;loop_j<MAP_SIZE;loop_j++)    ///
   {
     nodes[loop_i][loop_j].x_pos = loop_i;  ///
     nodes[loop_i][loop_j].y_pos = loop_j;  ///
     nodes[loop_i][loop_j].init();          //
   }
}

//////////This calculates the G value of a node in the A* algorithm
//         the current node coords, the detination coords, the current nodes G
int CalculateG(int x_src, int y_src, int x_dest, int y_dest, int src_G)
{
 if(map[x_dest][y_dest]==0)   ///If this place on the map isn't taken 
  {
  if((x_src == x_dest) || (y_src == y_dest))  //If we arn't moveing diagonally
    return(10 + src_G);                       // add 10 to the G value
  else                                        // if diagonall
    return(14 + src_G);                       // add 14 to the G value
  }
}
//This does the Hueristic ///current               //final
int CalculateH(int x_src, int y_src, int x_dest, int y_dest)
{
 int H_check;
   H_check = 10*abs(x_src - x_dest) + 10*abs(y_src - y_dest);
   return(H_check);
}

////This recursive function takes out all of the open nodes that have
//been closed.  When closed they get the value of 50000 - bigger than 
//any possible value.  This function makes them equal 0 and makes the
//open_count (records how many nodes are in the open_list) variable smaller
//by 1
void CleanOpenList()
{
 if(nodes[open_list[open_count].x][open_list[open_count].y].F == 50000)
  {
   open_list[open_count].x = 0;
   open_list[open_count].y = 0; 
   open_count--;
   CleanOpenList();
  }
}    

//This is the function used in the qsort() function.  It tells the qsort()
//to arrange the node array so that the nodes with the smallest F values are
//first
int Compare(struct grid *elem1, struct grid *elem2)		// Compare 
{
   if ( nodes[elem1->x][elem1->y].F < nodes[elem2->x][elem2->y].F)		
      return -1;												
   else if (nodes[elem1->x][elem1->y].F > nodes[elem2->x][elem2->y].F)		
      return 1;													
   else										
    {
     if ( nodes[elem1->x][elem1->y].H < nodes[elem2->x][elem2->y].H)		
       return -1;												
     else if (nodes[elem1->x][elem1->y].H > nodes[elem2->x][elem2->y].H)	
       return 1;													
     else	
       return 0;	
    }												
}

//This is the main pathfinding function.  There is a array - grid paths[500]
//that store x and y values for all the steps in the path.  the rest 
//is described above.

bool FindPath(grid *paths,int *total,int source_x,int source_y,int destin_x,int destin_y)
{
  int x,y;
  bool detected;
  grid *next, *past,*now;
      
     InitNodes(); //initialize the node positions.
        
	/////////checking///////////////First check for bad imputs.
// the map size is 128X128 but to cut down on search time I'm looking at it 
// as a 64X64 map with only the even nodes (2,4),(16,100) and so on.  so I first
// change all odd inputs to even.  	
      if(source_x%2 == 1)
        source_x+=1;    ////there is no chance that this will make the position
      if(source_y%2 == 1)//go off the map cause I only imput to 126X126
       source_y+=1;
      if(destin_x%2 == 1)
       destin_x+=1;
      if(destin_y%2 == 1)
       destin_y+=1;   
  
  
         // If there is no path to do:
          if((source_x==destin_x)&&(source_y==destin_y))
		 {
		  *total = 0;          //no place to go to
		  paths->x = destin_x; //the only part of the path is the place
		  paths->y = destin_y; // were the unit is now
		  return(TRUE);       //we found the path
	     }
     //   
      
         
      /////////////////////////     
        current_x = source_x; current_y = source_y;  //make the current node 
                                                     //the first node
        open_count = 0;   //set the number of nodes in the open_list to 0 
        for(loop_i=0;loop_i<100;loop_i++)//set the first 100 open_list variables
         {                                //to 0   
          open_list[loop_i].x = 0;  //
          open_list[loop_i].y = 0;  //
         }
        open_list[0].x = current_x;   //make the first node in the o_l the 
        open_list[0].y = current_y;   //current node.
        loop1 = 0;                    //loop1 will count the amount of times
                                    //the search alg has to go through the loop
 ///Do the A* alg untill we get to the end.  make sure we dont try for too long!
   while(((current_x!=destin_x)||(current_y!=destin_y)) && (loop1<10100))
    {
       loop1++;
        current_x = open_list[0].x; //take the lowest value node from the o_l	current_y = open_list[0].y; //(it is sorted so that the lowest nodes
                                    //are first
        nodes[current_x][current_y].Close();  //mark the current node as closed
        nodes[current_x][current_y].F = 50000;//make it's F 50000 so that the
                                              //cleaning func will recognize it
     for(loop_i=0;loop_i<8;loop_i++)   ///  go through all the neibours of the
       {                                 //current node
           x = current_x + x_neighbour[loop_i];   //make x and y the positions
           y = current_y + y_neighbour[loop_i];   //of nodes next to the current
                                                  //one
        if((x>=0)&&(x<MAP_SIZE)&&(y>=0)&&(y<MAP_SIZE)&&(map[x][y]!=1))
         //If we are on the map and in passable territory
         {  
          if(nodes[x][y].OPEN)  //if the neigbour is an open node recheck it's G
           {
            if(nodes[x][y].G > CalculateG(current_x, current_y, x, y, nodes[current_x][current_y].G))
             {
            /////////if the G from the current node is lower than the one it
                ////has now - change it and make the current node it's parent   
         nodes[x][y].G = CalculateG(current_x, current_y, x, y, nodes[current_x][current_y].G);
               nodes[x][y].F = nodes[x][y].G + nodes[x][y].H;
               nodes[x][y].parent = &nodes[current_x][current_y];
             }
           }
           
          if((!nodes[x][y].OPEN) && (!nodes[x][y].CLOSED)) //If the node is not
//and not closed
           {
            nodes[x][y].Open();  //make it open
            nodes[x][y].parent = &nodes[current_x][current_y]; //make the 
      //current node the parent,calculate the G,H, and F
            nodes[x][y].G = CalculateG(current_x, current_y, x, y, nodes[current_x][current_y].G);
            nodes[x][y].H = CalculateH(x,y,destin_x,destin_y);
            nodes[x][y].F = nodes[x][y].G + nodes[x][y].H;
            open_count++;                     make the o_c get bigger by 1
            open_list[open_count].x = x;      add this node to the o_l
            open_list[open_count].y = y;
           }
         }
       }
      qsort((void *) &open_list, open_count+1, sizeof(struct grid), (compfn)Compare );                      //sort the o_l from smallest to biggest	   
      CleanOpenList();          //take out the closed ones.

    if(loop1 >= 10000)//if we've checked 10000 times and still havent gotten
     return(FALSE);   //to the end then we've failed
    }
   

   //Now we have a parent-child connection from the destination to the source
   //so now we have to put that in the paths array from the begining to end.  
  
    current_x = destin_x;  //now make the current node the end node because
    current_y = destin_y;  //we are going to work from end to beginning
    loop_i=0;                           //
    detected = FALSE;                     //we haven't detected the beginning 
                                          //yet
      while((!detected) && (loop_i<5000))    
      {
        x = nodes[current_x][current_y].parent->x_pos; //get the position of the
        y = nodes[current_x][current_y].parent->y_pos; // parent node
       current_x = x;                             //make the current node the 
       current_y = y;                             //parent node
       if((current_x==source_x)&&(current_y==source_y))//If we've gotton to the 
        {                                              //begining
        detected=TRUE;                             //we've detected the source
        }
       loop_i++;              //
      }
     
     steps_in_path = loop_i*2;     //The total amount of steps on the path
     *total = steps_in_path; //(including the odd nodes) is double the amount
                              //of times that it took us to get from the end
                              //to start
    paths += steps_in_path; //set the pointer to the last node
    current_x = destin_x;   
    current_y = destin_y;
    loop_i=steps_in_path;           //
    detected = FALSE;
     
//Now we're going to go from the end to the start and put the values into the
//paths array
     while(!detected)  
      {
       paths->x = current_x;  //put the current values into the paths array
       paths->y = current_y;
        x = nodes[current_x][current_y].parent->x_pos;  //get the parent
        y = nodes[current_x][current_y].parent->y_pos;
       current_x = x;                                 //make that the current
       current_y = y;
       if(loop_i<steps_in_path)    //If we haven't gotten to the end
        { 
         next = paths;            //in the next few lines I find the odd values
         past = paths + 2;        //by finding the node between every two even
         paths+=1;               //ones
         paths->x = (next->x - past->x)/2 + past->x;
         paths->y = (next->y - past->y)/2 + past->y;  
         map[paths->x][paths->y] = 3;
         paths-=1;                      //go bach a step
        }
       
       if((current_x==source_x)&&(current_y==source_y)) //we've reached the 
        {                                               //start
        paths -= 2;               //go back 2 and make that the first node
        paths->x = current_x;       //of the path
        paths->y = current_y;
        detected=TRUE;
        
         next = paths;
         past = paths + 2;
         paths+=1;               //go up one to find the first odd node
         paths->x = (next->x - past->x)/2 + past->x;
         paths->y = (next->y - past->y)/2 + past->y;  
         map[paths->x][paths->y] = 3;
         paths-=1;
         
        }
       paths -= 2;
       loop_i -= 2;         //
      }
    //last = i+1;
  return(TRUE);          //YaY
}

for(i=0;i<50;i++)   {     for(j=2;j<4;j++)     {      do       {      x[j] = int(rand()%(MAP_SIZE-30))+15;      y[j] = int(rand()%(MAP_SIZE-30))+15;      }while((map[x[j]][y[j]].current_step.y]==1)||(map[x[j]][y[j]]==5);     }    FindPath(path,&length_of_path,x[2],y[2],x[3],y[3]);  }