Sign in to follow this  
mypel16000

Attempt at A star algorithm not working

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Can you please elaborate?
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 this post


Link to post
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 this post


Link to post
Share on other sites

Can you please elaborate?
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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this