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.

TL;DR Which graph should I use?

To make a first assesement of which graph type is best for your game, you can use this flow-chart:

• ¹ What's a large world? It depends, but if you'd need a grid graph larger than 400x400 nodes, a recast graph is almost always a better choice.

• ² For a spherical world or other weird world shapes, see Spherical Worlds.

• ³ Side scrolling games unfortunately have little support in this package. But a point graph can work well for some games.

• ⁴ For an infinite world, take a look at A small moving graph.

Keep in mind that this is only a rough guide, you should read the rest of this page for more information about the pros and cons of each graph.

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 be 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 (convert 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 robust mesh in seconds, something which 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. In fact, Unity's system is also based on recast.

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.

• Fast updates using Navmesh Cutting (limited to mostly cutting out holes in the navmesh).

• Decently fast graph updates that recalculate whole recast graph tiles.

• 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 represents the pathfinding data as a triangle mesh instead of squares (Grid Graph) or points (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 is 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.

• 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 set 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 for possible connections between the nodes using raycasts to see if they should be linked together. Getting good and smooth paths from a point graph can be hard as they only define a point of walkability, not an area like the other graph types. The raycast modifier does a decent job, though.

A common issue with point graphs is that getting the "right" closest node can be hard without adding a lot of nodes. For example if an agent moves close to a wall, the closest node might be on the other side of a wall. You can mitigate this by ensuring that you don't place your nodes too sparsely.

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.

• Slow graph updates.