Detect whether RVO agent can reach destination

Hello,

I have been testing the RichAI and RVO Controller for a long time, and it is time for me to ask on the forum. I have added a screenshot that describes the issue below.

My recurring issue is that RVO agents will run forever into an obstacle or run around if the destination is not reachable. In the screenshot I have 4 RVO agents (zombies) that illustrates how it happens. I place my player character in a tight corner and 3 of the RVO agents navigate close to the player and lock their positions. At this point, there isn’t a way for the fourth agent to get near the player, and I need a way to detect when this happens.

I have experimented with various error-prone solutions which don’t solve the underlying problem, for example by detecting whether the agent’s velocity is approximately zero for a certain duration, whether the agent’s position is roughly the same for a certain duration, and by manually changing the density threshold. These can “work”, but are not satisfactory as the agent will regardless run straight into obstacles for a long time.

I appreciate any ideas on how I can detect whether the path to the target is not reachable - meaning that obstacles and locked RVO agents are blocking the path.

Note: Some more details:

  • The Pathfinder uses a Recast Graph.
  • The RVO agents have “Collides With”: Default Agent (they are default agents themselves) and Default Obstacle.

You could possibly do some hacky fix. Like changing the layer of the agents when close but then you will get overlapping.

Thanks for the suggestion, but I’m not sure how changing the agents’ layers can fix the issue? Do you mean to alter the layers the agents collide with? And yes, it’s not viable if it introduces overlapping.

I just get the impression that this could be a common issue and that there is a simple solution for it.

ai.rvoDensityBehavior.lastJobDensityResult()
try this

Thanks, but I’ve already tried it.

Here’s a screenshot from testing it just now:

The last three of the debugged values are:
reached = IAstarAI.reachedEndOfPath
rvoReached = RichAI.rvoDensityBehavior.reachedDestination
lastResult = RichAI.rvoDensityBehavior.lastJobDensityResult

All of these values are false, even for the one zombie that is closest to the player and blocks the other zombs.

Hm, one thing I’m wondering is whether density threshold only considers RVO agents and not obstacles taking up space around the target (in this case, the player)? Since density threshold works when standing in the open, but doesn’t work as intended when near a tight space surrounded by obstacles as shown on the screenshot above.

I’m trying to read some of the scripts, but I haven’t understood yet how the destination is being determined (AIPath & AIBase) and how density threshold is calculated (RVODestinationCrowdedBehavior).

Hi

This is indeed a somewhat common problem, but sadly I do not have a great solution for it at the moment. My current best solution is the rvo density behavior, but it has the downside (as you have already discovered) that it does not take obstacles into account. So while it works well on open spaces, it doesn’t work when the destination is close to a wall. I have been working the last few days on another solution which would (hopefully) solve that, but it has required me to make some quite extensive changes to the local avoidance system. That solution is based on checking if an agent is blocking by another agent which has effectively reached its destination (this is recursive, so an agent can be blocked by an agent which is blocked by an agent, …, which has reached the destination). Annoyingly, I also cannot find any reference material on how other games tackle this issue.

Thanks for your reply and explanation, Aron. I don’t think I can help in terms of coding at the moment, but I’ll try looking for some info about it.

There’s an interesting idea presented on this reddit thread: Need help with AI surrounding player

BawdyLotion mentioned how Assassin’s Creed manages crowd control by assigning a certain number of “slots” around the player. Then enemies will take up slots when they are near one of them. If it’s taken, it’ll go to another free slot. Then I suppose the challenge would be to determine when slots are made inaccessible by obstacles. If this system could be functional, the remaining thing could be for instance to:

  • Introduce reactions for the enemies in case all slots are unavailable (ex. stop).
  • Provide accessible variables for the individual devs that can be used to handle the behavior of the AIs further.

What do you think?

I’ll keep looking for other ideas.

Hi

Yes for combat that is definitely a decent solution. I’ve used it successfully in a previous game. You can use AstarPath.active.data.recastGraph.PointOnNavmesh to check if a given location is actually on the navmesh. See NavmeshBase - A* Pathfinding Project

I recommend making agents reserve spaces before they reach them, to avoid agents being confused when they all try to move towards the same space.

Hello again,

It’s been about a week and the brief answer is that I still haven’t figured it out. On the screenshot below, I just want to determine when the path to the target (player) is not possible. Here, the selected zombie, “Zombie_Male_02_CC2” is running endlessly into the obstacle while trying to reach a point next to the player, which is blocked off by the two zombies in front.

I first tried to implement a “slot” system (4 capsules around the player: front, back, left, right), but it had its flaws and bugs. For example, if the player rotates around and the zombie stands still, the initial slot would eventually be wrong as the zombie would be standing close to one of the other slots. Having the zombie turn around with the player to follow the invisible slot would look unatural. So I tried to update the slots whenever the player moved and turned, which was messy - ex. zombies moving around whenever the player did a slight turn.

I’ve looked a bit on this older thread: Local avoidance issues on Recast graphs

I haven’t tried adding penalties, as I don’t think that would solve the current issue, since the solution should be “no path” in this case.

I’ve experimented with NavMeshCut, but it seemed to introduce new bugs and lots of teleporting. While NavMeshCut did make holes in the recast navmesh, the pathfinding found “impossible” paths for the AIs: A path was always found for the zombie to the player, but the path would be extremely narrow so the agent was never able to traverse it.

There’s also the DynamicGridObstacle script, but I didn’t get it to work with the agents. Does it work with CharacterControllers?

I haven’t looked into the ITraversalProvider yet. Could this be used to solve the issue?