getting help with A* pathfinding algorithm for game

Hi guys,

i have been working on a A* pathfinding algorithm and have run in some trouble. It doesn't connect the start point to the finish right. At the beginning it adds so many tiles to the closed list and not just the right path. towards the End the code only hast the best way and avoids the walls


Here an example to make it better to understand i inverted the tiles. spaces are walkable, the . are not walkable and represent the walls and the # represent the path

Code:

---

  ######################################.                                     
  ######################################.                        ###         
 #######################################.                        #.#         
 #######################################.##########################.########## 
 #######################################.#                        .           
                                      #.#                        .           
                                      #.#                        .           
                                      #.#                        .           
                                      #.#                        .           
                                      #.#                                     
                                      #.#                                     
                                      #.#              ..................     
                                      ###

---

I hope someone understands what i am doing here with the given comments in the code and can help :-( i have no idea where my misstake is.

main.cpp

Code:

---

#include <iostream>
#include "PathNode.h"
#include "PathFinding.h"
#include "MapDimensions.h"

using namespace std;

int main()
{
    tile start,finish;


char temp[mapx][mapy]=
    {


        "################################################################################",
        "########################################.#######################################",
        "########################################.#######################################",
        "########################################.##########################.############",
        "##s#####################################.##########################.#########f##",
        "########################################.##########################.############",
        "########################################.##########################.############",
        "########################################.##########################.############",
        "########################################.##########################.############",
        "########################################.##########################.############",
        "########################################.#######################################",
        "########################################.#######################################",
        "########################################.###############..................######",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################",
        "################################################################################"
    };

//get from start and finish the x and y coords
for(int i=0; i < mapx; i++)
{
    for(int j=0; j< mapy; j++)
    {
        if(temp[i][j]=='s')
        {
            start.x=i;
            start.y=j;
        }


        if(temp[i][j]=='f')
        {
            finish.x=i;
            finish.y=j;
        }


    }
}

PathFinding path;
path.findPath(temp,'#',' ','.',start,finish);


//print path
for(int t=0;t<path.closedList.size();t++)
{
    temp[path.closedList[t].x][path.closedList[t].y] = ' ';
}

//output complete map
for(int a=0; a<mapx; a++)
    {
        cout<<temp[a]<<endl;
    }



    return 0;
}

---

PathNode.h

Code:

---

#ifndef PATHNODE_H_
#define PATHNODE_H_

struct tile
{
//x and y coord of the current tile
int x;
int y;
//total score so f=g+h
int f;
// g is the steps needed from start to current point
int g;
//estimated length needed to get to goal. abs(goal.x -x) + abs(goal.y - y)
int h;
//parents x and y coords
int pX;
int pY;
};

#endif

---

MapDimensions.h

Code:

---

#ifndef MAPDIMENSIONS_H_
#define MAPDIMENSIONS_H_


//Map dimensions
    const int mapx =22;
    const int mapy =82;
    const int mapz =10;


#endif

---

PathFinding.h

Code:

---

#ifndef PATHFINDING_H_
#define PATHFINDING_H_

#include <vector>
#include "PathNode.h"
#include "MapDimensions.h"

using namespace std;

class PathFinding
{
    private:
        vector<tile> openList;
        bool isInClosed(tile a);
        bool isInOpen(tile a);
        tile getBestTile(const vector<tile> a);
        int getgScore(char matrix[mapx][mapy], char walkable, char hardwalkable,char notWalkable, tile a);
        void deleteElement(vector<tile>& a, tile b);

    public:
        PathFinding();
        vector<tile> closedList;
        void findPath(char matrix[mapx][mapy], char walkable, char hardwalkable,char notWalkable, tile start, tile finish);


};

#endif

---

PathFinding.cpp

Code:

---


#include <cmath>
#include "PathFinding.h"
#include "PathNode.h"
#include <iostream>

using namespace std;

PathFinding::PathFinding()
{
    openList.clear();
    closedList.clear();
}


bool PathFinding::isInClosed(tile a)
{

    //go through open list and if there's a match return true
    for(int i=0; i < closedList.size(); i++)
    {
        if(a.x == closedList[i].x && a.y == closedList[i].y)
        {
            return true;
        }
    }

    return false;
}


bool PathFinding::isInOpen(tile a)
{
    //go through open list and if there's a match return true
    for(int i=0; i < openList.size(); i++)
    {
        if(a.x == openList[i].x && a.y == openList[i].y)
        {
            return true;
        }
    }

    return false;
}


tile PathFinding::getBestTile(const vector<tile> a)
{
    tile best;

    /*
    best.x=a[0].x;
    best.y=a[0].y;
    best.g=a[0].g;
    best.f=a[0].f;
    best.h=a[0].h;
    best.pX=a[0].pX;
    best.pY=a[0].pY;
    */
    best =a[0];

    //find the coord with minimun f cost
    for(int i=1; i< a.size(); i++)
    {
        if(a[i].f < best.f)
        {
            /*
            best.x=a[i].x;
            best.y=a[i].y;
            best.g=a[i].g;
            best.f=a[i].f;
            best.h=a[i].h;
            best.pX=a[i].pX;
            best.pY=a[i].pY;
            */
            best=a[i];
        }
    }




    return best;



}

int PathFinding::getgScore(char matrix[mapx][mapy], char walkable, char hardwalkable,char notWalkable, tile a)
{

    int score;

    //if floor should be avoided because its not passable give it high value
    if(matrix[a.x][a.y] == notWalkable)
    {
        score =9;
    }


    //if the floor is walkable then tile is 1
    if(matrix[a.x][a.y] == walkable)
    {
        score =1;
    }

    //tile is hardwalkable so the cost to get there will be 2
    if(matrix[a.x][a.y] == hardwalkable)
    {
        score =2;
    }

    return score;

}

void PathFinding::deleteElement(vector<tile>& a, tile b)
{
    //find coord b and then if found delete it
    for(int i =0; i <a.size(); i++)
    {
        //if x and y are same we found coord
        if(a[i].x ==b.x && a[i].y == b.y)
        {

            a.erase(a.begin()+i);
        }
    }
}


void PathFinding::findPath(char matrix[mapx][mapy], char walkable, char hardwalkable,char notWalkable, tile start, tile finish)
{

    closedList.clear();
    openList.clear();

    //add the start to the closedList
    closedList.push_back(start);

    //create a variable which will be checked
    tile nCheck,parent;

    parent.x=start.x;
    parent.y=start.y;
    parent.g=0;
    parent.h=0;
    parent.f=0;
    parent.pX=start.x;
    parent.pY=start.y;

    bool endLoop =false;



    do
    {
        openList.clear();

        //check coord north
        nCheck.x=parent.x-1;
        nCheck.y=parent.y;
        nCheck.g=parent.g + getgScore(matrix,walkable,hardwalkable,notWalkable,nCheck);
        nCheck.h=abs(finish.x-nCheck.x) + abs(finish.y-nCheck.y);
        nCheck.f = nCheck.g + nCheck.h;
        nCheck.pX=parent.x;
        nCheck.pY=parent.y;
        if(nCheck.x >0 && nCheck.x < mapx && nCheck.y >0 && nCheck.y < mapy &&  isInClosed(nCheck) == false && isInOpen(nCheck) == false)
        {
                openList.push_back(nCheck);
        }


        //check south
        nCheck.x=parent.x+1;
        nCheck.y=parent.y;
        nCheck.g=parent.g + getgScore(matrix,walkable,hardwalkable,notWalkable,nCheck);
        nCheck.h=abs(finish.x-nCheck.x) + abs(finish.y-nCheck.y);
        nCheck.f = nCheck.g + nCheck.h;
        nCheck.pX=parent.x;
        nCheck.pY=parent.y;
        if(nCheck.x >0 && nCheck.x < mapx && nCheck.y >0 && nCheck.y < mapy &&  isInClosed(nCheck) == false && isInOpen(nCheck) == false)
        {
                openList.push_back(nCheck);
        }

        //check west
        nCheck.x=parent.x;
        nCheck.y=parent.y-1;
        nCheck.g=parent.g + getgScore(matrix,walkable,hardwalkable,notWalkable,nCheck);
        nCheck.h=abs(finish.x-nCheck.x) + abs(finish.y-nCheck.y);
        nCheck.f = nCheck.g + nCheck.h;
        nCheck.pX=parent.x;
        nCheck.pY=parent.y;
        if(nCheck.x >0 && nCheck.x < mapx && nCheck.y >0 && nCheck.y < mapy &&  isInClosed(nCheck) == false && isInOpen(nCheck) == false)
        {
                openList.push_back(nCheck);
        }

        //check east
        nCheck.x=parent.x;
        nCheck.y=parent.y+1;
        nCheck.g=parent.g + getgScore(matrix,walkable,hardwalkable,notWalkable,nCheck);
        nCheck.h=abs(finish.x-nCheck.x) + abs(finish.y-nCheck.y);
        nCheck.f = nCheck.g + nCheck.h;
        nCheck.pX=parent.x;
        nCheck.pY=parent.y;
        if(nCheck.x >0 && nCheck.x < mapx && nCheck.y >0 && nCheck.y < mapy &&  isInClosed(nCheck) == false && isInOpen(nCheck) == false)
        {
                openList.push_back(nCheck);
        }

        //if a coord in the open list is the finish set its values so that it will definitly be added
        for(int i =0; i < openList.size(); i++)
        {
            if(openList[i].x == finish.x && openList[i].y == finish.y)
            {
                openList[i].g=0;
                openList[i].h=0;
                openList[i].f=0;
            }
        }

            //get best f score from the added tiles in the openList
            closedList.push_back(getBestTile(openList));
          //setting parent to the best connection tile
        parent=getBestTile(openList);
            deleteElement(openList,getBestTile(openList));



        //to end the while loop since finish was reached
        if(isInClosed(finish) == true)
        {
            endLoop=true;
        }

        //just to see what is in the open list
        for(int i =0; i <openList.size(); i++)
        {
            if(i==0)
            {
              cout<<"openList"<<endl;
            }

            cout<<"x:"<<openList[i].x<<" y:"<<openList[i].y<<endl;

        }

    }
    while(endLoop != true);

    //to see what is in closed list
    for(int i=0; i<closedList.size(); i++)
    {
        cout<<"x"<<closedList[i].x<<" y"<<closedList[i].y<<endl;
    }




}

---

Your findPath implementation looks very weird. You seems to have mixed openList and closedList at a few places and so on. Check the pseudocode at wikipedia for an example implementation. It should be pretty straight-forward to implement A* from that (although I had to make quite radical modifications of your program to make it work).

Quote:

---

Originally Posted by Shakti

Your findPath implementation looks very weird. You seems to have mixed openList and closedList at a few places and so on. Check the pseudocode at wikipedia for an example implementation. It should be pretty straight-forward to implement A* from that (although I had to make quite radical modifications of your program to make it work).

---

ok could you hint me a bit more since i have been looking at it a long time :-)

I was using this as my guide to making it. the Pseudo Code is at the end almost Introduction to A* Pathfinding

Well to start off, openList.clear() clears the openList, while what you want to do is remove the tile with the lowest f score. Open list should contain the start tile when you enter the loop (so the first item you remove from the open list is the start tile).

You want to break the loop as soon as you have the destination tile in the closed list. Although a more efficient way would probably check if current tile is destination tile.

There are a few other problematic things aswell but start with those and see if you can not figure out the rest :)

Quote:

---

Originally Posted by Shakti

Well to start off, openList.clear() clears the openList, while what you want to do is remove the tile with the lowest f score. Open list should contain the start tile when you enter the loop (so the first item you remove from the open list is the start tile).

You want to break the loop as soon as you have the destination tile in the closed list. Although a more efficient way would probably check if current tile is destination tile.

There are a few other problematic things aswell but start with those and see if you can not figure out the rest :)

---

Okay thanks :-) will do. But what diffrence does it make if i add the start tile first to the openList and then remove it from there just to put it in the closedList in the first move :-)?
As a so to say backup in case no start is given to prevent errors ?

I'll do my best to figure the rest :-)

By doing that you won't have to do any special case for the first time around. The loop will then stay absolutely the same from start to the end.

Quote:

---

Originally Posted by Shakti

By doing that you won't have to do any special case for the first time around. The loop will then stay absolutely the same from start to the end.

---

Question to the pseudocode of the wiki. what exactly is the came_from ? Should i understand it as the Map given to the function or is it also a list which contains nodes of the path?

Came from in the wikipedia pseudocode is used to construct the path when the calculation is finished. It is roughly equivalent to pX and pY in your code.

okay thanks :-)

the tentative g_score is the the gscore of the tile i am looking at neighboring the current tile right? and if its bigger than the rest it should be ignored?
If its smaller then i should set its came from to current. and if not in openlist add it

Yah that sounds right :)

Quote:

---

Originally Posted by Shakti

Yah that sounds right :)

---

okay so practily speaking by my code only set the pX and pY before i add the best tile to the closed List or and not before?

And if the current route would be better set pX and pY and then add its tile to the openlist?

Code:

---

if(isInOpen(nCheck) == true)
        {
            if(nCheck.f < parent.f)
            {
                //how exactly do i have to implement here having trouble with thinking of how
            }
        }

---

I have trouble trying to figure out what to write in this condition what it should exactly do because this condition is missing in my code because how its written in the wiki and the other tutorial is kind of confusing me :p. The other suggestions that you said i should start with fixing i have fixed. here the code like it is right now

Code:

---

void PathFinding::findPath(char matrix[mapx][mapy], char walkable, char hardwalkable,char notWalkable, tile start, tile finish)
{

    closedList.clear();
    openList.clear();

    //add the start to the closedList
    start.g=0;
    start.h=abs(finish.x-start.x) + abs(finish.y-start.y);
    start.f=start.g+start.h;
    start.pX=start.x;
    start.pY=start.y;

    closedList.push_back(start);

    //create a variable which will be checked
    tile nCheck,parent;

    parent=start;

    bool endLoop = false;

    do
    {
        //check coord north
        nCheck.x=parent.x-1;
        nCheck.y=parent.y;
        nCheck.g=parent.g + getgScore(matrix,walkable,hardwalkable,notWalkable,nCheck);
        nCheck.h=abs(finish.x-nCheck.x) + abs(finish.y-nCheck.y);
        nCheck.f = nCheck.g + nCheck.h;
        nCheck.pX=parent.x;
        nCheck.pY=parent.y;
        if(nCheck.x >=0 && nCheck.x < mapx && nCheck.y  >=0 && nCheck.y < mapy &&  isInClosed(nCheck) ==  false && isInOpen(nCheck) == false &&  matrix[nCheck.x][nCheck.y]!=notWalkable)
        {
                openList.push_back(nCheck);
        }

        if(isInOpen(nCheck) == true)
        {
            if(nCheck.f < parent.f)
            {

            }
        }



        //check south
        nCheck.x=parent.x+1;
        nCheck.y=parent.y;
        nCheck.g=parent.g + getgScore(matrix,walkable,hardwalkable,notWalkable,nCheck);
        nCheck.h=abs(finish.x-nCheck.x) + abs(finish.y-nCheck.y);
        nCheck.f = nCheck.g + nCheck.h;
        nCheck.pX=parent.x;
        nCheck.pY=parent.y;
        if(nCheck.x >=0 && nCheck.x < mapx && nCheck.y  >=0 && nCheck.y < mapy &&  isInClosed(nCheck) ==  false && isInOpen(nCheck) == false &&  matrix[nCheck.x][nCheck.y]!=notWalkable)
        {
                openList.push_back(nCheck);
        }

        //check west
        nCheck.x=parent.x;
        nCheck.y=parent.y-1;
        nCheck.g=parent.g + getgScore(matrix,walkable,hardwalkable,notWalkable,nCheck);
        nCheck.h=abs(finish.x-nCheck.x) + abs(finish.y-nCheck.y);
        nCheck.f = nCheck.g + nCheck.h;
        nCheck.pX=parent.x;
        nCheck.pY=parent.y;
        if(nCheck.x >=0 && nCheck.x < mapx && nCheck.y  >=0 && nCheck.y < mapy &&  isInClosed(nCheck) ==  false && isInOpen(nCheck) == false &&  matrix[nCheck.x][nCheck.y]!=notWalkable)
        {
                openList.push_back(nCheck);
        }

        //check east
        nCheck.x=parent.x;
        nCheck.y=parent.y+1;
        nCheck.g=parent.g + getgScore(matrix,walkable,hardwalkable,notWalkable,nCheck);
        nCheck.h=abs(finish.x-nCheck.x) + abs(finish.y-nCheck.y);
        nCheck.f = nCheck.g + nCheck.h;
        nCheck.pX=parent.x;
        nCheck.pY=parent.y;
        if(nCheck.x >=0 && nCheck.x < mapx && nCheck.y  >=0 && nCheck.y < mapy &&  isInClosed(nCheck) ==  false && isInOpen(nCheck) == false &&  matrix[nCheck.x][nCheck.y]!=notWalkable)
        {
                openList.push_back(nCheck);
        }

        //if a coord in the open list is the finish set its values so that it will definitly be added
        for(int i =0; i < openList.size(); i++)
        {
            if(openList[i].x == finish.x && openList[i].y == finish.y)
            {
                openList[i].g=0;
                openList[i].h=0;
                openList[i].f=0;
            }
        }

            //get best f score from the added tiles in the openList
            closedList.push_back(getBestTile(openList));
            //set the parent to the best tile
            parent=getBestTile(openList);

            deleteElement(openList,getBestTile(openList));


        //to end the while loop since finish was reached
        if(isInClosed(finish) == true)
        {
            endLoop=true;
        }

     
 

    }
    while(endLoop != true);


}

---

Break things up more. This condition is just crazy:

Code:

---

if(nCheck.x >=0 && nCheck.x < mapx && nCheck.y  >=0 && nCheck.y < mapy &&  isInClosed(nCheck) ==  false && isInOpen(nCheck) == false &&  matrix[nCheck.x][nCheck.y]!=notWalkable)

---

Break it up more.

Also you are not close to mapping the wikipedia code to your own. What is your g_score container? What is your f_score container? Sure you store those values but where do you look these values up at all times? came_from is your pX and pY but this isn't the easiest way of doing this.

I strongly suggest you start from scratch and try to map the pseudocode more directly to c++ code, and pay special care to what containers you will need and what values you need to keep track of.

gscore container oder f score container? I need to new containers to collect all of these seperatly from the Information stored in every node?

i am trying to find out how to formulate the checking of g and f after each step that is where i am having problems and the pseudocode does not help. I need some help in this point what to do in sense of deleting the parent node from closedlist and therefore adding the checked node ?when for example from parent the node north of it has a better f score.

Got it finally to work :-) will post the code later on here in case anyone finds this thread and wants to build there own pathfinder :-)