As an old saying goes: if you can't explain it, then you don't master it. This will serve as a starting point to others that might be on the same path I was a few months ago: trying to understand the basic concept of ">efficient pathfinding.
The problem
Pathfinding is a domain in computing science that is widely known to be complex since most of the paper/explanation comes from expert/mathematician/AI veterans. Applied to games, it gets more complex as you get into optimizations more often than basic explanations. True, it is a complicated subject: it needs to be efficient and also be accurate.
The compromises
When you try to achieve both efficiency and accuracy, you will certainly need some very heavily-optimized code. So for games, we'll need to state some compromises. Do we actually need the shortest path or having a path at all will suffice? Can our level/terrain can be simplified into a basic layout? Those two questions are the fundamentals of the compromises: sufficient and simplistic. For games, an AI moving toward an objective will be sufficient enough to be believable. And to obtain good performances and efficient work flow, we'll need to break down our level into a more simplistic representation.
The theory
Pathfinding is a complex process that we can split down into three components: the spacial representation, the goal estimation and the agent. The spacial representation, also known as the graph, is a means to describe a network of inter-connected walkable zones (roads, floors, ...). The goal estimation, known as an heuristic, is a general representation to where might be the goal. This is a mere estimation that is needed to speed things up. Finally, the agent is the one responsible for actually searching through the spacial representation based on the goal estimation.
Putting this together you get an agent searching for a goal on a spatial representation with some hints to where it might be. Simple enough? But why do we need these three components? Why can't we just use a spatial representation and iterate through all the zones till we find our goal? Yes you could, but it depends on what you are trying to achieve. What if you have different types of enemies? Say we have a soldier and a tank heading toward the player. A tank can't go in tight spaces and can not make sharp turns. How would you represent both in a one component? With the three components above, both units are walking on the same terrain, looking for the same goal, the player, but have their own limitations: you got a spatial representation, a goal and two agents. That is why pathfinding is always explained as three distinct components.
The graph
There are several ways to represent a graph of walkable zones and I'll be describing the three most used throughout my research.
The first one, the most basic and easiest to understand is the grid. This is the most-explained type of graph when it come to pathfinding, go ahead and google "A star search algo" and you'll most likely find an evenly spaced grid that covers a square room/space. Let's take a look on a simple "H" shape.
As you can see, a uniform grid has been applied on the shape creating a network of nodes (pink and black dots). Yet effective and simple, a lot of memory is wasted on keeping data for a network that is not within our shape. To overcome this detail we could simply remove black dot from the graph and voil?. Here's another catch: from a to b would require a search through all the mid to south noded, ?96nodes, to find a path of ?19nodes. The search algorithm is wasting precious time and power to go from 96nodes to 19. You could also add diagonal connectiond between nodes to reduce the path a bit. Another catch: most of the implementations I saw relies on raycasting from the sky (to detect nodes that are outside of geometry) thus making it useless (or complex workaround) when dealing with environments that have a ceiling. The point is, this graph is inefficient because too much data is representing the same zone (we'll get into that in a moment).
The waypoints graph is the most used (based on pure observation in games). It does give you an alternative to the grid since more than 4 connections (8 with diagonal) between nodes can be made. Nodes are placed around the level with care to cover most of the walk-able areas without creating too much noise for the search algorithm.This graph can be placed along your geometry (doesn't care if it has a ceiling) and also reduce the nodes count: ?31 mid-south nodes and a path from a to b of ?11 nodes. That is a lot better than the grid-based graph but still has a major issue (like the grid graph). The resulting network from these two point-line-connections is stripping away part of your actual walk-able area. See the image below for a better understanding.The network contains data only about the connections between nodes, thus stripping away the actual floor of our geometry. Multiple problems emerge from this fact: paths will have angular turns, an agent could never land on the a or b since they are not on the network and the paths can not be reduced with some direct-line-of-sight. Because these types of network only consider the walk-able area to be dots (with a radius) and their connections, the outside of the network can only be unwalk-able area or at least not safe (like a ditch, or narrow passage). So cutting a corner or trying to go in straight lines between nodes may be risky. I say may be because it depends on your level and your network. You could place your nodes to take account of the fact that agents will cut corners and maybe your level doesn't have ditches/holes/obstacles.
For those that are still with me, the solution to the above problems lie within our actual geometry, meshes, commonly referred as navigation mesh or simply navmesh. The mesh of your floor geometry is pretty much all you'll ever need to build your network: connected vertices form triangles, put in our terms, interconnected nodes.As you can see, by giving each node an actual surface instead of point, the network reflects the actual floor. We also reduce the network from mid-south ?31nodes to 10 and a path of ?11 nodes to 8. What now? Well we can reduce a bit more our number of nodes by merging triangles into convex polygons. Why convex? A point and triangle are some kind of convex polygon and we can all affirm that two points lying within a convex shape can be linked with a straight line? Yes. In a convex polygon, for every point that lies on the edges to an other point on an other edge can be linked with a line that is contained within the polygon. In other words, an agent coming from the left side of a rectangle can cross over to the right side without worrying about collisions with walls.Once more we reduced our network significantly, 4 nodes total with a 3 nodes to our goal. As you can see, based on some simple geometry assumption, we were able to build a very efficient network for our "H" shape. I hope now you do understand that grids and graphs are very useless compared to a navmesh: we saved 3200% (131nodes to 4nodes) of processing power for our search algorithm. As intelligent beings, we do this process every time we plot a path in a known surface: we simplify the environment into basic shapes to find an path that is satisfying (we aren't computers that are looking for the most-optimized-path).
Navmesh grid is the most efficient and accurate method to describe spatial areas and that is what we are looking for.
The heuristic
The heuristic is an information that is provided to each node of your graph to direct the search algorithm toward the target(s). Acting like a heat map, your search algorithm will look into this map to prioritize nodes.Multiple algorithms can be used to generate a heat map. In fact, it all depends on your game design, level design, platform, etc. For example, for levels that don't have overlapping floors, the euclidean distance (distance between two points) will do the job (like in the above diagram). The heuristic is a game changer in pathfinding, without it, performance would drop since the search would need to look up every node till it finds the target. On the other hand, with a heuristic that isn't adapted to your game, it would result in false estimation and your search algorithm could waste some valuable time in the opposite direction of your target.
If your graph is relatively small (node count) and your target platform possesses enough memory, the best heuristic would be as follows: each nodes contains a list of all other nodes in the graph with their corresponding depth. So node #1 would know that it's 4 nodes away from #56, and thus providing the best estimation for the search algorithm - moving from lowest depth connections of each node would inevitably result in the shortest path.
The agent
This is where the search algorithm is performed. With a network and heuristic, a basic A* (pronounced "a star") algorithm can find the shortest path between two nodes. A* algorithm is really well documented and is pretty simple to implement (under 50 lines of code), so I don't have anything more to say on that topic.
The result
At this point, the agent found a path of nodes toward the target. As stated in my previous posts of April, Pathfinding 101 and Pathfinding 102-ish, we'll need to find a way to optimize the path into a list of waypoints. This is where I struggled the most, I tried to find an algorithm that would optimize the path based on my understanding of the Funnel algorithm. And then I found a simple implementation in C++ (first result on google). It does work perfectly and it only requires a list of portals to walk through, so it will work with any graph you decide to use.
Demo
A tech demo that combines everything discussed in this article.
You could always approximate your environment with convex hulls that have much less detail then the actual environment mesh. Then updating the navmesh would be fairly trivial as a convex hull could be considered a navmesh :)
Thanks! Your article starts out strong but I think it would be even better if you would talk more about the heat map (how is it generated?) and how to actually form the path of waypoints using the navmesh.
As you can see, a uniform grid has been applied on the shape creating a network of nodes (pink and black dots). Yet effective and simple, a lot of memory is wasted on keeping data for a network that is not within our shape. To overcome this detail we could simply remove black dot from the graph and voil?. Here's another catch: from a to b would require a search through all the mid to south noded, ?96nodes, to find a path of ?19nodes. The search algorithm is wasting precious time and power to go from 96nodes to 19. You could also add diagonal connectiond between nodes to reduce the path a bit. Another catch: most of the implementations I saw relies on raycasting from the sky (to detect nodes that are outside of geometry) thus making it useless (or complex workaround) when dealing with environments that have a ceiling. The point is, this graph is inefficient because too much data is representing the same zone (we'll get into that in a moment).
The waypoints graph is the most used (based on pure observation in games). It does give you an alternative to the grid since more than 4 connections (8 with diagonal) between nodes can be made. Nodes are placed around the level with care to cover most of the walk-able areas without creating too much noise for the search algorithm.
This graph can be placed along your geometry (doesn't care if it has a ceiling) and also reduce the nodes count: ?31 mid-south nodes and a path from a to b of ?11 nodes. That is a lot better than the grid-based graph but still has a major issue (like the grid graph). The resulting network from these two point-line-connections is stripping away part of your actual walk-able area. See the image below for a better understanding.
The network contains data only about the connections between nodes, thus stripping away the actual floor of our geometry. Multiple problems emerge from this fact: paths will have angular turns, an agent could never land on the a or b since they are not on the network and the paths can not be reduced with some direct-line-of-sight. Because these types of network only consider the walk-able area to be dots (with a radius) and their connections, the outside of the network can only be unwalk-able area or at least not safe (like a ditch, or narrow passage). So cutting a corner or trying to go in straight lines between nodes may be risky. I say may be because it depends on your level and your network. You could place your nodes to take account of the fact that agents will cut corners and maybe your level doesn't have ditches/holes/obstacles.
For those that are still with me, the solution to the above problems lie within our actual geometry, meshes, commonly referred as navigation mesh or simply navmesh. The mesh of your floor geometry is pretty much all you'll ever need to build your network: connected vertices form triangles, put in our terms, interconnected nodes.
As you can see, by giving each node an actual surface instead of point, the network reflects the actual floor. We also reduce the network from mid-south ?31nodes to 10 and a path of ?11 nodes to 8. What now? Well we can reduce a bit more our number of nodes by merging triangles into convex polygons. Why convex? A point and triangle are some kind of convex polygon and we can all affirm that two points lying within a convex shape can be linked with a straight line? Yes. In a convex polygon, for every point that lies on the edges to an other point on an other edge can be linked with a line that is contained within the polygon. In other words, an agent coming from the left side of a rectangle can cross over to the right side without worrying about collisions with walls.
Once more we reduced our network significantly, 4 nodes total with a 3 nodes to our goal. As you can see, based on some simple geometry assumption, we were able to build a very efficient network for our "H" shape. I hope now you do understand that grids and graphs are very useless compared to a navmesh: we saved 3200% (131nodes to 4nodes) of processing power for our search algorithm. As intelligent beings, we do this process every time we plot a path in a known surface: we simplify the environment into basic shapes to find an path that is satisfying (we aren't computers that are looking for the most-optimized-path).
Navmesh grid is the most efficient and accurate method to describe spatial areas and that is what we are looking for.
Multiple algorithms can be used to generate a heat map. In fact, it all depends on your game design, level design, platform, etc. For example, for levels that don't have overlapping floors, the euclidean distance (distance between two points) will do the job (like in the above diagram). The heuristic is a game changer in pathfinding, without it, performance would drop since the search would need to look up every node till it finds the target. On the other hand, with a heuristic that isn't adapted to your game, it would result in false estimation and your search algorithm could waste some valuable time in the opposite direction of your target.
If your graph is relatively small (node count) and your target platform possesses enough memory, the best heuristic would be as follows: each nodes contains a list of all other nodes in the graph with their corresponding depth. So node #1 would know that it's 4 nodes away from #56, and thus providing the best estimation for the search algorithm - moving from lowest depth connections of each node would inevitably result in the shortest path.
i'm using navigation mesh concept in my project, this is my experience
pros: fast, accurate
cons: when enviroment updated, nav mesh must be rebuilt, and the algorithm too do that is expensive