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.