• Advertisement
Sign in to follow this  

Problems implementing A* - Need a knowledgeable eye to look at my code

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

So I decided a few days ago that i would write my own implementation of A* since my earlier luck trying to add other peoples code and refactoring it to it'll work with my game failed all the time and only worked as time sinks.

 

I followed this guide here: http://homepages.abdn.ac.uk/f.guerin/pages/teaching/CS1015/practicals/aStarTutorial.htm

 

I am not really sure where the problems occur, but looking trough the open list it seems duplicates gets added even though i have a check that wouldn't enable that behavior. The algorithm just keeps going until i stop it, having thousands of Nodes in the lists from a 15 by 15 map. (The size is currently hardcoded)

 

Pathfinding.h

#include <vector>
#include <algorithm>

struct Position{
	Position(){}
	Position(int x, int y){ this->x = x; this->y = y; }
	int x, y;
};
class Node {
public:
	Node(Position pos) { this->pos = pos; }

	Node* getParent() { return parent; };
	void setParent(Node *parent) { this->parent = parent; }

	Position getPosition(){ return pos; }

	int getFcost(){ return g + h; }
	int getGcost(){ return g; }
	int getHcost(){ return g; }

	void setGcost(int g) { this->g = g; }
	void setHcost(int h) { this->h = h; }

	bool operator < (Node& str){
		return (f < str.getFcost());
	}

private:
	Position pos;

	int f = 0;
	int g = 0;
	int h = 0;

	Node *parent;
};

class Pathfinding {
public:
	Pathfinding(){};

	bool findPath(Position, Position, std::vector<std::vector<int>>);

	std::vector<Node*> getPath(){ return path; }

	//void checkNeighbours(Node*, Node*);

	void addToClosed(Node* current){ closed.push_back(current); }
	void addToOpen(Node* current) { open.push_back(current); }

	void removeFromOpen(Node*) { open.erase(open.begin()); }

	int calculateManhattanHeuristic(Position current, Position target) { return (10 * (std::abs(current.x - target.x) + std::abs(current.y - target.y))); }

	Node* getCurrentPoint();

	bool inClosedList(Node*);
	bool inOpenList(Node*);

private:
	std::vector<Node*> open;
	std::vector<Node*> closed;
	std::vector<Node*> path;
};

Pathfinding.cpp

#include "Pathfinding.h"

bool Pathfinding::inClosedList(Node *current)
{
	bool inClosed = false;
	for (int i = 0; i < closed.size(); i++) if (closed.at(i) == current) inClosed = true;
	return inClosed;
}
bool Pathfinding::inOpenList(Node *current)
{
	bool inOpen = false;
	for (int i = 0; i < open.size(); i++) if (open.at(i) == current) inOpen = true;
	return inOpen;
}
Node* Pathfinding::getCurrentPoint(){
	std::sort(open.begin(), open.end());
	return open.at(0);
}

bool Pathfinding::findPath(Position startPos, Position targetPos, std::vector<std::vector<int>> map){


	// Add starting and target position as Nodes.
	// No check if it's blocked or if they are the same yet.
	Node *start = new Node(startPos);
	Node *target = new Node(targetPos);

	// Add the start Node to the open list.
	addToOpen(start);

	do{
		// Get the Node with the least F-score.
		Node *current = getCurrentPoint();

		// Removes the current node from the open list.
		removeFromOpen(current);
		// Adds the current node to the closed list.
		addToClosed(current);

		// Creates temp neighbour Node, initializes g-cost to 0., creates node to see if it's diagonal movement.
		Node *neighbour;
		int newGcost = 0;
		bool corner;

		// For every position in a 3x3 area, all neighbours plus current position..
		for (int x = -1; x < 2; x++)
			for (int y = -1; y < 2; y++)
			{
				// If it's the current position, skip.
				if (x == 0 && y == 0)
				{
					continue;
				}
				// If the neighbour's position is outside the map, skip.
				if (current->getPosition().x + x < 0 || current->getPosition().x + x > 14 || current->getPosition().y + y < 0 || current->getPosition().y + y > 14)
				{
					continue;
				}
				else{
					// If the neighbour's is not blocked..
					if (map.at(current->getPosition().x + x).at(current->getPosition().y + y) == 0)
					{
						// Check if diagonal.
						if (x != 0 && y != -1 && y != 1) corner = true; else corner = false;
						// Create neighbour at position.
						neighbour = new Node(Position(current->getPosition().x + x, current->getPosition().y + y));

						// If the neighbour is not in the closed list.
						if (!inClosedList(neighbour))
						{
							// Add G-cost dependand on corner, diagonal from current position.
							if (corner)
							{
								newGcost += 14 + current->getGcost();
							}
							else newGcost += 10;

							// Add the G and H-cost. F-cost is calculated in the Node-class, getFcost().
							neighbour->setGcost(newGcost);
							neighbour->setHcost(calculateManhattanHeuristic(current->getPosition(), target->getPosition()));

							// If neighbour is not in the open list.
							if (!inOpenList(neighbour))
							{
								// Set current Node as neighbour's parent.
								neighbour->setParent(current);
								// Add neighbour to the open list.
								addToOpen(neighbour);
							}
							// If neighbour is in the open list.
							else
							{
								// Calculate new G-cost..
								if (corner)
								{
									newGcost += 14 + current->getGcost();
								}
								else newGcost += 10;
								// If the new G-cost is better then old G-cost for neighbour, change parent. Cheaper path found.
								if (current->getGcost() < neighbour->getGcost() + newGcost)
								{
									neighbour->setParent(current);
								}
							}
						}
					} // end neighbour blocked if.

				}
			}
	// Continue to look for a path until Open list is empty, there are no more Nodes to check.
	} while (!open.empty());

	// If target Node is in closed list we have found a path.
	if (inClosedList(target))
	{
		// Reverse the path trough the targets parents until we have gotten to the start position.
		// Set as path, get path with getPath().
		Node* reverse = target;
		while (reverse != start)
		{
//I noticed now that i hadn't completed this part.
			path.push_back(reverse);
		}
		// Return true as we have found a path.
		return true;
	}
	// Return false as we have not been able to find a path.
	else return false;
}

I am at loss at what to try next...

Edited by Pether

Share this post


Link to post
Share on other sites
Advertisement

Here


	void removeFromOpen(Node*) { open.erase(open.begin()); }

You didn't remove the given node, instead you always removes the first one only. Rewrite your code to remove the given node.

Share this post


Link to post
Share on other sites

Here


	void removeFromOpen(Node*) { open.erase(open.begin()); }

You didn't remove the given node, instead you always removes the first one only. Rewrite your code to remove the given node.

 

I have used this before and have tried it again:

void Pathfinding::removeFromOpen(Node *current)
{
	for (int i = 0; i < open.size(); i++)
		if (open.at(i) == current)
		{
			open.erase(open.begin() + i);
			break;
		}
}

But the problem is still there.

The reason i delete the first one, is because the current Node is the Node at the beginning.

Share this post


Link to post
Share on other sites

I just took a  quick look, here are the bad smells I could find:

 

Not using it, but here should be h:

    int getHcost(){ return g; }

I could not understand the logic of yout newGcost update, maybe you should double  check it.

Edited by KnolanCross

Share this post


Link to post
Share on other sites

I just took a  quick look, here are the bad smells I could find:

 

Not using it, but here should be h:

    int getHcost(){ return g; }

I could not understand the logic of yout newGcost update, maybe you should double  check it.

 

Ah, fixed that.

 

The newGcost is checking to see if the cost to get the the neighbour is cheaper if i go from the current node (the + g cost i am doing), then the current path to the neighbour node.

 

It's the 6'th point on the guide:

http://homepages.abdn.ac.uk/f.guerin/pages/teaching/CS1015/practicals/aStarTutorial.htm

 

 

6) If an adjacent square is already on the open list, check to see if this path to that square is a better one. In other words, check to see if the G score for that square is lower if we use the current square to get there. If not, don’t do anything. 
    On the other hand, if the G cost of the new path is lower, change the parent of the adjacent square to the selected square (in the diagram above, change the direction of the pointer to point at the selected square). Finally, recalculate both the F and G scores of that square. If this seems confusing, you will see it illustrated below.

Share this post


Link to post
Share on other sites

My point is, why on diagonals you add the current->getGcost(); and not on straight lines. Also, you never reset this value/set it to a initial during your whole neighborhood loop.

 

At least in my implementation I always SET it nodeG + the distance between the two nodes. I don't add it to a buffer, hence I use "=", not "+=".

In you implementation it seems to me it should be:

if (corner){
    newGcost = current->getGcost() + 14;
}
else {
    newGcost = current->getGcost() + 10;
}

Again, I may be wrong here, but the way it is in your code really didn't made sense to me.

Edited by KnolanCross

Share this post


Link to post
Share on other sites

My point is, why on diagonals you add the current->getGcost(); and not on straight lines. Also, you never reset this value/set it to a initial during your whole neighborhood loop.

 

At least in my implementation I always SET it nodeG + the distance between the two nodes. I don't add it to a buffer, hence I use "=", not "+=".

In you implementation it seems to me it should be:

if (corner){
    newGcost = current->getGcost() + 14;
}
else {
    newGcost = current->getGcost() + 10;
}

Again, I may be wrong here, but the way it is in your code really didn't made sense to me.

 Ah. Ok. Yeah, i noticed what you meant there and have fixed it.

 

*edit*

 

I found the problem i was having.

I was going checks:

closed.at(i) == current

This will be true if all the variables were the same, but since they would have different costs it wouldn't return true.

I instead checked to see if the pos.x and pos.y were the same. Bam. Now to fix some other stuff to see if it works as it should.

Edited by Pether

Share this post


Link to post
Share on other sites

I have gotten it to 'work'.

This is the path it gives me:

https://www.dropbox.com/s/vfwx5ee1vqzauhv/failpath.png?dl=0

 

As you can see it gets to the target, but it does so by doing some strange things.

Is the heuristic wrong? Because it goes away from the target?

 

Blue : Start.

Red : Target.

Black : Blocked.

 

Also, it seems to be checking all nodes on the map..

Edited by Pether

Share this post


Link to post
Share on other sites

If the cost of moving diagonally is the same as the cost of moving horizontally or vertically, that path seems optimal to me.

 

Diagonal is 14 cost and horizontal/vertical is 10, so same cost.

But i tried changing diagonal to 24, and even 50. It still gives the same path, even gives a path that almost only has diagonal path's.

I also tried changing all horizontal/vertical costs to 200, but still gives same path's..

It seems it gives 3-4 different paths no matter the cost?

 

And even so, if it moves away from the target, going up, the h will get higher, and thus it won't be picked as the next?

Share this post


Link to post
Share on other sites
Did you manage to fix your code? If you can post a complete program that I can compile and run myself, I'll give you a hand. But you should learn how to debug your programs.

Share this post


Link to post
Share on other sites

Heya,

 

no, I haven't got it to work. But I haven't had any time to look at it since last time as I've had three assignments due today and another one this weekend. In a world with unlimited time I would have created a better environment to test the pathfinding, showing all the values and behind able to create obstacles and new paths while it's running, but haven't had time to do that. But I have thought of doing a desk test since the fault most likely lies somewhere in the code that calculates the costs of moving, so I should be able to see where if I just write it down.

 

 

I cut the code down to the bare minimum to run and show the pathfinding.

https://www.dropbox.com/s/to7ljzjiuzlxlbd/Gamestuff.rar?dl=0

 

*edit*

 

I actually got it to work correctly, turns out the sortfunction for the vector didn't work as planned so I replaced it.

Edited by Pether

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement