Intro

If you'd like to use a pathfinding algorithm that uses minimal run-time processing power, and you've got a bit of programming experience, this is a great place to both learn and snag a sharp piece of a code for your 3D game. If you can't follow everything I'm posting here, then feel free to contact me and ask questions. All code here is 100% free to use for any purpose. If you'd like to support me, tell your friends about Plunker, and buy it! I'm not going to package this in a friendly drag and drop Unity Asset, I'm going to upload the source code and guide you through how to use it in your own game and you'll probably want to alter it to fit your needs. If you can follow how I made this then I'm confident that you can make much use of it.

Features

This code builds a network of connected nodes that are processed as waypoints for the fastest path from node A to node B. Every single path from every node to every other node will be stored in an array. This way, you can pre-process the fastest paths and then look them up often without burning processing power. Almost immediately after booting, you can query the Node Network for the fastest path between two transforms that can readily see one of the nodes. In other words, if your player is in a maze, running from enemies, the enemy can call NodeNetwork.FastestPath(Player.transform, Enemy.transform) some raycasting will be done to determine which nodes are visible to the player character and the enemy character. The output is an array of waypoints that you can use in your enemy script.

In this section I'm going to walk you through Pathfinding algorithms in Plunker in 5 sections.

• Theory
• Application
• Beam Casting
• Dijkstra
• Runtime Access

Theory - Dijkstra

When finding the fastest path in a 3D environment, one may hear mention of something called A-Star search algorithms. This is an abstract extension of Dijkstra's algorithm for finding the fastest path between two nodes using heuristics. I'm going to focus on my own implementation of Dijkstra's Algorithm. School teaches you algorithms like these in a conceptual way, but often you realize that the concepts require a lot of work to apply to real life niche solutions. Dijkstra wasn't thinking of massive sand creatures navigating a maze to hunt down a player character on their own, but because his conceptual algorithm is abstract and vague, it can be applied to many things with some thought and work. I won't explain Dijkstra's in detail, since there's an entire Wikipedia page that explains it.

To apply these ideas to our implementation the first thing we need is a formal reference to everything we are using in our algorithms. The DijkNode (below) is a way to capture all information in a convenient chunk of data (Notice at the bottom of the code sample we define a 2D array). Our 2D array, or our network as defined in the code, can be thought of as a lookup table where the first row (network[0,x]) will be a list of DijkNodes that contain info on each nodes relation to node 0. If this is confusing I will explain it further.

Data Structure - DijkNode

network[0,1] is a single DijkNode. Each DijkNode stored in the first row (network[0,somenumber]) has information on that x node only as it relates to the 0th node. In other words network[4,9].min_dist would tell you the minimum distance that it would take to get to the 9th node from the 4th node. So once we've filled out this entire 2D array we will be able to look up the fastest path between two nodes in terms of waypoints of other nodes. Example of how you would grab the fastest path is at the bottom, it won't work until we've constructed a network and filled the 2D array out though. This is where Dijkstra's algorithm comes in, we would implement it to fill in our data table.

                                    struct DijkNode
{
    public List<int> nodes; //List of indices of nodes that have physically unblocked line of sight to this referenced node
    public Transform trans; //Transform is used for a point in world space but a Vector3 is a fair replacement for a simple implementation
    public bool finalized;  //To mark that this node's min_dist has been finalized for certain
    public float min_dist;  //The total distance of the minimum set of nodes between Start(this row) and Finish(this node)
    public List<Transform> min_path; //The actual list of nodes, in order, forming the shortest path between Start(this row) and Finish(this node)
}

DijkNode[,] network;

//would access this for stored/processed info
//Transform[] fastest_path_between_start_and_finish = network[start_node_index,finish_node_index].min_path.toArray();
                                

If you look back at this image, you'll see all of the nodes (empty game objects with pink cubes added for visibility) that I've placed in the stone/sand maze in Plunker. These are hand placed but at the end of this guide, I'll explain how one would automate the node placement.

In order to fill in our DijkNode table with an algorithm, we need the transforms of these nodes as well as a way to see which nodes "connect" directly. If we can reference these, then we can literally achieve everything else through our algorithms. Below I'll place an image of a visualisation of all node connections.

Beam Casting (Wide Ray Casting)

If we simply ray cast from node to node, we will have a connection, but when we think further about what this connection means, then we see some problems with this approach. A ray cast from one point to another identifies that an infinitely thin space exists between two nodes, but as far as we know it could be a pinhole, which is not going to be a path at all unless your AI character is a tiny fly or a speck of dust. Of course for the case of carefully setting up your own nodes, you can easily say, "hey I'll never do anything stupid or lazy like that, I'll put my nodes exactly where they need to go". Even so, we'll be efficiently raycasting a lot to find our character the correct closest nodes, so let’s use this function I've cooked up for easy checks for connections that are wide enough for our characters to get through.

                                    public bool BeamCast(Transform target, Transform origin, float width)
{
    width = width / 2;
    RaycastHit rch;
    Ray close_ray;

    Vector3 ray_direction = target.position - origin.position;

    close_ray = new Ray(origin.position + Vector3.Cross(ray_direction, Vector3.up).normalized * width, ray_direction);
    if (!Physics.Raycast(close_ray, out rch, Vector3.Distance(origin.position, target.position), layermask_all, QueryTriggerInteraction.Ignore))
    {
        close_ray = new Ray(origin.position + Vector3.Cross(ray_direction, Vector3.down).normalized * width, ray_direction);
        if (!Physics.Raycast(close_ray, out rch, Vector3.Distance(origin.position, target.position), layermask_all, QueryTriggerInteraction.Ignore))
        {
            return false; //beam not obstructed
        }
    }

    return true; //beam obstructed
}
                                

The creatures in Plunker are generally pretty huge, so I start with 2f as the width, but this function will do two raycasts parallel with the Y(upward) plane. Imagine the rays being the edges of a beam like the light bridges in portal. If the entire beam can make an uninterrupted connection, then we can say that the characters of a similar width can also walk that path. Let’s take a look at how we use this to iterate through all of the possible node connections in a one-time initialization.

The following code block is the first half of the initialization function for our DijkNode table/database of shortest paths. The first thing we do is set references of transforms to each DijkNode, and initialize Lists. At the same time, we check on line 16 there if we are at a DijkNode referencing its own node. Remember each DijkNode is exists only to describe the connection between two nodes. If our indices are the same, like the DijkNode located at network[x,x], then we will have a min_dist that describes the distance of the minimum path between node x and itself. This should always be 0. We will use this to help us in the next section. We also initialize our min_path saying that the path from x to x is one node, x.

Next, we iterate through them and BeamCast between each. When there is an uninterrupted beam, we add to a list of indices on our DijkNodes that can be connected. Notice how we have set the for-loops to only check each connection from one direction. This almost halves the work for the computer, remember this for later when I highlight how we could do the same elsewhere.

                                    void FillPaths()
{
    //instantiate square matrix, contains x^2 total nodes, where x is the number of nodes to start with
    network = new DijkNode[NLength, NLength];
    
    //initialize DijkNodes
    for (int i = 0; i < NLength; i++)                       
    {
        for (int j = 0; j < NLength; j++)                   
        {
            network[i, j].trans = node_network[j];
            network[i, j].min_path = new List<Transform>();
            network[i, j].nodes = new List<int>();

            //in each row, we have one starting node. Hence the min_dist should be 0. 
            if (i == j)                                              
            {
                network[i, j].min_dist = 0;
                network[i, j].min_path.Add(network[i, j].trans);
            }
            else { network[i, j].min_dist = float.MaxValue; }
        }
    }


    //find connections between initialized nodes
    for (int i = 0; i < NLength; i++)
    {
        for (int j = i + 1; j < NLength; j++)
        {

            if (!BeamCast(node_network[i], node_network[j], 2f))
            { 
                for (int k = 0; k < NLength; k++)
                {
                    network[k, i].nodes.Add(j);
                    network[k, j].nodes.Add(i);
                }
                //This is where you'd draw the line with a line_rendering function
            }
        }
    }
                                

Applying Dijkstra

At this stage, we have information and can easily plug everything into a Dijkstra style fastest path algorithm. I'll paste this gif again in hopes that you see the steps in both the gif and the code.

We'll iterate through each row of DijkNodes, in this way we'll find the fastest path to each of the DijkNodes from whichever row we're on. Row 0 will be an Array of DijkNodes that contain the fastest paths from node 0 to node x where x is the index of each other DijkNode. We want to process each node exactly once, but we do not want to process them in numerical order of their indices. For row 0, we'll start at DijkNode 0 and crawl outward based on connected nodes. Each time we process a DijkNode we look at its connected nodes, current min_dist, current min_path, and we update the connected nodes with new minimum distances from the start node along with min_path that we have stored at each node.

How do we crawl outward? It seems like a simple problem for a human eyes but when you think of using nodes as references you can think yourself in absolute circles. We start with a loop, only operating on the node with the current lowest minimum distance from the starting node (remember untouched nodes have a min_dist of float.MaxValue), and one that has not been chosen. When we finish processing, we update all of the connected nodes and mark this node as processed. We then loop back to see a couple new nearby (no longer MaxValue) nodes with distance information that have not yet been marked as processed/finalized. So long as all of the nodes have some connection to the rest, each one will be processed once and the loop will end having processed the entire network. Each node should have been updated with the fastest path and distance values.

It's ok if this takes some time/effort to sink in. Maybe even some clarification on my part, but I hope you can see that by the time we pass through the whole table, we can now use it as a look up table like this: "network[startnode,endnode].min_path".

                                        //Dijkstra inspired algorithm 
    for (int k = 0; k < NLength; k++) 
    {
        //loop NLength times on each row
        for (int c = 0; c < NLength; c++) 
        {
            //initialize values
            int closest_index = -1;
            float closest_dist = float.MaxValue; 
            //Find the current closest node to k-node that has not been processed 
            //(this is why we set k,k min_dist of 0 and all others in the row with MaxValue earlier)
            for (int i = 0; i < NLength; i++)
            {
                if (!network[k, i].finalized && network[k, i].min_dist < closest_dist)
                {
                    closest_dist = network[k, i].min_dist;
                    closest_index = i;
                }

            }
            if (closest_index == -1) { Debug.LogError("Problem with finding path for " + this.gameObject.name); break; } //If this comes up, something is setup wrong...

            for (int a = 0; a < network[k, closest_index].nodes.Count; a++) //iterate through the nodes that have a direct connection
            {
                //This code can get extremely complex if you don't place values into variables to break up and contain the logic
                int connected_node_index = network[k, closest_index].nodes[a]; 
                Vector3 point_A = network[k, closest_index].trans.position;
                Vector3 point_B = network[k, connected_node_index].trans.position;

                float new_min = network[k, closest_index].min_dist + Vector3.Distance(point_A, point_B);
                //make sure to set all info on all connected nodes so the closest one can be processed next
                if (!network[k, connected_node_index].finalized && network[k, connected_node_index].min_dist > new_min) 
                {
                    network[k, connected_node_index].min_dist = new_min;
                    network[k, connected_node_index].min_path = new List<Transform>(network[k, closest_index].min_path);
                    network[k, connected_node_index].min_path.Add(network[k, connected_node_index].trans);
                }
            }

            network[k, closest_index].finalized = true; //mark that it has been processed
        }
    }
}
                                

These suggestions will not make your code any better but they're things that I might have done if the situation called for it, as well as ideas for if you're using this as a learning tool and you want to take your tutorial creation further.

Multi-target pathfinding

If you want multiple targets for the enemy or follower character to follow, you can check multiple fastest paths each time you FindPath and take the fastest path between the two.

path-types and feature data between nodes

You might add more info to the DijkNode struct such as if the path is clear or maybe if it is a section that the player moves more slowly through, or maybe they take damage if they walk through fire, so you'd want to add that in and calculate at the end to make sure they don't take too much total damage by the end of the path.

static vs non-static nodes

If you've got a lot of moving platforms or shifting landscapes, or obstacles that can move, you may want to determine which connections will not be interrupted so that you can update more hazardous regions more efficiently.

Using smart Dijkstra algorithms to further optimize

The path from A to B is the same distance and an exact reverse of the path from B to A. We can use this relatively easily to make the construction of the table faster. We would only care to do this if our entire network became too large or we were reprocessing it at runtime.

Sub Networks

You could create pockets of nodes that connect through only one doorway each to each other so that entire sections can be calculated separately and then cross sub-network calculations can still happen. This would help the calculations that FindPath makes when it is finding which nodes are closest to the follower and to the target. If you had a smaller pool of nodes to check then you might save some power when you have a lot of nodes.

If you felt any part of this guide was awkwardly paced, or hard to follow, please send me an email at August@AuggoDoggoGames.com and give me a chance to clear it up and improve at sharing my code creations. In the future, this is where I'll post answers to specific questions that aren't simply answered by updating a portion of the guide.