Set dynamic obstacles to navigation mesh

[panuchka]

Would it be possible to extend the toolkit to support dynamic obstacles in the navmesh?

Use case: I have a game scene that has n+1 enemies, that are following the player using the navmesh. One enemy has to know where the others are in order to navigate properly on the map and not "merging" into each other.

[clementlevasseur]

Hey !

This library just help to know the shortest path on a static navigation mesh. If you want an obstacle, you have to change the navigation mesh. A simple way to add dynamic obstacle would be delete the vertex of the navigation mesh where your player is.

If you have an idea of implementation, do not hesitate to PR :)

[panuchka]

I can update the dynamically generated mesh (http://www.babylonjs-playground.com/#VKBJN#64) itself pretty easily, since I create it from a model (bunch of ones and zeros). It is, however, pretty heavy operation.

I'm not quite sure if you already suggested this, but there should be a way to update zoneNodes somehow. Basicly, I need two functions, add and remove that either add or remove specific nodes from the navigation zone. Could you point me to the right direction? I can pinpoint the location of every vertex on the navmesh I created but is there a way to remove/add vertices to the node system this library uses?

Hopefully what I wrote makes some sense 😅

[Glidias]

https://github.com/Glidias/three-altern-pathfinding/wiki/Dev-notes%3A-Temporary-Obstacles-approach/

Navmesh cutting demo: https://playcanv.as/p/rOVt2SJg/

Skill a WIP and incomplete.

The idea:

Create a delauney triangulation to further subdivide each relevant triangle on the navmesh based off any projected 2d-convex ordered obstacle points over 3D triangle surface (where the projected ordered convex obstacle points must also be clip-constrained within the clipping hull of the triangle 2D bounds itself.). Then, modify each original node triangle to use a sub-set of triangles (secondary nodes) based off the triangulation. Modify the zone Nodes and neighbours to match the sub-set accordingly.

(above: mock example of triangulation produced using 1 obstacle. For multiple intersecting obstacles, a union of points is required for the concave hull of multiple obstacles.

I'm currently using Delaunator for the delauney triangulation and it's a very quick way to create submeshes in real-time per frame since the output contains half-edges information allowing you to easily derive neighbour information easily.

---

I think the current system has zone Nodes but a lot of geometric data was removed from it as it's not relavant to pathfinding. If you've got a seperate mesh reference for the navmesh, I suggest you relate each triangle in that mesh reference to the respective Nodes...though you might need to modify source code to facilitate this process of relating the mesh geometry to the Node.