findStraightPath: Elevation ignored if path doesn't turn

[GoogleCodeExporter]

In findStraightPath, the apex does not change unless a right or left turn 
is needed to get to the next portal. 

The problem is that this can cause some important changes in elevation to 
be ignored. For example, if your start point is at the top of a stairway 
and your endpoint is not right at the bottom, but several meters from the 
bottom, the path returned will be floating far above the ground when it 
passes the bottom of the stairs. (see attachment for example)

To fix this, I'd propose that after finding the straightpath you run 
through a 2nd pass where a triArea2D check for changes in elevation happens 
at each portal, and if the area is greater than X or less than -X, push a 
new apex.

However I'm afraid this may cause a speed hit due to not only the 
additional triArea2D calls, but the determination of the elevation at the 
edge midpoint that the path passes over.

Original issue reported on code.google.com by seaninaf...@gmail.com on 15 Nov 2009 at 12:08

Attachments:

• [detour elevation issue.JPG](https://storage.googleapis.com/google-code-attachments/recastnavigation/issue-19/comment-0/detour elevation issue.JPG)

[GoogleCodeExporter]

What you inspected is indeed expected behavior of the algorithm. What you 
suggested
would work in some cases, but because of the detail mesh, there still would be
certain locations where the path either passes through the terrain or is 
hanging over it.

I'm not 100% sure what would be the best choice. I think it is more a cosmetic 
error
(moving along navmesh is kind of 2d problem), and calculating exact terrain 
following
path for the whole length is really inefficient. Of course it depends how you 
use the
path.

My preferred way to use the findStraightPath() is to just query the next few 
points
(pass array size of 2) and use that to steer towards the goal. It allows the 
agent to
deviate from the actual straight path if necessary. 

I did one test earlier where I sampled the height of the path at constant 
intervals
(just for visualization purposes) and it worked well, look at the picture at 
this post:
http://digestingduck.blogspot.com/2009/08/height-detail-mesh-progress.html

Certain things were a bit annoying to track, I think I could provide sample 
code how
to do that.

Original comment by memono...@gmail.com on 15 Nov 2009 at 10:00

[GoogleCodeExporter]

I don't think passing a small array would address the problem I show in the 
picture, 
because the path detour returns only has 1 point (i.e. it goes directly to the 
end).

The example you show of height sampling of course looks good, but that specific 
mesh 
wouldn't uncover this issue for 2 reasons: 1) there are no "stairway-type" 
changes in 
elevation, 2) your path makes a few turns. Again back to my example picture, if 
I set 
the end point so that it's not reachable in a straight line, the extra apexes 
will 
cause the elevation to be much more accurate on the returned path. The issue is 
only 
on straight-line runs.

Anyway, I'll try to throw something together to resolve this issue for my 
specific 
application and I'll send you what I wind up with if it seems speedy enough - 
maybe 
you can incorporate it as an optional alternative to findStraightPath

Thanks for your help, and keep up the great work!

Original comment by seaninaf...@gmail.com on 17 Nov 2009 at 1:27

[GoogleCodeExporter]

In that example picture, the path is hugging the detail mesh. That particular 
method
would also work in your case (even if it is expensive).

I think I should have elaborated my just-few-points example. Basically I use the
straight path to generate a good movement velocity, which in my case is also
flattened to 2D.

What is your use case for the straight path?

Original comment by memono...@gmail.com on 17 Nov 2009 at 8:06

[GoogleCodeExporter]

Do you have the code you used to make the path hug the detail mesh? That's 
pretty 
much what I need (if it can be done fast enough).

Unfortunately, the engine I'm using doesn't handle gravity at all, so I can't 
just 
feed in a velocity and let the engine pull agents to the proper height, I have 
to 
feed in a sequence of x,y,z values for any movement. 

So, an example use case would be the picture I submitted - I have a creature at 
the 
top of the temple steps and I want to tell it to move to the end spot down by 
the 
fountain. If I use the path returned by findStraightPath they will just walk 
through 
the air in a straight line. I need at least a couple extra points at the top & 
bottom 
of the stair angle so that they stick to the surface of the stairs.

If this is asking more than this project was intended to handle, just let me 
know. 

Original comment by seaninaf...@gmail.com on 21 Nov 2009 at 8:41

[GoogleCodeExporter]

I have made the assumption that you would use the physics geometry to base the
character firmly on ground. The detail mesh is there to allow you do to better
initial guess for that projection (i.e. no need to project characters which our 
out
of view, etc).

The Detour navmesh API has function called getPolyHeight() which allows you to 
query
the detail mesh height at given location within a navmesh polygon.

When you move along the path, you need to keep track of when you exit a navmesh
polygon to be able to query the proper height. Unfortunately it is a bit 
cumbersome
currently and there is no code which does this book keeping for now.

There is one function which waits to be implemented whose purpose is to help 
stepping
along the path. That is, based on movement delta, check on which polygon edge 
the
step exits and move the "current" polygon to the next polygon (can be through 
many
next polygons) along the corridor.

Original comment by memono...@gmail.com on 21 Nov 2009 at 10:20

[GoogleCodeExporter]

Yes, it seems I was trying to get the library to do more than it was intended. 

I will look at using getPolyHeight() to make the path hug the detail mesh.

Thanks for your help.

Original comment by seaninaf...@gmail.com on 22 Nov 2009 at 8:17

[GoogleCodeExporter]

There is now a path iterator code in the latest SVN version. This does almost 
what
you asked for.

Original comment by memono...@gmail.com on 6 Dec 2009 at 8:35

• Changed state: Fixed