search

andriyDev / landmass

A navigation system for video games written in Rust.
Apache License 2.0
30 stars 2 forks source link

Add obstacles to local collision avoidance. #1

Closed andriyDev closed 1 year ago

andriyDev commented 1 year ago

Currently, agents can walk off the edge of the nav mesh to try to avoid each other. This is obviously undesirable. We can add dodgy::Obstacles to the local avoidance problem which correspond to the borders of the nav mesh. This will keep agents on the nav mesh.

andriyDev commented 1 year ago

Unfortunately, if we use the nav mesh borders as the obstacles, the characters can "hug" walls. The path simplification algorithm (SSFA) is trying to make the agent go to the edge of the nav mesh, but there is a wall there, so the agent can only ever get as close as its radius. This means until the agent gets colinear with the next waypoint, it will slide along the wall trying to get closer to its current waypoint. This can slow agents down quite a bit around corners.

There are two options here: 1) Expand the dodgy::Obstacles so that the walls only stop the agent's from walking off the nav mesh. 2) Modify the portals so that the SSFA never wants to get too close to the edge of the nav mesh.

Both options are quite tricky. 1) Expanding the obstacles can lead to some tricky situations (imagine a small hole in the nav mesh with a radius less than the agent). How robust should expansion be? 2) The nav mesh is no longer the area that the agent can be, but the area that the agent's disc is allowed to intersect with. Also how do we shrink the portals to actually prevent the "hugging" problem?

andriyDev commented 1 year ago

I wonder if we can somehow modify dodgy to do this for us? Perhaps just pushing the obstacles away from the agent by the correct amount can deal with this somehow?

andriyDev commented 1 year ago

Ok, I solved it! ...ish. Looking at Unity I saw they went with what looks like the 1. approach. I then realized, what if agents don't care about their own radius. Instead we can avoid obstacles with a radius of ~0, and the agent will get really close to the edges which should reduce the effect of "hugging". This totally worked!

So to be clear, I fixed this in commits e1c8d9ad66dab7d022068cfa5b36bc573386c068 and a0187c00d710b48807f472416d29c3966bba3047.