I am setting up A* pathfinding for my game in C++ and SDL.
I have only the basic knowledge of how A* and pathfinding works so I've been going by different tutorials and help from friends.
Here is the code involved:
SearchCell: (node)
/* Includes */
#include <math.h>
#include "Constants.h"
#include <fstream>
#include <limits>
/* Node for A* */
struct SearchCell
{
int x, y, ID;
SearchCell* parent;
float G; // Accumelated distance from start node to were the cell is
float H; // Hueristic, estimated distance to the goal
SearchCell() : parent(0) {};
SearchCell(int X, int Y, int id, SearchCell* Parent) :
x(X),
y(Y),
parent(Parent),
ID(id),
G(0.0f),
H(0.0f)
{};
float get_f()
{
return G + H;
};
float heuristic(SearchCell* nodeEnd)
{
float x = static_cast<float>(fabs(static_cast<float>(this->x - nodeEnd->x)));
float y = static_cast<float>(fabs(static_cast<float>(this->y - nodeEnd->y)));
return x + y;
};
// Comparison operators
inline bool operator<(std::shared_ptr<SearchCell>& a) { return get_f() < a->get_f(); }
inline bool operator<=(std::shared_ptr<SearchCell>& a) { return get_f() <= a->get_f(); }
inline bool operator>(std::shared_ptr<SearchCell>& a) { return get_f() > a->get_f(); }
};
// for std::sort
struct cell_cmp
{
bool operator()(const std::shared_ptr<SearchCell>& a, const std::shared_ptr<SearchCell>& b) const
{
return (a->get_f() < b->get_f());
}
};
};Pathfinding class header
/* Includes */
#include <vector>
#include <tr1/memory>
#include "Logic.h"
#include "SearchCell.h"
#include "Gridmanager.h"
class Pathfinder
{
public:
Pathfinder();
~Pathfinder();
Point3 next_path_pos();
bool find_path(Point3, Point3);
bool foundGoal;
private:
typedef std::shared_ptr<Point3> pointPtr;
typedef std::shared_ptr<SearchCell> cellPtr;
cellPtr startCell;
cellPtr goalCell;
std::vector<cellPtr> openList;
std::vector<cellPtr> visitedList;
std::vector<pointPtr> pathList;
cellPtr get_next_cell();
void add_cell(int, int, float, SearchCell*);
void search_path();
};The pahtfinding class source
#include "Pathfinder.h"
#include "Camera.h"
#include <fstream>
#include <algorithm>
Pathfinder::Pathfinder()
{
startCell.reset();
goalCell.reset();
foundGoal = false;
openList.reserve(MAP_WIDTH * MAP_HEIGHT);
}
Pathfinder::~Pathfinder()
{
}
bool Pathfinder::find_path(Point3 currentPos, Point3 targetPos)
{
if (foundGoal)
{
openList.clear();
visitedList.clear();
pathList.clear();
}
// Start and goal in units rather then pixels (tiles are squares so same width as height)
currentPos /= TILE_WIDTH;
targetPos /= TILE_WIDTH;
startCell.reset(new SearchCell(currentPos.x, currentPos.y, (currentPos.y*MAP_WIDTH)+currentPos.x, 0));
goalCell.reset(new SearchCell(targetPos.x, targetPos.y, (targetPos.y*MAP_WIDTH)+targetPos.x, 0));
startCell->H = startCell->heuristic(goalCell.get());
openList.push_back(startCell);
foundGoal = false;
search_path();
return foundGoal;
}
std::shared_ptr<SearchCell> Pathfinder::get_next_cell()
{
// This causes segmentation fault
std::sort(openList.begin(), openList.end(), cell_cmp());
cellPtr nextCell = openList.front();
visitedList.push_back(nextCell);
openList.erase(openList.begin());
return nextCell;
}
void Pathfinder::add_cell(int x, int y, float newCost, SearchCell* parent)
{
int ID = y * MAP_WIDTH + x;
int screenX = x * 16;
int screenY = y * 16;
if (!Gridmanager::is_within_screen(screenX, screenY))
{
return;
}
if (!Gridmanager::is_within_grid(x, y))
{
return;
}
// The segmentationfault only occours when i check for this
if (Gridmanager::is_wall(ID))
{
return;
}
for (unsigned int i = 0; i < openList.size(); i++)
{
if (ID == openList->ID)
{
if (openList->G <= newCost)
{
return;
}
else
{
openList.erase(openList.begin() + i);
break;
}
}
}
cellPtr newChild(new SearchCell(x, y, ID, parent));
newChild->G = newCost;
newChild->H = newChild->heuristic(goalCell.get());
openList.push_back(newChild);
}
void Pathfinder::search_path()
{
while (!openList.empty())
{
cellPtr currentCell = get_next_cell();
if (currentCell->ID == goalCell->ID)
{
goalCell->parent = currentCell->parent;
SearchCell* getPath = goalCell.get();
while (getPath->parent != NULL)
{
pathList.push_back(pointPtr(new Point3));
pathList.back()->x = getPath->x;
pathList.back()->y = getPath->y;
getPath = getPath->parent;
}
foundGoal = true;
return;
}
else
{
// East cell
add_cell(currentCell->x + 1, currentCell->y, currentCell->G + 1.0f, currentCell.get());
// West cell
add_cell(currentCell->x - 1, currentCell->y, currentCell->G + 1.0f, currentCell.get());
// North cell
add_cell(currentCell->x, currentCell->y + 1, currentCell->G + 1.0f, currentCell.get());
// South cell
add_cell(currentCell->x, currentCell->y - 1, currentCell->G + 1.0f, currentCell.get());
// East-North cell
add_cell(currentCell->x + 1, currentCell->y + 1, currentCell->G + 1.414f, currentCell.get());
// West-North cell
add_cell(currentCell->x - 1, currentCell->y + 1, currentCell->G + 1.414f, currentCell.get());
// East-South cell
add_cell(currentCell->x + 1, currentCell->y - 1, currentCell->G + 1.414f, currentCell.get());
// West-South cell
add_cell(currentCell->x - 1, currentCell->y - 1, currentCell->G + 1.414f, currentCell.get());
}
}
foundGoal = false;
openList.clear();
visitedList.clear();
}
Point3 Pathfinder::next_path_pos()
{
Point3 nextPos(0, 0, 0);
nextPos.x = goalCell->x;
nextPos.y = goalCell->y;
if (!pathList.empty())
{
nextPos = *pathList.back();
pathList.pop_back();
}
if (pathList.empty())
{
openList.clear();
visitedList.clear();
foundGoal = false;
}
nextPos *= TILE_WIDTH;
return nextPos;
}Everything is working well except for the fact that i get these wierd segmentation faults when i try to order my open list with std::sort
std::sort(openList.begin(), openList.end(), cell_cmp());
But this only happends when i check for walls though..
if (Gridmanager::is_wall(ID))
{
return;
}If i comment out the above section it works alot faster but ofcourse the walls are ignored but the vector gets sorted fine with no segmentation fault.
If I comment out the sort part, the actual pathfinding works but it takes sooo long for it to be calculated.
I have searched alot on the net and this is the things ive tried:
"strict weak order"
I understand that one cause for segmentation fault with std::sort can be ambigious sorting methods. Please see the first code section (SearchCell) I am pretty sure this works as inteded (and the sort DOES work when i dont check for walls?!)
NULL pointers.
I dont have the best understanding of std::shared_ptr but i did check so the ptrs arent NULL and they dont seem to be.
Now this does seems like the most likely reason becaus when the add_cell method returns under different circumstances, there are no problems.
Debug
When debugging the callstack backwards go like this (when the crash occours):
#0 00424842 SearchCell::get_f(this=0x0)
#1 00427549 cell_cmp::operator() (this=0x22f92c, a=@0x33300b8, b=@0x22f988)
So, as you can see the compare function gets called with valid memory adresses (i think?) but the get_f() (method used for comparison) gets caleld by 0x0 (NULL pointer?)
As you can see i dont really understand what is happening, but ive tried everything and i am at a loss.
Thanks in advance for your help! / AS.
