Thread: getting help with A* pathfinding algorithm for game

  1. #1
    Registered User
    Join Date
    Mar 2012
    Posts
    18

    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;
        }
    
    
    
    
    }
    Last edited by Thorbenn; 02-24-2013 at 01:42 PM.

  2. #2
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    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).

  3. #3
    Registered User
    Join Date
    Mar 2012
    Posts
    18
    Quote Originally Posted by Shakti View Post
    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

  4. #4
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    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

  5. #5
    Registered User
    Join Date
    Mar 2012
    Posts
    18
    Quote Originally Posted by Shakti View Post
    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 :-)

  6. #6
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    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.

  7. #7
    Registered User
    Join Date
    Mar 2012
    Posts
    18
    Quote Originally Posted by Shakti View Post
    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?

  8. #8
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    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.

  9. #9
    Registered User
    Join Date
    Mar 2012
    Posts
    18
    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

  10. #10
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    Yah that sounds right

  11. #11
    Registered User
    Join Date
    Mar 2012
    Posts
    18
    Quote Originally Posted by Shakti View Post
    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 . 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);
    
    
    }
    Last edited by Thorbenn; 02-28-2013 at 11:47 AM.

  12. #12
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    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.

  13. #13
    Registered User
    Join Date
    Mar 2012
    Posts
    18
    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.

  14. #14
    Registered User
    Join Date
    Mar 2012
    Posts
    18
    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 :-)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. All-angle pathfinding algorithm?
    By TriKri in forum Game Programming
    Replies: 6
    Last Post: 06-20-2007, 07:26 PM
  2. Trouble Generating Game Algorithm
    By justlivelife15 in forum Game Programming
    Replies: 3
    Last Post: 06-13-2007, 09:58 AM
  3. Saving Game data algorithm,perhaps?
    By Sentral in forum Game Programming
    Replies: 2
    Last Post: 08-25-2006, 06:14 PM
  4. My pathfinding algorithm
    By BobMcGee123 in forum Game Programming
    Replies: 7
    Last Post: 09-23-2005, 05:08 PM
  5. need algorithm for game of life
    By Unregistered in forum C Programming
    Replies: 9
    Last Post: 05-18-2002, 11:27 PM