• Building navigable node graphs
• Navigating a node graph using the A* algorithm
• Practical application of A* navigation in a simple game demo

Pathfinding is really just a way to tell an AI system to find the most efficient way to navigate from one point to another. However, before you can achieve this, you need to establish the points themselves. In pathfinding systems, these points are generally called "nodes." These nodes are all connected together in some fashion to create a network, which we refer to as a "node graph." You can think of this node graph as a series of interconnected waypoints. The AI search algorithm will navigate throughout these points to move from one node to another, by way of the most efficient path of neighboring nodes.

To facilitate experimentation and interaction while working with pathfinding algorithms, we begin our lecture by teaching you how to write a visual node graph editor. This editor allows a user to quickly and intuitively place nodes in a 2D field and connect them together to form a final node graph. These node graphs can also be edited within the application, with nodes being repositioned or reconnected to form an infinite variety of patterns and navigation possibilities. The editor also supports loading and saving of node graphs, allowing for maximum flexibility when testing out various pathfinding algorithms.

The benefit is that once we get into coding the pathfinding behavior, the completed node graph editor can be used as a tool to quickly test a variety of different node layouts. This helps you not only to see how the pathfinding system is working, but also provides an easy way to see where improvements or tweaks to the system can be made to customize the behavior, by watching how the AI actor moves from the start point to the goal.

Once you have the knowledge and means to create your own navigable node graphs, it's time to take a look at navigating them through pathfinding. While the A* algorithm is the primary focus of this video, we build up to it by discussing some of the more fundamental pathfinding algorithms from which A* is derived. Starting with breadth-first and depth-first navigation, we quickly take you through Dijkstra's algorithm, and finally up to A*.

You'll see how weighted graphs are used by A* to determine path efficiency from one node to the next, and how edge relaxation can be employed to stop excess calculations along inefficient paths. We also show you how A* uses an estimation calculation known the heuristic, which speeds up calculation by taking an estimate of the distance from any given point to the final goal node, and using that estimate as a basis for comparison.

To complete the lecture, we take everything learned up to this point and combine it with the behavior system concepts explored in the first part of the series, "Behavior Systems." In doing this, we create a simple game demo, in which we have a state-based AI-driven Enemy actor. The Enemy actor begins the demo in a "Wander" state, meaning that it is using the A* search algorithm, along with a series of randomly selected goal nodes, to patrol the level, following a node graph designed to chart out out the level's navigable areas.

Surrounding the Enemy actor is a visible radius, which serves as the limit of the Enemy's visual range. If the player enters this radius, either actively or by standing too close to the Enemy's path while in the Wander state, the Enemy switches to a "Seek Player" state, in which the Enemy actor begins using the A* algorithm to find the best path to the player. This path is constantly updating based on the player's position, giving the impression that the Enemy is chasing the player around the level, while still navigating throughout the level's underlying node graph. This pursuit will continue until the enemy comes into contact with the player.

Once the Enemy actor touches the player, we assume that the Enemy is heavily damaged by the contact, and it switches to a new state called "Seek Health." In this state, the behavior of the AI changes, as it now uses the A* algorithm to find the best path to a stationary health pickup. Once the health pickup is retrieved, the Enemy actor reenters the Wander state, and the whole cycle begins again.

Using this example, we can see how the combination of a state-based behavior system, with pathfinding navigation, can give the illusion of complex AI with sophisticated decision-making capabilities and believable reactions.