• Create Account

### #ActualAlanSmithee

Posted 22 April 2012 - 07:08 PM

Hello.

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());
}
};
};

/* 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 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[i]->ID)
{
if (openList[i]->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.

### #3AlanSmithee

Posted 22 April 2012 - 03:31 PM

Hello.

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());
}
};
};

/* 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 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[i]->ID)
{
if (openList[i]->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.

### #2AlanSmithee

Posted 22 April 2012 - 03:06 PM

Hello.

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
{
if (a->get_f() <= b->get_f())
return true;

else if (a->get_f() > b->get_f())
return true;
}
};

/* 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 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[i]->ID)
{
if (openList[i]->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.

### #1AlanSmithee

Posted 22 April 2012 - 03:01 PM

Hello.

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
{
if (a->get_f() <= b->get_f())
return true;

else if (a->get_f() > b->get_f())
return true;
}
};

/* 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 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[i]->ID)
{
if (openList[i]->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.