Sign in to follow this  
Crayz92

Local avoidance/steering vs. stationary agents

Recommended Posts

I'm having a difficult time coming up with a local avoidance strategy for my agents.  My problem is pathing/steering around stationary units in a semi-intelligent manner.  I've recorded a quick demonstration of the problem here: https://vid.me/5VvF4

And here's a demonstration of ideal behavior: https://vid.me/LTuHi

The movement of units is pretty smooth and directed, so it would suggest they perform some sort of path planning rather than steering.  Steering also seems to be documented mostly for groups/non stationary agents.  I know that Dota 2 uses a square grid to perform pathfinding, but the movement of these units is precise and not aligned to the grid, so there much be some other algorithm that takes into consideration nearby units and constructs a simple path to reach the destination.  I'm having a hard time figuring out how this could be done.

Things I have tried:

1. Flagging nodes on my square grid as Occupied - during pathfinding search occupied nodes are treated as unwalkable.  works, but it's a headache trying to get agents to move smoothly and introduces a handful of other problems, i.e. targeting a unit that is completely surrounded, keeping agents aligned to the grid

2. I tried adapting the bug algorithm in a way that works with agents as obstacles.  While an agent is moving along its path and colliding with another agent, it scans neighbor nodes for walkable space, inserts the best neighbor node to its path, and moves towards the new node before continuing to move towards the goal.  Sort of works, but it causes agents to move back and forth quite a bit as they progress towards the goal again only to find that there's another collision in the way.  There are also some cases where the agent gets trapped because it fails to backtrack or work around maze like situations.

3. Steering.  As seen in the first demonstration video, steering has some limitations that I don't know how to work around.  I've thought about treating groups of stationary units as one single obstacle and implementing obstacle avoidance steering vs polygons, but I'm not sure how to go about that, or if it will end up being optimal and/or efficient, and forming proper polygons seems like a daunting task when my agents have a variable radius.

4. Local proximity pathfinding search - find points around all nearby agents and perform a search against those points.  I haven't implemented or tested this idea yet, it doesn't sound much better than using the map's actual pathfinding grid with Occupied (unwalkable) nodes marked where agents are standing.

 

Is there a standard solution?  Maybe it's a trivial matter and my overthinking/stress is causing me to see past an easy solution.

Share this post


Link to post
Share on other sites
8 hours ago, ApochPiQ said:

Steering should be able to trivially handle static obstacles. What forces are you applying?

Seek, separation, and neighbor avoidance.  The agent gets stuck when its path runs between 2 obstacles which are perpendicular to the path and distance between the 2 obstacles is less than the agent's radius.  The agent ends up in an endless loop bouncing between the 2 obstacles rather than steering around them intelligently.  The problem scales when there are even more agents/obstacles placed in such a manner

Share this post


Link to post
Share on other sites

What are your weights and effective distances for each of those? Increasing avoidance slightly might push the agent around the combined force of the 2 obstacles.

Also, that is exactly the problem with a steering only solution, however. This is very similar to the "cul-de-sac" problem, in fact. The go-to solution to get out of stuff like that is pathfinding (e.g. A*). Also, you don't have to align movement to the grid if a straight line exists to a waypoint further down the path.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this