filtering out the navmesh islands

[deathbeard]

I need to filter out all the navmesh islands because characters are sometimes getting stuck in them, but I have a problem.
The filtering works well, but the recast filtering allows islands through if they touch the borders of the current navmesh tile, which is undestandably necessary, but it means that any potential island falling on a border gets allowed.  See here in the screen, the inaccessible rooftops of 2 buildings have a mesh because they crossed a tile border:

https://dl.dropbox.com/u/90125288/screenshot_1680.jpg

and here, more small bits that happen to have hit borders:
https://dl.dropbox.com/u/90125288/screenshot_1681.jpg

Is there a way to perform a post-filtering?  A second island filter that takes into account the neighboring tiles?  Or is it too late once all the tiles are built?

[Mikko Mononen]

Hi,

The build process does not have the neighbour tiles at hand, and my
attempts to do so just made the build process really complicated (or
too memory intensive).

There is navmesh prune tool example which takes points that are known
to be navigable (i.e. a spawn points), and flood fills polygons on the
final navmesh and then tags them with some flags (or removes flags):
http://code.google.com/p/recastnavigation/source/browse/trunk/RecastDemo/Source/NavMeshPruneTool.cpp

That allows you to disable those unneeded polygons, but it will not
allow you to remove them. Repacking the navmesh tile data is not very
easy.


--mikko

[deathbeard]

I was afraid of that.
Flood fill is still not perfect, unless you have your entire world loaded at once you would be pruning some valid areas.

What about some kind of post-build technique that doesn't remove, just flags the islands as unwalkable?  It would do the built-in island filtering but taking into account any loaded neighboring tiles, and only considering it a border if there is no neighbor tile currently loaded on that side?

[Mikko Mononen]

Hi,

I added some sample code for doing kinda inverse of the pruning code
discussed earlier.
You can find it in NavMeshTesterTool in the latest version from SVN.
The idea is that the code will walk through all the polygons in the
navmesh and flood the area connected to the polygon (each area is
visited only once). If the visited are bbox is small enough, the
polygons are disables.

The example does this for all tiles, but you can do that also by just
loading a tile and all its' neighbours and do the flooding for the
center tile only.

p.s. I did something stupid with the SVN, so I hope that you will get
a clean version.

--mikko