• FEATURED

View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Attempt at A star algorithm not working

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

12 replies to this topic

### #1mypel16000  Members

Posted 18 December 2013 - 04:17 PM

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

### #2FLeBlanc  Members

Posted 18 December 2013 - 04:31 PM

When you generate a new location while checking neighbors, you need to make sure that the new location is within bounds, and if not don't try to use the location for pathing.

### #3mypel16000  Members

Posted 18 December 2013 - 04:53 PM

I am aware of that, and I mentioned I was, but that isn't my problem. The problem is it should be going towards node (0, 0) when instead, it's following a weird pattern and then suddendly jumping to the other side for no immediatly apparent reason. Thanks for your help though

### #4FLeBlanc  Members

Posted 18 December 2013 - 05:13 PM

Are your nodes allocated as an array? If so, and if your X coordinate, for example, exceeds the proper dimensions then it will "wrap around" to the other side. Also, where does the exact crash occur? Have you fired up the debugger and inspected everything? What does getPoint() do?

### #5Postie  Members

Posted 18 December 2013 - 05:48 PM

I'm confused. You said you call the function with parameters that attempt to traverse from (400,300) to (25,25), but the pathfinding starts at (5,5) but there's only (39,29) nodes in your map?

Currently working on an open world survival RPG - For info check out my Development blog:

### #6Godmil  Members

Posted 18 December 2013 - 05:55 PM

I can't help here but I gatta ask, how does it work that you don't give a type (or auto) to your iterators 'i' in the for loops? I didn't know you could do that.

Actually, what type are 'start' and 'endnode' if they're objects could you post their code too? Also what is 'openlist'? Are all these variables created globally outside the function? If so that may not be the best method.

Edited by Godmil, 18 December 2013 - 06:25 PM.

### #7Pink Horror  Members

Posted 18 December 2013 - 10:48 PM

I can't help here but I gatta ask, how does it work that you don't give a type (or auto) to your iterators 'i' in the for loops? I didn't know you could do that.

Actually, what type are 'start' and 'endnode' if they're objects could you post their code too? Also what is 'openlist'? Are all these variables created globally outside the function? If so that may not be the best method.

I bet they're all globals or statics.

### #8dejaime  Members

Posted 18 December 2013 - 11:11 PM

Your path goes from (400, 300) to (25, 25), but you're saying the map is (39, 29) tiles. I think I don't understand what these numbers mean.

I bet they're all globals or statics.

Well, they can be all simple members from the Pathfinder class; if more than one Pathfinder can be instantiated at once...

Edited by dejaime, 18 December 2013 - 11:12 PM.

### #9mypel16000  Members

Posted 19 December 2013 - 04:06 AM

The map is composed of 40x30 tiles each one of a width and height of 64 pixels. This makes a map of 2560x1920 pixels.

They are both, two specific nodes formed by a Node class as follows:

#pragma once
#include "Position.h"
class Node
{
public:
Node(void);
Node(int x, int y, bool w);
Position* getPosition();
Node* getParentNode();
void setParentNode(Node *p);
int getX();
int getY();
int getGScore(Node *p);
int getHScore(Node *p);
int getGScore();
int getHScore();
int getFScore();

void computeScores(Node *end);

bool hasParent();
bool closed, opened;
bool walkable;

private:

Node* parent;
int x, y, f, g, h;

};


And implementation:

#include "Node.h"

Node::Node(void)
{
parent = NULL;
closed = false;
opened = false;

x = y = f = g = f = 0;
}

Node::Node( int x, int y, bool w)
{
Node();

this->walkable = w;
this->x = x;
this->y = y;
}

Position* Node::getPosition()
{
return new Position(sf::Vector2f((float)(x * 64), (float)(y * 64)));
}

Node* Node::getParentNode()
{
return parent;
}

void Node::setParentNode(Node *p)
{
parent = p;
}

int Node::getX()
{
return x;
}

int Node::getY()
{
return y;
}

int Node::getGScore(Node *p)
{
return p->g + ((x == p->x || y == p->y) ? 10:14);
//changed last 10 from 14 to 10
}

int Node::getHScore(Node *p)
{
return ((abs(p->x - x) + abs(p->y - y)) *10 );
}

int Node::getGScore()
{
return g;
}

int Node::getHScore()
{
return h;
}

int Node::getFScore()
{
return f;
}

void Node::computeScores(Node *end)
{
g = getGScore(parent);
h = getHScore(end);
f = g + h;
}

bool Node::hasParent()
{
return parent != NULL;
}


Just  to make it clear, the node's x and y are its coordinates in the node map, starting from 0,0 and going to 40,30. If a point were at (70,70) it would be in the node with coordinates (1,1)  (the second down and to the right) as there is a 0,0 tile a 0,1 and a 1,0.

The functions getPoint() and getPointFromCoord() return the node with a given set of coordinates. getPoint uses the node's coordinate in the tile map of 40x30 where as the latter gets it from a set of coordinates in the actual pixel map (just by dividing by 64). Note that both list is a list containing all the nodes in the map. Here they are:

Node* Pathfinder::getNodeFromCoord(int x, int y)
{
for ( i = list.begin(); i != list.end(); i++ )
{
if((*i)->getX() == (int)(x / 64)
&& (*i)->getY() == (int)(y / 64))
{
return (*i);
}
}
}

Node* Pathfinder::getPoint(int x, int y)
{
for ( i = list.begin(); i != list.end(); i++ )
{
if((*i)->getX() == (int)(x)
&& (*i)->getY() == (int)y)
{
return (*i);
}
}
}


Edited by mypel16000, 19 December 2013 - 04:07 AM.

### #10Godmil  Members

Posted 19 December 2013 - 04:27 AM

Your path goes from (400, 300) to (25, 25), but you're saying the map is (39, 29) tiles. I think I don't understand what these numbers mean.

I bet they're all globals or statics.

Well, they can be all simple members from the Pathfinder class; if more than one Pathfinder can be instantiated at once...

The x/y values are screen coordinates, which are converted into node objects (the nodes are a grid where each is 64*64 units).

Is there any advantage to pre-initialising an iterator in for loops?

I'd recommend scrapping lines like this:

for (i = openList.begin(); i != openList.end(); ++ i)

and just use

for (auto i: openList)

(with the c++11 compiler flag)

then you also don't need to dereference the i in the loop.

### #11zaphod2  Members

Posted 19 December 2013 - 05: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.

### #12mypel16000  Members

Posted 19 December 2013 - 05: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

### #13dejaime  Members

Posted 19 December 2013 - 06:43 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

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...

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.