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.
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.
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.
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.
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.
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.
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.
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".
I know what you're thinking. What good is all of this if you need to be at a node to find where the nearest node to the player is? In this last chunk of code, we take in two transforms and find a path between them using the nodes as waypoints. Keep in mind that to use this, your entire open area needs to have nodes visible. Think of the nodes as torches that connect, and "illuminate" the entire space so that there are no spaces that cannot be seen by a node. As long as both the target and the user are within sight of some node, the function will return a valid path. I'll allow you to create characters and program how they move and also how they make use of these waypoint arrays. As a hint, FindPath() is meant to be used less than once per frame. I have mine set to iterate through a list of 7 creatures and have them call FindPath once every few seconds. Each time they call it, they have an entire path to follow, and it is unlikely to change dramatically until they get close to the target, at which point they will see the target directly and you should be writing code to move toward the target if it is visible rather than following a path.
Here is a quick video of one of my sand-people enemies finding their way through an entire maze to where the player's marker is. Much more terrifying in regular speed.
If you're going to use my source code for your project or even poke around in it, please read through the rest of this walkthrough. It will save you time to understand it before you drag and drop it into your project. Ideally, you'll take pieces that you want and make a very modified version once you understand exactly what all of the parts do. I want to educate rather than give away free code, but again, you're free to do whatever you want with this, commercial or otherwise! If you'd like to make it rain, here is my money catching bucket. https://www.paypal.me/AuggoDoggo/5
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.
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.
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.
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.
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.
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.