Recommended way to implement "holes" in navmesh?

[verekia]

This library is fantastic! I managed to get pathfinding working very easily for a game. Thank you so much @frapa.

But I have a question. How would you recommend adding holes to a navmesh?

Let's say we have a square:

[
  [0, 0],
  [0, 100],
  [100, 100],
  [100, 0],
]

But I don't want the whole square to be walkable. I would like to have a smaller inner square obstacle, for instance:

[
  [20, 20],
  [20, 80],
  [80, 80],
  [80, 20],
]

I managed to get this case working in the online editor by creating 2 polygons and connecting them: Shaped like [ and ].

That's fine for a simple case like this, but for a video game with a complex map and many obstacles in the middle of the map, I am not sure how to proceed. This method would be very tedious. Any recommendation?

[verekia]

I managed to get it working using earcut: https://github.com/mapbox/earcut

const allPoints = [...outerPoints, ...centralObstaclePoints]

const triangles = earcut(allPoints.flat(), [outerPoints.length]).map(index => allPoints[index])

const groupedTriangles = triangles.reduce((acc, cur, i) => {
  if (i % 3 === 0) {
    acc.push([])
  }
  acc[acc.length - 1].push(cur)
  return acc
}, [])

const navmesh = new NavMesh(groupedTriangles)

[frapa]

Hi @verekia,

Thanks for reporting that!

I have to check to be sure, but I believe the library will handle counterclockwise polygons as outer boundaries and clockwise polygons as holes, so you might be able to use that.

The editor most likely ensures everything is counterclockwise so it's hard to use if you need holes.

I will check when I have some more time!

[verekia]

Thank you for your answer! I am trying the following polygons:

const polygons = [
  // outer, counterclockwise
  [
    [0, 0],
    [500, 0],
    [500, 500],
    [0, 500],
  ],
  // inner, clockwise
  [
    [100, 100],
    [100, 400],
    [400, 400],
    [400, 100],
  ],
]

const navmesh = new NavMesh(polygons)

Is this what you mean? With this code, it seems like the inner square is not creating a hole. The resulting path goes through the inner square.

[frapa]

Sorry for coming back so late.

I checked, not I do not handle holes correctly right now. Your best bet, is to use earcut directly before passing the data to nav2d. earcut has a explicit holes parameter.

After that, pass the triangulated data to nav2d and it should solve your issue.

[verekia]

Thank you for your answer @frapa

I am already using earcut to triangulate with holes, but the pathfinding seems off when there are holes.

For context, I am using nav2d on the game https://minimana.io The monsters on the map run after the character, and I use nav2d pathfinding at every frame.

This is what the map looks like, with the navmesh in blue, and the triangles generated by earcut in red.

In this video example, I made a hole, and I am running around it. You can see that the monster sometimes takes the wrong path (when it starts turning counter-clockwise). The monster was closer to me clockwise, but it decided to go the other way:

https://github.com/frapa/nav2d/assets/522007/8432c033-fe57-4545-86b7-876f8b0dccb8

I have noticed this behavior whenever I have holes.

You can see it here as well:

https://github.com/frapa/nav2d/assets/522007/e8e8b8ca-e899-4b1c-9849-857a889518a1

(This bridges area is in the middle of the map on the screenshot above, but the blue navmesh is covering the bridges)

If you think the issue comes from nav2d, I would be happy to offer a bounty for a fix, as this is pretty important for this kind of game :)

Feel free to reach out to me on Discord or Twitter (verekia) if you want to have a chat :)

[frapa]

Oh, thanks for a link to the game, it's great to see the library is useful. It seems also plenty fast!

Also, great videos showing the problem. This isn't a bug with the library, actually nav2d is working fine here. The problem is that path finding works with these steps:

1. Search which triangles are on the shortest path.
2. Use a funnel algorithm to draw a path through the triangles to find the straightest possible line.

To do (1) it will use the triangle centroids for a heuristic of how long the path is, but it's just an heuristic so it can get the wrong estimate, such as in this case. Typically, path-finding algorithms are focused on speed, because it is an expensive operation and games usually need performance, so it's typical to sacrifice some accuracy for a path that's good enough. This is what nav2d is doing here.

In other words, try to count the triangles between the characters, and you will see that it's actually taking the path with the least amount of triangles, only they are larger, so it leads to a longer path effectively.

To solve this issue, you have 2 options:

1. You could try changing the heuristic function, for instance by compensating the distance by the size of the triangles. I wouldn't recommend as this is going to be tricky to get right and might not work at all.
2. You can provide a better triangulated navigation mesh. earcut is built for speed just like nav2d but it sacrifices triangulation quality to achieve it. You see this in the number of thin elongated triangles you have in the mesh. Additionally, you actually don't need to triangulate each time, so you can basically do a high-quality triangulation every time you change the map of your game, then simply load the already triangulated high quality navigation mesh. I would recommend going this way, as you are sure to encounter far less issues.

One optimization we could add here is that we can add a flag to tell nav2d to avoid triangulation, to save additional load time when the navigation mesh is already triangulated.

[verekia]

Thank you so much for your answer!

I switched to https://github.com/r3mi/poly2tri.js, which creates a much cleaner mesh and works better with nav2d's pathfinding!