1
\$\begingroup\$

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?

\$\endgroup\$

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.