Skip to main content
gamedev.net
🔒 Locked

Infinite looping while implementing A* algorithm *SOLVED*

Started by Zeraan Jun 11, 2009 at 11:35 PM 3 replies 900+ views
Original Post
Zeraan
Zeraan
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[i + X][j + Y].height - TileMap[X][Y].height); //Factor in the tile's height
                                if (height < 0 && height > -3)
                                    height *= -3;
                                else if (height <= 2)
                                    height *= 3;
                                else
                                    height *= 6; //climbing a cliff tile requires some time

                                //if (i == j || i == (j * -1)) //it's a diagonal
                                //    height += 2;

                                gValue = absX + absY + height + GMap[X, Y];

                                if (GMap[X + i, Y + j] == 0 || GMap[X + i, Y + j] > gValue) //This tile is better accessed from current tile
                                {
                                    GMap[X + i, Y + j] = gValue;
                                    if (i == 0 && j == 1) //Moved down
                                        PathMap[X + i, Y + j] = 2;
                                    else if (i == 0 && j == -1) //Moved up
                                        PathMap[X + i, Y + j] = 7;
                                    else if (i == 1 && j == 0) //Moved right
                                        PathMap[X + i, Y + j] = 4;
                                    else if (i == -1 && j == 0) //Moved left
                                        PathMap[X + i, Y + j] = 5;
                                    else if (i == -1 && j == -1) //Moved up left
                                        PathMap[X + i, Y + j] = 8;
                                    else if (i == -1 && j == 1) //Moved down left
                                        PathMap[X + i, Y + j] = 3;
                                    else if (i == 1 && j == -1) //Moved up right
                                        PathMap[X + i, Y + j] = 6;
                                    else if (i == 1 && j == 1) //Moved down right
                                        PathMap[X + i, Y + j] = 1;
                                    Travelled[X + i, Y + j] = false;
                                }
                            }
                        }
                    MaxValue = SuperMapSize * SuperMapSize * 100; //So it's impossible to have this accidentally lower than gValue
                    for (int i = -1; i < 2; i++) //Find the next lowest gValue
                        for (int j = -1; j < 2; j++)
                        {
                            if (GMap[X + i, Y + j] < MaxValue && Travelled[X + i, Y + j] == false)
                            {
                                MaxValue = GMap[X + i, Y + j];
                                NextX = X + i;
                                NextY = Y + j;
                            }
                        }
                    X = NextX;
                    Y = NextY;
                    Travelled[X, Y] = true;
                }
This is my first time I've attempted to implement A* algorithm. One 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. [Edited by - Zeraan on June 12, 2009 5:06:53 PM]
LorenzoGatti
LorenzoGatti
Quote:
Original post by Zeraan
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.
...
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]
Omae Wa Mou Shindeiru
Zeraan
Zeraan
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 openSet                                        inOpenSet = 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 down                                        PathMap[openSet[iterator].X + i, openSet[iterator].Y + j] = 2;                                    else if (i == 0 && j == -1) //Moved up                                        PathMap[openSet[iterator].X + i, openSet[iterator].Y + j] = 7;                                    else if (i == 1 && j == 0) //Moved right                                        PathMap[openSet[iterator].X + i, openSet[iterator].Y + j] = 4;                                    else if (i == -1 && j == 0) //Moved left                                        PathMap[openSet[iterator].X + i, openSet[iterator].Y + j] = 5;                                    else if (i == -1 && j == -1) //Moved up left                                        PathMap[openSet[iterator].X + i, openSet[iterator].Y + j] = 8;                                    else if (i == -1 && j == 1) //Moved down left                                        PathMap[openSet[iterator].X + i, openSet[iterator].Y + j] = 3;                                    else if (i == 1 && j == -1) //Moved up right                                        PathMap[openSet[iterator].X + i, openSet[iterator].Y + j] = 6;                                    else if (i == 1 && j == 1) //Moved down right                                        PathMap[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 set                    for(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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.