Sign in to follow this  

A* AStar Pathfinding Problems (C++)

This topic is 2398 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey. I'm currently developing a simple game in SDL and XNA that both include A* Pathfinding.

But in a simple Pacman-type game enemies can't seem to find the right path to the Player. It only finds the way when there's a maximum of two walls between, or something.


I've built my code around developing pseudocode from this article: [url="http://www.policyalmanac.org/games/aStarTutorial.htm"]http://www.policyalm...tarTutorial.htm[/url]

My AStar class in C++:

[code]

#include "AStar.h"

AStar::AStar()
{
vector<PathNode> OpenList;
vector<PathNode> ClosedList;

for (int i = 0; i < 8; i++)
{
AdjacentSquare.push_back(PathNode());
}
};

void AStar::SetSize(int width, int height)
{
Width = width;
Height = height;
}


vector<PathNode> AStar::Execute(Map *map, int startX, int startY, int goalX, int goalY)
{

OpenList.clear();
ClosedList.clear();

OpenList.push_back(PathNode());
OpenList[OpenList.size()-1].Set(startX, startY, NULL, 0, ManhattanMethod(startX, startY, goalX, goalY));

PathNode CurrentSquare;

bool found_new = false;
bool first = true;

do
{

found_new = false;

for each(PathNode node in OpenList)
{
if (node.IsSet)
{
if (first)
{
CurrentSquare = node;
found_new = true;
first = false;
}
else
{
if (node.F < CurrentSquare.F)
{
CurrentSquare = node;
found_new = true;
}
}
}
}


for (int i=0; i < AdjacentSquare.size(); i++)
{
AdjacentSquare[i].Clear();
}

RemoveInOpenList(CurrentSquare.X, CurrentSquare.Y);
ClosedList.push_back(CurrentSquare);

if (!map->WallExists(CurrentSquare.X-Width, CurrentSquare.Y-Height))
{
AdjacentSquare[0].Set(CurrentSquare.X-Width, CurrentSquare.Y-Height, &CurrentSquare, 14, DiagonalShortcut(CurrentSquare.X-Width, CurrentSquare.Y-Height, goalX, goalY));
}
if (!map->WallExists(CurrentSquare.X-Width, CurrentSquare.Y))
{
AdjacentSquare[1].Set(CurrentSquare.X-Width, CurrentSquare.Y, &CurrentSquare, 10, ManhattanMethod(CurrentSquare.X-Width, CurrentSquare.Y, goalX, goalY));
}
if (!map->WallExists(CurrentSquare.X-Width, CurrentSquare.Y+Height))
{
AdjacentSquare[2].Set(CurrentSquare.X-Width, CurrentSquare.Y+Height, &CurrentSquare, 14, DiagonalShortcut(CurrentSquare.X-Width, CurrentSquare.Y+Height, goalX, goalY));
}

if (!map->WallExists(CurrentSquare.X, CurrentSquare.Y-Height))
{
AdjacentSquare[3].Set(CurrentSquare.X, CurrentSquare.Y-Height, &CurrentSquare, 10, ManhattanMethod(CurrentSquare.X, CurrentSquare.Y-Height, goalX, goalY));
}
if (!map->WallExists(CurrentSquare.X, CurrentSquare.Y+Height))
{
AdjacentSquare[4].Set(CurrentSquare.X, CurrentSquare.Y+Height, &CurrentSquare, 10, ManhattanMethod(CurrentSquare.X, CurrentSquare.Y+Height, goalX, goalY));
}

if (!map->WallExists(CurrentSquare.X+Width, CurrentSquare.Y-Height))
{
AdjacentSquare[5].Set(CurrentSquare.X+Width, CurrentSquare.Y-Height, &CurrentSquare, 14, DiagonalShortcut(CurrentSquare.X+Width, CurrentSquare.Y-Height, goalX, goalY));
}

if (!map->WallExists(CurrentSquare.X+Width, CurrentSquare.Y))
{
AdjacentSquare[6].Set(CurrentSquare.X+Width, CurrentSquare.Y, &CurrentSquare, 10, ManhattanMethod(CurrentSquare.X+Width, CurrentSquare.Y, goalX, goalY));
}

if (!map->WallExists(CurrentSquare.X+Width, CurrentSquare.Y+Height))
{
AdjacentSquare[7].Set(CurrentSquare.X+Width, CurrentSquare.Y+Height, &CurrentSquare, 14, DiagonalShortcut(CurrentSquare.X+Width, CurrentSquare.Y+Height, goalX, goalY));
}


for (int n=0; n < AdjacentSquare.size(); n++)
{

if (AdjacentSquare[n].IsSet && !IsInClosedList(AdjacentSquare[n].X, AdjacentSquare[n].Y))
{
if (!IsInOpenList(AdjacentSquare[n].X, AdjacentSquare[n].Y))
{

int h = 0;
int g = 0;

if (abs(AdjacentSquare[n].X - CurrentSquare.X) == Width && (abs(AdjacentSquare[n].Y - CurrentSquare.Y) == Height))
{
g = 14;
h = DiagonalShortcut(AdjacentSquare[n].X, AdjacentSquare[n].Y, goalX, goalY);
}
else
{
g = 10;
h = ManhattanMethod(AdjacentSquare[n].X, AdjacentSquare[n].Y, goalX, goalY);
}

OpenList.push_back(PathNode());
OpenList[OpenList.size()-1].Set(AdjacentSquare[n].X, AdjacentSquare[n].Y, &CurrentSquare, g, h);

}
else
{
if (AdjacentSquare[n].G < CurrentSquare.G)
{
AdjacentSquare[n].Parent = &CurrentSquare;

int h = 0;
int g = 0;

if (abs(AdjacentSquare[n].X - CurrentSquare.X) == Width && abs(AdjacentSquare[n].Y - CurrentSquare.Y) == Height)
{
g = 14;
h = DiagonalShortcut(AdjacentSquare[n].X, AdjacentSquare[n].Y, goalX, goalY);
}
else
{
g = 10;
h = ManhattanMethod(AdjacentSquare[n].X, AdjacentSquare[n].Y, goalX, goalY);
}

AdjacentSquare[n].H = h;
AdjacentSquare[n].G = g;
AdjacentSquare[n].F = AdjacentSquare[n].G + AdjacentSquare[n].H;

}
}
}

}


} while (!IsInClosedList(goalX, goalY) && found_new);


return ClosedList;
};

void AStar::RemoveInOpenList(int x, int y)
{

for (int i=0; i < OpenList.size(); i++)
{
if (OpenList[i].X == x && OpenList[i].Y == y)
{
OpenList.erase(OpenList.begin()+i);
break;
}
}
};

int AStar::ManhattanMethod(int startX, int startY, int goalX, int goalY)
{
return 10 * (abs(startX - goalX) + abs(startY - goalY));
};

int AStar::DiagonalShortcut(int currentX, int currentY, int goalX, int goalY)
{

int h;

int xDistance = abs(currentX-goalX);
int yDistance = abs(currentY-goalY);

if (xDistance > yDistance)
{
h = (14*yDistance) + (10*(xDistance-yDistance));
}
else
{
h = (14*xDistance) + (10*(yDistance-xDistance));
}

/*
int h = 0;

int xDistance = Math.Abs(current.X - goal.X);
int yDistance = Math.Abs(current.Y - goal.Y);

if (xDistance > yDistance)
{
h = 14 * yDistance + (10 * (xDistance - yDistance));
}
else
{
h = 14 * xDistance + (10 * (yDistance - xDistance));
}
*/

return h;




};


bool AStar::IsInOpenList(int x, int y)
{
bool exists = false;

for (int n=0; n < OpenList.size(); n++)
{

if (OpenList[n].X == x && OpenList[n].Y == y)
{
exists = true;
break;
}

}

return exists;
};

bool AStar::IsInClosedList(int x, int y)
{
bool exists = false;

for (int n=0; n < ClosedList.size(); n++)
{

if (ClosedList[n].X == x && ClosedList[n].Y == y)
{
exists = true;
break;
}

}

return exists;
};
[/code]


If anyone has any idea what's wrong with my method and what I'm doing wrong, please give me some advice.

This is for a school project and I can't seem to find a simple explanation for what's wrong.

Share this post


Link to post
Share on other sites

This topic is 2398 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this