How to query different elevations using the NavMesh generated for detour/recast

[InnerSilence]

I am trying to find a way to check if there are navmesh available for different elevations given the (x, y) coordinates and get those height values.
Lets say we have a two story building and both floors are walkable and we have navmesh already generated for it using recast. Now I want to be able to query Z values for the given point (x, y)
and get Z values for both floors. Is there any way to do it with recast/detour?

[Jadd]

You could use dtNavMeshQuery::queryPolygons. Supply a center point (x, 0.0f, y) with up/down extents (0.1f, 100000.0f, 0.1f), and using the provided dtCollectPolysQuery filter you can collect all the touched polys which can then be used to query the height from the detail mesh. Depending on the usage, a custom query filter may be a better option too.

[Alisha]

You can use for this

query->queryPolygons(const float* center, const float* halfExtents,
						   const dtQueryFilter* filter,
						   dtPolyRef* polys, int* polyCount, const int maxPolys)

to find polygons for the location
and then

query->getPolyHeight(const dtMeshTile* tile, const dtPoly* poly, const float* pos, float* height)

to find available Z for each found one.

I suppose you already using GitHub - recastnavigation/recastnavigation: Navigation-mesh Toolset for Games

[Jadd]

...

Beat you by about 1 minute.

[Alisha]

Beat you by about 1 minute.

Yea I sent and then saw your post before mine

[InnerSilence]

Thanks dudes, gonna give it a try now.

[namreeb]

Querying polygons will work in most cases, but it can be glitchy if you employ some fuzzy logic to handle the selection of a reasonable value when multiple options are available. What I did in my pathfinding library was to separate it out by the possible reasons for wanting a Z value at a given (X, Y):

1. A raycast from (x1, y1, z1) to (x2, y2). In this case, I use the raycast ability of Detour because it will follow the navmesh from the source position. This is useful for something like the mage blink spell or filling the Z value when building a spline for fear, polymorph, etc.
2. A generic query that returns a std::vector<float> for a given (X, Y). This forces the caller to deal with the possibility of multiple values on their own in a contextual way.

In code it looks like this:

        // for finding height(s) at a given (x, y), there are two scenarios:
        // 1: we want to find exactly one z for a given path which has this (x, y) as a hop.  in this case, there should only be one correct value,
        //    and it is the value that would be achieved by walking either from the previous hop to this one, or from this hop to the next one. 
        // 2: for a given (x, y), we want to find all possible z values
        //
        // NOTE: if your usage is outside of both of these scenarios, you are probably doing something wrong
        float FindHeight(const math::Vertex &source, const math::Vertex &target) const; // scenario one
        bool FindHeights(float x, float y, std::vector<float> &output) const;           // scenario two

DANGER WILL ROBINSON

Depending on what you're using this for and what your settings were when you built the mesh with Recast, the Z value you get from Detour will be imprecise. For this reason I have an internal function (available only to my pathfind library, not to callers/users of it) to find a precise value. It will take the value from Detour as a hint and refine it to a significantly more precise value from the actual terrain. The steps to do this are basically:

1. Take z hint, add to it the detail max sample error value you provided Recast. Code:

float Map::FindPreciseZ(float x, float y, float zHint) const
{
    float result = zHint;

    // zHint is assumed to be a value from the Detour detailed tri mesh, which has an error of +/- MeshSettings::DetailSampleMaxError.
    // because we want to ensure that zHint is above the 'true' value, we shift up this error range so that the error is
    // instead 0 <= error <= 2*MeshSettings::DetailSampleMaxError
    zHint += MeshSettings::DetailSampleMaxError;

2. Query the ADT Z value, if present, for (x, y).
3. Raycast from (x, y, zHint) straight down, hitting only collision terrain.
4. Return whichever of steps 2 and 3 is larger than the other.

Note that if you are operating as the server, a precise Z value is only necessary for the end of a spline. The intermediate hops can use the imprecise value from Detour, and in fact that is what the Blizzard servers do. If you sniff a spline from their servers, and look at the error of the intermediate points and the end point, the intermediate points will always have a relatively high error range (something like +/- 0.3) and the end point will always be much more precise (+/- 0.0005). The client has some built-in fault tolerance to absorb this. This was almost certainly done as an optimization on Blizzard's part for their server.

Note also that if you are operating as the client (i.e. a bot), you will want a precise Z value every time. My private server anticheat would examine the accuracy of Z value in the click to move struct, and a consistently imprecise Z value would signify a bot.

[InnerSilence]

Thx namreeb, your post was very insightful.

[InnerSilence]

I was doing some testing and I noticed that roof of buildings are also considered as valid walkable polys and hence are returning in the query results. Is there anyway to filter those out? If not, what solutions are there beside checking if they are connected to other places or not.

[namreeb]

I was doing some testing and I noticed that roof of buildings are also considered as valid walkable polys and hence are returning in the query results. Is there anyway to filter those out? If not, what solutions are there beside checking if they are connected to other places or not.

I experimented with this once for a bot many years ago. I did a flood fill from the different races starting positions, and removed polygons that were not touched. This accomplished my goal of reducing the navmesh size. It was more than ten years ago but I want to say this achieved a 40% reduction in size or so. I don't know what you're use case it, but I highly doubt that this is worthwhile for you. Space is much cheaper now than it was then, so I don't see that as being an issue. Moreover just because an area is disconnected does not mean that you're never going to want to query information about it.

[silverpieces]

I'm making some progress on navigation, but don't understand how to make a flight path. I can avoid obstacles on the ground, but when airborne I've just been directly pathing. I tried all the walk setting types, but none of them generate a path. There was a blog post elsewhere with how to overcome this with R/D, but the site has been removed

[charles420]

If in process trace line

[ostapus]

If in process trace line

mind to share offset for function ?

tia!