|
A* Pathfinding Project
3.1.4
The A* Pathfinding Project for Unity 3D
|
|
A* Pathfinding Project
3.1.4
The A* Pathfinding Project for Unity 3D
|
There are several different graph types included in the project, and there is the availability to create 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. It generates nodes in a grid pattern width*depth.
It works great for most scenes and is especially good when runtime changing of the graph is needed (such as in an RTS or Tower Defence game).
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 does not support graph updating using GraphUpdateObjects (yet, working on it) 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 
