Home
Blogs
Forums
News
Portfolios
Projects
Tutorials
32 users logged in
New? Learn about game development.
Before posting, review our community guidelines.
Follow Us
Chat in the GameDev.net Discord!
Mastodon
Back to General and Gameplay Programming

Problem with A*

Started by
10 comments, last by Gleade 9 years, 5 months ago

Hello, I am attempting to create my own version of A*. The trouble I'm having is mainly that my program isn't finding the closed nodes properly. And all in all I'm not sure if I'm even doing it the right way. Is there anyone that can help point me in the right direction?

Here is my code:

PathFinder.cpp


PathFinder::PathFinder(unsigned int width, unsigned int height, std::vector<int> newMap)
{
    this->width = width;
    this->height = height;

    for (unsigned int i = 0; i < width; ++i)
    {
        for (unsigned int j = 0; j < height; ++j)
        {
            // Create our map and assign the nodes their positions
            map.push_back(new Node(i * 32, j * 32));

            // If there is a collision node here, add it to the closed list
            if(newMap[i + j] > 0)
            {

                closedList.push_back(map[i + j]);
            }
        }
    }
}

PathFinder::~PathFinder()
{

}

bool PathFinder::checkClosed(Node *node)
{
    for (std::vector<Node*>::iterator it = closedList.begin() ; it != closedList.end(); ++it)
    {
        if(*it == node)
        {
            return true;
        }
    }

    return false;

}

bool PathFinder::checkOpen(Node *node)
{
    for (std::vector<Node*>::iterator it = openList.begin() ; it != openList.end(); ++it)
    {
        if(*it == node)
        {
            //std::cout << "a" << std::endl;
            return true;
        }
    }

    return false;

}

std::vector<int> PathFinder::findPath(Node &start, Node &finish)
{
    // Initalize variables
    for(std::vector<Node*>::iterator it = map.begin() ; it != map.end(); ++it)
    {
        // Reset our list
        (*it)->Gvalue = 10;
        (*it)->Hvalue = 0;
        (*it)->searchX = 0;
        (*it)->searchY = 0;
         (*it)->shape.setFillColor(sf::Color::Black);
    }
    foundFinish = false;
    std::vector<int> result;
    closedList.clear();
    openList.clear();


    // Set our parent node to the start of the search area
    nodeParent = &start;

    // Add our parent node to the open list
    // to search for surrounding nodes
    openList.push_back(nodeParent);
    // For debugging
    openList[0]->shape.setFillColor(sf::Color::Blue);

    while(!foundFinish)
    {
        // Search for surrounding nodes not in the closed list
        for(unsigned int i=0; i < openList.size(); i++)
        {

            // IF we've found the finish
            if(openList[i]->x == finish.x && openList[i]->y == finish.y)
            {
                foundFinish = true;
            }


            // If we've found the finish
            if(openList[i]->x == finish.x && openList[i]->y == finish.y)
            {
                // We've found the node, so finish here
                foundFinish = true;
                openList[i]->shape.setFillColor(sf::Color::Green);
                // Exit out of the loop
                break;
            }

            for(std::vector<Node*>::iterator it = map.begin() ; it != map.end(); ++it)
            {
                // Find node to the left of us
                if(((*it)->x == openList[i]->x-32 && (*it)->y == openList[i]->y))
                {
                    if(!checkClosed(*it) && !checkOpen(*it))
                    {
                        // Add to the GValue
                        (*it)->Gvalue += openList[i]->Gvalue;
                        // Set our Hvalue to the shortest path
                        (*it)->setShortestPath(finish);
                        // Calculate our Fvalue F = G + H
                        (*it)->calculateHValue();
                        openList.push_back(*it);
                    }
                }

                // Find node to the left-diagonal of us
                if(((*it)->x == openList[i]->x-32 && (*it)->y == openList[i]->y-32))
                {
                    if(!checkClosed(*it) && !checkOpen(*it))
                    {
                        // Add to the GValue
                        (*it)->Gvalue += openList[i]->Gvalue + 4;
                        // Set our Hvalue to the shortest path
                        (*it)->setShortestPath(finish);
                        // Calculate our Fvalue F = G + H
                        (*it)->calculateHValue();
                        openList.push_back(*it);
                    }
                }

                // Find node to the right of us
                if((*it)->x == openList[i]->x+32 && (*it)->y == openList[i]->y)
                {
                    if(!checkClosed(*it) && !checkOpen(*it))
                    {
                        // Add to the GValue
                        (*it)->Gvalue += openList[i]->Gvalue;
                        // Set our Hvalue to the shortest path
                        (*it)->setShortestPath(finish);
                        // Calculate our Fvalue F = G + H
                        (*it)->calculateHValue();
                        openList.push_back(*it);
                    }
                }

                // Find node to the right- diagonal of us
                if((*it)->x == openList[i]->x+32 && (*it)->y == openList[i]->y-32)
                {
                    if(!checkClosed(*it) && !checkOpen(*it))
                    {
                        // Add to the GValue
                        (*it)->Gvalue += openList[i]->Gvalue + 4;
                        // Set our Hvalue to the shortest path
                        (*it)->setShortestPath(finish);
                        // Calculate our Fvalue F = G + H
                        (*it)->calculateHValue();
                        openList.push_back(*it);
                    }
                }

                // Find node below us
                if((*it)->x == openList[i]->x && (*it)->y == openList[i]->y + 32)
                {
                    if(!checkClosed(*it) && !checkOpen(*it))
                    {
                        // Add to the GValue
                        (*it)->Gvalue += openList[i]->Gvalue;
                        // Set our Hvalue to the shortest path
                        (*it)->setShortestPath(finish);
                        // Calculate our Fvalue F = G + H
                        (*it)->calculateHValue();
                        openList.push_back(*it);
                    }
                }

                // Find node right-below diagonal us
                if((*it)->x == openList[i]->x + 32 && (*it)->y == openList[i]->y + 32)
                {
                    if(!checkClosed(*it) && !checkOpen(*it))
                    {
                        // Add to the GValue
                        (*it)->Gvalue += openList[i]->Gvalue + 4;
                        // Set our Hvalue to the shortest path
                        (*it)->setShortestPath(finish);
                        // Calculate our Fvalue F = G + H
                        (*it)->calculateHValue();
                        openList.push_back(*it);
                    }
                }


                // Find node above us
                if((*it)->x == openList[i]->x && (*it)->y == openList[i]->y-32)
                {
                    if(!checkClosed(*it) && !checkOpen(*it))
                    {
                        // Add to the GValue
                        (*it)->Gvalue += openList[i]->Gvalue;
                        // Set our Hvalue to the shortest path
                        (*it)->setShortestPath(finish);
                        // Calculate our Fvalue F = G + H
                        (*it)->calculateHValue();
                        openList.push_back(*it);
                    }
                }

                    // Find node above-left diagonal us
                if((*it)->x == openList[i]->x-32 && (*it)->y == openList[i]->y-32)
                {
                    if(!checkClosed(*it) && !checkOpen(*it))
                    {
                        // Add to the GValue
                        (*it)->Gvalue += openList[i]->Gvalue + 4;
                        // Set our Hvalue to the shortest path
                        (*it)->setShortestPath(finish);
                        // Calculate our Fvalue F = G + H
                        (*it)->calculateHValue();
                        openList.push_back(*it);
                    }
                }
            }

            // Remove the current node from the open list to the closed list

            closedList.push_back(openList[i]);
            //openList.erase(openList.begin());
            std::sort(openList.begin(), openList.end(), sortByFValue);
            i = 0;
        }

        std::cout << "Found path ";
        // After for loop
    }



    return result;
}

Node.cpp


Node::Node(unsigned int xPos, unsigned int yPos)
{
    x = xPos;
    y = yPos;
}

bool Node::compareNode(Node other)
{
    if(other.x == searchX && searchY == other.y)
    {
        return true;
    }
    else
    {
          return false;
    }

}

void Node::calculateHValue()
{
    Fvalue = Gvalue + Hvalue;
}


void Node::setShortestPath(Node other)
{
    searchX = x;
    searchY = y;
    // While we aren't the finish node
    while(!compareNode(other))
    {
       // std::cout << "x: " << searchX << " y: " << searchY << " finding: " << other.x << " " << other.y << std::endl;
        // Move our search x and y to the node
        if(searchX > other.x)
        {
            searchX -= 32;
        }
        else if(searchX < other.x)
        {
            searchX += 32;
        }
        else if(searchY > other.y)
        {
            searchY -= 32;
        }
        else if(searchY < other.y)
        {
            searchY += 32;
        }

        // Increment our Hvalue
        Hvalue += 1;

    }

}
Advertisement

for(unsigned int i=0; i < openList.size(); i++)

It's never a good idea to iterate a container AND modify it at the same time. Elements can become invalid.

According to the Wikipedia article, you should loop while the openList is not empty:


while(openList.size())  // instead of while(!foundFinish)
{
    // pathfinding stuff here
}

I also don't see you ever remove anything from the openList. You've commented that part of your code out:


//openList.erase(openList.begin());
"I would try to find halo source code by bungie best fps engine ever created, u see why call of duty loses speed due to its detail." -- GettingNifty

Hello Gleade.

If you want you can look here https://github.com/Mikalai/punk_project_a/blob/master/source/badziaha/global_field.cpp function findPathA(). This implementation is based on the article from wikipedia.

Maybe it will help you.

Hey guys, thanks for your replies. I took your advice TheComet & re-thought the design for my code. Now I just need to trace back and return the path.

Here is what I came up with and it seems to work:


std::vector<int> PathFinder::findPath(Node &start, Node &finish)
{
    // Initalize variables
    for(std::vector<Node*>::iterator it = map.begin() ; it != map.end(); ++it)
    {
        // Reset our list
        (*it)->Gvalue = 10;
        (*it)->Hvalue = 0;
        (*it)->searchX = 0;
        (*it)->searchY = 0;
        (*it)->shape.setFillColor(sf::Color::Black);
    }
    foundFinish = false;
    std::vector<int> result;
    closedList.clear();
    closedList = oldClosedList;
    openList.clear();


    // Set our parent node to the start of the search area
    nodeParent = &start;

    // Add our parent node to the open list
    // to search for surrounding nodes
    openList.push_back(nodeParent);
    // For debugging
    openList[0]->shape.setFillColor(sf::Color::Blue);

    if(inBounds(&finish))
    {

        while(openList.size())
        {


            nodeParent = openList.front();


            closedList.push_back(nodeParent);

                        // If we've found the finish
            if(nodeParent->x == finish.x && nodeParent->y == finish.y)
            {
                // We've found the node, so finish here
                closedList.push_back(openList[0]);
                foundFinish = true;
                nodeParent->shape.setFillColor(sf::Color::Green);
                break;
            }

             for(std::vector<Node*>::iterator it = map.begin() ; it != map.end(); ++it)
                {
                    // Find node to the left of us
                    if(((*it)->x == openList[0]->x-32 && (*it)->y == openList[0]->y))
                    {
                        if(!checkClosed(*it) && !checkOpen(*it))
                        {
                            // Add to the GValue
                            (*it)->Gvalue += openList[0]->Gvalue;
                            // Set our Hvalue to the shortest path
                            (*it)->setShortestPath(finish);
                            // Calculate our Fvalue F = G + H
                            (*it)->calculateHValue();
                            openList.push_back(*it);
                        }
                    }

                    // Find node to the left-diagonal of us
                    if(((*it)->x == openList[0]->x-32 && (*it)->y == openList[0]->y-32))
                    {
                        if(!checkClosed(*it) && !checkOpen(*it))
                        {
                            // Add to the GValue
                            (*it)->Gvalue += openList[0]->Gvalue + 4;
                            // Set our Hvalue to the shortest path
                            (*it)->setShortestPath(finish);
                            // Calculate our Fvalue F = G + H
                            (*it)->calculateHValue();
                            openList.push_back(*it);

                        }
                    }

                    // Find node to the right of us
                    if((*it)->x == openList[0]->x+32 && (*it)->y == openList[0]->y)
                    {
                        if(!checkClosed(*it) && !checkOpen(*it))
                        {
                            // Add to the GValue
                            (*it)->Gvalue += openList[0]->Gvalue;
                            // Set our Hvalue to the shortest path
                            (*it)->setShortestPath(finish);
                            // Calculate our Fvalue F = G + H
                            (*it)->calculateHValue();
                            openList.push_back(*it);
                        }
                    }

                    // Find node to the right- diagonal of us
                    if((*it)->x == openList[0]->x+32 && (*it)->y == openList[0]->y-32)
                    {
                        if(!checkClosed(*it) && !checkOpen(*it))
                        {
                            // Add to the GValue
                            (*it)->Gvalue += openList[0]->Gvalue + 4;
                            // Set our Hvalue to the shortest path
                            (*it)->setShortestPath(finish);
                            // Calculate our Fvalue F = G + H
                            (*it)->calculateHValue();
                            openList.push_back(*it);
                        }
                    }

                    // Find node below us
                    if((*it)->x == openList[0]->x && (*it)->y == openList[0]->y + 32)
                    {
                        if(!checkClosed(*it) && !checkOpen(*it))
                        {
                            // Add to the GValue
                            (*it)->Gvalue += openList[0]->Gvalue;
                            // Set our Hvalue to the shortest path
                            (*it)->setShortestPath(finish);
                            // Calculate our Fvalue F = G + H
                            (*it)->calculateHValue();
                            openList.push_back(*it);

                        }
                    }

                    // Find node right-below diagonal us
                    if((*it)->x == openList[0]->x + 32 && (*it)->y == openList[0]->y + 32)
                    {
                        if(!checkClosed(*it) && !checkOpen(*it))
                        {
                            // Add to the GValue
                            (*it)->Gvalue += openList[0]->Gvalue + 4;
                            // Set our Hvalue to the shortest path
                            (*it)->setShortestPath(finish);
                            // Calculate our Fvalue F = G + H
                            (*it)->calculateHValue();
                            openList.push_back(*it);
                        }
                    }


                    // Find node above us
                    if((*it)->x == openList[0]->x && (*it)->y == openList[0]->y-32)
                    {
                        if(!checkClosed(*it) && !checkOpen(*it))
                        {
                            // Add to the GValue
                            (*it)->Gvalue += openList[0]->Gvalue;
                            // Set our Hvalue to the shortest path
                            (*it)->setShortestPath(finish);
                            // Calculate our Fvalue F = G + H
                            (*it)->calculateHValue();
                            openList.push_back(*it);
                        }
                    }

                        // Find node above-left diagonal us
                    if((*it)->x == openList[0]->x-32 && (*it)->y == openList[0]->y-32)
                    {
                        if(!checkClosed(*it) && !checkOpen(*it))
                        {
                            // Add to the GValue
                            (*it)->Gvalue += openList[0]->Gvalue + 4;
                            // Set our Hvalue to the shortest path
                            (*it)->setShortestPath(finish);
                            // Calculate our Fvalue F = G + H
                            (*it)->calculateHValue();
                            openList.push_back(*it);
                        }

                    }
                }

            if(openList.size() > 0)
            {
                openList.erase(openList.begin());
            }

            std::sort(openList.begin(), openList.end(),sortByFValue);


        }
    }
    return result;
}

Sorry for the double post, but I have a new problem with my current code (see above). I think the search that it's doing for each node is more of a "flood fill" search rather than the standard A* shortest path search. Does anyone know what I'm doing wrong?

Hmm, maybe it's just me not seeing it, but what happens when a node is re-encountered in the open-list during your 8-way directional sweep of the nodes?

It is at this time you should recalculate the G-Cost for the node in question to see if it is now a better path. I feel I'm doing a inadequate job of explaining but take a look at this (The third bullet point is what i'm getting at and I can't see it in any of your post's):

c) For each of the 8 squares adjacent to this current square …

  • If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.

  • If it isn’t on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square.

  • If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.

This is of course just a portion of the entire algorithm. It's gone over in a pragmatic approach for the expert, and layman alike masterfully here: http://www.policyalmanac.org/games/aStarTutorial.htm

-Marcus

Here is my check node function (to test if it's on the open list already:


bool PathFinder::checkOpen(Node *node)
{
    for (std::vector<Node*>::iterator it = openList.begin() ; it != openList.end(); ++it)
    {
        if(*it == node)
        {
            if((*it)->Gvalue < openList[0]->Gvalue)
            {
                (*it)->Gvalue += openList[0]->Gvalue;
                (*it)->calculateFValue();
                std::sort(openList.begin(), openList.end(),sortByFValue);
            }
            return true;
        }
    }

    return false;

}

Here is a screenshot to further convey my problem
Yellow Square: Point A
Green Square: Point B
Purple Square: (Invalid terrain) Closed Nodes
Blue Nodes: Closed Nodes (The nodes that have been on the open list)

Screenshot album:
http://imgur.com/a/xhd5V

Mind If I see your calculateFValue Method?

"

if(*it == node)
{
if((*it)->Gvalue < openList[0]->Gvalue)
{
(*it)->Gvalue += openList[0]->Gvalue;
(*it)->calculateFValue();
std::sort(openList.begin(), openList.end(),sortByFValue);
}
return true;
}

"

Would have used source tags, but the editor keeps inserting span tags within the source, but this should be sufficient

You loop through potentially all of the nodes in the open-list and when you find the one IN the open-List that is equivalent to the iterators pointer, you don't pay attention to it. You reference and compare to OpenList[0] (which is the one node in your openList, IF your keeping sorted based on FCost, that should have the lowest F-Cost but is probably not the node whom you have to recalculate). You know your code better then I, maybe I'm missing something?

-Marcus

Sure:


void Node::calculateFValue()
{
    Fvalue = Gvalue + Hvalue;
}

You loop through potentially all of the nodes in the open-list and when you find the one IN the open-List that is equivalent to the iterators pointer, you don't pay attention to it. You reference and compare to OpenList[0] (which is the one node in your openList, IF your keeping sorted based on FCost, that should have the lowest F-Cost but is probably not the node whom you have to recalculate). You know your code better then I, maybe I'm missing something?

-Marcus

You are right, I fixed the checkOpen function to:


bool PathFinder::checkOpen(Node *node)
{
    for (std::vector<Node*>::iterator it = openList.begin() ; it != openList.end(); ++it)
    {
        if(*it == node)
        {
            if((*it)->Gvalue < node->Gvalue)
            {
                (*it)->Gvalue += node->Gvalue;
                (*it)->calculateFValue();
                std::sort(openList.begin(), openList.end(),sortByFValue);
            }
            return true;
        }
    }

    return false;

}

Sadly though, this may have fixed some future issues with tracing back & finding the path, it didn't fix my current problem :(

This topic is closed to new replies.

Advertisement

Popular Topics

Aybe One
How do you manage yourself and your time as years pass on? GDNet Lounge
Jikoob
Too many managers? General and Gameplay Programming
ReignOnU
Do your part to stop global warming and climate change GDNet Lounge
Konjointed
C++ how do you use dependency injection? For Beginners
aigan
The promise of freedom in story games Game Design and Theory
robertrobert
Facebook Ads for sales on steam, does it work? Games Business and Law
Advertisement

Recommended Tutorials

Myopic Rhino
A Tutorial on Pointers and Arrays in C General and Gameplay Programming
GameDev.net
Game operation costs: the unpredictable beast? Networking and Multiplayer
adityarajani
How to Create a Realistic Formula 1 car in 3D Visual Arts
sunandshadow
Developing Your Game Concept By Making A Design Document Game Design and Theory
Myopic Rhino
Multiple Monitor Support Code General and Gameplay Programming

Reticulating splines

About GameDev.net
Community Guidelines
Terms of Service
Privacy Policy
Contact Us
Copyright (c) 1999-2024 GameDev.net, LLC
Back to Top