Pathfinding is a fundamental tool commonly used to move characters around a map intelligently. Here I will be going over the A* algorithm written in C++.
It’s important to visualize how the pathfinding algorithms search for the most efficient path. Here is a neat demo using a JavaScript library called Pathfinding.js. By playing with Pathfinder.js, you should notice that the algorithm first tries to go straight for the end point and only when it hits a blocked node will it look for nodes that follow a less direct path.
The Algorithm
In a nutshell, the A* algorithm uses a graph of nodes that have a weight associated to them used to weigh paths from the start node to the end node.
What weight represents is arbitrary, since A* can be applied to different scenarios. For navigating through a map of squares for example, this value could be based on distance and steps taken. The algorithm processes neighboring nodes, adding all neighbors to an “open list” and then moving on to the lowest cost node in that list.
Given the open list begins with the start node (opposed to be empty), the main loop of the algorithm looks like this:
- Get next node from open list (now known as current node)
- Skip node if in closed list or out of bounds
- Add current node to closed list
- Remove current node from open list
- Process neighboring nodes (North, West, South, East)
- Set current node as parent of neighbor if weight is less
In all, the algorithm uses three lists:
- Open List: Keeps track of which nodes to search next and is ordered by weight
- Closed List: Al nodes that have already been searched
- Path: Linked list that connects the end node to the start node
To clarify on the path, there are actually multiple paths that exist because less efficient paths may be found before the most efficient path. The end node will have the final path, and that is all we care about.
Implementation
Next we’ll go over the structures and functions involved with this algorithm. One core structure is the node.
Node Structure
As mentioned before, this is implemented in C++ and the graph is comprised of nodes.
Here is the Node structure with only its members:
struct Node {
int x;
int y;
int index = 0;
int distance;
bool blocked = 0;
int weight = 0;
Node *parent = NULL;
};I use indices to keep track of nodes. This includes determining which node is the start and end, as well as which nodes have already been processed (closed list) and which nodes should be processed next (open list).
Note: The index struct member is there for convenience, so a coordinate to index lookup doesn’t need to be run every time.
The path list mentioned before is a linked list created through the parent struct member, which points to another node.
Grid and List Structures
Nodes are stored as pointers in a vector. The open list is implemented as a multiset with the comparison function, NodeComp, so sorting is automatically done. Lastly, the closed list is implemented as a vector of ints that stores the indexes.
typedef std::multiset<Node*, NodeComp> NodeList; // So we don't need to type out the full definition everywhere NodeList open_list; // Node pointers to process std::vector<int> closed_list; // Node indices already processed std::vector<Node*> grid; // All nodes
