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


}




}

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.

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.

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?

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!

OK, thanks so much for that, a lot of points to go through and look at, so that's my next step. I'll update once done.

Happy New year!

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

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.