   Infinite looping while implementing A* algorithm *SOLVED*
  We're working on a tile-based tactical RPG, and we're stumped with this problem.  I developed this function that returns a list of directions to follow on the map.  However, on really hilly maps, it enters an infinite loop.Narrowing it down, we discovered it to be within the first while loop, so I'll just post that code here.int X = StartX % SuperMapSize; int Y = StartY % SuperMapSize; int TargetX = EndX % SuperMapSize; int TargetY = EndY % SuperMapSize; int StartingX = StartX % SuperMapSize; int StartingY = StartY % SuperMapSize; int length = 0; //How long is the path? int[,] PathMap = new int[SuperMapSize, SuperMapSize]; //Track which movements are taken while walking int[,] GMap = new int[SuperMapSize, SuperMapSize]; //Cost of path bool[,] Travelled = new bool[SuperMapSize, SuperMapSize]; //See if path is already touched int NextX = 0; int NextY = 0; int gValue; int absX, absY; int height; int MaxValue; while (!(X == TargetX && Y == TargetY)) {for (int i = -1; i < 2; i++)    for (int j = -1; j < 2; j++) //Fill in GMap, and determine the next best action    {   if (i + X >= 0 && i + X < SuperMapSize && //Make sure it's safely inside the area  j + Y >= 0 && j + Y < SuperMapSize)   {  absX = TargetX - (i + X); //Factor in distance to the target spot  if (absX < 0) absX *= -1;  else absX *= 1;  absY = TargetY - (j + Y);  if (absY < 0) absY *= -1;  else absY *= 1;  height = (TileMap[j + Y].height - TileMap[X][Y].height); <span class="cpp-comment">//Factor in the tile's height</span>  <span class="cpp-keyword">if</span> (height &lt; <span class="cpp-number">0</span> &amp;&amp; height &gt; -<span class="cpp-number">3</span>) height *= -<span class="cpp-number">3</span>;  <span class="cpp-keyword">else</span> <span class="cpp-keyword">if</span> (height &lt;= <span class="cpp-number">2</span>) height *= <span class="cpp-number">3</span>;  <span class="cpp-keyword">else</span> height *= <span class="cpp-number">6</span>; <span class="cpp-comment">//climbing a cliff tile requires some time</span>  <span class="cpp-comment">//if (i == j || i == (j * -1)) //it's a diagonal</span>  <span class="cpp-comment">//    height += 2;</span>  gValue = absX + absY + height + GMap[X, Y];  <span class="cpp-keyword">if</span> (GMap[X + i, Y + j] == <span class="cpp-number">0</span> || GMap[X + i, Y + j] &gt; gValue) <span class="cpp-comment">//This tile is better accessed from current tile</span>  { GMap[X + i, Y + j] = gValue; <span class="cpp-keyword">if</span> (i == <span class="cpp-number">0</span> &amp;&amp; j == <span class="cpp-number">1</span>) <span class="cpp-comment">//Moved down</span>PathMap[X + i, Y + j] = <span class="cpp-number">2</span>; <span class="cpp-keyword">else</span> <span class="cpp-keyword">if</span> (i == <span class="cpp-number">0</span> &amp;&amp; j == -<span class="cpp-number">1</span>) <span class="cpp-comment">//Moved up</span>PathMap[X + i, Y + j] = <span class="cpp-number">7</span>; <span class="cpp-keyword">else</span> <span class="cpp-keyword">if</span> (i == <span class="cpp-number">1</span> &amp;&amp; j == <span class="cpp-number">0</span>) <span class="cpp-comment">//Moved right</span>PathMap[X + i, Y + j] = <span class="cpp-number">4</span>; <span class="cpp-keyword">else</span> <span class="cpp-keyword">if</span> (i == -<span class="cpp-number">1</span> &amp;&amp; j == <span class="cpp-number">0</span>) <span class="cpp-comment">//Moved left</span>PathMap[X + i, Y + j] = <span class="cpp-number">5</span>; <span class="cpp-keyword">else</span> <span class="cpp-keyword">if</span> (i == -<span class="cpp-number">1</span> &amp;&amp; j == -<span class="cpp-number">1</span>) <span class="cpp-comment">//Moved up left</span>PathMap[X + i, Y + j] = <span class="cpp-number">8</span>; <span class="cpp-keyword">else</span> <span class="cpp-keyword">if</span> (i == -<span class="cpp-number">1</span> &amp;&amp; j == <span class="cpp-number">1</span>) <span class="cpp-comment">//Moved down left</span>PathMap[X + i, Y + j] = <span class="cpp-number">3</span>; <span class="cpp-keyword">else</span> <span class="cpp-keyword">if</span> (i == <span class="cpp-number">1</span> &amp;&amp; j == -<span class="cpp-number">1</span>) <span class="cpp-comment">//Moved up right</span>PathMap[X + i, Y + j] = <span class="cpp-number">6</span>; <span class="cpp-keyword">else</span> <span class="cpp-keyword">if</span> (i == <span class="cpp-number">1</span> &amp;&amp; j == <span class="cpp-number">1</span>) <span class="cpp-comment">//Moved down right</span>PathMap[X + i, Y + j] = <span class="cpp-number">1</span>; Travelled[X + i, Y + j] = <span class="cpp-keyword">false</span>;  }   }    }MaxValue = SuperMapSize * SuperMapSize * <span class="cpp-number">100</span>; <span class="cpp-comment">//So it's impossible to have this accidentally lower than gValue</span><span class="cpp-keyword">for</span> (<span class="cpp-keyword">int</span> i = -<span class="cpp-number">1</span>; i &lt; <span class="cpp-number">2</span>; i++) <span class="cpp-comment">//Find the next lowest gValue</span>    <span class="cpp-keyword">for</span> (<span class="cpp-keyword">int</span> j = -<span class="cpp-number">1</span>; j &lt; <span class="cpp-number">2</span>; j++)    {   <span class="cpp-keyword">if</span> (GMap[X + i, Y + j] &lt; MaxValue &amp;&amp; Travelled[X + i, Y + j] == <span class="cpp-keyword">false</span>)   {  MaxValue = GMap[X + i, Y + j];  NextX = X + i;  NextY = Y + j;   }    }X = NextX;Y = NextY;Travelled[X, Y] = <span class="cpp-keyword">true</span>; }</pre></div><!–ENDSCRIPT–>This is my first time I've attempted to implement A* algorithm.  &#79;ne thing that seemed to help is implementing "Travelled" map that checks if the tile is already traversed, to prevent flipping back and forth between two tiles with lowest gValue.  Then I realized that I forgot to carry over gValue from previous tile to current tile, so I added that.If someone can help me, I'd really appreciate it!  Thanks.<!–EDIT–><span class=editedby><!–/EDIT–>[Edited by - Zeraan on June 12, 2009 5:06:53 PM]<!–EDIT–></span><!–/EDIT–>
Quote:Original post by ZeraanWe're working on a tile-based tactical RPG, and we're stumped with this problem.  I developed this function that returns a list of directions to follow on the map.  However, on really hilly maps, it enters an infinite loop....This is my first time I've attempted to implement A* algorithm.The code snippet is not an A* implementation at all. You don't have a priority queue containing all candidate paths and you are forced to process every cell, most likely missing some possible movements due to the interference of missing or wrong data (GMap at locations that haven't yet been reached by the cheapest path) and/or premature Travelled flags.[Edited by - LorenzoGatti on June 18, 2009 3:33:34 AM];  I used this and either I don't understand it clearly, or it didn't explain well enough.  Priority queues?  I'll look for some other tutorials.  Thanks for taking the time looking through my code!   ;  Okay, I've looked at wikipedia article, and it helped clarify the concept.  Here's the updated code:Point[] closedSet = new Point[0]; //Set of tiles already evaluated Point[] openSet = new Point[1]; //Set of tentative tiles to be evaluated int[,] gScore = new int[SuperMapSize, SuperMapSize]; //Distance from start along optimal path int[,] hScore = new int[SuperMapSize, SuperMapSize]; //Estimate of distance int[,] fScore = new int[SuperMapSize, SuperMapSize]; //Estimated total distance int[,] PathMap = new int[SuperMapSize, SuperMapSize]; //Track which movements are taken while walking int X = StartX % SuperMapSize; int Y = StartY % SuperMapSize; int TargetX = EndX % SuperMapSize; int TargetY = EndY % SuperMapSize; int StartingX = StartX % SuperMapSize; int StartingY = StartY % SuperMapSize; openSet[0].X = X; openSet[0].Y = Y; int iterator = 0; int count = 0; int length = 0; //How long is the path? int NextX = 0; int NextY = 0; int gValue; int absX, absY; int height; int MaxValue; bool Break = false; bool inOpenSet = false; bool isBetter = false; int tentative_gScore; while (openSet.Length > 0) //Is there still possible moves? {if(openSet[iterator].X == TargetX && openSet[iterator].Y == TargetY)    break;for (int i = -1; i < 2; i++)    for(int j = -1; j < 2; j++)    {   for (int k = 0; k < closedSet.Length; k++)   {  if (openSet[iterator].X + i == closedSet[k].X && openSet[iterator].Y + j == closedSet[k].Y)//Already in closed set Break = true;   }   if (!Break)   {  absX = TargetX - (i + openSet[iterator].X); //Factor in distance to the target spot  if (absX < 0) absX *= -10;  else absX *= 10;  absY = TargetY - (j + openSet[iterator].Y);  if (absY < 0) absY *= -10;  else absY *= 10;  height = TileMap[TargetX][TargetY].height - TileMap[openSet[iterator].X+i][openSet[iterator].Y+j].height;  if(height < 0) height *= -20;  else height *= 20;  tentative_gScore = gScore[openSet[iterator].X + i, openSet[iterator].Y + j] + absX + absY + height;  isBetter = false;  inOpenSet = false;  for (int k = 0; k < openSet.Length; k++)  { if (openSet[k].X == openSet[iterator].X+i && openSet[k].Y == openSet[iterator].Y+j) //Already in openSetinOpenSet = true;  }  if (!inOpenSet) //not in either closed or open set, already performed closed set check  { Point[] temp = new Point[openSet.Length + 1]; //Add this to openSet for (int k = 0; k < openSet.Length; k++) {temp[k] = openSet[k]; } temp[temp.Length - 1].X = openSet[iterator].X + i; temp[temp.Length - 1].Y = openSet[iterator].Y + j; openSet = temp; hScore[openSet[iterator].X + i,openSet[iterator].Y + j] = absX + absY + height; //estimate of distance isBetter = true;  }  else if(tentative_gScore < gScore[openSet[iterator].X+i, openSet[iterator].Y+j])//Better accessed from this tile isBetter = true;  if(isBetter)  { if (i == 0 && j == 1) //Moved downPathMap[openSet[iterator].X + i, openSet[iterator].Y + j] = 2; else if (i == 0 && j == -1) //Moved upPathMap[openSet[iterator].X + i, openSet[iterator].Y + j] = 7; else if (i == 1 && j == 0) //Moved rightPathMap[openSet[iterator].X + i, openSet[iterator].Y + j] = 4; else if (i == -1 && j == 0) //Moved leftPathMap[openSet[iterator].X + i, openSet[iterator].Y + j] = 5; else if (i == -1 && j == -1) //Moved up leftPathMap[openSet[iterator].X + i, openSet[iterator].Y + j] = 8; else if (i == -1 && j == 1) //Moved down leftPathMap[openSet[iterator].X + i, openSet[iterator].Y + j] = 3; else if (i == 1 && j == -1) //Moved up rightPathMap[openSet[iterator].X + i, openSet[iterator].Y + j] = 6; else if (i == 1 && j == 1) //Moved down rightPathMap[openSet[iterator].X + i, openSet[iterator].Y + j] = 1; gScore[openSet[iterator].X + i, openSet[iterator].Y + j] = tentative_gScore; fScore[openSet[iterator].X + i, openSet[iterator].Y + j] = gScore[openSet[iterator].X + i, openSet[iterator].Y + j] + hScore[openSet[iterator].X + i, openSet[iterator].Y + j];  }   }    }Point[] temp2 = new Point[openSet.Length-1]; //Remove the current iterator and add it to closed setfor(int i = 0; i < iterator; i++)    temp2 = openSet;for(int i = iterator + 1; i < openSet.Length; i++)    temp2[i-1] = openSet;Point[] temp3 = new Point[closedSet.Length + 1];for(int i = 0; i < closedSet.Length; i++)    temp3 = closedSet;temp3[temp3.Length-1].X = openSet[iterator].X; temp3[temp3.Length-1].Y = openSet[iterator].Y;openSet = temp2;closedSet = temp3;MaxValue = SuperMapSize * SuperMapSize * 1000;for(int i = 0; i < openSet.Length; i++) //Now find the tile with lowest f score{    if(fScore[openSet.X, openSet.Y] < MaxValue)    {   iterator = i;   MaxValue = fScore[openSet.X, openSet.Y];    }} }However, for some reason, when reaching the target tile, it doesn't add the direction to previous tile on that target tile in this loop.  Is this loop exiting prematurely?  Is this the correct implementation of A* algorithm?Thanks!Edit: Fixed the too wide post.   ;  I forgot to reset Break to false.  It now works beautifully!  Thanks for that nudge in the right direction.   