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

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.

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

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?

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

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);
		}
	}
}

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.