Public Group

# Attempt at A star algorithm not working

This topic is 1768 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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

##### Share on other sites

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.

##### Share on other sites

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

##### Share on other sites

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?

##### Share on other sites

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?

##### Share on other sites

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

##### Share on other sites

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.

##### Share on other sites
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

##### Share on other sites

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

##### Share on other sites

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.

1. 1
Rutin
44
2. 2
3. 3
4. 4
5. 5

• 11
• 9
• 12
• 10
• 13
• ### Forum Statistics

• Total Topics
632983
• Total Posts
3009714
• ### Who's Online (See full list)

There are no registered users currently online

×