A very fast Collider-based AI Navigation system written in C# for Unity3D for both small maps and open worlds.
Description
Super Pathfinding System is an extremely lightweight tools that can calculate paths between two positions, in almost any possible 3D scenario with just a few lines of code.
You can use paths for many different purposes, like moving characters, animals and vehicles in different environments, from houses with a lot of rooms, to large open world maps.
Script works using Physics Raycasts and colliders detection to explore the world and find the best path.
There is basically no limitation about what this pathfinding system can do, it's only a matter of configuration. Code is well documented, commented and easy to read. All code can be edited but cannot be shared neither for free or for commercial purposes without any consent from Corvostudio.
Package also contains more useful stuff, like a demo scene and a working example AI that with a few lines of code can calculate and move across paths using Pathfinding System's API. However it's suggested to write your AI from scratch, or implement API into your custom AI.
To implement this system Simply add SuperPathfinding component to the unit you'd like to move.
You will able to calculate and manage path from API's like FindPath(destination) method. After calculation is completed, generated paths (PathData) can be accessed with GetLastCalculatedPath() or assigning callbacks in FindPath() arguments.
A sample AI that also moves along paths using GoTo(position) and Stop() methods is included as example, to make this system as much plug and play as possible.
Quick tutorial
Speed and performance
Attributes customization
Pathfinder Options
Node Width: Witdh of a node. Can be considered as "step distance". This should be similar to unit width. A smaller value increase precision, but will need more nodes to have longer paths.
Unit Radius: Radius of the pathfinder. When highQualityObstaclesCheck, is used to check if units fits inside small closed spaces.
Unit Height: Height of the pathfinder. Path will avoid taller spaces.
Unit Climb Angle: Max climb angle for the pathfinder. Path will avoid areas where slope is higher then this value.
Unit Step Height: Max step height for the pathfinder. Path will avoid or go around obstacles higher then this value.
Scan Height: Height of the scan area. This should have the same height of the standard navigable building in your map. An higher value may reduce performance. If your pathfider have to navigate toward the top of a mountain, it's better to recalculate path multiple times instead of having one big path that can go as high as the mountain is.
Scanned Layer Masks: Mask for the calculation. Path will be calculated on colliders that match one of the selected layers.
Allow Diagonals: Allow diagonal movements. This will affect performance by 1.2 to 1.6x.
Path Start Position: Position where path calculation should start from. If set to none, it will use position of the transform of the object itself. Usefull if you want to have one PathFinding component to calculate path for multiple units.
Performance Options
Processing Speed: During runtime, affects max number of cycles per frame. On low-end devices you should use "low" or "very low". Script is very optimized anyway, and in most cases paths are computed in so few cycles that you will not see any difference. To take a deeper look on this, try calculating complex paths at RUNTIME with different speed values. You can do that just from the inspector.
Grid Nodes Limit: Max number of calculated nodes. WARNING: This doesn't refear to final path nodes, but consider also nodes calculated while trying to find the path. You will always want a maximum number of calculable nodes: Script sometimes cannot understeand if he already found the best path (or example if destination isn't on the ground), so after some times it must stop and assume that calculated path is already best path. If you have some tricky environment, you could raise it to increment chanche to get best path. If you have some simple environments it's suggested to have a low number and calculate the path multiple times while pathfinder reaches his destination.
High Quality Obstacle Check: If true, algorithm will take deeper considerations about where pathfinder can and cannot fit, based on his radius.
Debug Options
Test Path Destination: Assign this with a custom Transform to make some tests even while not in runtime. You can use assigned Transform's position to calculate some paths with dedicated buttons on component's inspector.
Test path and grid calculation [BTN]: [Test Path Destionation assigned is required] Generate and show a path and every calculated node from the start position to the test destination. You will be able to see how the algorithm perform and get a Debug Log of the calculation costs. It's recomended to try this feature at RUNTIME to test required processing time.
Test path calculation only [BTN]: [Test Path Destionation assigned is required] Generate and show a path from the start position to the test destination. You will be able to see how the algorithm perform and get a Debug Log of the calculation costs. It's recomended to try this feature at RUNTIME to test required processing time.
Test grid calculation (no test destination needed) [BTN]: Generate and show a path and every calculated node from the start position to a random position nearby. This feature is usefull to make multiple quick tests. It's recomended to try this feature at RUNTIME to test required processing time.
Clear all [BTN]: Clear data path and stop all in processing calculations on the component.
Frequently Asked Questions
"How does this work?"
Simply add SuperPathfinding component to the unit you'd like to move and you will able to calculate and manage path from API's like FindPath(destination) method.
A sample AI that also moves along paths using GoTo(position) and Stop() methods is included as example, to make this system as much plug and play as possible.
Super Pathfinding System uses a "dynamic grid system" where a virtual non-squared grid is created in many cycles scanning and raycasting nearby environment. Once that calculated grid is connecting the start point and the destination, an A* algorithm proceed to find the best path. Algorithm will find a path and represent it as Vector3 array of waypoints inside a PathNode object. You can manipulate found path getting node by node from start position to destination and discarding them while navigating path. An example AI is included, so set up should be quite easy.
"What do you mean by cycle?"
During calculation many Raycasts will be called - once for "cycle". Every cycle scans a "grid node", so "max cycles" is equals to "max grid nodes" and "Raycasts quantity". Raycasts aren't usually expansive actions, but if called many times in a single frame can really broke performance. Super Pathfinding Algorithm allow user to decide how many cycles scripts can make in a single frame, and maximum amount of cycles during a calculation.
Usually a medium-budget computer should be able to handle multiple pathfinders calculating paths up to 600 cycles with a medium processing speed giving satisfying results without any frame rate drop.
You don't need to reach target in only one calculation, but you should split travel in multiple paths when possible.
"So every calculation has a fixed amount of cycles?"
This is quite important: If the passed destination is places on a walkable collider, script should able to recognize if best path can be reached without making all selected cycles. Sometimes path can be calculated within less then 100 cycles, but this really depends on 3D world complexity and situation. If you want to make sure that destination is placed on a walkable area, there are functions to adjust destination before starting the calculation.
"How much time does this system need to calculate a path?"
You can calculate it by yourself: the formula is Needed Frames = gridNodesLimit / processingSpeed (you can see processing speed values in Scripting API session). Usually just a few frames are enough to calculate a quite good path (often even no time is needed), but increasing scan and path quality will increase needed time. I don't think there are many scenarios where this algorithm will need to have a setup that takes more then half second, but if you have some questions about your particular situation, you can always send me a mail.
Remember that you can test calculation time only during runtime (both from API and inspector's GUI), while when editor is not in runtime it will always calculate path instantly.
"How can I optimize integration?"
The Sample AI that comes with script is a good example about how to efficiently use those API's. Anyway implementation pattern can be something like:
When a destination is available, calculate a path and start moving along it. Path's shouldn't be too long if destination is very far, because you can always subdivide the trip in multiple paths. Every time path limit has been reached, or maybe also when too much time has passed, if the destination hasn't been reached yet AI should recalulcate a new path.
If you want to target low end devices but still have a lot of AI's I suggest also to call FindPath only on a limited number of AI's at the same time, maybe implementing a queue.
