Jump to content

  • Log In with Google      Sign In   
  • Create Account

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.

  • You cannot reply to this topic
12 replies to this topic

#1 mypel16000   Members   -  Reputation: 46

Like
0Likes
Like

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

 



Sponsor:

#2 FLeBlanc   Crossbones+   -  Reputation: 3117

Like
1Likes
Like

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.



#3 mypel16000   Members   -  Reputation: 46

Like
0Likes
Like

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



#4 FLeBlanc   Crossbones+   -  Reputation: 3117

Like
0Likes
Like

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? 



#5 Postie   Members   -  Reputation: 1116

Like
0Likes
Like

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: ByteWrangler

#6 Godmil   Members   -  Reputation: 744

Like
1Likes
Like

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.


#7 Pink Horror   Members   -  Reputation: 1229

Like
0Likes
Like

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.



#8 dejaime   Crossbones+   -  Reputation: 4119

Like
0Likes
Like

Posted 18 December 2013 - 11:11 PM

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, 18 December 2013 - 11:12 PM.


#9 mypel16000   Members   -  Reputation: 46

Like
0Likes
Like

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.


#10 Godmil   Members   -  Reputation: 744

Like
1Likes
Like

Posted 19 December 2013 - 04:27 AM

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.



#11 zaphod2   Members   -  Reputation: 718

Like
1Likes
Like

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.



#12 mypel16000   Members   -  Reputation: 46

Like
0Likes
Like

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



#13 dejaime   Crossbones+   -  Reputation: 4119

Like
2Likes
Like

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.



PARTNERS