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

User Tag List

Results 1 to 13 of 13
  1. #1
    InnerSilence's Avatar Member
    Reputation
    10
    Join Date
    Oct 2019
    Posts
    32
    Thanks G/R
    4/7
    Trade Feedback
    0 (0%)
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

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

    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?

    These ads disappear when you log in.

  2. #2
    Jadd's Avatar 🐸
    Reputation
    1475
    Join Date
    May 2008
    Posts
    2,401
    Thanks G/R
    77/302
    Trade Feedback
    0 (0%)
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    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.

  3. Thanks InnerSilence, Corthezz (2 members gave Thanks to Jadd for this useful post)
  4. #3
    Alisha's Avatar Member
    Reputation
    13
    Join Date
    Nov 2015
    Posts
    13
    Thanks G/R
    4/7
    Trade Feedback
    0 (0%)
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    You can use for this
    Code:
    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
    Code:
    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

  5. Thanks InnerSilence, Corthezz (2 members gave Thanks to Alisha for this useful post)
  6. #4
    Jadd's Avatar 🐸
    Reputation
    1475
    Join Date
    May 2008
    Posts
    2,401
    Thanks G/R
    77/302
    Trade Feedback
    0 (0%)
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Originally Posted by Alisha View Post
    ...
    Beat you by about 1 minute.

  7. #5
    Alisha's Avatar Member
    Reputation
    13
    Join Date
    Nov 2015
    Posts
    13
    Thanks G/R
    4/7
    Trade Feedback
    0 (0%)
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Originally Posted by Jadd View Post
    Beat you by about 1 minute.
    Yea I sent and then saw your post before mine

  8. #6
    InnerSilence's Avatar Member
    Reputation
    10
    Join Date
    Oct 2019
    Posts
    32
    Thanks G/R
    4/7
    Trade Feedback
    0 (0%)
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Thanks dudes, gonna give it a try now.

  9. #7
    namreeb's Avatar Legendary

    Reputation
    613
    Join Date
    Sep 2008
    Posts
    1,003
    Thanks G/R
    6/191
    Trade Feedback
    0 (0%)
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)
    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:

    Code:
            // 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:
    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.

  10. Thanks InnerSilence, Corthezz (2 members gave Thanks to namreeb for this useful post)
  11. #8
    InnerSilence's Avatar Member
    Reputation
    10
    Join Date
    Oct 2019
    Posts
    32
    Thanks G/R
    4/7
    Trade Feedback
    0 (0%)
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Thx namreeb, your post was very insightful.

  12. #9
    InnerSilence's Avatar Member
    Reputation
    10
    Join Date
    Oct 2019
    Posts
    32
    Thanks G/R
    4/7
    Trade Feedback
    0 (0%)
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    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.

  13. #10
    namreeb's Avatar Legendary

    Reputation
    613
    Join Date
    Sep 2008
    Posts
    1,003
    Thanks G/R
    6/191
    Trade Feedback
    0 (0%)
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)
    Originally Posted by InnerSilence View Post
    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.

  14. Thanks InnerSilence (1 members gave Thanks to namreeb for this useful post)
  15. #11
    silverpieces's Avatar Member
    Reputation
    1
    Join Date
    Nov 2020
    Posts
    11
    Thanks G/R
    4/0
    Trade Feedback
    0 (0%)
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    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

  16. #12
    charles420's Avatar Contributor
    Reputation
    237
    Join Date
    Jun 2009
    Posts
    231
    Thanks G/R
    12/67
    Trade Feedback
    0 (0%)
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    If in process trace line

  17. #13
    ostapus's Avatar Active Member
    Reputation
    43
    Join Date
    Nov 2008
    Posts
    167
    Thanks G/R
    1/0
    Trade Feedback
    0 (0%)
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Originally Posted by charles420 View Post
    If in process trace line
    mind to share offset for function ?

    tia!

Similar Threads

  1. Replies: 9
    Last Post: 11-28-2009, 06:49 PM
  2. How to fly and attack at the same time!
    By Glynbeard in forum World of Warcraft Exploits
    Replies: 34
    Last Post: 04-13-2007, 09:46 PM
  3. HOW TO: Get on top of the Darnassus Bank [Movie Attached]
    By Kelzs in forum World of Warcraft Exploration
    Replies: 6
    Last Post: 03-01-2007, 04:13 PM
  4. [Guide] How to not get banned using GLIDER
    By israelijedi in forum World of Warcraft Guides
    Replies: 6
    Last Post: 02-15-2007, 03:28 PM
All times are GMT -5. The time now is 11:34 AM. Powered by vBulletin® Version 4.2.3
Copyright © 2021 vBulletin Solutions, Inc. All rights reserved. User Alert System provided by Advanced User Tagging (Pro) - vBulletin Mods & Addons Copyright © 2021 DragonByte Technologies Ltd.
Digital Point modules: Sphinx-based search