2D pathfinding collision avoidance (with walls and obstacles)

[fry-]

It would be nice to have some collision avoidance for a moving unit on a navigation polygon, so it won't collide with edges that it has to pass by or obstacles that stand in its paths way.
For avoiding collision with the edges of the nav-polygon, it would be nice if the engine would apply some invert offset to the navigation polygon to shrink it down accordingly to the X * Y shape of the current unit. For a reference on how the polygon should be shrinked, here is a link:
http://stackoverflow.com/questions/1109536/an-algorithm-for-inflating-deflating-offsetting-buffering-polygons
This would allow perfect movement of units that have different dimensions (X * Y) without colliding at walls/edges. Also, if the polygon gets shrunk, paths that are too small to pass would be automatically collapsed and removed from consideration.

Avoidance of collision with other units / objects that are currently standing still or collide with the moving unit would be nice to have too. An idea would be to check the current path segment the unit is moving at, if this segment is intersecting with an idling unit/object and if so, find an alternative path for this segment.
Some considerations and further readings about this collision avoidance with other units can be found in this link under the "Notes on implementation" section at "1. Other Units (collision avoidance)" subsection: http://www.policyalmanac.org/games/aStarTutorial.htm

Sadly I'm too noob to directly help with code I guess, but I would still like to help as much as I can with testing or anything else if this gets implemented.
Thanks in advance!

[SuperUserNameMan]

+10
I started to try to implement an algorithm for collision avoidance in gdscript a month ago, but it was not a good idea ... so I gave up.

Then I asked to @reduz on IRC if it was feasible to implement path calculation directly using data into the physics server. I forgot the details of his answer (little brain that i am), but I noted into my TODO list that he pointed me to "Detour" from https://github.com/memononen/recastnavigation and that he said it should not be too difficult to integrate. (I also remember he said he was interested in it, but that he preferred to implement his own algorithms because of the API).

[fry-]

@SuperUserNameMan Yes I joined a short talk about this topic on IRC with @reduz lately too. We didn't talked about the details, but he also said it is possible and shouldn't be too hard to achieve. He also said that he could implement it, and thats why I thought I'll make a feature request here so it might get implemented someday 😸

[bojidar-bg]

+50

[reduz]

shrinking the polygon is ok, but you have to do it for every unit of every
different size and this is pretty costly. Most games just create a navmesh
that is thinner than the area you are planning to go by.
To do it automatically, Navigation should create many versions of the
polygons and cache them.

Local obstacle avoidance is a different thing, this will be eventually be
implemented, together with off-mesh links.

On Tue, May 12, 2015 at 10:59 AM, Johannes Danneker <
[email protected]> wrote:

@SuperUserNameMan https://github.com/SuperUserNameMan Yes I joined a
short talk about this topic on IRC with @reduz https://github.com/reduz
lately too. We didn't talked about the details, but he also said it is
possible and shouldn't be too hard to achieve. He also said that he could
implement it, and thats why I thought I'll make a feature request here so
it might get implemented someday [image: 😸]

—
Reply to this email directly or view it on GitHub
#1887 (comment).

[fry-]

Another idea about the "shrinked polygon" thing: would it be possible to implement some "navmesh layer" on which you can assign the different unit-nodes? With this, you could make different sized polygons by hand, assign different layer values to them and depending on how big your unit is you can let it walk on that layer you prepared.
The problem with only one navmesh in my opinion is, that you can make this shrinking by hand only for the smallest unit, so it will be able to explore every walkable area. but this will cause constant collision for bigger units...
Also these different navigation polygon layers would allow to make different kind of terrain for different units. Like one layer for ground units and another layer for water- / sea-units.
What do you think, would this be possible? 😛 😀

[benbot]

Has anyone started working on this? I could take a crack at it.

[akien-mga]

@thecodethinker Not that I know of, you'd be very welcome to give it a go :)

[reduz]

will most likely work myself in 2.1, need to do more research

On Wed, Feb 3, 2016 at 3:45 AM, Rémi Verschelde [email protected]
wrote:

@thecodethinker https://github.com/thecodethinker Not that I know of,
you'd be very welcome to give it a go :)

—
Reply to this email directly or view it on GitHub
#1887 (comment).

[fry-]

maybe there is a way to not shrink the polygon, but instead move the center point of the moving object / unit from which the path gets calculated relative to that object / unit? Is that understandable? 😀

[neikeq]

It's too late to work on this for 2.1. What could be a good target milestone? (if planned)

[akien-mga]

Related (but from what I understand different in its scope) to #3821.

[akien-mga]

Let's try 2.2 for the milestone and aim at discussing this further with @reduz :)

[Zylann]

Just bumped again into this too. I ended up making the polygon myself (tedious), as my levels aren't only made of tiles.
Situations I've run into:

Even after shrinking down AI movement shape into a sphere it still gets stuck:

I could increase the margin even more but I fear the AI won't find the player if he sneaks inside the margin.
Edit: ok that might also be because my AI center is offset from its feet, so I can fix that in my game, though the original issue is still relevant

[akien-mga]

Moving to the next milestone as 3.1 is now feature frozen.

[supagu]

I'm not sure how this is being implemented, but it would be good to have something like:

Navigation.get_simple_path ( Vector3 start, Vector3 end, float radius, bool optimize=true )

so the addition of a radius to handle different sized characters.

[mitchcurtis]

+1. This is something that is sorely needed for navigation.

Local obstacle avoidance is a different thing, this will be eventually be
implemented, together with off-mesh links.

Can you share any timeframe for the local obstacle avoidance? :D

[TheMikirog]

Years later and the lack of Collission Avoidance still annoy me to no end.
It can take months to implement your own version, which is buggy most of the time. Either program it yourself or just give up on tile/grid mapping entirely and I hate that with a passion.

[Xrayez]

Note: shrinking polygons is available since #28987:

var polygons = Geometry.offset_polygon(polygon, -10) # negative shrink

The implementation should be fast because it uses Clipper library internally, with join type set to JOIN_SQUARE or JOIN_MITER (JOIN_ROUND is slower).

[Regnaris]

For a tile based maps, where actors fits in one tile and map doesn't have bottlenecks where actor cannot get through, I found this solution:

• Get path with get_simple_path with optimize = false.
• Optimize path yourself using script, with help of cast_motion() from direct_space_state, where shape is a shape of an actor.

Using this method you can make actor not to cut corners, like zero-size point. There still some overlapping left, but i think it will fit until we have a better options.

[ElfEars]

Considering we've got clipper, you could always use it's boolean functions to difference out object hitbox shapes simulating object avoidance. Not sure how inefficient it is though so it could be hideous. (If you only did it once per update and used a globally referenced navigationpolygon it would probably be OK though.)

[Calinou]

This was implemented by #34776, closing.

[d-bucur]

@Calinou How does #34776 solve this? The collision avoidance only works with dynamic obstacles, but for static obstacles the path generation still skims the corners, as described here https://godotengine.org/qa/23519/navigation-using-tiles-pathfinding-issue-corners-navmesh

This still seems very relevant in Godot4 beta3 using tilemaps
Edit: Found another open issue for this so probably don't need to reopen this one #60546