Need to occlude NavigationPolygon set in TileSet at runtime

[TotCac]

NavigationPolygon can be added to a Tileset to mark a tile to be used by Navigation2d to find a path.
While building your Tilemap, each tile have static data of navigation to be considered by pathfinding.

Problem: If you an extra layer of object that have to be avoided by Navigation2d pathfinding, how can you do?

Is it possible to have this improvment to 2d pathfinding?

[akien-mga]

I can confirm the need for something like this, unless I'm misusing Navigation2D.

In DynaDungeons, I had tried using Navigation2D (not committed) for pathfinding, but my problem is that I use two tilemaps:

• One for ground and wall tiles, which have NavigationPolygons to make them either allowed or not for pathfinding (e.g. wall is not allowed, ground is allowed).
• One for "obstacles" that can be destroyed and thus reveal the ground tile behind them. Typically they are not allowed for pathfinding, but the ground tile behind them is.

With the implementation I had tried, the "allowed" status of the ground tile would take precedence over the "not allowed" status of the obstacle, thus pathfinding would ignore all obstacles.

[jackmakesthings]

Yesss. This would be an extremely good thing to have, I've been wrestling with the same problem @akien-mga described above.

[ProbDenis]

Yes, having some kind of "NavigationOccluder" object would be extremely useful.

[Anarchid]

Having a way to punch holes into navmeshes would be prim, too :P

[Zylann]

I have the same issue as akien-mga, and I can even have non-tile objects on top of it, that need to be avoided as well. Actually, in some cases it would be easier to build navigation only with occluders instead of nav. polys.

[akien-mga]

Given how popular this issue is, I'll make sure it's fixed sometime before 2.1 is released :)

[PixelWizzard]

That would be great!

[genete]

I also need that for my games.
Currently the Navigation2D only takes in consideration the first NavigationPolygon found in the children list. If I have two NavigationPolygon as children and change the position of them, then the Navigation2D consider the first of its children.
It would be great to have this:

1. Change Navigation2D to consider all the NavigationPolygon children's the result of a boolean combination of all them.
2. Add one new parameter to the NavigationPolygon to make one boolean operation with the next NavigationPolygon in the children list
3. Add one new parameter to the NavigationPolygon node to enable or disable its effect.
4. As said, new navigation occluder. I imagine this would be a bit difficult to implement if the occluder object is not a children of the Navigation2D

With 1) and 2) would be very easy to create moving walls or opening doors. With 3) it would be great to make bodies to do not allow mutual crossing if they are occluding the path.

I have one question:
@TotCac : When you said: "While building your Tilemap, each tile have static data of navigation to be considered by pathfinding." What are you referring to? Is that documented anywhere?
Thanks!

[kakoeimon]

I think this is in the TODO list but not in the 2.1 as it looks like.
By the way it's called Detour / Recast.
Recast is for creating the navamesh from the polygons of the a 3d model (this is a technique introduced in 3d)
and Detour is the way to navigate on the navigation mesh.
Right now we have only Detour in Godot, a tool for creating NavMesh for 2D and a way to import a 3D navmesh created by the Recast in Blender for example.
We do not have obstacle avoidance and for this reason we do not have the ability to block passages of the navigation mesh, we also we do not have crowd control and for this reason agents eventually get in line when they want to get to the same location.

Edit: Sorry my mistake. This is in the todo list for 2.1
https://trello.com/c/vfEeGOIc/35-local-obstacle-avoidance-in-navigationpoly-mesh

[TotCac]

Don't know if this trello is really used by developpers

[TotCac]

@kakoeimon when you build your tileset, you define a navigation polygon for each tile. Then, if you set a tilemap as a children of a Navigation2D, each tile will be linked to your navigation2d, and you build a full level of navigation. I said static data because you can't modify it at runtime as it's a tile information. Check this: https://www.youtube.com/watch?v=S-zEA_Ce1mk

[batmanasb]

To add to this, you can actually use the "set_cell()" in the Tilemap node to switch cells with a NavigationPolygon to cells without them. Which is a way to cut off paths for doors and other roadblocks.

[kakoeimon]

@batmanasb You are right. Changing the tile from a tile with navigation polygon to a tile without navigation polygon updates the navigation mesh and blocks passages.
@TotCac so to solve your problem you can create a tilemap without graphics but with two blocks

1. with a NavigationPolygonInstance
2. with StaticBody2D
   Then make this "transparent" tilemap to take the position of the tiles from another tilemap (the one with the graphics for walls and floors) and use "set_cell()" to change the tiles when ever you want to put somewhere an "obstacle" without changing the graphics.

By the way @reduz reports his progress in Trello.

[TotCac]

@kakoeimon It's exactly what I am doing here https://www.youtube.com/watch?v=ThYeRtSqeBU, while adding some wall at runtime, i update a navigation tilemap which is only a navigationpolygoninstance and a staticbody. The problem is for "dynamic" object as car as you can see in video.

edit: my mistake @kakoeimon, hint of tilemap navigation2d what no for you but to @genete :)

[kakoeimon]

@TotCac Yep, that's why we need obstacle avoidance.

[akien-mga]

Given how popular this issue is, I'll make sure it's fixed sometime before 2.1 is released :)

I've tried... But it's not critical for the imminent 2.1, so moving to the next milestone.

[TotCac]

As 2.2 is cancelled, any chance having this in 3.0?

[Zylann]

This Q&A question could be related: https://godotengine.org/qa/8757/2d-navigation-weighted-tiles-for-difficult-terrain
It also makes sense when you know the AStar class does supports avoidance through "difficulty". Could be implemented by painting the vertices of the navmesh with a custom vertex attribute?

[bojidar-bg]

Bump, which version would include this? 😃

[plucian]

2.1.2, that'd be great -> 2.1.3

[ProbDenis]

Any chance for this in 3.0 or 3.1? Would be incredibly useful.

[TotCac]

I think they should freeze 3.0 and stop adding feature because release get delayed and delayed.
Maybe for a 3.1 I hope

[seanfy]

When implementing this, would it be possible to give Tilemap node an option to make the whole tilemap navigable by default？

In some cases putting tiles or objects later that blocks your npcs or player from walking through is more natural than painting walkable areas for them.

[tengkuizdihar]

mfw this issue still open after 2 years

[plucian]

how would this be different from just removing a tile from the path ? Or put a tile that does not a have a navigation polygon attached to it..

[TotCac]

Because obstacle can be bigger than a tile

[plucian]

that's not an issue. add as many tiles without nav pol to have a very big obstacle. Also it does not matter the size of the obstacle (could a different object not necessarily a tile), what matters is the break in the nav. path.

[tengkuizdihar]

I'm bumping this issue so that someone that's good enough to implement this. Btw, they also have a lengthy explanation of the algorithm being used and what not. Please dev, do implement this. I'm afraid I'm not good enough to even understand it. Thank you.

[Zireael07]

@balenol: Godot already is making use of a polygon clipping library named triangle. I am not sure if triangle is exposed to scripting, though?

[tengkuizdihar]

@Zireael07 I didn't know that. Maybe the only thing this "good enough than I am"-person should do, is to expose that library to the polygon2D object? I mean, does it have the NOT operation (i'm talking about boolean operation on polygon here) so that we could occlude the navmesh somehow? That would be awesome.

[TotCac]

I'd already open an issue to expose Clipper library to GDScript, as it's a part of engine external library aldeay #22275.

But, it's not for computing at real time, and should not be used for our needs of new NavigationServer :)
It's on the dev roadmap, we just have to wait for now

[PabloNeirotti]

Not sure what use cases you'll be aiming to cover in the end. But if I could have a Navigation2D with many NavigationPolygonInstance inside and have them all get added together, that'd be super neat.

[tengkuizdihar]

@PabloNeirotti you do have the ability to do that right now. As long as the corners from each polygon is overlapping, godot will try to solve it. I've tried it with about 10000 instance before and it lag like hell. The clipper implementation is pretty useful because now instead of many instance with overlapping corners, you have one big polygon instance.

[Jeto143]

+1 on the NavigationOccluder suggestion, that would actually be perfect. Occluders would take precedence over polygons, and a tilemap would ideally also have an option to be fully navigable by default (as also suggested).

[Xrayez]

I think this could be solved with Clipper internally but I'm completely nebulous to path finding and navigation, though I'll give an idea. 😆

If I understand correctly, NavigationPolygon is used as a child of Navigation2D to define walkable areas to find a path. NavigationOccluder would then negate any walkable areas. This could be done just like in CSG nodes in 3D, having UNION for NavigationPolygon and SUBSTRACTION operation defined for NavigationOccluder. The order of nodes could determine how the overall navigation is morphed, and even having ability to disable/enable such nodes by turning their visibility and being able to locally transform navigation polygons based on nodes transform.

[TotCac]

Hello friends,

More than 3 years now that we ask for something to help us.
This is not the solution for collision avoidance, but may be a good workaround for some of you.

Polygon operations on 2D (merge, xor...) and offseting has been merged into master branch 👍

Will have a try into this soon!

[tengkuizdihar]

@TotCac OH YEAAAAAAAAAAAAAAAAAAAH

[TotCac]

Congrats to @Xrayez juste above

[Xrayez]

Thanks, I've exposed these methods in such a way that it would be applied to plenty of use cases I believe.

I can't really help here until I actually need navigation features in my project to truly understand the use case, maybe some fellows can implement this in the core some day (wait another 3 years? 😅).

[Abstract-Everything]

Polygon operations on 2D (merge, xor...) and offseting has been merged into master branch +1

How are these operations exposed?

[Xrayez]

@J-Camilleri they are available in Geometry singleton, see #28987. It's pretty elemental so these could be used universally and applied to fix this issue I believe (either via scripting or within engine).

[tengkuizdihar]

@Xrayez definitely. This is definitely helpful. Now I could just make a big/segmented navigation polygon and then clip it off bits by bits when loading. Thank you.

[ToxicCrack]

If anyone still has the problem with multiple tilemaps, here is a solution i came up with:
https://github.com/ToxicCrack/godot-tilemap-navigation

[Calinou]

Dynamic collision avoidance has been implemented in #34776, closing.