NavMesh pathfinding behavior

[D8H]

This is an implementation of a pathfinding behavior that uses A* over a NavMesh. The initial discussion: https://github.com/4ian/GDevelop/discussions/2787

Trello card:

• https://trello.com/c/Fvu5OgmO/330-add-an-isometric-option-to-pathfinding-behavior-to-follow-isometric-angles-instead-of-45-degrees-angles

Used work

• a NavMesh generator by Stephen A. Pratt (ported from Recast).
  • http://www.critterai.org/projects/nmgen_study/
• a A* pathfinding over a NavMesh by Michael Hadley
  • https://github.com/mikewesthad/navmesh
• a scan-line polygon fill algorithm by Darel Rex Finley
  • https://alienryderflex.com/polygon_fill/

Known limitations

• The pathfinding can't find a path if the object is not inside the mesh.
• The pathfinding can't find a path if the target is not inside the mesh (even if the target is not actually in an obstacle, but in the margin).
• The pathfinding library loops on polygons center to search for start and end nodes. This kill the performances on big mesh.

We could add the mesh polygons AABB to a RBush solve these 3 limitations.

Examples

Project must be opened with this custom build: https://www.dropbox.com/s/6yy7uptw5ffceoh/gdevelop-navmesh-beta139-2022-07-30.7z?dl=1

• squares at random position

  • Project: https://www.dropbox.com/s/t8in8c9ba5z3zm2/NavMeshForestExample.zip?dl=1
  • Build: https://d8h.itch.io/navmesh-random-obstacles-demo

• 2 sizes of moving objects and obstacle dragging

  • Project: https://www.dropbox.com/s/q0hg46ytv6as2fb/NavMeshSizeExample.zip?dl=1
  • Build: https://d8h.itch.io/navmesh-draggable-obstacles-demo

• a modified version of the AI example

  • Project: https://www.dropbox.com/s/fvjd7b0bjfxvbdv/NavMesh-basic-ai-with-pathfinding.zip?dl=1
  • Build: https://d8h.itch.io/navmesh-ai-demo

• to check that functions are linked to the implementation

  • Project: https://www.dropbox.com/s/yzda05q8s206qy0/NavMeshFunctionTest.zip?dl=1

• a modified version of the isometry example

  • Project: https://www.dropbox.com/s/r5np0yhfp7grscg/NavMeshIsometricExample.zip?dl=1
  • Build: https://d8h.itch.io/navmesh-isometric-demo

[4ian]

Nice! 🚀 Looking forward to checking all of this!

[D8H]

I think that's in this case a UX improvement to be done for the editor rather than something that the extension should support itself :)

Do you mean the ability to precalculate the meshes? There is still the need to handle dynamic changes, but I will remove the action and watch the obstacles instead. It will be easier to use optimizations if the invalidation is done internally.

With the "2 sizes of moving objects and obstacle dragging", the gray robots ask a new path when they reach their destination so it can happen during the dragging of an obstacle and freeze a bit. The obstacle behavior can be disable temporary to avoid mesh refresh during the dragging. There will still be one refresh because the behavior disabling will invalidate the meshes, but I think that should be ok. A property "Allow mesh refresh" could be added to avoid this. If it's set to false, the manager will remember that the meshes are invalidated but keep using them.

[4ian]

Do you mean the ability to precalculate the meshes?

No (my comment is out of context, not sure why), I meant the fact that using the behavior shared data, having multiple scenes force you to change multiple times your settings if you have multiple scenes with the behavior. Not a big deal!

[D8H]

I added an action to disable the NavMesh updates. For instance, it allows to drag an obstacle while paths are computed without rebuilding/invalidating the meshes continuously.

[D8H]

With the automatic invalidation of the NavMesh, this can happen:

• events change the obstacle locations
• events ask a path
• pre-events, the obstacle manager watch the obstacles and invalidate NavMeshes

The path is actually computed with the old obstacle locations. This may not be an issue because the other pathfinding behavior works this way too.

[D8H]

I opened 4 change requests. For clarity, should I remove from the code the TODO linked to these requests? Do you think one of these requests should be included in the 1st version?

[4ian]

For clarity, should I remove from the code the TODO linked to these requests?

I would say yes, so that the code is cleaner (in the sense these are not things to do to improve the code).

Do you think one of these requests should be included in the 1st version?

Thanks for opening these. I don't think any should be mandatory for a first version (as you demonstrated in an example, the NavMesh pathfinding can be used to replace the old pathfinding, which is enough for me to consider it publishable!).

[D8H]

I did a pass on todo.

• In the behaviors, only one remain on the debug drawing.
• In the NavMesh generator, it's remainders of the part of CritterAI implementation that hasn't been ported. I didn't see the need for them but in case a bug is found, it can be useful to check if this could solve it.

[D8H]

I published the NavMesh generator as a library. I made a few changes to avoid some reallocations when updating meshes. I think I'll integrate it the same way as the P2P extension did for its libraries. https://www.npmjs.com/package/navmesh-generator

[4ian]

That's a great idea 👍 This can create some interest around the library itself :)

[4ian]

With the platformer rework now in, we can I think get back to this! @D8H anything that was outstanding there? Do you want to rebase on master (otherwise I'll do it)?

[D8H]

For the library, I left a catted TS instead of a packaged library because I think it will be easier to debug, but I could package one if your want.

[4ian]

@D8H may I ask you to rebase an additional time this on top of master? 😇

[4ian]

I think that we could go ahead with this if we:

• Rename the existing pathfinding as "Pathfinding (grid based)"
• Name this one as "Pathfinding (polygon based)" or something similar so that it's understandable.
• Surely mark this one as experimental for a few versions :)

Also, I think we should clean the usage of the debug draw. It's very nice to have, but I think it should use the runtime scene exposing some way to "add stuff" to the debug draw, and the action should work then without a shape painter :) I say this because I just tried to test this:

And this does not work because it can't be called more than once in a row because it's waiting to draw the result. And more generally we should avoid relying on a shape painter, it's convenient but not really for the user as there is too many chances someone would badly configure it :)

EDIT: I also put the shape painter not at 0;0, and had the "clear at each frame" activated... too many stuff to get properly for a poor user trying this, we should rework this to directly draw using a graphics object exposed by the scene :)

[D8H]

It gets a bit messy when the NavMesh is shown with hitboxes.

I guess we could

• Add a new action to hide or show the debug layer
• In the action "Draw collision hitboxes and points", rename the parameter "Enable debug draw" as "Show collision masks and points"

The big issue would be to make it understandable for users that one action alone doesn't do anything. Does forwarding to the other action in the description enough to make it user friendly?

The good side is that it allows users to toggle between debug and production easily and it's very simple to implement (an automatic activation would mean to keep track of the number of JS instances that want to draw on debug to disable it when there is none).

Looking at this example, I wonder if the action should allow to show/hide collision masks per layer to avoid the background to make it unreadable.

[D8H]

I also changed the descriptions to start with a verb. It is a recommendation to write documentations in the wiki and I thing it apply well for behavior descriptions. It avoid heavy formulation like "With this behavior", "This behavior allows to". The title is often a noun so even for "Platform" or "Character", it could be better to start with a verb to avoid redundancy. I will ask the extension team if they want to add this in the best practice page.

I should probably write a documentation because users might not be used to scene properties. I could use this page for inpiration: https://wiki.gdevelop.io/gdevelop5/behaviors/pathfinding

[D8H]

I added 2 parameters to allow a clear debug view for the behavior to draw on it.

[4ian]

Looks great! 👍 I think we should merge this early this week so that it's part of the next release, after making an additional check on the whole thing :)

[Silver-Streak]

@D8H Reading through this PR and the original discussion, I noticed there isn't an action to stop movement on the path. Is that something you would consider adding?

(This also doesn't exist on the main pathfinding behavior, now that I've dug in on it, but no reason to keep that deficiency in your new actions if it can be avoided)

[D8H]

@D8H Reading through this PR and the original discussion, I noticed there isn't an action to stop movement on the path. Is that something you would consider adding?

(This also doesn't exist on the main pathfinding behavior, now that I've dug in on it, but no reason to keep that deficiency in your new actions if it can be avoided)

Doesn't the "disable behavior" action serve this purpose?

The goal was to have the same level of functionality to keep the PR from growing and add new features after it's merged.

[Silver-Streak]

Doesn't the "disable behavior" action serve this purpose?

Sadly, no, it keeps the path going as soon as you re-enable it.

The goal was to have the same level of functionality to keep the PR from growing and add new features after it's merged.

That's totally valid, but I thought I would ask.

[Hillihix]

When should this behavior be expected approximately?

[D8H]

When should this behavior be expected approximately?

Probably not soon. We should probably rather add a shared properties feature to events-based behaviors and make this a community extension.

[Hillihix]

When should this behavior be expected approximately?

Probably not soon. We should probably rather add a shared properties feature to events-based behaviors and make this a community extension.

Can I learn more about this feature?

[D8H]

It's scene properties where the rastering grid is setup for this extension. Events-based bavariors can only define properties to be set on objects for now.

[D8H]

I close this PR as this extension was added as a community extension.

• https://github.com/GDevelopApp/GDevelop-extensions/pull/669

[DH-555]

Thanks for this extension. Our game (Zsquare: https://liluo.io/games/aef70ed3-d55b-4eb0-964e-55ba618a478d) used it before the extension was published and worked better than the default pathfinding system in all terms. It should be included as a native GDevelop feature. In our game, we recalculate a new route for every square in the screen every frame, a thing that is impossible to achieve with the default grid-based pathfinding without lag and for several objects when there are huge distances.