AI Pathfinding and Decision Making

This project builds upon the previous one and explores AI pathfinding algorithms. While I focus mainly on A*, I also implemented Dijkstra for reference and comparison. I explore various different heuristics that can be applied to A*, their performance and feasibility. Finally I implemented simple decision making using these algorithms where a 2D Boid traverses an environment (A tile-map) while avoiding moving (other boids) as well as stationary obstacles.

You can download and play around with the project from my GitHub.

Creating a Graph or two

The first thing needed was a graph I could test my algorithms on. I created two different ones. The first graph is hand crafted with a few nodes and edges. I tried to create my childhood neighborhood, with relatively accurate positioning of nodes representing important landmarks.

A simple graph

The numbers in the center of each node represent their ID while the numbers along the edges represent edge weights. I also estimated the relative positions of the nodes (represented by the (x,y) coordinates in brackets next to each node)

The other graph was extremely big and dense. For obvious reasons it could not be hand authored, but I also did not want to create an absolutely random graph. Instead I created my own tile map class which would create a tile mapped graph based on given input values.

The class skeleton for TileMap

This class would create a NxN tile map where N represents the number of tiles per side. Each node would also have connections to all of its adjacent nodes. As an example here is what a 3×3 tile map graph would look like.

A 3×3 tile graph. The numbers represent node id’s

For the sake of simplicity, I made all the edge costs identical. Using this class I was able to create very large graphs containing thousands of nodes by increasing the value of N.

A* Vs Dijkstra

Now that I had graphs for reference, I went about implementing A* and Dijkstra’s algorithms for pathfinding. For this I first needed to create some data structures. One structure representing a Directed Weighted Edge and the other a Directed Weighted Graph. I also had to create a heuristics class for A* .The first one I used was based on Euclidean distance between the target node and the current node being processed (more on this later).

Class skeleton for Directed Weighted Graph

Storing each node as an integer value helped simplify the implementation of the algorithms.

Once the algorithms were implemented I went about analyzing their runtime performance for the two graphs I created earlier.

For the simple hand crafted graph, both A* and Dijkstra took roughly the same amount of time (0.6ms and 0.2ms respectively). At the same time however the number of nodes visited by A* were lower (14) than those visited by Dijkstra (18). This result was not unexpected as the performance of A* can vary greatly based on the chosen heuristic which in this case was inadmissible (note that I chose Euclidean distance as the heuristic). This inference was also supported by the observation that A* took a longer route to the goal node, because it probably overestimated the cost to the goal.

The tile graph is where A* out shined Dijkstra. For reference I chose a tile map of 50 nodes per side which meant a dense graph of 2500 nodes was generated, with each edge having a weight of 5. Here for a selected target node, Dijkstra took ~1.7sec while A* took ~73ms which made it almost twice as fast. Not only that the nodes visited were a lot fewer compared to Dijkstra. While Dijkstra covered 1935 nodes, A* was able to find the target in only 66 nodes. This means A* used a lot less memory compared to Dijkstra while calculating path to target.

The runtime analysis for A* and Dijkstra on the two graphs

This proves that the type of heuristic used by A* is highly dependent on the graph that A* is is being run on and that there is no general heuristic that works for every graph

A* Heuristics

Since I found out that that the validity of heuristics varies from graph to graph and, that my current Euclidean distance heuristic was inadmissible for the first graph I tested, I decided to test another heuristic to see if it worked better.

Note that a heuristic is admissible if it consistently underestimates or is equal to the actual cost. What is important, and this is what admissibility guarantees, is that while A* is exploring down non-optimal paths it will not find the goal and finish the search before exploring down the optimal path. This is because as it goes down those non-optimal paths, even though they seem great at first, the cost/length of them will start to add up and at some point the algorithm will return to explore down the optimal path. If overestimation was allowed and did so down the optimal path, then A* might actually go down the non-optimal path and find the goal (which terminates the search, and therefore prevents A* from ever exploring the optimal path). On the flip side this also means that the more A* underestimates the cost to goal, the longer it will run for before arriving at the goal.

For my second heuristic I decided to use Manhattan distance since it could be applied to both my graphs. The results however were identical to those of Euclidean heuristic. For both the small and the large graph, A* visited the same number of nodes, with the only difference being that the path calculated for the tile graph was different. In both cases however, the algorithm did run slightly faster but that is most likely because calculating the Manhattan distance is a faster operation than calculating the Euclidean distance.

Finally for the simple graph I decided to create a precomputed heuristic based on a given target node (which in this case was 10). Running A* with this heuristic gave a much better output. In fact, the solution path was optimal (as compared to Dijkstra) and at the same time the algorithm visited lesser nodes (7 compared to 18 visited by Dijkstra) which meant less memory used. The time taken however was still identical to that taken by Dijkstra (~0.3ms). Not considering the runtime (which is understandable since the graph is really small), having a precomputed heuristic should give the most optimal solution (which it did)

Pathfinding with a Boid

Now that I had a working A* algorithm, it was time to get it working with my Boid.

The first thing needed was a division scheme to convert world space into graph space (and vice versa). Fortunately this is where the Tile Map class comes in. Consider TileMap.h (screenshot above), one of the inputs to the constructor (i_startPosition) determines where the starting node of the graph goes (i.e. node 0). Starting from this node I placed all subsequent nodes in order. The Tile Map class also has a function which gets the node based on mouse click position. This allows for Quantization from world space to graph space. Conversely I have a localize function built into the Directed Weighted Graph which gives the world coordinates of a node. This allows for Localization from graph space to world space.

For moving the Boid itself I created a new steering behavior called Dynamic Path Follow. Besides the usual inputs required for generating a dynamic steering output, this behavior also takes in a list of waypoints which the Boid needs to travel to in the order in which they are given. For the actual movement this behavior delegates to dynamic arrive.

In essence how it would work is on clicking at a point on the tile graph I get the node at that point. Then I get the node where the Boid is currently at. Running the A* algorithm between these two nodes I get a path. Localizing all the nodes in this path to world space I get a list of waypoints which I then feed into Dynamic Path follow. This ultimately moves the boid from the start node to the end node.

Boid Path follow!

In the video above each purple dot represents a node in the Tile Graph. The A* algorithm in this case uses the Euclidean heuristic.

The other thing to test was collision avoidance between boids. For this I created a new dynamic behavior called collision avoidance. In essence, this behavior compares a target boid against every other boid to check whether they are about to collide. If they are, then it delegates behavior to dynamic separation.

To test this I introduced a few Boids in the level which had dynamic wander enabled on them. Only the Boid fixed to the graph would be actively checking for collision avoidance. A thing to note here is that this behavior has no idea about the waypoints that the Boid is following and if it causes the Boid to move away from its current target (even if somehow pushed closer to the goal) it will try to get back to the node currently being processed, completely disregarding the tile graph. I could set it up so that the boid recalculates a new path but that will end up being too computationally expensive.

Only the Red Boid checks for collision avoidance!

As a final note I created an obstacle avoidance dynamic behavior. How the output of this behavior was not ideal as my tile graph was very dense. To make it work I created a stationary obstacle avoidance system which uses Ray casting to detect stationary objects. This is based on the common AABB – Raycast detection algorithm. If an obstacle is detected, the Boid retreats back to a certain distance from the object but at a certain offset angle so that it will eventually find a way around it (if there is one)

I tested this system and it works if I greatly reduce the number of nodes in my tile map. Even then it does not give the best behavior primarily because the tile map and A* have no knowledge of the obstacles in the level. As such if a path generated passes through a node that has an obstacle on it, the algorithm will keep trying to get to that node while obstacle avoidance will prevent it.

In the future I plan on updating my tile map class so that I can dynamically remove one or all edges from a node or update their weights. That way I can update my tile map to invalidate all nodes with obstacles on them.

1 Comment »

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s