Unity: Pathfinding Research

02. Environment

The environment I created is mainly a flat surface with a good amount of obstacles, making it challenging but able to accurately reflect the performance of each algorithms.

03. Performance Metric

The performance metric used to compare & evaluate the different pathfinding algorithms was the number of frames it took for an agent to go from the start position to the target position. Unity engine runs the game at 60 frames per second which allowed me to easily calculate the total number of frames by multiplying the time (in seconds) by 60.

void Update() {
    timer += Time.deltaTime;
    foreach (GameObject i in agents) { 
        if (Vector3.Distance(i.transform.position, target.transform.position) < 2) { 
            print(i.name);
            print(timer);
            agents.Remove(i);
        }
    }
}
                                

04. Algorithms

>> Waypoint

At the most basic level of AI pathfinding, my development of the main structure of wayfinding consists of only one script. The script takes in an array of already set waypoints and directs the agents towards the waypoints in the order they were added.

if(Vector3.Distance(this.transform.position, waypoints[currentWP].transform.position) < 1) {
    if (tag == 0){
        currentWP++;
    }
    if (tag == 1){
        currentWP = currentWP - 1;
    }
}
// Change tag to 1 if the NCP reaches the end
if (currentWP >= waypoints.Length) {
    tag = 1;
    currentWP = currentWP - 1;
}
// Change tag to 0 if the NPC reaches the begining
if (currentWP <= 0) {
    tag = 0;
}
                                    

>> A*

A* is a best-first search, meaning that it is formulated in terms of weighted graphs. Starting from a specific starting node of a graph, it aims to find a path to the given goal node having the smallest code. My implementation of A* follows the logic by maintaining a tree of paths originating at the start node and extending those paths one edge at a time until its termination criterion is satisfied.

Specifically, A* selects the path that minimizes:

f(n) = g(n) + h(n)

Where n is the next node on the path, g(n) is the cost of the path from the start node to n, and h(n) is a heuristic function that estimates the cost of the cheapest path from n to the goal.

while (openSet.Count > 0) {
    Node node = openSet[0];
    for (int i = 1; i < openSet.Count; i ++) {
        if (openSet[i].fCost < node.fCost || openSet[i].fCost == node.fCost) {
            if (openSet[i].hCost < node.hCost)
                node = openSet[i];
        }
    }
    openSet.Remove(node);
    closedSet.Add(node);
    if (node == targetNode) {
        
        pathSuccess = true;
        break;
    }
    foreach (Node neighbour in grid.GetNeighbours(node)) {
        if (!neighbour.walkable || closedSet.Contains(neighbour)) {
            continue;
        }
        int newCostToNeighbour = node.gCost + GetDistance(node, neighbour);
        if (newCostToNeighbour < neighbour.gCost || !openSet.Contains(neighbour)) {
            neighbour.gCost = newCostToNeighbour;
            neighbour.hCost = GetDistance(neighbour, targetNode);
            neighbour.parent = node;

            if (!openSet.Contains(neighbour))
                openSet.Add(neighbour);
        }
    }
}
                                

>> NavMesh

My implementation of the NavMesh pathfinding utilizes a combination of Unity features and a simple script for the settings. The environment is baked with Unity and certain terrains are added with different costs to affect the pathing and movement speed of the agents, different terrain includes: mud, sand, ice, walls, and ceilings. The environment is also baked according to the agents' property (ex. Agent that has higher mass and can only go on ramps that are less steep compared to a lighter mass agent), creating a unique environment and pathing for different agents.

My setting script contains adjustment to the agents pathfinding ability within the NavMesh system.

void Update() {
    NavMeshHit navHit;
    if (NavMesh.SamplePosition(transform.position, out navHit, 1f, NavMesh.AllAreas))
    {
        int mask1 = navHit.mask;
        int index = 0;
        while ((mask1 >>= 1) > 0)
        {
            index++;
        }
        float areaCost = NavMesh.GetAreaCost(index);
        int wallMask = 1 << NavMesh.GetAreaFromName("Wall");
        int ceilingMask = 1 << NavMesh.GetAreaFromName("Ceiling");
        agent.speed = basespeed - areaCost - rb.mass;
    }
    agent.SetDestination(target.transform.position);
}
                                

Results

---

Waypoint algorithm has the highest average time with half of the runs being very inconsistent due to the nature of the algorithmm where the agents only travel in a straight line towards the next waypoint and are unable to detect and navigate around the obstacles. This method becomes extremely inefficient in a complicated environment because of the amount of work required to manually set up the waypoints.

A* algorithm achieved great results suprisingly. The results are consistent and very efficient. Though the agents are able to navigate through the environment automatically, the downside of this method is that it requires a lot of manual coding and conditions to handle different forms of obstacles. It would work very well in a medium complexity and sized world, and certainly would not be the best option in a more complex and bigger environment.

The NavMesh algorithm works the best of the three algorithms tested. It is an abstract data structure used in artificial intelligence applications to aid agents in pathfindng through complicated spaces. Using one of the already implemented Unity features, less coding and better results are achieved compared to the other methods. With most of the work handled by Unity, more features and possibilities are opened up for both the environment and the agents.

Next Step

---

There are endless possibilities to improve the pathfinding algorithms implemented for this research. If I had more time and resources, I would like to create a more complex environment to see how different algorithms would interact with it. Additionally, different speed modifiers and terrain costs for the environment are also on top of the to-do list, along with giving special abilities to the agents like walking on the wall, teleport, or fly with a cool down timer.