Path finding on generated NavMesh

[D8H]

Navigation meshes seems to be a good search space in term of performances and allows to find path that seem rather natural (line segments).

There is an MIT JavaScript library that do path finding on NavMesh:
https://github.com/mikewesthad/navmesh

I guess it could be interesting to integrate a library like this into the path finding behavior. It may be challenging to handle moving obstacles if NavMesh generation is costly.

Is there some rules to follow to add a dependency to the engine?

[4ian]

Interesting :)
I would think of making this into a separate extension to keep things simple (a "NavMeshPathfindingBehavior"?).

Is there some rules to follow to add a dependency to the engine?

As this is an extension that will be in the "core", it will have to be maintained, so the rule of thumb is to check we're using something as simple, lightweight and performant as possible.

In the case of an extension like this relying a lot on object hitboxes, it would be worth checking if we can store the objects in a RBush, like the platformer behavior, the existing pathfinding behavior and the light obstacle.
The goal in the future will be to move these RBush to a single RBush handled by the game engine. So that collisions and anything needing to fetch objects around a position can do it in a very efficient way.

I had a PR to do this a while ago: #1393
But never finished this because in certain cases, the performance was worse (because the overhead of updating the spatial structure at every object movement could be larger than the collision testing, when there are a tons of moving objects). Would be good to revisit this, because it's a better architecture for the future.

[D8H]

There is a good resource about NavMesh generation: http://www.critterai.org/projects/nmgen_study/
It's the documentation of a Java library for 3D that is a simplification of Recast (C++): https://github.com/memononen/recastnavigation

For 2D, "only" these algorithms should be needed:

• polygons rasterisation (Bresenham for segments and a fill)
• space segmentation with the watershed algorithm
  • it uses a distance field
• contour generation (from grid elements to polygons)
• convex polygon generation
  • triangularisation and merging

The NavMesh generation clearly seem very costly. There are algorithms to update it, but even a static one with an action to build it after the level is set should be useful. It could even be generated by the IDE if it's too long to process.

[4ian]

This is by the way (generation at the beginning, or re-generation on demand by an action) something we could do for the existing pathfinding (to allow to "freeze" the obstacles in the RBush and only compute paths).

EDIT: might be something to think about more globally in the engine.

[D8H]

I still have some cleaning to do and tests to write but it's nearly done.
I built a demo:
https://games.gdevelop-app.com/game-8e6b079f-c775-4978-8ce6-953db493289a/index.html
(right click to move, left click to drag obstacles)

[D8H]

The isometric example with NavMesh (try to go to the small island in one click)
https://games.gdevelop-app.com/game-ad10c590-362a-44b4-b9a8-254d43d8b07b/index.html

[D8H]

This is the behavior interface in case someone has a suggestion.

Game settings:
The navigation meshes (one by object size with a one cell increment) are shared by all objects.

Properties:
One day, it could be interesting to:

• allow to smooth the path
• have a non-blocking extra margin to avoid to huge the walls
• something like layers for obstacles

Conditions:

Actions:
There is also an invalidate action that is independent from objects.

[4ian]

This looks very clear :)
A few questions:

• When/How is the navmesh initially created?
• Is this handling objects that are moving?
• Could we give an action to re-create he navmesh (after some important changes in the scene for example at runtime)?

[D8H]

* When/How is the navmesh initially created?

When a path is asked, it looks in a map for the right mesh (for the object size) or create one.

* Is this handling objects that are moving?
* Could we give an action to re-create he navmesh (after some important changes in the scene for example at runtime)?

Yes, there is an invalidate action that is not on the screenshot because it's an extension action. In the 1st example, the obstacles can be dragged and the mesh is updated on screen on the next move.

[D8H]

I'm trying more complex cases to find limitations.

I realize a limitation (which was documented, but I didn't see the implication) about the A-star pathfinding on NavMesh library I used. The A-Star heuristic is based on the center of each polygon. This work well on rectangular grids but here with the funneling algorithm, the path won't go through polygon centers (in orange). In the following screenshot, the character will make a weird detour (in red).
It's not easy to think of a better heuristic and actually vertices that are not on an obstacle will probably always be an issue for the funneling algorithm. Thankfully, the navigation mesh can be filtered to avoid such cases.

After the filtering:

I also made some few changes to generate better NavMesh.
There is a lot less polygons than on the previous build. It's not far from an optimal segmentation. The corners are eaten a bit by the rasterization but I think it can be solved with smaller rasterization cells, more margin (the object size is set to 0 to better see the approximations) or a well placed obstacle.
https://games.gdevelop-app.com/game-cb6eb2e0-78e5-4464-88a1-cfe0e4414d9a/index.html

[D8H]

I continued to work on the vertex merging to handle imbrication and vertices shared by more than 3 regions.

I did a small example to generate cases (it logs the obstacles positions, so if you find something weird, please copy paste it):
https://games.gdevelop-app.com/game-58de2435-2c93-4360-aea3-5f60f16ffaab/index.html

[D8H]

I opened a PR: #2856