Any way to query 'reachability island' for points on the navmesh? (5.6)

Behavior & Navigation Navigation
1

I just want to do a very quick check for whether a given point is reachable from another, by hopefully comparing something like a ‘reachability island ID’, where all polys that are reachable from each other share an ID. I know other pathfinding libraries support this.

Is such a thing generated and stored anywhere in the Unity 5.6 navmesh?

1 Like
2

I second this, I’m doing sort of a tower defense game and I need to check if all spawn points for enemy units are able to reach the end/target point each time I put a new tower on the map, so towers cannot completely block enemy paths to their final target, I’m using the old unity’s navmesh obstacle to carve the navmesh on runtime.

if only I could ask if after adding a tower (obstacle) and therefore carving the mesh, the mesh is now divided in more sections than before, then I can ask if the section/region/connected polygons that contains the end point and the start point are the same, asking for a path with CalculatePath(spawnPoint, TargetPoint); is not an option because I also need to check if I’m not isolating any of the current enemies in an island:

RED POINT = target/end
GREEN POINT = start/spawn point
CYAN POINTS = enemy units
YELLOW BLOCKS = towers/navmeshObstacles

a95ec80ca0568812e96d49786a608ef9371a2988.jpeg
a95ec80ca0568812e96d49786a608ef9371a2988.jpeg1536×1024 215 KB

doing a CalculatePath() for each enemy would be expensive (100+ enemies in the map), so I could just take all islands and do something like this (pseudo code):

bool IsTowerCreationForbidden()
{
   bool forbidTowerCreation = false;
   foreach (Island in Navmesh.Islands)
   {
       if (island.containsAgent())
       {
           bool pathFound = island.GetAnyAgentInThisIsland().CalculatePath(start,end);
           if (!pathFound)
           {
               forbidTowerCreation = true;
               break;
           }
       }
   }
    return forbidTowerCreation;
}
3

Not there’s no inherent “island ID” in the navmesh system. If you know the island locations in advance you can calculate paths and check if the resulting path status is : NavMeshPathStatus.PathComplete - meaning the two ends are connected . Notice that the path calculated will be using any links if possible, this may or may not be desired.

4

That’s a shame! It would be fairly easy to add.

Ok, if I want to do this myself, is there any data I can use about poly connectivity, so I can extract connected components easily? The most likely candidate looks like NavMesh.CalculateTriangulation - but do you know if verts are guaranteed to be unique, so polys sharing two indices are connected? IIRC that’s the case in Recast/Detour but I don’t know how far you guys have diverged.

It would seem very messy to have to guess at poly connectivity by comparing poly vert positions. If connectivity information isn’t exposed anywhere, can I request it please?

Edit: I can get some of the way with requesting paths between some region centres for now thanks, but this isn’t going to scale at all well!

2 Likes
5

Yeah, it really is a shame. A* Pathfinding Project assigns unique numbers to islands and in fact it has a function called IsPathPossible() that simply verifies if the island numbers are the same and the two points have a walkable status.