Using navmesh at my "heightmap" on server

[Christmas Eve]

First, I wanted to say how great Recast and Detour are!  You guys are the best!

I recently got a pathfinding solution working with Recast/Detour from scene data from Unity and it works great (thanks to the creators of Recast).

I've viewed the other posts related to using the navmesh as a heightmap and I know Mikko said it is costly to keep querying and locating a polygon from an XYZ.  So costly that he recommends you try to avoid looking this up repeatedly and, in fact, cache it.

My problem is this:  I'm disconnected from Unity so I do not have the luxury of raycasting on the scene to find out where to snap my NPCs to as they walk along a path.  My server, instead, has a heightmap of the terrain which works flawlessly.  The terrain, however, is just 2D and there are various other structures that a player can walk on (e.g. houses, bridges, even towers).  I've played with a multitude of different solutions but none achieve exactly what I want.  I've done raycasting in Unity on, say, level 1 of a tavern and exported a "sub height-map" of it, followed by a sub heightmap of the upper level.  While this option seems feasible, there are holes.  These 2D heightmaps all need to be seamlessly connected together so characters do not fall.  For example, the staircase from level 1 needs to butt up against the floor as you enter level 2.  Now consider a tower with a spiral staircase that winds all the way up a tall tower.  My method doesn't seem to be very fit for this scenario.

For a recast navmesh, on the other hand, this stuff is trivial!!  The walkable area is seamless and you need not concern yourself with "levels".

But, the question is, is it too expensive for me to find polygon heights every frame for every NPC as they walk about the world?  I enabled BvTrees in all of my navmesh builds.  Does that help?

If not, do you have any suggestions for me using Recast navmeshes as my 3D height maps?

I have one quick additional question....  When I get corners from findStraightPath, am I guaranteed that every position in between one corner and the next corner is over a polygon on the navmesh?  Is there no chance that straight lines between nodes ever (even slightly) clip a point outside the navmesh?  So, if I query polygons for an XZ as I walk from node to node, will I always get a closest point on a poly for which I can determine height?

Thanks in advance!

[Ben Hymers]

It depends :) How many agents are we talking? The only real way to find out is to try it and profile, but in my experience finding accurate positions on the detail navmesh is expensive but not so expensive I couldn't do it for all characters every frame - I just had to optimise some helper methods that were doing it many (many!) times a frame.

An idea for if you're finding it's expensive: do it less frequently for characters that are further away, or don't use the detail poly mesh for them at all. Another idea: split doing it for all agents over several frames so you're doing a constant number of checks every frame.

For the straight path stuff; yes, the line between two consecutive points in the string-pulled path will be on the navmesh, *in 2D*. As I think you've already found, it doesn't account for height differences which is why you need to project onto the detail navmesh. But yes, this projection will be on the navmesh (if it isn't, that's a bug).

One thing I just remembered - I don't know if this ever changed in official Recast but it's something I had to do locally. When I looked at this last I think I remember some very rare cases where the geometry of the navmesh was such that the edges in the string pulled path could 'touch' a vertex or edge, and numerical imprecision would result in those points not being on the navmesh... by passing in a small range to the findNearestPoly you'll clamp your input point to the navmesh *but* this will be clamped to the poly edge, not the detail poly edge, which results in some odd discontinuities. I had to rewrite it to clamp to the detail mesh even when the input point lay outside the poly in XZ. If you find this happening (weird discontinuities in height of string-pulled paths along navmesh edges) - let me know and I'll have a look at our implementation of findNearestPoly again!

Hope that helps!

[Christmas Eve]

Hey Ben, :)

Thank you for the reply!  Currently, I only have a few hundred NPCs but I'm planning on handling ten thousand or so by the time the game is done.

I read what you said about following the string-pulled path and that it should be always over detail polys but could be on the border and cause an issue.

I decided to keep speed in mind even though it's very early on and avoid querying all polygons in the tile. So this is what I did.

Call findPath

Call findStraightPath

Simulate a crawl between each of the points returned by findStraightPath.  In doing this:

(1) I call closestPointOnPolyBoundary on each interpolated position,

(2) I simultaneously follow along with a pointer to the poly array returned by findPath, checking to see if closestPointOnPolyBoundary works, if it fails, I move on to the next poly

What's happening is my interpolated path from point to point is ends up failing and not resyncing with the next poly from findPath so it crashes and burns.  I speculate that the reason is because of the numerical imprecision you speak of.  But, then again, it should be very rare.  And this has happened on 3 out of 5 paths I've tried.  Therefore, I think something else must be wrong.  By the way, I've tried using closestPointOnPoly() in place of closestPointOnPolyBoundary() but it also failed on the same three paths.

When I say I interpolate from corner to corner, I'm doing this (as an example):

x1/y1/z1 = 1st corner

x2/y2/z2 = 2nd corner

deltaX=(x2-x1)/50; deltaY=(y2-y1)/50; deltaZ=(z2-z1)/50;
for(int i=0;i<50;i++) {

   <check the location x1,y1,z1>

   x1+=deltaX; y1+=deltaY; z1+=deltaZ;

}

When I check a location and it fails, I assume the location must be over the *next* polygon so I increment my poly pointer.  Unfortunately, this doesn't work.  It'll get through the rest of the polygons (from findPath) without a hit.

Any ideas? :(

[Christmas Eve]

I tried this again using just calls to getPolyHeight() along the way for each increment and it did the same thing.  Then, I tried keeping track of my current X and Z as a double instead of a float and that made it work with more scenarios but not all.  As I move from one point to another in small increments, there is way too high of a chance that Detour thinks I'm off the detail mesh.  I'm really hoping to rely on Detour for heights instead of my own geometry.  I would love nothing more than to throw all of that overhead away and rely solely on the navmesh.

The only thing I have not tried yet is using the poly array result from findStraightPath to make sure that every time I reach a new corner, that I'm referring to the proper poly ref.

But, I think it would a waste of time because, when my code fails on a position, I try looping through the WHOLE array of poly refs from findPath() just for kicks, and it turns out getPolyHeight fails on all polygons in the path! :(

[Ben Hymers]

It might be less rare than you think it should be; string pulling tends to generate paths that hug the edges of the navmesh or sometimes the edge between two polys. That's the perfect place to get nasty imprecision issues! I would stay away from what you're doing.

If you're finding it's not working on positions on paths that aren't near edges, that's something I'd be interested in seeing. Do you have any debug draw of these cases? A picture is waaaaaay more useful than words to us :)

[Christmas Eve]

Hey Ben!  I was just thinking that.  I really need to visualize what I'm doing.  Right now, I'm just looking at numbers and trying to make sense of it.  I don't have a debug draw but I'm going to copy my tests and dependencies back into an SDL project I have.

On another front, do you know anything about this epsilon value in dtClosestHeightPointTriangle in DetourCommon.cpp?

static const float EPS = 1e-4f;

I double it:

static const float EPS = 2e-4f;

And I found the height of the entire path!  Not sure if I should be doing this?  Or, maybe I should at least make a copy of this function and use it only for my purpose?  Could I get myself into any trouble with strange results by doing this?

[Ben Hymers]

Mikko says it all the time - debug draw is critical! Seriously, implement it in your game, it's SO worth the time investment.

I don't know what the knock-on of altering that epsilon value will be; if you can manage to use your new value just for this use case that would probably be best. Its value looks like some arbitrarily small value which isn't really the right way to deal with floating point inaccuracy, so you might be alright changing it though (it's just one random small value instead of another!). Only one way to find out :)

[Christmas Eve]

Hey Ben,

I've been away from my code for a while on a business trip.  When I came back to it, I realized I'm not always finding heights along the string-pulled path with getPolyHeight(), even with tracking the X/Z with double-precision numbers and even with having doubled that epsilon value.  It's working much of the time but not always.

I know I need to use debug draw for my own diagnostic purposes and also so I can share visuals with people but, I have a general question....

Without even knowing any specifics of my code or seeing any visuals, what is the recommended solution for my use case?  If findPath returns a list of polygons and findStraightPath returns a bunch of corners within that corridor, what is the recommended code to extract the height of that string-pulled path through the corridor?  I'm going to set aside speed for now and I want the most accurate.  It seems like the procedure should be quite simple.

Is there a snippet of code you can point me to or, perhaps even pseudo code for the loop from corner to corner?

[Christmas Eve]

Or, even simpler yet.  What about code to just give heights from point A to point B?

If I give you a NavMesh generated by Recast and then give you all the polyrefs from point A to point B, can you give me the heights from A to B at any increment I say?

Simpler yet, I don't necessarily even have to supply the poly list; just the two points.  But I can imagine this would be *very* slow.  I'm assuming we'd have to query all polygons?  I'm thinking this approach would be out of the question since findPath already tells me which polygons are involved.

[Mikko Mononen]

How big are your coordinates? Once your coordinates are beyond 3000 or so you start to loose precision of many calculations because squaring such numbers makes the result larger than what can be fit in the size of mantissa of 32bit float.

That epsilon is ridiculously big already, I dont think doubling it will be the right choice.

If the precision is the problem, I think the right choice would be to take a look at the calculations and try to make the more local (i.e. relative to tile or query point, etc).

--mikko

--

---
You received this message because you are subscribed to the Google Groups "recastnavigation" group.
To unsubscribe from this group and stop receiving emails from it, send an email to recastnavigati...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Christmas Eve]

Hi Mikko!  Thanks for the response.  I do have a level that's 10000x10000 meters that I was using to test.  But, the other day, I came across another one of your posts where you informed the user of the same thing (losing precision after 3000) so I began using a 1500x1500m map but, unfortunately, I had the same outcome.  The other couple threads where this issue was mentioned ended pretty much in the same way; the poster was to avoid going over 3000wu and possibly using their game physics instead.  I never actually saw a solution that uses the navmesh and detail polys.

I'm not sure if you ever played World of Warcraft but, consider the towers in that game, like the Tower of Azora.  They have high, winding spiral staircases.  I want to have something similar in my MMORPG.  At first I was using mini height maps on my server but some of the geometry in some of the structures I'm adding are too complex for that.  The detail mesh is perfect if I could use it.

What If I did a search and replace in all of the Recast and Detour .CPP and .H files: "float" ---> "double"   lol... hmmm?   Sounds like a neat quick and dirty trick but I'm sure you have places where you memcpy 4 bytes for a float or 12 bytes for a coordinate (unless you use sizeof(float)), the float would be replaced with double... WOW maybe I should look into trying this. haha

As for your last suggestion, I didn't quite follow you.  If an NPC is moving from point A to point B, points A and B could reside in different tiles.  When you say local, what do you mean?  Like, start from 0 in my calculations?  I don't think it's an inaccuracy in my code.  I'm actually using doubles but then convert to float just when I'm calling a Detour function.  When my game is tracking the movement of an NPC, it uses two double values to track the X and Z.  I basically normalize a double precision vector that points from point A (findStraightPath node) to point B (next findStraightPath node) and I come up with an X adder and a Z adder, both doubles.  I can't see how I can get more accurate than this.

[Christmas Eve]

Any ideas?

I still have not made progress on this yet.  My game uses recast navigation without a hitch but I've put it on hold in search of the best method of determining the height along the string-pulled paths (without relying on my own scene geometry, which isn't available to my server).  I can see that the detail mesh is definitely accurate enough for my needs but the various queries available to me fail to always find the correct height for a given XZ.

As I stated, this is not a unique case for me.  It actually appears to be a bug in the path returned by findStraightPath, or possibly an issue with getPolyHeight.  Either way, I've proven it to be impossible to get the height along the continuous path made up of straight lines drawn from node-to-node as returned by findStraightPath.  So the waypoints inside the corridor that straightPath gives do not always travel over valid detail polys.

[Mikko Mononen]

I still believe this is a floating point accuracy issues as I mentioned earlier. I recommend to open an issue in github with a repro case that can be validated and fixed.

--mikko

[Ben Hymers]

Here's something that might help you: When you call findStraightPath, pass in DT_STRAIGHTPATH_ALL_CROSSINGS for the options - it'll give you the same path in XZ but with all border crossings with the in-between polys too, which will at least be giving you the height at those borders. Then because it gives you the poly refs too, you can subdivide the line between two sequential points and check their height on the detail mesh, knowing which poly the points are on.

If that still fails to find points on the poly, then I think Mikko is right - this must be a floating point inaccuracy problem, and a test case that we can reproduce and investigate would be very helpful! An .obj we can load into the RecastDemo, and a start/end point of a search, and whatever code you're using to check for heights along this path, would really help us nail it.

And of course.... a screenshot!

[Christmas Eve]

Thank you Ben!

I haven't had a lot of time to work on this in the past few days but this looks like it's going to work.  I used that ALL CROSSINGS flag and I get way more poly references/coordinates back and, so far I only tried half-way between the points returned by findStraightPath and I successfully got heights.  I'll try interpolating even further but I think it's going to work because, like you said, I always know the polygon to use. If I'm between B and C, for example, I know to use polygon B and so on.  

[Christmas Eve]

I've tested this further and DT_STRAIGHTPATH_ALL_CROSSINGS seems to work very well!  I can lerp toward the next corner and always find heights on the poly given to me at the previous corner.

This is huge -- it means a server need not necessarily have the entire world geometry that the clients use.

[Ben Hymers]

You're welcome :) Sorry I didn't mention it earlier!