Chapter 7: A* Pathfinding

In this chapter, we will implement the A* algorithm in Unity3D using C#. The A* pathfinding algorithm is widely used in games and interactive applications because of its simplicity and effectiveness. We talked about this algorithm previously in Chapter 1, Introduction to AI. However, here, we'll review the algorithm again, this time from an implementation perspective.

In this chapter, we will look at the following topics:

• Revisiting the A* algorithm
• Implementing the A* algorithm
• Setting up the scene
• Testing the pathfinder

Technical requirements

For this chapter, you just need Unity3D 2022. You can find the example project described in this chapter in the Chapter 7 folder in the book repository: https://github.com/PacktPublishing/Unity-Artificial-Intelligence-Programming-Fifth-Edition/tree/main/Chapter07.

Revisiting the A* algorithm

Let's review the A* algorithm before we proceed to implement it in the next section. The foundation of any pathfinding algorithm is a representation of the world. Pathfinding algorithms cannot search over the noisy structure of polygons in the game map; instead, we need to provide them with a simplified version of the world. Using this simplified structure, we can identify the locations that an agent can traverse, as well as the inaccessible ones.

There are many ways of doing this; however, for this example, we use one of the most straightforward solutions: a 2D grid. Therefore, we implement the GridManager class to convert the "real" map into a 2D tile representation. The GridManager class keeps a list of Node objects representing a single tile in the 2D grid. First, of course, we need to implement the Node class too: this class stores node information such as its position, whether it's a traversable node or an obstacle, the cost...

Implementing the A* algorithm

First, we implement the basic classes that we introduced before, such as the Node class, the GridManager class, and the PriorityQueue class. Then, we use them in the main AStar class.

Node

The Node class represents each tile object in the 2D grid. Its code is shown in the Node.cs file:

using UnityEngine;
using System;
public class Node {
    public float costSoFar;
    public float fScore;
    public bool isObstacle;
    public Node parent;
    public Vector3 position;
    
    public Node(Vector3 pos) {
        fScore = 0.0f;
        costSoFar = 0.0f;
        isObstacle = false;
        parent = null;
        ...

Setting up the scene

We are going to set up a scene that looks like the following screenshot:

Figure 7.1 – Our sample test scene with obstacles

Let's follow a step-by-step procedure to do this:

1. We create a directional light, the start and end game object, a few obstacle objects, a plane entity to be used as ground, and two empty game objects in which we put the GridManager and TestAStar scripts. After this step, our scene hierarchy should be like this:

Figure 7.2 – The demo scene hierarchy

2. We create a bunch of cube entities and add them to the Obstacles layer. GridManager looks for objects with this tag when it creates the grid world representation:

Figure 7.3 – The Obstacle nodes seen in the Inspector

3. We then create a cube entity and tag it as Start:

Figure 7.4 – The Start node seen in the Inspector

4. Then, we create another cube entity...

Summary

In this chapter, we learned how to implement the A* pathfinding algorithm in Unity3D. First, we implemented our own A* pathfinding class, grid representation class, priority queue class, and node class. Finally, we used debug draw functionalities to visualize the grid and path information.

In later chapters, we will see that thanks to Unity3D's NavMesh and NavAgent features, it may not be necessary for you to implement a custom pathfinding algorithm on your own.

Nonetheless, understanding a basic pathfinding algorithm gives you a better foundation for getting to grips with many other advanced pathfinding techniques.

In the next chapter, we will extend the idea behind the A* algorithm to a more complex world representation: navigation meshes.