Jump to content
  • Advertisement
Sign in to follow this  
deukalion

A* AStar Pathfinding Problems (C++)

This topic is 2609 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: http://www.policyalm...tarTutorial.htm

My AStar class in C++:



#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.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.X == x && OpenList.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;
};



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
Advertisement
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!