Sign in to follow this  

[Pathfinding] Beginning looking at and implementing A Star [C++]

Recommended Posts

Sorry if this in the wrong area

 

So, I'm trying to put together a program that runs through a text file of a grid, then create/output a path from a start coordinate to and end coordinate, now I've managed to import the text file needed and can output into another just fine.

 

I do understand the A-Star Algorithm, its just putting it into coherent code that is my issue, so far I have:

 



struct Point
{
int x;
int y;
int heuristic;
char value;


bool wall = false;
bool water = false;
bool grass = false;
bool startNode = false;
bool endNode = false;


int nodeCost;
int costOf;// Node + parent cost


int valueF;// Total Score nodeCost + heuristic


Point* parent;
};



class Map
{
public:
static const int ARRAY_SIZE = 10;


void LoadFile();
void Display() const;
void aStar();


private:
Point   mArray[ARRAY_SIZE];
};




void Map::LoadFile()
{
ifstream infile("Map.txt");
if (!infile)
{
cout << "Cannot open File";
exit(1);
}
for (int i = 0; i < ARRAY_SIZE; i++)
{
infile >> mArray[i].x >> mArray[i].y;
}
}


void Map::aStar()
{
LoadFile();


void push_back(const int& _val);


deque <Point*> openList;
Point* startNode = new (Point);
deque <Point*> closedList;
Point* endNode = new (Point);






startNode->x = mArray[0].x;
startNode->y = mArray[0].y;


openList.push_back(startNode);
startNode->parent = 0;


while (!openList.empty())
{
Point* currentNode;


startNode = currentNode;


openList.push_back(move(currentNode));


if (currentNode == endNode)
{
ofstream output("output_1.txt");
if (!output)
{
cout << "Cannot open file";
exit(1);
}
output << "Coordinates are:" << endl;
output << mArray[10].x << mArray[10].y;
output.close();
}


}




}

 

My issue right now is what to do next, I need to set up a heuristic (Manhatten distance) but unsure of what to do/how to explain what I need to do next.

 

Any help?

Edited by SCB

Share this post


Link to post
Share on other sites

It's hard to answer your question directly, but when I tried to implement it myself a few years ago, I ran into the problem of not knowing what data structure to use. I recall something about how using a list or a set or a vector wasn't appropriate, but I got something to work with one or the other.

 

You may want to take a look at how MicroPather does it: http://www.grinninglizard.com/MicroPather/index.htm

 

Also, Amit's website is a great resource: http://www.redblobgames.com/pathfinding/a-star/introduction.html and especially http://www.redblobgames.com/pathfinding/a-star/implementation.html which has three language-specific details.

 

While you said you know A* and just need to figure out the implementation details, it helps to look at other implementations, even if they are in a different language, as you get a sense of what's involved at the code level.

 

You basically need to start iterating through your nodes. You've got your start node and the concept of a current node, although since currentNode isn't initialized I'm not sure what "startNode = currentNode" is accomplishing. Maybe you meant to reverse the assignment?

 

Basically, you take your start node and add it to the open list (looking at your code, I bet you did mean to say "currentNode = startNode").

 

Then, go through your open list's nodes by popping them out (so they are no longer in the open list).

 

If your current node is at the goal node, great! You should have setup someway to say where this node came from, and you should be able to reverse your way to the nodes in your path.

 

Otherwise, get the neighbors of your current node and add them to the open list. How you add them is where the Manhattan distance comes into play, and this is why I said that the data structure used is important. In Amit's code, he uses a custom class called PriorityQueue, and he uses the cost so far and the Manhattan distance heuristic to determine which of the neighbor nodes will get processed first. Essentially, your code should try to pick the most likely candidate to be closest to the goal each time through. You'll be adding nodes to the open list as you check each node, but your calculation should allow you to say that one node is the best candidate in the open list.

 

In the end, Amit recommends using a third-party library if you just want to get pathfinding in your game. I would use Micropather.

 

But if you're trying to implement it for the challenge or the learning, it might be a good idea to try to implement his version, then modify it or rewrite it once you see how it all works together.

 

I got the book Artificial Intelligence for Games, and I tried to follow the pseudocode provided, but ran into issues with what the open and closed lists should be implemented with. My pathfinding didn't look great, but at least my entities got from point A to point B. B-)

Share this post


Link to post
Share on other sites

Ah thanks for the reply, reading through it's been a great help, yea I got 'StartNode = CurrentNode' the wrong way round(I am trying to say, in code, that I want the starting element of my array to equal the current node to be looked at, to then add that to the openlist)

 

I have been reading through the stuff from redblobgames already and have it open on another screen, it's been really helpful so far but actually implementing it in my own code is where I've been struggling.

 

I do know a bit of java, so looking at that code and then translating, for lack of a better term, to C++ has been working for some things. The priority Queue has been a nightmare to sort out, but I get what its supposed to be doing so with some focus should be able to implement it with practice.

Share this post


Link to post
Share on other sites

Before considering heuristics, I would like to suggest that you improve your data structures. It saves a lot of memory, and (more importantly) it helps in understand what data belongs where.

 

Data structures that you have (names are suggestions, feel free to deviate):

- You have (x,y) positions everywhere. It makes life easier if you make a Position class for that.

- You need map data. A single grid element is normally called "Tile", it contains data what the grid element shows, likely your "wall/water/grass" booleans. A position is optional.

- The "Map" class is useful. It contains all grid elements, and you can ask for a tile by position (ie it needs a "const Tile &GetTile(const Position &xy)" method.)

- Your current LoadFile routine is broken. It doesn't set all the fields in Point (note that I propose to rename that to something else), and it doesn't close the file after loading.

 

The AStar algorithm is a new layer on top of the Map.

- It's better to make a new separate AStar class that does the actual computation.

- As to where you put that class, adding the AStar routine to the map class is one option, as you have now. Another option is to instantiate an AStar object near the code that needs the path.

- Typically, the call to compute a path takes a start and end position. You seem to have "beginNode" and "endNode" flags, but they are never set, so I don't know where you get them from. If they are in the map data that you load, add a getBeginPosition() and getEndPosition() method to the Map class to query the positions.

- During the computation, you need to keep track of positions, and their costs. This is often called Node. It should contain Position, and the cost of the traveled path so far. Many explanations also add the heuristic and total cost, but these costs are quite cheap to recompute, so to me it's optional whether or not you add those costs. A link to the parent node is also useful.

- As you already found, there are 2 lists, an open list and a closed list.

  The closed list is the simplest. It's the collection of Positions that have known costs to reach from the starting point. The collection only grows, and you need to quickly find a cost from a position in it. A "deque" is therefore not the right data structure, a "map" works better, eg "std::map<Position, Node>".

  The open list is the set of positions that are "in progress". A "deque" works there, eg "std::deque<Node>". EDIT: Sorry, total bollocks here, it needs a std::multimap! It needs ordering on increasing total cost (ie getting a node from the deque should always give you the node with the smallest total cost).

- The result of the a-star call is another thing you may want to consider. Internally, the AStar algorithm returns a sequence of Nodes. External users can't do much with all the cost information, so instead returning a std::vector<Position> seems a good idea.

 

Last but not least, please add proper indetning to your code, it's very hard to read now.

To paste code in the forum editor: 1) copy the code to the clipboard. 2) Press the "<>" symbol in the forum editor, a popup window appears. 3) Paste the code in the window. 4)Select language. 5) Press ok/done.

 

That covers your code mostly, as far as I can see. On to the question.

 

 

My issue right now is what to do next, I need to set up a heuristic (Manhatten distance) but unsure of what to do/how to explain what I need to do next.

The heuristic is an estimate of costs you will need to make in order to reach the destination from an intermediate point between the starting point and the destination.

 

 

Ideally, it's equal to the real costs (ie the shortest path from the intermediate point to the destination), but that's hard, as we are still doing that calculation. So instead, the normal approach is to settle for something that is easier to compute. Typically you assume there are no obstacles, and with that assumption, you compute the path length. That is often not much more than computing the number of horizontal steps, number of vertical steps, and number of diagonal steps (if you have hem), multiplying each with the cost of such a step, and adding everything.

 

Manhattan distance is not doing any diagonal movement, and boils down to "return abs(current.x - endpos.x) * COST_PER_X_STEP + abs(current.y - endpos.y) * COST_PER_Y_STEP;"

 

The import point in the heuristic is, if you want the optimal path, it should never give a cost estimate that is bigger than the real cost.

Edited by Alberth

Share this post


Link to post
Share on other sites

Thanks Alberth, I've been readjusting things to make it look better and more readable structurally.

 

The map data I'm using is from a txt file of costs (to make up a map) like so:

1100011111
1001000011
1032111011
1030301011
1030301011
1030301011
1012111011
1010000011
1000111111
1111111111

this is saved in a 10x10 array (saved as mArray in my code) with another text file supplying the start and end nodes (3, 4 and 7, 8 in this case) but needs to be able to work with any txt file not just these.

 

 

this is called/saved here:

class Map
{
public:
	static const int ARRAY_SIZE = 10;

	void LoadFile();
	void Display() const;
	void aStar();

private:
	node   mArray[ARRAY_SIZE];
};


void Map::LoadFile()
{
	ifstream infile("Map.txt");
	if (!infile)
	{
		cout << "Cannot open File";
		exit(1);
	}
	for (int i = 0; i < ARRAY_SIZE; i++)
	{
		infile >> mArray[i].xPos >> mArray[i].yPos;
	}
} 

now as for the A Star part, so far I've got the following:

void dMap::aStar()
{
	LoadFile();

	void push_back(const int& _val);

	deque <node*> openList;
	node* startNode = new (node);
	deque <node*> closedList;
	node* endNode = new (node);

	

	startNode->xPos = mArray[0].xPos;
	startNode->yPos = mArray[0].yPos;

	openList.push_back(startNode);
	startNode->parent = 0;

	while (!openList.empty())
	{
		node* currentNode;

		currentNode = startNode;

		openList.push_back(move(currentNode));

		if (currentNode == endNode)
		{
			ofstream output("output_1.txt");
			if (!output)
			{
				cout << "Cannot open file";
				exit(1);
			}
			output << "Coordinates are:" << endl;
			output << mArray[10].xPos << mArray[10].yPos;
			output.close();
		}

		else if (currentNode == startNode)
		{
			openList.pop_back();

// This is where I'm up to, popping the startNode onto the openlist, then finding the next node with the lowwest cost
		}

	}
	

} 

I've not called the costs, or the heuristic yet as I'm not quite sure where/how to do that just yet, I get how they do it, but putting into C++ is where I'm finding it tricky.

 

 

Finally, I've done what you suggested when it comes to using the code brackets on the forum, did it come out alright this time?

 

Share this post


Link to post
Share on other sites

this is saved in a 10x10 array (saved as mArray in my code)
 

class Map
{
public:
    static const int ARRAY_SIZE = 10;

    void LoadFile();
    void Display() const;
    void aStar();

private:
    node mArray[ARRAY_SIZE];
};

Last time I checked, 10x10 equaled 100, so why is ARRAY_SIZE 10 ?
 

The map data I'm using is from a txt file of costs (to make up a map) like so:
 

    for (int i = 0; i < ARRAY_SIZE; i++)
    {
        infile >> mArray[i].xPos >> mArray[i].yPos;
    }

If the numbers are costs, why are you reading them into xPos and yPos ?

 

It is probably useful to write a "dumpCostMap" method in the Map class, that prints the map as it is stored in the mArray. If you call that method, and the output matches with your original data file, you can be reasonably sure that your data is where you think it is.

 

Also, please add a "infile.close();" call after reading the file. Be nice with your resources, clean them up after use.

deque <node*> openList;

I am sorry. Now that I check your code again, I noticed that "deque" is not what you want at all here.

You should use a std::multimap instead. The map can sort its elements on total cost. A deque cannot sort at all. I'll fix my previous post too.

 

You need to make the openList work first. The main loop (below) depends on it.

    while (!openList.empty())
    {
        node* currentNode;

        currentNode = startNode;

        openList.push_back(move(currentNode));

        if (currentNode == endNode) {
            ....
        } else {
            ....
        }

The "currentNode = startNode" line is wrong. In the "while" condition, you checked there is a node in the openlist. The first thing you do in the loop is to pull the node with the smallest total cost from the openList. That is the node you should work on, rather than "startNode". (Just above the loop you add the startNode in the openList, to make it the first thing it works on.)

 

I assume "openList.push_back(move(currentNode))" is supposed to add the neighbours to the openList? If so, why do you add only one new node? A position in the map can have up to 4 neighbours.

Also, this is way too soon for adding neighbours. You first update the closed list, and check for the node being the end-node (ie you reached the destination!).

 

When you are not at the destination, it makes sense to add neighbours.

 

You also need to check that you are not adding nodes that are already explored.

 

 

 

Overall:

1: Work on map loading

2: Work on getting the node with the smallest total cost from the openList

3: Reread the details of AStar. Where does it get the next node to explore, how does it start, what order is used for checking end nodes and already added neighbours, where does it exactly check for the destination.

Finally, I've done what you suggested when it comes to using the code brackets on the forum, did it come out alright this time?

Yes, much better, thanks!

 

 

 

 

Share this post


Link to post
Share on other sites

Alright, I've decided I am gonna start a fresh project with a basic grid to get my head around this and then adjust it into my current project

Share this post


Link to post
Share on other sites
So after starting again, I've gotten my head around it some more:
 
I've been able to read in the text files and put them into 2 separate arrays fine, the real issue I'm having is with adding to the openlist and compares their costs so that the smallest goes onto the Priority Queue and then compare its neighbors, I just cannot work this out after hours upon hours of reading and watching youtube videos on the subject
 
Here is my code so far:
 
 
#include "stdafx.h"
#include <iostream>
#include <string>
#include <fstream>
#include <deque>
#include <math.h>
#include <vector>
#include <deque>
using namespace std;
 
struct pNode
{
int xPos;
int yPos;
pNode* Parent;
pNode* child;
 
 
 
float g; //Cost of this Node plus predecessors
float h;//Heuristic estimate to Goal state
float f; // f= g+h
 
 
 
pNode() :
Parent(0),
child(0),
g(0.0f),
h(0.0f),
f(0.0f)
{
bool wall = false;
bool water = false;
bool grass = false;
bool startNode = false;
bool endNode = false;
}
};
 
class compare
{
public:
 
bool compareNodes()
{
pNode *x;
pNode *y;
return x->f > y->f;
}
};
 
class dMap
{
public:
static const int ARRAY_SIZE = 100;
 
void LoadFile();
void Display() const;
void priorityQueue();
void aStar();
 
private:
pNode   mArray[ARRAY_SIZE];
pNode   mArrayCoords[ARRAY_SIZE];
};
 
 
void dMap::LoadFile()
{
ifstream infile("dMap.txt");
if (!infile)
{
cout << "Cannot open File";
exit(1);
}
for (int i = 0; i < ARRAY_SIZE; i++)
{
infile >> mArray[i].xPos >> mArray[i].yPos;
}
}
 
void dMap::priorityQueue()
{
int disX = mArray[ARRAY_SIZE].xPos;
int disY = mArray[ARRAY_SIZE].yPos;
int heuristic(int xPos, int yPos);
 
struct pQueue
{
 
int fx;
int fy;
int x;
int y;
 
int cost;
int h;
int totalCost;
 
 
pQueue(int _x, int _y, int _cost)
{
x = _x;
y = _y;
cost = _cost;
h = heuristic(x, y);
 
totalCost = cost + h;
}
 
int manhattenDistance(int xPos, int yPos)
{
return abs(xPos - fx) + abs(yPos - fy);
}//Manhatten Distance
 
bool operator<(const pQueue &b)const
{
return totalCost>b.totalCost;
}
 
};
}
 
 
 
 
void dMap::aStar()
{
LoadFile();
 
pNode mArrayCoords[ARRAY_SIZE];
ifstream infile("dCoords.txt");
if (!infile)
{
cout << "Cannot open File";
exit(1);
}
for (int i = 0; i <9; i++)
{
infile >> mArrayCoords[i].xPos >> mArrayCoords[i].yPos;
}
 
deque <pNode*> openList;
pNode* startNode = new (pNode);
deque <pNode*> closedList;
pNode* endNode = new (pNode);
pNode* currentNode = new (pNode);
deque <pNode*> finalList;
 
//startNode ->
 
 
 
 
}
 

 

Share this post


Link to post
Share on other sites

pNode's constructor sets 5 local variables to false, then destroys them. If you're not using that code (yet), take it out.

 

compareNodes() can never work because it's comparing uninitialised values dereferenced from uninitialised pointers.

 

dMap::priorityQueue() accesses mArray[ARRAY_SIZE].xPos, which is an invalid position. (There is no item 100 in a 100-sized array - they go from 0..99.)

 

struct pQueue seems to be a near-duplicate of struct pNode, which is bad because (a) if it's the same thing, you only need one of them, and (b) that's not what a priority queue looks like.

 

pNode* currentNode = new (pNode) is wrong because you wouldn't create an entirely new node for that - the idea is that you pull them off the open list, one by one.

 

 

I think you need to clean up what you have, remove anything irrelevant, fix bugs, and keep it simple. A* is fundamentally about examining a node, generating successor nodes, adding them to the open list, and repeating the process until you find a node that satisfies the goal. The closed list is just there to keep track of nodes you've already examined. The open list is all the nodes you need to examine, sorted to have the most promising one first (based on the 'f' score). Each node has nodes connected to it, which are the ones you add to the open list when you're processing the current node. Get something resembling that basic loop in place.

Share this post


Link to post
Share on other sites

deque<pNode*> openList;

I'm having is with adding to the openlist and compares their costs so that the smallest goes onto the Priority Queue and then compare its neighbors

 

A "deque" is a list, it's purpose is to make it fast to add or remove elements at the head and the tail quickly. For example you can make a temporary buffer with it, add new elements at one side, and the elements come out at the other side, in the same order as you added them.

 

In particular, it doesn't do sorting, your compare function isn't actually used. http://en.cppreference.com/w/cpp/container/deque

 

 

A second problem is that you store pointers to nodes in the list, while your comparator is about comparing nodes. Even if "deque" would do sorting, it would still not use your compare routine, as comparing pointers and comparing node objects are two different things.

 

To solve both, use std::multiset<pNode> instead for your open list. At least I think that should work for total costs. It will however fail for finding duplicate nodes (as in, at the same position). I am not sure how standard A-star solves that, but you can either keep a set around, that you sort on position (std::set, with a custom comparator), or rely on the closed list by checking that when you pull a node from the open list.

Share this post


Link to post
Share on other sites

 

deque<pNode*> openList;

 

 

I'm having is with adding to the openlist and compares their costs so that the smallest goes onto the Priority Queue and then compare its neighbors

 

A "deque" is a list, it's purpose is to make it fast to add or remove elements at the head and the tail quickly. For example you can make a temporary buffer with it, add new elements at one side, and the elements come out at the other side, in the same order as you added them.

 

In particular, it doesn't do sorting, your compare function isn't actually used. http://en.cppreference.com/w/cpp/container/deque

 

 

A second problem is that you store pointers to nodes in the list, while your comparator is about comparing nodes. Even if "deque" would do sorting, it would still not use your compare routine, as comparing pointers and comparing node objects are two different things.

 

To solve both, use std::multiset<pNode> instead for your open list. At least I think that should work for total costs. It will however fail for finding duplicate nodes (as in, at the same position). I am not sure how standard A-star solves that, but you can either keep a set around, that you sort on position (std::set, with a custom comparator), or rely on the closed list by checking that when you pull a node from the open list.

 

 

 

Yea, I actually used:

list<pNode*>openList;

and

#include  <list>;

this was a step I missed when I went through it again. Completely realise what you meant with Deque though 

Edited by SCB

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