|
A* Pathfinding Project
4.0.9
The A* Pathfinding Project for Unity 3D
|
|
A* Pathfinding Project
4.0.9
The A* Pathfinding Project for Unity 3D
|
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.
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.
The grid graph can also be used as a hexagon graph if configured to use six neighbours per node instead of eight or four. If you want to see an example you can take a look at the example scene called 'Example14_TurnBased_Hexagon'.
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 favourite 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.
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 two previous 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.
The Recast Graph type is by far the most advanced graph generator in this system. It is based on Recast, an open source navmesh and navigation system in C++ which I have translated a part of to C# to run it natively in Unity.
The recast graph generator will voxelize the world (sort of rasterize it to a lot of cubes) 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.
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 is a bit limited in some aspects, it only supports 4 neighbours and not 8 and uses a bit more memory than a grid graph. But it works great when you need a grid graph for overlapping areas.
1.8.2 
