Attempt at A star algorithm not working

Pelayo M · 2013-12-19T12:43:12

Help please, I am attempting to create an A* algorithm to do some pathfinding in C++. The function I use is: pathfinder.aStar(400, 300, 25, 25); Which is a fairly simple diagonal movement. My map is divided in 64x64 nodes. And for some reason, the pathfinding follows the following path of nodes: 5,5 6,3 6,5 7,3 7,4 7,5 38,28 38,29 And crashes as only 39x29 nodes were created and it wants to go onto (39,30) My code is as follows: std::vector<Position*> Pathfinder::aStar(int x1, int y1, int x2, int y2) { start = getNodeFromCoord(x1, y1); endNode = getNodeFromCoord(x2, y2); n = 0; openList.push_back(start); start->opened = true; while (n == 0 || (current != endNode && n < 50)) { //Look for the smallest F value in the openList and make it the current point for (i = openList.begin(); i != openList.end(); ++ i) { if (i == openList.begin() || (*i)->getFScore() <= current->getFScore()) { current = (*i); } } if ( current == endNode ) { break; } //Change from open to closed list openList.remove(current); current->opened = false; closedList.push_back(current); current->closed = true; // Get all current's adjacent walkable points for (int x = -1; x < 2; x ++) { for (int y = -1; y < 2; y ++) { // If it's current point then pass if (x == 0 && y == 0) { continue; } // Get this point child = getPoint(current->getX() + x, current->getY() + y); std::cout << current->getX() + x << " --- " << current->getY() + y << std::endl; std::cout<<child->getX() << " " << child->getY() << std::endl << std::endl; // If it's closed or not walkable then pass if (child->closed || !child->walkable) { continue; } // If we are at a corner if (x != 0 && y != 0) { // if the next horizontal point is not walkable or in the closed list then pass if (!nodeIsWalkable(current->getX(), current->getY() + y) || getPoint(current->getX(), current->getY() + y)->closed) { continue; } // if the next vertical point is not walkable or in the closed list then pass if (!nodeIsWalkable(current->getX() + x, current->getY()) || getPoint(current->getX() + x, current->getY())->closed) { continue; } } // If it's already in the openList if (child->opened) { // If it has a worse g score than the one that pass through the current point // then its path is improved when it's parent is the current point if (child->getGScore() > child->getGScore(current)) { // Change its parent and g score child->setParentNode(current); child->computeScores(endNode); } } else { // Add it to the openList with current point as parent openList.push_back(child); child->opened = true; // Compute it's g, h and f score child->setParentNode(current); child->computeScores(endNode); } } } n++; } //Reset for (i = openList.begin(); i != openList.end(); ++ i) { (*i)->opened = false; } for (i = closedList.begin(); i != closedList.end(); ++ i) { (*i)->closed = false; } while (current->hasParent() && current != start) { path.push_back(current->getPosition()); current = current->getParentNode(); n ++; } return path; } Any ideas? Thank you

For Beginners

Started by mypel16000 December 18, 2013 10:17 PM

11 comments, last by DejaimeNeto 10 years, 4 months ago

zaphod2

1,522

December 19, 2013 11:24 AM

Your getPoint and getNodeFromCoord functions don't always return a value. (Possibly a C heirloom that they can be compiled.) They don't return values if the coordinates you're searching for is not in the list. I assume that out of bounds coordinates are not listed, so their behavior are undefined in this case. And that might cause your problem. Please try if adding proper boundary checking in aStar and error checking in getPoint and getNodeFromCoord solve your problem or not.

mypel16000

Author

December 19, 2013 11:44 AM

I understand, but that's not the problem. It is the pathfinding that isn't working. It is not going the right way. Whilst I appreciate these tips for improving my code, the real problem is that the algorithm doesn't work. I'm thinking there might be a problem calculating the F G and H scores, or a problem in the code which looks at adjacent nodes

DejaimeNeto

4,221

December 19, 2013 12:43 PM

I understand, but that's not the problem. It is the pathfinding that isn't working. It is not going the right way. Whilst I appreciate these tips for improving my code, the real problem is that the algorithm doesn't work. I'm thinking there might be a problem calculating the F G and H scores, or a problem in the code which looks at adjacent nodes

We'll have a hard time trying to help you find the problem on your a-star implementation if we don't know what your code is doing. There could be problems in the list implementation, score calculations, walkable data checking; to name a few...

Build and Gun

Attempt at A star algorithm not working

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Attempt at A star algorithm not working

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines