I have build my own NavMesh representation, generation and path finding on it in c++ and it works very well so far. However i struggle archiving this seemingly easy task:

I want to find a random point within the NavMesh meeting some criteria or to be a bit more general I want to extract a subarea of my NavMesh which fulfills some requirements.

These are simple things like "get a random point which has at least distance x to the nearest wall" or "find a point which is not visible from point x". I need these for AI tactics or spawning enemies not to near to the player.

Picking a random point in the NavMesh and testing if this requirement is true is easy but not efficient if only a small subarea is valid and I end up picking and testing random points forever.

I should mention that a subarea cannot be described by a subset of polygons in the NavMesh as these have nothing to do with these criteria. For example the area with all points with a minimal distance to a wall will surely split most polygons in half.

To summarize my question:

What is a efficient way to describe a subarea of a NavMesh meeting some criteria. Are there efficient methods of finding a point inside a NavMesh which fulfills given criteria without randomly picking one and testing it?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.