I'm pleased to announce that PathFinder has been given a major overhaul and is now live on AssetStore. Following is the update:
- Added a new graph type which is more memory and performance friendly
- Added binary heap based sorting to the search algorithm, make the search faster
- Path-smoothing has been reworked entirely
- Reorganise structure of the code
- All Example scripts has been rewritten
- C# counter part of the source and examples are now included
With the addition of the new graph and binary heap based sorting, it goes without saying that the new code is a lot more faster. Well, just have a look at this video, I think it shows more than I can possibly say.
The scene shown is setup with a square grid with grid size of 0.5 over an
area of 100x100. Effectively 40k nodes. The grid is then optimised and
clustered into smaller area based node for more efficient search
algorithm. In older code, search a path from end to end with such node resolution would take easily take up to 0.1second or longer. With the new code, well as you probably can see, the queue time for the search is hardly noticeable even with a handful of agent call for search every 0.1seconds. This is largely thanks to the new adaptive node that I used. The adaptive node clusters together an area of smaller node into one. This reduce the total node needed across the whole scene. And since the new node cover a bigger area, the search would involve much less node as each adaptive node would cover much more ground than the evenly distributed grid node. The two images below would show the strong contrast between the two node types.
 |
| Adaptive Node, it takes much less of them to cover the area |
 |
| Typical grid node, there's thousands of them to cover the area |
Also the path-smoothing has been improved. The old algorithm has a tendency to cut through area which is suppose to be unwalkable. The new algorithm has eliminate this entirely. And it has a build in mean smoothing to make the corner more... smooth.
Having say that, the new PathFinder is by no mean perfect. There are a lot of places which can use more work. You can expect me to keep working on it. And I have to say, at this point, the path smoothing seems to be a lot more taxing on the performance than the search algorithm itself. I totally didn't expect that. I'm guessing the next logical step would be optimising the path smoothing.
Thanks Song - this is a great update.
ReplyDeleteHi,
ReplyDeleteI have a system that dynamically creates Vector3 values for all 8 corners of a large cube, thus creating 8 nodes. I will use the nodes as a route to a target object on the other side of the large cube.
Can I assign these custom nodes dynamically to PathFinder, and pass the shortest node route to the AI enemy, which uses it's own custom Physics movement script? The AI enemy already has a waypoint system set-up to receive Vector3 co-ordinates, and it is able to move in all three dimensions. All I need now is to work out the shortest route and I am hoping PathFinder can help with that.
I'm finding the prospect of pathfinding quite daunting, and would like to know if this is at least possible before I jump in feet first!
Thanks
Paul
Hi Paul,
ReplyDeleteOther than the typically grid-based or navmesh graph. You can use a simply line based graph, which is basically a series of randomly or manually placed node connect to each other subject to line of sight.
PathFinder does support that Line-graph. So you can assign the dynamic nodes your code has created to PathFinder and generate the graph based on it. It shouldn't take more than a few line of code. And from there on, you can call the search method on PathFinder to get the shortest path.
In short, yes PathFinder should be able help you to skip the path-finding all together.
Hope that helps.
Song
Just to make it clear, the graph generation bit is handled by PathFinder. You just need to assign the node.
ReplyDeleteThat sounds great. Is there any online documentation to look over to get an idea what is needed to be done?
ReplyDeleteActually never mind I just bought it! Will be working with it over the coming days and will review it after extensive use ;)
ReplyDeleteSorry for the delay. I've lost internet for the past 2 days.
ReplyDeletePlease contact me directly via email. I'll help you setup what you need. You will find my email in the pdf documentation included.
Hi! Just saw your PathFinder on Asset Store and I'm considering buying it; but I have a couple of questions about graph generation. First, how fast is it? Can it be generated at runtime? Re-generated dynamically?
ReplyDeleteCan I add/remove parts of node graph dynamically? I.e. my game dynamically loads (and unloads) small chunks of gameworld - will this work with PathFinder?
Also, what does PathFinder use to detect obstacles - scene geometry, colliders, something else? Can I generate a node graph without any scene objects whatsoever - i.e. I have some sort of in-memory representation of a game level - can PathFinder work with that?
Does PathFinder support dynamic obstacles in any way?
For path searching, it's relatively fast. However it's not designed for nav-grid generation for large area during runtime. The nav-grid generation is based on collider, also it doesnt support dynamic obstacle so I imagine it will not support most of the scenario you have in mind.
Delete