Graph Types
Brief overview of the different graph types.
There are several different graph types included in the project, and you can even write your own.
In this document I will shortly explain the different graph types and their settings.
Grid Graph
The Grid Graph is the most straight forward graph. As the name implies it generates nodes in a grid pattern.
It works great for most scenes and is especially good when you need to update the graph during runtime (such as in an RTS or a Tower Defence game).
It is not particularly good from a performance and memory point of view at handling large worlds with large open spaces however as it represents all regions with the same node density regardless of if they need that detail or not.
Pros:
Grid graphs work well with penalties and tags.
Graph updates are fast.
Scanning the graph is comparatively fast.
Cons:
Memory usage is higher than a recast graph.
Pathfinding over long distances can get much slower than on a recast graph.
It doesn't scale to very large worlds.
Hexagonal Grid Graph
You can create a hexagonal graph by creating a grid graph and changing the Shape option in the grid graph inspector to Hexagonal. All the same pros and cons as for a normal grid graph applies.
If you want to see an example you can take a look at the example scene called 'Example14_TurnBased_Hexagon'.
Layered Grid Graph - A* Pro Only
The GridGraph is great, but sometimes the world contains overlapping areas, such as a house with multiple floors. The GridGraph cannot handle that in a good way. So here's a grid graph which supports overlapping areas. It uses a bit more memory compared to a normal grid graph, but otherwise it works the same.
Recast Graph - A* Pro Only
The Recast Graph generates a triangle navmesh instead of a grid. It is based on Recast, an open source navmesh and navigation system in C++ which has been translated and modified to run natively in Unity.
The recast graph generator will voxelize the world (sort of rasterize it to a lot of cubes, like a high resolution Minecraft world) and then build a navigation mesh of it which can be used similar to the Navmesh Graph. It can generate a stable mesh in seconds, what could take hours using manual mesh building. If you have been using Unity's navigation system before, this graph should seem familiar to you, as it is based on the same principles.
If you prefer to manually create a navmesh in a 3D modelling program, you can use the Navmesh Graph.
Pros:
Can represent small details and large areas at the same time.
Pathfinding is fast due to the low node count.
Supports large worlds.
Pretty fast updates using Navmesh Cutting (limited to mostly cutting out holes in the navmesh).
Comparatively low memory usage.
Cons:
Can be slow to scan, especially if you need very high detail or very large worlds.
Slower to update than a grid graph (but navmesh cutting is faster if you can use it).
Large undulating empty regions, like a hill without any trees or obstacles, can be hard for the recast graph to represent well. Though, enabling tiling can help break up the large nodes.
Recast graphs are bad at representing tags and penalties.
Navmesh Graph
The Navmesh Graph is the other main graph type. This graph expresses the pathfinding data as a triangle mesh instead of squares (Grid Graph) or point (Point Graph).
This is perfect for smooth and fast pathfinding where the graph doesn't need much changing during runtime.
It is often faster than a grid graph since it usually contains fewer nodes and thus requires less searching.
The paths returned from it can be used directly, but the funnel modifier is strongly recommended.
The system can generate navmeshes automatically (see Recast Graph - A* Pro Only), but with this graph you will have to create them yourself in your favorite 3D modelling application.
A navmesh should be a mesh where the polygons describe the walkable area, vertices should always (except possibly in some special cases) lie at the edges of the mesh, not in the middle of it (i.e a vertex with polygons surrounding it).
It can also be good to split very long edges because similarly sized polygons yield better paths than really big and really small polygons next to each other.
Pros:
Can represent small details and large areas at the same time.
Pathfinding is fast due to the low node count.
Supports large worlds.
Pretty fast updates using Navmesh Cutting (limited to mostly cutting out holes in the navmesh).
Comparatively low memory usage.
Fast to scan.
Cons:
Requires a lot of manual work to create the navmesh (or you have to write a script to do it automatically).
Navmesh graphs are bad at representing tags and penalties.
Point Graph
The PointGraph is the simplest of all graph types, but allows for a lot of customization, it consists of a bunch of user placed points which are linked together. A point graph is scanned by taking a root Transform, and treating every child of it as a node. It then checks the connections between the nodes using raycasts to see if they should be linked together.
To get good, smooth paths from a point graph might be hard as they only define a point of walkability, not an area like the other graph types. The raycast modifier does a quite good job, though.
A problem is that when getting the closest nodes for a path request, the closest node might be a node on the other side of a wall, so make sure you don't place your nodes too sparse.
Using this graph type is discouraged unless the other graph types just don't work for your game.
Pros:
You are in full control over where nodes are placed. You can even make 3D pathfinding with this.
Fast to scan for simple cases, but can get very slow if you are not careful with your settings.
Cons:
Requires a lot of manual work to place all the nodes (or you have to write a script to do it automatically).
It's hard to get good quality paths without a very large number of nodes.
Pathfinding is often slow due to the high node count that is required.
Relatively slow graph updates.