Hello, I’ve been looking into A* as a replacement for Unity’s Navmesh system and A* looks pretty good, but I do have some questions on a few of the features:
RVO:
-I saw that on your docs page, you state the Obstacles are not working with RVO at the moment. Does this mean that objects with an RVO component can only avoid each other and nothing else (I may not understand how you define “obstacle”)?
Navmesh:
-Have you ever tested / seen how navmesh cutting performs on any mobile devices?
RVO and Navmesh:
-Do you know if there is a major performance difference between using navmesh cutting for agents to avoid each other vs using RVO to do the same?
Any response is appreciated, thank you for reading.
Update:
Here is essentially what I’m trying to see if A* can currently replace (where Unity (Free) NAV Mesh system plots a route to a destination point, but is unable to go around another agent and will not re-calculate its path (since the other agent is not calculated on the navmesh and becomes stuck until the blocking agent moves away):
That is why I was asking about Navmesh cutting (and of course I don’t fully understand how your system “re-calculates” paths/routes based on blockages).
Try the beta, it has support for rvo obstacles. They are mostly obstacles, they don’t really avoid them much. Pathfinding is supposed to take care of that. But it makes sure that they don’t move outside the navmesh.
I haven’t tested navmesh cutting on mobile devices. It is a bit heavy, but I think it should work fine if you use a reasonably small number of them. Use pretty small tiles on the recast graph since that will make sure it only has to update a smaller area each time.
You cannot use navmesh cutting to avoid other agents. If an agent had a navmesh cut, it would cut away the navmesh below it, then the agent would think that it was not on the navmesh and would get really confused and move/teleport to the closest point on the navmesh.
Anyway, RVO would be vastly more performant even if it was possible, it can handle thousands of agents (not on mobile though :p, and the rendering of them would probably kill your frame rate anyway).
Thank you for the response, having read it I made an update to the original post with more details on the issue I’m hoping A* can handle that Unity Free cannot.
and of course I don't fully understand how your system "re-calculates" paths/routes based on blockages
A common misconception is that local avoidance causes different paths to be calculated. It doesn't. It only adjusts the velocities of the agents to move them around each other, but they don't recalculate the paths.
Sorry, the Unity local avoidance algorithm and the one used in this project are roughly the same, so anything that it cannot do, this system will likely not be able to do either.
What you can do is that you detect if an agent is stationary (blocking) and then enable a NavmeshCut on it. Since it does not need to recompute the path while stationary (you will need to make sure path searching is disabled while stationary), it is fine to add a navmesh cut. This will enable other agents to recalculate a path around it. The downside is that if the blocking agent completely blocked the path to the target, other agents trying to get there will think there is absolutely no way to get to their destination.
Yeah, I’ve got some issues to work through:
-) Having multiple agents that use the Navmesh but can also block each other.
-) The dangers of cutting the Navmesh under a agent that was stationary but decided to move while the cut was still in place.
-) Agents that are still in motion while blocking each other.
Have you ever tried/seen something logic like (wondering if it would do any good):
-Calculate my path from my location to my destination.
-Periodically check the next path segment in front of the agent (Linecast/Raycast each segment to see if something is blocking it).
->IF something is blocking a segment, calculate the remainder of the path from the last good segment (or just current agent position if the two are close). Essentially forcing a different Node order, then checking new Node endpoint with another Linecast/Raycast (and accepting it if there is no blockage, but rejecting it if there is one).
Not sure if that can be done, but I did see some sort of “path randomization” in a tutorial video on your A* system. For that matter, can you access Nodes like that? In a way that says, “I don’t care what your normal logic says, start from the node that I choose ?” Essentially invalidating a path endpoint and forcing the system to choose a different one that satisfies your logic?
Example:
0) Linecast determines something is blocking the current path segment
Path is re-calculated from current position trying the “next best node” each time (which is verified by a another Linecast). If the line cast shows everything is okay, go to step 2.
Continue to plot the path as normal (and now let the periodic Linecast determine if the steps need to be repeated).
Out of curiosity, do commercial games actually re-calculate paths based on blockages? Or do they also more/less have a “try to go around” type of logic that you know of?
Thank you again for the support, I really do appreciate it.
For navmesh graphs, this is pretty tricky, I am not sure how to solve it in a good way.
Commercial games usually don’t recalculate the paths, they use some local avoidance. The exception is very grid focused games where it is sometimes possible to calculate routes around other agents (those approaches usually have a number of limitations of where they can be applied however).
Take a look at SC2, they use pushing/queuing, planetary annihilation use some kind of force based/pushing based approach I think. Command and Conquer 3 does some kind of path replanning for when paths are blocked by stationary agents I think, but I have not looked in to it that much.
