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

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.

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.

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.

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.

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.

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.

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

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?