A* Pathfinding Project

Support for Raycast Command


It would be great if the Layered Grid Graph used RayCastCommand API, I think that it would help reduce main thread overhead significantly when scanning and updating.
I may implement it myself when I find the time.


I have done some experiments with this (and the burst compiler) recently. It seems to work quite well.
It’s annoying that Unity hasn’t got a batch version of Physics.CheckCapsule and Physics.CheckSphere yet though.


Just wanted to let you know that beta 4.3 (see https://www.arongranberg.com/astar/download) contains WIP code for scanning the grid graph (not layered grid graph though) with the burst compiler.
Unfortunately it seems to be bottlenecked by allocating the node instances as well as calling Physics.CheckCapsule for each node. Physics.CheckCapsule can currently not be jobified in Unity.


I am also looking at what it would take to add support for the raycastOffset to point graphs. It seems like the RaycastModifier supports it but the PointGraph doesn’t support the RaycastModifier (or I misunderstood something). Even if I put my walkable waypoints a little bit above ground, the direct raycasts occasionally clip the edge of stairs and other walkable elements.


It’s a reasonable suggestion. Would you mind creating a new thread in the Feature Requests category for this?


Can the node instances use a custom block allocator or something along those lines?
I would be more than happy to use whatever was supported rather than capsules.
I assume that you mean to determine if the path is blocked at each hit along the ray? For the most part I can just emulate with a ray or two.

Thanks for looking into this!


I should mention that what we really want is to get as much work off the main thread as possible. We are still not even close to fully utilizing all cores and Scans (at start and on change) cause noticeable stalls on the main thread.
I don’t care if they take seconds to complete using burst or traditional threads or whatever, just as long as they don’t stall the main thread for an extended period of time.
Our map geometry consists primarily of boxColliders. I was thinking that we could create an alternate thread safe representation of our colliders and then do custom raycasts off the main thread. Do you know of anything other than the raycasts which requires the main thread in the graph scanning?





Beta version 4.3.5 which I just uploaded (https://www.arongranberg.com/astar/download) now has even better support for burst for grid graphs (not layered grid graphs yet). It is faster and in particular the Ray collision checking mode is much faster since it can be fully jobified. I have also improved the handling of async scanning so I can now scan a grid graph asynchronously without dropping below 30 fps.

Unfortunately not. They are however now allocated in a separate thread, which helps a lot. Interestingly enough it seems like C# has some sort of locking going on during allocations, because trying to use multiple threads to allocate them just makes things slower.