[A.I. For Games] Pathfinding

This blog series is a part of the write-up assignments of my A.I. for Games class in the Master of Entertainment Arts & Engineering program at University of Utah. The series will focus on implementing different kinds of A.I. algorithms in C++ with the openFrameworks library, following most of the topics in the book Artificial Intelligence for Games by Ian Millington and John Funge.

In this post, I will talk about the implementations of our graph structure and the results of some pathfinding algorithms.

Pathfinding

Pathfinding is an interesting sub-category in the AI model. It is being placed on the between decision making and movement. Usually, pathfinding algorithms are only used to retrieve an optimal path, how this path is going to be interpreted and used is the responsibility of some other algorithms. However, there are also cases in which the pathfinding algorithm actually decide where to go and how to get there.

Data Structure

Let’s talk about the data structure first. We will be using a directed non-negative weighted graph, which implies directed non-negative weighted edges. As for the nodes, currently, I’m just using an uint32_t as the nodes indices, and for nodes representation. For the edge representation, the class basically holds the reference to the source node and the sink node, and a cost to reach from source to sink.

As for the actual graph class, it basically holds an array of all the nodes, along with some helper members.

uint32_t as node

Edge class

A* Graph Search

To calculate the optimal path from source to sink, I am going to use A* graph search. Details of the information are in the other post.

Dynamic Path Follow

In order to utilize the path retrieved from A* algorithm. We need to actually construct a path that is just a vector of kinematics so that they are in the world space. We can then pass this new path into our dynamic path follow steering algorithm.

Inside the path following algorithm, it will keep on checking the path deque and see if there is still at least a target in the deque. If there is, then it will delegate the target to dynamic arrive until it reaches the target (within a threshold value). After that, we will pop the deque and look at the next target. The process will keep on going until there is no target left in the deque.

Dynamic path follow constructor signature

Path follow algorithm

Collision/Obstacle Avoidance

Check out the other post for collision and obstacle avoidance!

In Action

First, I am going to test the path follow algorithm without any obstacles. The result that is shown below demonstrates that the quantization, localization and the major part of the path following algorithm do work. However, there are some problems that we need to address. First, The boid appears to be stopping and restarting every time it reaches a node, which is because of me using the same radius value as the stop radius for dynamic arrive and the smooth radius for the path following steering. Second, the boid’s motion won’t stop once it reaches the final node.

After tweaking some of the parameters and not allowing the path to clear (so that the steering will just become dynamic arrive in the end), the result looks a lot better already.

Path follow and dynamic arrive parameters settings

Modifying path follow so that the path deque will never become empty

Now we can add the functionalities of changing the target position dynamically and using the new path calculated by A* to update the steering path.