[SFML 2.0]Problem with A* algorithm

[noct]

Hello there. Im working on an implementation of A* algorithm for my SFML game-project. I've recently got some problems with passing 2d arrays to a function (I think).

I got segmentation fault error when receving array[][sizex] (I have an idea why) and many other errors with array[sizey][sizex].
Lets take a look on the code:

aStar.hpp:

//(...)
class Node
{
public:
Node();
sf::Vector2i position;
sf::Vector2i parentPosition;

int gCost;
int hCost;
int fCost;

bool operator == (const Node & nod);


};

class aStar
{
public:

aStar();
int manhattan(sf::Vector2i start, sf::Vector2i end);

Node StartNode;
Node EndNode;

  vector<Node> OpenSet;
  vector<Node> ClosedSet;
  vector<Node> NeighborSet;
  vector<Node> PathSet;

void findPath(sf::Vector2i start, sf::Vector2i end, int tmap[10][10], int collisionMap[10][10]);
void buildPath();
int minfCost(vector<Node> vec);
void findNeighbors(Node CurrentNode, int tmap[10][10], int collisionMap[10][10]);

};
//(...)

aStar.cpp:

//(...)
aStar::aStar()
{
StartNode.parentPosition = sf::Vector2i(0,0);

}

Node::Node()
{
gCost = 0;
hCost = 0;
}


//int Node::fCost() { return gCost+hCost; }

void aStar::findNeighbors(Node CurrentNode, int tmap[10][10], int collisionMap[10][10])
{

   for (int y=-1; y<=1; y++)
{
    for (int x=-1; x<=1; x++)
    {
        int checkX=CurrentNode.position.x+x, checkY=CurrentNode.position.y+y;

        if(x==0 && y==0) {continue; }

        if(checkX < 0 || checkX > 10 || checkY < 0 || checkY > 10) {continue; }
        if(collisionMap[checkY][checkX] == 0)
        {
            Node newNode;
            newNode.position = sf::Vector2i(checkX, checkY);
            newNode.parentPosition = CurrentNode.position;

            if((newNode.position.x==CurrentNode.position.x && newNode.position.y!=CurrentNode.position.y) ||
               (newNode.position.y==CurrentNode.position.y && newNode.position.x!=CurrentNode.position.x))
                    {
                     newNode.gCost = 10 + CurrentNode.gCost;
                    }
            else
                    {
                     newNode.gCost = 14 + CurrentNode.gCost;
                    }

           // OpenSet.push_back(newNode);

           NeighborSet.push_back(newNode);
            tmap[checkY][checkX] = 1;
        }


    }


}
}

bool Node::operator == (const Node & nod)
{ return (this->position == nod.position); }

int aStar::manhattan(sf::Vector2i start, sf::Vector2i end)
{
    int dist;
    dist = abs(start.x - end.x) + abs(start.y - end.y);
    return (dist*10);
}


int aStar::minfCost(vector<Node> vec)
{ int min = vec[0].fCost;
 unsigned int i=0;
    for(; i<vec.size(); i++)
    {
        if(vec[i].fCost < min) {min =vec[i].fCost; }
    }
    return i;
}


void aStar::findPath(sf::Vector2i start, sf::Vector2i end, int tmap[10][10], int collisionMap[10][10])
{

StartNode.position = start;
StartNode.gCost = 0;
StartNode.fCost = StartNode.gCost + manhattan(start, end);
EndNode.position = end;

Node CurrentNode;

OpenSet.push_back(StartNode);

while (OpenSet.size() > 0)
{
    CurrentNode = OpenSet[minfCost(OpenSet)];
    if(CurrentNode == EndNode) { buildPath();   return ; }

OpenSet.erase( remove(OpenSet.begin(), OpenSet.end(), CurrentNode), OpenSet.end() );
ClosedSet.push_back(CurrentNode);

findNeighbors(CurrentNode, tmap, collisionMap);
for ( unsigned int i=0; i<NeighborSet.size(); i++)
{
    if(find(ClosedSet.begin(), ClosedSet.end(), NeighborSet[i]) != ClosedSet.end() )
    {
        continue;
    }
      int tent = CurrentNode.gCost + manhattan(CurrentNode.position, NeighborSet[i].position);

    if(! (find(OpenSet.begin(), OpenSet.end(), NeighborSet[i]) != OpenSet.end() ))
    {// not found
      OpenSet.push_back(NeighborSet[i]);
    }
    else if (tent >= NeighborSet[i].gCost)
    {
        continue;
    }

    NeighborSet[i].fCost = NeighborSet[i].gCost = manhattan(NeighborSet[i].position, EndNode.position);
}

}

}

void aStar::buildPath()
{
    PathSet.push_back(EndNode);
    Node newNode = EndNode;
    while (newNode.parentPosition != sf::Vector2i(-1,-1)) // only possible if newNode == StartNode
    {
        newNode.position = newNode.parentPosition;
        PathSet.push_back(newNode);
    }


}
//(...)

I know it's a big piece of code, sorry for that, however I am not able to specify what's going wrong here.
I know this code Isn't the highest quality, I want to optimise it after I'll have it working
I use std namespace by default.

I got an error wherever I use tmap[10][10] (ctrl+f it)

tmap is a 10x10 int array filled with 0,1,2,3 ("block" numbers)
collisionMap is a 10x10 int array filled with 0 if a "block" is walkable, 1 if isn't and 2 if a "block" is start/end of desired path.

If you think the only option is to rewrite the entire thing, just tell me. I'm looking for at least some tips if fixing this is not possible/worth.



Debugger output: http://pastebin.com/uRFxyrXa

I've been using those pseudocodes/tutorials: (+stack ofc)
http://www.growingwiththeweb.com/2012/06/a-pathfinding-algorithm.html
https://en.wikipedia.org/wiki/A*_search_algorithm
http://www.policyalmanac.org/games/aStarTutorial.htm

[eXpl0it3r]

Arrays and std::vectors start with 0 as index. If allocate 10, elemts than you use the indices 0-9. In your code however you're trying to access the index 10 which will lead to undefined behavior and thus a crash.

Btw. this a very, very basic C++ beginners mistake, maybe it would be good to spend a bit more time with simpler things than an A* algorithm?

[noct]

Do you mean this?

  if(checkX < 0 || checkX > 10 || checkY < 0 || checkY > 10) {continue; }

It's for sure not the line causing error here (in most and in tested cases), corrected it tho.

I think I need A* for later management of multiple entities - it's the easiest and optimal algorithm which can be expanded with more movement costs.

I'm wondering if storing parentPosition is enough - do I need a class (Node'ish) object instead?

Btw, even experts happen to make stupid/be tired mistakes, this doesn't indicate anything.


#Changed Manhattan to 8-way distance measuring

[noct]

Ok, got it to be working properly. Well, kinda.

bool aStar::findPath(sf::Vector2i start, sf::Vector2i end, int tmap[10][10], int collisionMap[10][10])
{
    cout << "START" << endl;
    cout <<end.x<<" " << end.y <<endl;
StartNode.position = start;
EndNode.position = end;

OpenSet.push_back(StartNode);


while (OpenSet[minfCost(OpenSet)] != EndNode )
{
Node CurrentNode;
CurrentNode = OpenSet[minfCost(OpenSet)];


OpenSet.erase( remove(OpenSet.begin(), OpenSet.end(), CurrentNode), OpenSet.end() );
ClosedSet.push_back(CurrentNode);
tmap[CurrentNode.position.y][CurrentNode.position.x] = 2;

if(CurrentNode == EndNode) {break; }


// neighbors
for (int y=-1; y<=1; y++)
{
    for (int x=-1; x<=1; x++)
    {
     int checkX=CurrentNode.position.x+x, checkY=CurrentNode.position.y+y;

        if(x==0 && y==0) { continue; }

        if(checkX < 0 || checkX > 9 || checkY < 0 || checkY > 9) {continue; }
        if(collisionMap[checkY][checkX] == 0)
        {
         Node newNode;
         newNode.position = sf::Vector2i(checkX, checkY);
         newNode.parentPosition = CurrentNode.position;

            if((newNode.position.x==CurrentNode.position.x && newNode.position.y!=CurrentNode.position.y) ||
               (newNode.position.y==CurrentNode.position.y && newNode.position.x!=CurrentNode.position.x))
                  { newNode.gCost = 10 + CurrentNode.gCost; }
            else
                  { newNode.gCost = 14 + CurrentNode.gCost; }

         newNode.hCost = heuristic(newNode.position, EndNode.position);
         newNode.fCost = newNode.gCost + newNode.hCost;
         OpenSet.push_back(newNode);
         tmap[checkY][checkX]=1;

        OpenSet.erase( remove(OpenSet.begin(), OpenSet.end(), CurrentNode), OpenSet.end() );
         ClosedSet.push_back(CurrentNode);
        }

    }
}

cout << CurrentNode.parentPosition.x << " " << CurrentNode.parentPosition.y<< endl;

}
/*
int tmpx=OpenSet[minfCost(OpenSet)].position.x, tmpy=OpenSet[minfCost(OpenSet)].position.y;
tmap[tmpy][tmpx] = 5;
cout <<"BUILD PATH" << endl;
*/
cout << "EXIT FINDING" << endl;

OpenSet.clear();
ClosedSet.clear();
return true;
}

This's how it's working so far. Green rects are "open", red "closed", black are impassable. It's not slow, I've just set a 1s timer between findPath() function calls.

Now I know the algorithm ends when it should be, however I have a problem with filling PathSet. Algorithm stops when "currentNode" is equal to "EndNode" (i've got == an != operator overloads with object.position comparision)

I don't think so, but should I disable checking from ClosedSet? How am I able to get my ParentNode as Node class object? AFAIK class can't contain it's own objects.

[Zentropy]

A class can't contain itself as a stack member field, but it CAN contain a pointer to its type.  That is,

class Node
{
public:
     Node();
private:
    Node parentNode;  //Not okay.
}

is illegal, but

class Node
{
public:
     Node();
private:
    Node* parentNode;  //THIS Node* is ok
}

is totally valid and how linked lists are done in C++.  Doing your comparison to EndNode check via pointer address is also what you want to do instead of comparing data fields (like you're doing now) anyway.  This is because in general when doing this kind of check, you want to know if the CurrentNode IS the EndNode (that is, literally the same object at the same place in memory), while your method now doesn't care whether CurrentNode actually IS EndNode, just that they share some equivalent values.  I don't think it matters in this particular case, but most of the time it WILL matter.  It's super imperative to understand this distinction or you're gonna have a really bad time sooner or later