   A*
  Hi,I am trying to write a capture the flag game in C++ (devC++).  First I decided that I wanted to do the pathfinding.  I wanted to get to the point were I could mark units and tell them were to move to without them bumping into trees,buildings,etc...So I wrote a A* function that gets a pointer to the path array, a pointer to the length_of_path variable, initial x,y positions and destination x,y positions:FindPath(path,*length_of_path,xi,yi,xf,yf);The Source code is at the end of the letter.  I'm self taught so sorry if I have cinventional code or somethingThe function outputs the path into the path array (the path variable is a structure with an x and y variable) and the length of the path.Now, the function works perfectly if I use it a few times in a row, but if I run it in a loop for about 50 times in a row with random x's and y's the program sometimes crashes.  This isn't acceptable for such a basic part of the game.I was trying to fix this problem for over TWO MONTHS and nothing worked.  This is really frusterating because I really want to get on with the game.  Can someone please try to help me or give advice?  Feel free to ask any question you want.  I have the code bellow and I hope that a good programmer can see a problem or give a suggestion  Please Help!!Source: (For some reason all of the < were changed to < and the < to >* 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 Gint 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//finalint 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 1void 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//firstint 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_lcurrent_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 itfor(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 gottenreturn(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 arraywhile(!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}[Edited by - daniel_i_l on December 12, 2005 9:28:06 AM]
  Is there any reason why you can't run this under a debugger? That should show you exactly where it's crashing, and from there it's usually easy to fix such a bug.At the very least, use cout/endl statements to log some of your program variables during execution. Perhaps certain values of x and y cause the crash, for example.   ;  Kylotan,I tried to debug but thee problem occers only after about 50 runs of the alg.  I cant go through the alg everytime untill it crashes, that would take forever.  I have DevC++, is there any way to run the program normally and then check what line the program got up to after it crashes?  Is there anything else simaler to that that I can do to see what caused my program to crash?-and if anyone has the time do you think that you could go over the code please?Or, does anyone have an idea as to what causes this to crash?  I'm suspecting the pointers because I'm not very experianced with them.  Could that be the problem?Or can anyone tell me another way or give me a source of a way to make a better and more efficiant A* function with the same input and output as the one that I have?Any advice could help me cause this is really driving me crazy!Thanks in advance.[Edited by - daniel_i_l on December 12, 2005 10:51:44 AM];  Sorry I dont have time to go over the code, however, could you tell us how it crashes? I dont know much about DevC++, but in debug at least there should be some messageIf not, my suggestion would be to use try-catch to manage your errors, or/and start using assertions.Good luck!   ;  The program crashes when I run the following code: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]);  }I am basicly running the A* 50 times.  If I do this once or twice then the program crashes.Could you explain how I could use asserts to solve the problem?   ;  Looking at your code, I would say that the crash is probably due to an out-of-bound array *somewhere*. Or by the pure evileness of global extern C++ arrays. So you should use assertions to check your index values before accessing the arrays. But the REAL thing to do would be using an array class with an assert in the accessor.   ;  Thanks Steadtler,I've never really used assertations before, could you explain what I should do, were I should put them, or could you give me a good link? ;Quote:Original post by daniel_i_lThanks Steadtler,I've never really used assertations before, could you explain what I should do, were I should put them, or could you give me a good link?Look up assert in your help or man pages. It's commonly implemented as a macro.http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vclib/html/_CRT_assert.asp;  //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.  do you store an current index into this array for this somewhere? maybe you forget to reset it to zero when starting a new loop, if you run your 50-loops test with different points on terrain maybe the result won't end up at 50 loops, also if you are already picking up random start / ending points maybe a point is selected inside a wall or your path is so big that your array can't hold them anymore and you get acces violation.  also more accurate description of error would come in very handy. ;  As to your bug, the above suggestions for finding it are all good. As an aside, I noticed that in your Compare() function which you use with qsort, you test first if the path costs (F) are ordered. Then, if they are the same, you sort based on heuristic cost (H). You should do this secondary sort on the path-to-node cost (G). If you need/want the algorithmic reasons for doing this, just holler.Cheers,Timkin   