I was watching this talk by Oskar Stålberg, who is one of the creators behind a cool indie game called Bad North. In it he said he had fun making a custom "navmesh," and since I had no experience whatsoever from navmeshes, I decided to make my own navmesh. I've earlier got questions if my pathfinding-for-cars algorithm is working on Unity's navmesh (or any navmesh) and I've up until now said "I have no idea" because I wasn't sure how a navmesh is working.
What is a navmesh?
Once upon a time it was common to divide the area, where a character in a game can walk around, into a grid, like a chessboard. The problem with this method is that if you have a big map, you will get a large chessboard, making pathfinding very slow. A better way (in some cases) is to make a navigation mesh (navmesh). You do this by dividing the area into convex shapes, such as triangles, meaning that you will hopefully end up with fewer triangles than cells in the chessboard. This will make pathfinding more efficient because the pathfinding algorithm has to investigate fewer nodes.
How can you learn how to make a navmesh?
To learn how to make a navmesh, I googled "Unity navmesh tutorial." But all tutorials I found were about how Unity's own navmesh system is working - not how to make your own custom navmesh. But why are there almost no tutorials on navmeshes? The reason is not that finding your way around a navmesh is difficult - the reason is that it's difficult to create the shapes, like the triangles, that makes up the navmesh itself. So after much research, I learned that if you want to learn how a navmesh is working, you have to learn the following areas:
How to create the navmesh itself
A navmesh consists of connected convex shapes. The reason they have to be convex is that if you are standing inside of a convex shape, you can walk in a straight line to any other point in that shape. If the shape had been concave you would have to do some local pathfinding inside of the concave shape. These shapes are in many cases just triangles, but some merge these triangles into other convex shapes, such as rectangles, to make pathfinding more efficient.
The problem is: how can you create these connected triangles from the game level you have? You might have these houses and you want some character to find the shortest path between the houses. I believe the answer to that question is Constrained Delaunay Triangulation, which is a big topic, and I've written a tutorial on it here: Constrained Delaunay Triangulation. So now you have something that looks like this:
How to find the shortest path on a navmesh
You have these connected triangles, and now you want to find the shortest path from one triangle to another triangle. To do that you connect the center of each triangle with the center of each neighbor, and then you just run some pathfinding algorithm, like A* (A star), on that graph. When the character is moving between each triangle, it should not move to the center of the next triangle, but the closest point on the edge shared by the current triangle and the next triangle.
The shortest path on a navmesh can be simplified by using a line-of-sight algorithm - the character doesn't have to navigate between the triangles if it can move in a straight line to the goal triangle. But how can you detect if a character can see the goal point it wants to reach? The answer is by using a line-line intersection algorithm. If you draw a straight line from the character to the position it wants to reach, and if this line is not intersecting with any of the triangles edges that are obstacle (has no neighbor), then the character can move in a straight line to the position it wants to reach.
How to make characters follow the shortest path
Now you know which triangles the character has to pass to reach the goal destination. To make it reach the destination, you should learn a set of algorithms called Steering Behaviors. This is what Unity is using to make the characters find their way around their navmesh system. For example, they are using an algorithm called RVO to prevent characters from colliding with each other.
More than pathfinding
Navmeshes are useful for other areas than just pathfinding for characters. While researching navmeshes I read that you can use them to simulate flow. When simulating flow in games you move a texture by using a color and the color determines in which direction the texture should move. For example, if the color is red, then the texture moves in a certain direction. This makes it look like the water is flowing. This colored texture is called flowmap, but they are almost impossible to paint by hand, and what if the flow is suddenly changing direction while the game is running? With a navmesh, you can create dynamic flowmaps.
To make this work you should connect the vertices of each triangle in the navmesh, and then run a flowfield algorithm to find the shortest path from each node to the destination in the triangle you want to reach. As said before, you can use the line-of-sight algorithm to detect if a node can see the goal position. Each node will now get a direction and this direction is used to set the vertex color of the mesh. You can access this vertex color in a shader and thus get the flow direction. Moving the texture in the direction of the flow is kinda tricky and this is a good article on the subject.
This is the dynamic flowmap that determines the direction of flow:
...and then you can simulate something like smoke on the navmesh:
...or water:
Read more
This was just a short introduction, so if you want to learn more about navmeshes, you should read:
What is a navmesh?
Once upon a time it was common to divide the area, where a character in a game can walk around, into a grid, like a chessboard. The problem with this method is that if you have a big map, you will get a large chessboard, making pathfinding very slow. A better way (in some cases) is to make a navigation mesh (navmesh). You do this by dividing the area into convex shapes, such as triangles, meaning that you will hopefully end up with fewer triangles than cells in the chessboard. This will make pathfinding more efficient because the pathfinding algorithm has to investigate fewer nodes.
How can you learn how to make a navmesh?
To learn how to make a navmesh, I googled "Unity navmesh tutorial." But all tutorials I found were about how Unity's own navmesh system is working - not how to make your own custom navmesh. But why are there almost no tutorials on navmeshes? The reason is not that finding your way around a navmesh is difficult - the reason is that it's difficult to create the shapes, like the triangles, that makes up the navmesh itself. So after much research, I learned that if you want to learn how a navmesh is working, you have to learn the following areas:
- How to create the navmesh itself
- How to find the shortest path on a navmesh
- How to make characters follow the shortest path
How to create the navmesh itself
A navmesh consists of connected convex shapes. The reason they have to be convex is that if you are standing inside of a convex shape, you can walk in a straight line to any other point in that shape. If the shape had been concave you would have to do some local pathfinding inside of the concave shape. These shapes are in many cases just triangles, but some merge these triangles into other convex shapes, such as rectangles, to make pathfinding more efficient.
The problem is: how can you create these connected triangles from the game level you have? You might have these houses and you want some character to find the shortest path between the houses. I believe the answer to that question is Constrained Delaunay Triangulation, which is a big topic, and I've written a tutorial on it here: Constrained Delaunay Triangulation. So now you have something that looks like this:
How to find the shortest path on a navmesh
You have these connected triangles, and now you want to find the shortest path from one triangle to another triangle. To do that you connect the center of each triangle with the center of each neighbor, and then you just run some pathfinding algorithm, like A* (A star), on that graph. When the character is moving between each triangle, it should not move to the center of the next triangle, but the closest point on the edge shared by the current triangle and the next triangle.
The shortest path on a navmesh can be simplified by using a line-of-sight algorithm - the character doesn't have to navigate between the triangles if it can move in a straight line to the goal triangle. But how can you detect if a character can see the goal point it wants to reach? The answer is by using a line-line intersection algorithm. If you draw a straight line from the character to the position it wants to reach, and if this line is not intersecting with any of the triangles edges that are obstacle (has no neighbor), then the character can move in a straight line to the position it wants to reach.
How to make characters follow the shortest path
Now you know which triangles the character has to pass to reach the goal destination. To make it reach the destination, you should learn a set of algorithms called Steering Behaviors. This is what Unity is using to make the characters find their way around their navmesh system. For example, they are using an algorithm called RVO to prevent characters from colliding with each other.
More than pathfinding
Navmeshes are useful for other areas than just pathfinding for characters. While researching navmeshes I read that you can use them to simulate flow. When simulating flow in games you move a texture by using a color and the color determines in which direction the texture should move. For example, if the color is red, then the texture moves in a certain direction. This makes it look like the water is flowing. This colored texture is called flowmap, but they are almost impossible to paint by hand, and what if the flow is suddenly changing direction while the game is running? With a navmesh, you can create dynamic flowmaps.
To make this work you should connect the vertices of each triangle in the navmesh, and then run a flowfield algorithm to find the shortest path from each node to the destination in the triangle you want to reach. As said before, you can use the line-of-sight algorithm to detect if a node can see the goal position. Each node will now get a direction and this direction is used to set the vertex color of the mesh. You can access this vertex color in a shader and thus get the flow direction. Moving the texture in the direction of the flow is kinda tricky and this is a good article on the subject.
This is the dynamic flowmap that determines the direction of flow:
...and then you can simulate something like smoke on the navmesh:
...or water:
Read more
This was just a short introduction, so if you want to learn more about navmeshes, you should read:
- Inner Workings of the Navigation System
- "Simplified 3D Movement and Pathfinding Using Navigation Meshes" - which is a very good article found in the book "Game Programming Gems"
// few days ago I learnt A* for grid_based_movement
ReplyDeletethan i found that A* is very efficient that it can be used for any kind of graph
when I saw unity`s navmesh and I searches how it can be done
I got steps at
https://gamedev.stackexchange.com/questions/38721/how-can-i-generate-a-navigation-mesh-for-a-tile-grid
But for delaury triangulation I found nothing I am glad i finally found your amazing tutorial Thank's for making it