version beta 4.3.84
with RVO
Like the picture below, both of them are stop moving
Hi
Are you using any other components than AIPath + RVOController?
Seeker + AIPath + RVOController, and Behavior Tree which does not affect the movement stuff.
I take a new picture which should be more useful, the situation only occur when two AIPath meet each other in a narrow path. The red area is non walkable.
And this is more complex situation which does not occur very frequently, the red is non walkable, the blue is non movable RVO agent. the green who wants to move to his destination but could not pass the gap between the blue thus the green just get stuck at this position (though there in fact has a path which could leads the green to his destination but the shortest path he calculated is A => B instead of C => A => B)
Hi,
Has RVO changed since 4.3.84? I’m going to try the newest version of A*.
Yes actually- 5.0 shipped with updates to local avoidance- you can read about them here: A* Pathfinding Project 5.0 – Arongranberg.com
In the second scenario, where the green circle moves from A to B, the AIPath gets stuck at its current position. Is this a bug in A* or a limitation of ORCA? Can the latest version handle this situation?
It’s a limitation, but whether it’s within the algorithm, the scope of implementation, etc, that’s more of a question for Aron.
I just tried it and this specific situation is pretty tricky still.
@tealtxgr
From what I’ve read in the ORCA PDF, an agent moves backward only when it collides with others. If no collision occurs, it does not move backward. In extreme cases, when an agent is externally tangent to another, it moves left or right at a 90-degree angle.
if non-moving agents block its front path and side path both, the agent cannot navigate around them by ORCA. Instead, I thing the pathfinding system is responsible for finding a way around these obstacles. Is there an option to enable pathfinding to consider neighboring agents?
I think your best bet here is using penalties on the area underneath your stopped agents to discourage pathfinding from running through them. This is pretty dependent on your needs though, so there isn’t a “silver bullet” for what you’re asking. It’s certainly possible though.
I think it is not easy to do so with a NavMesh graph, but for a grid graph, it is possible. In games like Warcraft 3 or Age of Empires 2, the unit path system takes the other units into consideration when doing pathfinding. Do you know how these games do it?
Based on how units move in AOE2 (my beloved <3) I’d actually imagine their all just on an isometric grid graph rather than a Recast-like graph. The way units will happily zigzag around things kinda leads me to that rationale. So with a grid graph penalties would work pretty well. You can also tag areas to be straight up unwalkable too.
I need A* to provide an API that allows pathfinding while considering neighboring units, without requiring manual penalty adjustments for nodes.
Also, EA has released a lot of source code, including Red Alert and Generals: Zero Hour. Are you interested in reading them? Some of the implementations seem to take neighboring units into account for pathfinding and movement.
It’s a fine suggestion, imo- right now you either have something like penalities on one side of the extreme, and then you have local avoidance which isn’t really “pathfinding” in general, so something inbetween makes for a great idea. I’d recommend making a specific post in the “feature suggestions” category for it.
I saw this was released and I’m extremely stoked about it as a precedent, but I probably won’t be diving much into them myself outside of cursory glances.