Assignment 2-Write Up
Path Finding along with movement forms the most basic level of AI techniques and is a fundamental requirement in almost any games. Pathfinding helps in moving the character from one place to another place intelligently in the most efficient path possible. A pathfinding algorithm generates the path from the current position to the final position based on some conditions which we will discuss below. The path generated from the pathfinding algorithms is then resolved using a Path follow algorithm which translates the path to movement and finally this movement is delegated to either arrive or seek to reach the destination.
Before we go into details of the pathfinding algorithms, let us look at the data structures we are using. The main data we use is Node; a node is the representation of a node on the world graph. We also have edges which connect different nodes, and a node can have multiple edges out of it with each edge having a weight that is used to calculate which node is the best path. The next data structure is a Node Record. A node record stores how much was the cost to arrive at a particular node and what is the estimated total amount of cost from that node to the end node. This total estimated cost is calculated as the sum of cost to the node and a value called heuristic. The final data structure is the Path which is a collection of directed weighted edges, and it is what is returned by the pathfinding algorithm.
Different algorithms have different values for the heuristic and different criteria for calculating the heuristic. There can be three broad values for heuristic which are; it can always be underestimated than the actual total cost which is what is used in A*. The second is when heuristic is 0, in which case it is Dijkstra’s algorithm. The final case is when heuristics always overestimate the cost which results in Greedy algorithms. Because of this, Dijstra’s is a special case of A*.
Now let us discuss both Dijkstra’s algorithm and A* in brief.
Dijkstra’s algorithm: Dijkstra works by spreading out from the start node along its connections. As it spreads out to more distant nodes, it keeps a record of the direction it came from, and once it reaches the end node, it will then generate the path by traversing the edges backward to the source node. Dijkstra’s algorithm only considers the cost so far to the current node and does not consider the future cost and since we terminate the algorithm as soon as we find the end node, the path given by Dijkstra might not always be the smallest. The main problem with Dijkstra is that it searches the entire graph for the shortest possible route. This is useful if we’re trying to find the shortest path to every possible node, but not for point-to-point pathfinding.
Dijkstra also has a O(n2) execution complexity and O(n2) memory complexity for the worst case scenario, since it has to go through all the nodes and all the connections of each node. Below is a video showing Dijkstra’s pathfinding. The boid is moving from node 0 to node 6. The nodes are modeled after real-life map as shown below.
A* is designed to be a better version of Dijstra with fewer comparisons as it takes into account not only the current cost to a node but also estimated cost from the node to the end node.
A*: The basic algorithm for A* is very similar to Dijkstra, but instead of always considering the open node with the lowest cost to that node, we choose the node that is most likely to lead to the shortest overall path. The node that is selected is chosen by a heuristic. If the heuristic is accurate, then the algorithm will be efficient. If the heuristic is terrible, then it can perform even worse than Dijkstra. For each node, we calculate the estimated total cost from the node to the end node which is the sum of cost until that node and the heuristic. The heuristic is generally calculated as the value of the distance between the two nodes. There are many types of heuristics used for A*.
Some of the common heuristics for A* and that I have implemented in my code are [1]
1. Manhattan distance: Manhattan distance is the standard heuristic for square nodes which is what I am using. It is defined as the sum of difference is x and y between the two nodes.
dx = abs(node.x - goal.x)</span> dy = abs(node.y - goal.y)</span></span> return (dx + dy)</span></span>
2. Euclidean distance: Manhattan distance does not work well if we want to calculate the path diagonally. To create the path in any direction we use Euclidean distance. It is defined as
dx = abs(node.x - goal.x)</span></span> dy = abs(node.y - goal.y)</span></span> return sqrt(dx * dx + dy * dy)</span></span>
3. Diagonal distance: This is particularly useful for diagonal movement but not for straight line movement.
dx = abs(node.x - goal.x)</span>   dy = abs(node.y - goal.y)</span></span>   return (dx + dy) + min(dx, dy)</span></span>
4. Zero: This returns a zero, which essentially converts A* into dijkstra.
Below is a video showing the A* movement.
The video above and the video for Dijkstra are both generated for the same graph, with the same nodes and with their edges having the same weights, but we can see the difference in how the path is calculated for Dijkstra compared to A*. A* is guaranteed to give the shortest path for any given tree as long as the heuristic is admissible.
The performance for A* can be given as O(lm) for both memory usage and execution time, where l is the number of nodes whose estimated cost is less than that of goal and m is the number of outgoing connections for each node. Since A* takes into consideration the future cost and updates the current node with the new connection when it finds a better one, A* is considerably faster compared to Djikstra for the same number of nodes and graph even though the big O notation looks similar for both.
Implementation Details:
1. AStar: The algorithm has two priority queues called the openlist and closelist. I have implemented these lists as vectors. The reason why we use priority queues is that we want to sort the nodes that are inserted into these queues according to the estimated total cost. The open list contains all the nodes that are currently being considered and nodes which will be considered next. Closelist contains all the nodes that have already been visited. The algorithm starts with inserting the start node into the open list. Once inserted we get the connections of that node. We then iterate over these connections and end node for each connection and the cost to reach that node.
We then check if the node is in the close list and if it is and has less cost to reach, we remove it from the close list and insert into open list. We then check if the node already is in open list. If it is, then checks if the cost to reach it less than the existing cost, then we will update the connection to that node. Else we will insert into the open list and move the current node to close list. Since I am using a vector instead of custom queues, I use a sort function to sort all the data using std::sort.
bool SortHelperFunction(NodeRecord* n1, NodeRecord* n2) { return n1->m_EstimatedTotalCost < n2->m_EstimatedTotalCost; }
std::sort(openList.begin(), openList.end(), SortHelperFunction);
I sort both open and close list to have the nodes with the least cost at the beginning to access them easily.
Once we find the end node, then I get each node from the end and reverse the vector. The resulting output is a Path structure which contains a vector of DirectedWeightedEdges.
2. Calculating Heuristics: I have an enum which specifies all the heuristics supported in my implementation. All the heuristics are implemented as static functions that take in two nodes and return a float representing the heuristic. In the Astar class, I have a GetHeuristic function which serves as a wrapper for calling all the different Heuristic functions.
float AStar::GetHeuristic(Node* i_StartNode, Node* i_EndNode)
{
switch (m_Heuristic)
{
case Heuristic::Euclidean:
return Heuristics::Euclidean(i_StartNode, i_EndNode);
case Heuristic::Manhattan:
case Heuristic::Default:
return Heuristics::Manhattan(i_StartNode, i_EndNode);
case Heuristic::Diagonal:
return Heuristics::Diagonal(i_StartNode, i_EndNode);
case Heuristic::Zero:
return 0;
}
return 0;
}
enum class Heuristic
{
Manhattan,
Euclidean,
Diagonal,
Default,
Zero
};
struct Heuristics
{
static float Manhattan(Node* i_StartNode, Node* i_EndNode) { return abs(i_StartNode-&amp;gt;m_Position.x - i_EndNode-&amp;gt;m_Position.x) + abs(i_StartNode-&amp;gt;m_Position.y - i_EndNode-&amp;gt;m_Position.y); }
static float Euclidean(Node* i_StartNode, Node* i_EndNode) { return i_StartNode-&amp;gt;m_Position.distance(i_EndNode-&amp;gt;m_Position); }
static float Diagonal(Node* i_StartNode, Node* i_EndNode)
{
float dx = abs(i_StartNode-&amp;gt;m_Position.x - i_EndNode-&amp;gt;m_Position.x);
float dy = abs(i_StartNode-&amp;gt;m_Position.y - i_EndNode-&amp;gt;m_Position.y);
return (dx + dy) + std::min(dx, dy);
}
};
3. Calculating the movement from the path returned from A*: The A* algorithm returns a Path struct as described above. The resulting path is then inputted to a new movement algorithm called the DynamicPathFollow.
a. DynamicPathFollow: DynamicPathFollow is a delegated behavior. It delegates the actual job of getting the dynamic output to DynamicArrive and DynamicLookWhereYouGo. The way that I implemented this algorithm is by taking each point in the path and using dynamicarrive to move the boid to that position. I continuously check if the characters position is inside the slow radius and once it moves inside the slow radius, I change the target for dynamic arrive at the next point. This happens until the final point is reached.
4. Creating a grid instead of graphs: As discussed above I created a graph based on a real-world location. Since this graph only had 11 nodes, it was pretty easy to create by hand. But if we want to create bigger graphs, then it would be impossible to do it by hand. So I implemented a grid class that reads in an image and translates it into a grid using a technique called tiling. In this method, we divide the entire space into tiles with the center of each tile acting as the node. When creating a path for such grids, instead of checking the connections we get the neighbors and have a constant value as the cost between these nodes. Once we need to insert the node records into the open list, we create a new directed weighted edge for the current node and end node and when creating the path, use this edge to find the source and sink.
The following is the image that I am using for my grid generation. The code accepts any image and converts it into a grid. Also, to work with grids, I added a Boolean to check if a particular node can be reached by the boid. This is for collision avoidance.
There are two main ways of doing collision avoidance. One is to do collision detection actively for every frame for the boid with all the objects in the scene. For a graph as big as mine, this uses considerable resources. The second way is to create a path which has collision information built in as part of the node information. This is the way I am doing. Even though this method is resource intensive when the path is getting generated, once the path is generated it would only take resources that are needed for path follow only.
The better the resolution of each tile, the better the collision detection would be. I am using tiles of 3×3 pixels. I have experimented with other values such as 2×2, 4×4, 8×8, etc. The higher resolution ones provide great collision detection but are slow to get the path, move erratically since there are many more nodes in the path.
The one that I have selected has a good balance between speed and performance.
Analysis:
A* and Dijkstra are two of the most famous path following algorithms that are used. Even though the use of Djikstra in production games is very rare, we can get a better look at how it works and how it relates to A*. As shown above, even for same weights and nodes, A* performs a lot better than Dijkstra and that I think is one of the reason it is so widely used in games. I also found that the amount of memory taken by Dijkstra is higher by a couple MB when creating the path for the grid when compared to A*. It also took considerably longer time for Djikstra to find the path for huge graphs. Sometimes the difference between A* and Dijkstra would be more than a few minutes. This difference is not very visible when using the smaller graph as A* is only faster by a couple of milliseconds instead of minutes. I think the reason for this is because of how Dijkstra goes through every node, the numbers of which are very high in my grid. I believe I had about 90,000 nodes in the scene with a 3×3 tile map. This also shows than even though both Dijkstra and A* have similar theoretical big O values for computational complexity, the practical performance is totally different.
Download:
You can download the sample here: Download
Controls on Keyboard
1 – Djikstra
2 – A* with Manhattan
3 – A* with Grid and click to move.
References:
[1] Amit , Heuristics,http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html [website] Available: Stanford.edu