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.