Monday, July 19, 2010

Constrained Movement Along Navmesh pt. 3


The most boring topic of the year makes a comeback! I have been struggling a bit to make robust movement along navigation mesh, but I think I finally nailed it.

Why should you care?

The basis of solid navigation loop is good collision handling. For navigation meshes this means a way to handle movement along connected graph of convex polygons. That is, how to move from one polygon to another and how to handle the case when the desired move collides with blocking navigation mesh edge.

The method should also return the polygons it walked through during the movement. This is used to fixup the path corridor so that on next update we have valid path to follow again.

First idea: Raycast



My very first implementation of movement code used raycasts. I used similar iterative code as the good 'ol ellipsoid vs. trimesh collision detection. The problem with that solution was that the rays end up being parallel to the polygon edges when sliding or hit vertices when aiming for next corner. I ended up running into a lot of floating point accuracy errors and quite interesting special case hacks to get rid of them.

Second idea: Point in Polygon


My second attempt changed the whole idea upside down. I can calculate the sliding movement inside a convex polygon by clamping the target point to be the nearest point in the polygon. To handle the connected graph of convex polygons (like navmesh) we can check if the nearest point would lie on an edge which leads to neighbor polygon, and follow that until the goal polygon has been found.

While the basic idea is sound, here area a couple of cases where it does not produce desired result. Firstly there are some corner cases where it will miss potential move to neighbour polygon because it does not check visibility (see my previous post). Interestingly this is not a problem when using triangles.

Second, nasty problem is that it does not handle well the case that the nearest point is at a polygon vertex. In this case either edge are equally good candidate to follow and I could not find goo heuristic which would handle all the corner cases I had in mind.

This method is a bit similar to the jump-and-walk algorithm which is used to locate triangles in triangulation. It is known to work on triangulations which have convex boundary.

Third idea: Search


This idea extends the previous by making it breath first search instead of iterative loop. That nicely solves the problem of trying to choose good branching at each iteration, all branches are followed instead.

The search expands to all edges which touch circle containing the start and goal location (start+delta). The search is stopped when the goal polygon is found or no more polygons can be visited. In case the goal is inside a polygon, the goal location is accepted, else the nearest point to all visited blocked polygon edges is chosen.

In pseudo code it looks something like this:

// Applies constrained movement from startPos to goalPos.
// The result is stored in clampedPos.
// Returns number of visited polygons
.
int Navmesh::navmeshMoveAlong(Vec3 startPos, PolyRef startRef, Vec3 goalPos,
PolyRef* visited, Vec3& clampedPos)
{
Stack stack(16); // Tiny stack
ClosedList closed(32); // Tiny closed list
Vec3 bestPos, p;
float bestDist = FLT_MAX, d;
PolyRef bestRef = UNDEF;
// Search constraint
Vec3 searchPos = (startPos+goalPos)/2;
const float searchRadius = vdist(startPos,goalPos)/2;
// Init
bestp = start;
stack.push(startRef);
closed.add(startRef,startRef); // Self ref, start maker.

while (!stack.empty())
{
// Pop front.
PolyRef cur = stack.pop();
Poly* poly = getPoly(cur);
// If target is inside the poly, stop search.
if (pointInPoly(goalPos, poly))
{
bestRef = cur;
bestPos = goalPos;
break;
}
// Follow edges or keep track of nearest point on blocking edge.
for (int i=0, j=poly->nv; i<poly->nv; j=i++)
{
const PolyRef neiRef = poly->nei[j];
const Vec3& sp = getVertex(poly->v[j]);
const Vec3& sq = getVertex(poly->v[i]);

if (neiRef == UNDEF)
{
// Blocked edge, calc distance.
p = closestPtPtSeg(goalPos, sp,sq);
d = vdist(p,goalPos);
if (d < bestd)
{
// Update nearest distance.
bestPos = p;
bestDist = d;
bestRef = cur;
}
}
else
{
// Skip already visited.
if (closed.find(neiRef)) continue;
// Store to closed with parent for trace back.
closed.add(neiRef,cur);
// Non-blocked edge, follow if within search radius.
p = closestPtPtSeg(searchPos, sp,sq);
d = vdist(p, searchPos);
if (d <= searchRadius)
stack.push(neiRef);
}
}
}
// Trace back and store visited polygons.
followVisited(bestRef,visited,closed);
// Store best movement position.
clampedPos = bestPos;
// Return number of visited polys.
return visited.size();
}

So it is a tiny special case pathfinder. The result is movement which can quite liberally move along the navmesh and if it encounters walls it will slide. The slack is necessary when you need to shortcut a little for example when very close to the next corner along the path.

The code above is meant to perform well when you do really small increments. It aims to be faster than regular pathfinder which is tuned to perform well with potentially thousands of nodes.

For such local case you may maintain the open list (stack) and closed lists using simple arrays. There are many cases in the code which may trash your cache (accessing the navmesh data), but by using small arrays for open and closed lists you can avoid some of it. Since we expect the lists to be small, we can potentially use simple linear searches which simplifies the code.

Next Step

My next task is to figure out nice way to calculate 2D local collision environment from 2.5D navmesh. This is to be used with velocity obstacles. Then I should be ready move on porting the VO code to Detour.

21 comments:

  1. Just a thought - why not just do your breadth-first search through the corridor polygons that your pathfinding returned?

    ReplyDelete
  2. Good question.

    I have noticed that for multiagent navigation or nice curved paths the corridor is not always enough.

    There is currently similar code which limits the advancemen to the corridor called moveAlongPathCorridor(). It is one implementation of method #2, and has such problems.

    You can check the curved path case with my Paris presentation using the first navmesh demo. If you turn on 'visited' and 'corridor' you can see that sometimes that agent needs to steer outside the corridor when trying to move along curved path. And it is fine to do that, since we cah fix the corridor.

    You can also use the same movement function to fix up the corridor when you are following a target. In that case you don't have the corridor.

    ReplyDelete
  3. Question: your examples seem to deal with simple velocities (like your treating an agent as a single point). Do you do anything to handle agents with a radius (such that no part of their radius is allowed to exit the navmesh)?

    ReplyDelete
  4. I always expand the navmeshes by agent radius so that I can treat the agents as points. Makes a lot of things an order of magnitude easier.

    ReplyDelete
  5. Ahhh right I had forgotten. Yes I'm writing a bunch of sphere line segment intersection code now and yeah - not fun. However, we have several different widths of characters and have elected to have only one navmesh for everyone. Perhaps a decision we will revisit - we will see.

    ReplyDelete
  6. Sphere line intersection is the easy part. One hard problem is how do you pick a location inside the navmesh which is agent radius away from the border? It is really complicated problem alone. You probably end up not doing it and it will degrade the robustness of your solution.

    The really complicated problem is how are you going find a path in the first place where the agent can fit through. Not a simple problem. Check the paper referenced in this post:
    http://digestingduck.blogspot.com/2010/05/towards-better-navmesh-path-planning.html

    String pulling is a lot more complicated too, but kinda doable, look for extended funnel algorithm.

    You maybe able to get away with simple tweaks here and there, but it is really complicated problem to get right. You have been warned :)

    I encourage to use multiple meshes and implement streaming to keep the navmesh memory usage low. It might not be fun either, but IMHO it is much more manageable problem.

    ReplyDelete
  7. Hello Mikko,

    I converted recast / detour debug drawing to function with the Ogre3D engine and adapted the crowdtool as my basis for managing all agents i use in pathfinding for the moment.

    Based on this i started running through my level and sending agents.

    It works very well. However i noticed two rather small issues which I wanted to ask you about.

    The first may even be related to this. In case of having an agent walking/running through a small passage (really small but as the navmesh is generated regarding the agent's radius it is obvious the agent should fit through there) this often seems troublesome, as they will get stuck or slow down greatly while going through the passage. I've noticed this a couple of times and I don't think the issue is related to my code so I wanted to inform you. However this is not crucial.

    What is more crucial is the problem that I am having with agents never really stopping. If i send them to a target, upon arriving, they tend to "slide" further with some velocity (visible by vector) into one direction. It makes no sense why they would do that, it looks like they were on ice and they just start sliding in one direction with a steady velocity for some seconds until being too far away from the targetpoint and moving back, sliding in another direction after getting to the point.
    To get sure it is not my code causing this, i made a halt function setting the agent's position as move target (just one time - then waiting). However, halting an agent still makes him slide.

    Did i forget a parameter or anything? I am a bit confused as to why this happens. My unit scaling is 1 world unit = real meter. Radius being around 0.5 and height 1.75.
    I thought it may be due to my scaling, but i found nothing to prove this.

    Btw, I found no forum, no wiki, no contact info, nothing - so I ask this here now :) hope it's okay

    ReplyDelete
  8. Those two issues should been handled better by my latest commit R241.

    The problem was/is how the local avoidance distributes the samples. The earlier code did not add a sample for stopping, which made the agent to drift away, and I also improved how the samples are distributed, which makes the method handle tight spots better.

    The code will still slowdown the agent quite a bit when the agent approaches a choke point from an angle. I don't think there is a good way to fix than. The algorithm sees this situation almost as if the NPC tried to walk straight towards a wall.

    Let me know if the new changes made things better for you.

    I think there are quite a few ogre folks trying to use Recast & Detour. It would be nice if someone who has gotten it to work, could make a example code how to query meshes from ogre and maybe share the debug draw code too. It seems it is not that complicated, but I have had quite a few questions about it.

    Also a note of warning, I'm still changing the crowd manager quite a bit.

    ReplyDelete
  9. Yes we already have the pathsmoother/string puller algorithm working - it basically has to lie a "cylinder" against each side of the funnel as you progress along your path when trying to decide which corners to preserve.

    ReplyDelete
  10. I just spent 5 hours going through all the changes that were made in recast /detour to work in my application. Yes, that's a long time ;) but all the extra draw calls and all the changes that were made on the crowdtool etc. took me a lot of effort to adapt the existing code. You made really a lot of changes considering my svn checkout was only like 2 months old ;) but that just shows how active the development is!

    So after those 3-4 hours of chaning code I couldn't position my agents anymore. Fun story - I was so invested in finding errors in my code, that I forgot to actually export the navmesh again with the new recastdemo :) which i then did and it worked! 1 hour of anger just because of such forgetfulness!

    My agents are still not moving. I will get this to work tomorrow and then post about how it is working now and also about my code in regards of ogre... I think it might be a bit too messy to "release", I rather did it hack-ish, just as I do if I am prototyping. Slow performance also exists in matters of debug drawing.

    Oh and in case you do not know - there is a full port of recastdemo to ogre, with its own repository (svn). I took a look at it and found it not useful for my case, so i converted it my way (debug drawing) and also i prefer to use the original RecastDemo. However there is 2 big threads in the ogre forums purely on Recast / Detour. If you didn't know that already. And if someone asks you about ogre + recast / detour you could link them to the threads and the svn


    SVN of this recast demo (not made by me) is: http://bitbucket.org/paulwilson77/ogrerecast/wiki/Home
    This is the forum thread for it:http://www.ogre3d.org/forums/viewtopic.php?f=11&t=57487

    This is a more general thread in the ogre forums regarding recast / detour that might be of interest to Ogre users who wanna use it:
    http://www.ogre3d.org/forums/viewtopic.php?f=16&t=52455


    What do you mean by "query a mesh"?
    For picking i use MOC and use the query flags used for my mesh.
    If you mean using an ogre mesh as input for the navmesh generation - I must disappoint you. I exported an .obj file from Maya that I use in RecastDemo to generate my navmesh. As well as i export from Maya to Ogre. The navmesh and the exported ogre mesh are of identical proportion. Visualization of the navmesh fits.

    Oh, btw. just in case you are interested: This is a some weeks old screenshot from my implementation:
    http://survival.lukasmeindl.at/images/1/11/Navmeshwin4.png
    This is ingame in debug view, using the Ogre3D engine.
    I use one Vertexobject (Ogre ManualObject) for my crowdtool and one for my navmesh. Many things could be made more efficient of course, but as it is it works for me ;)

    Oh and I will report back if I made progress...

    ReplyDelete
  11. Hey Mikko,

    1. So finally I got this to run... I can report you, there is a significantly smaller amound of sliding occuring now. The agent however is still moving around the target a little, never really stopping completly. I guess what we would need (at least from my view this would be helpful) is some kind of check if the distance to the target is smaller than a certain small amount and then stop going on with the pathfinding in case this is true.

    But really, it is much much better with the new update. It took me very long to apply it because i basically copied the whole crowdtool and manager over, instead of deriving my own classes as subclasses of them. I will probably go for this soon. So much about my code being "dirty" ;) I told you.

    2. Oh and now I got another problem. I used to set my move targets on each tick. I need this for pursuing a target as well as for the movement of my playercharacter. BUT with the new version this will make all my agents stop and not ever start moving. This took me really long to figure where the problem is, my code seemed to be correct here, then i turned on the Recast Demo and tried it there (simply by creating a crowd and in move mode clicking as fast as i could on a position: Result is, they will never really start moving. Is this planned behaviour? I thought I'd better ask, however it seems quite like a bug to me.

    3. Moving through small passages now works correctly and nice, they even walk around there very smoothly and nice. Really perfect as far as I tested it.

    4. As well as single agents trying to go to a target, also crowds will never really stop moving and start pushing each other away a little or sliding in a direction slowly as group.


    I hope you can answer to this soon. Especially on 2 - because this is quite essential for my project to move on ;)

    Thanks a lot!

    ReplyDelete
  12. Hi Lukas,

    Good to hear that you got it working. And thank you for the patience. Few more updates and the crowdmanager should be in good shape.

    I think your approach is good, it is just that my code is still a bit messy too :). Every game will have it's unique needs for crow management, and I will not try to satisfy them all.

    So, my idea is to provide a set of classes which makes it easier to implement the agent movement and an example implementation in form of the CrowdManager. I expect people to use it as quick starting point to get things rolling, but you will most likely end up rewriting it as your project matures.

    Do you have some examples how to make the agents never stop? I was able to repro it few times when the movement target was right at the border of the navmesh.

    Currently I do not handle multiple agents trying to reach the same target in any way. They are basically trying push each other away and fight for the space, as you noticed. This is another really complicated problem. More on later once I get my current TODO list slimmer.

    If your agents are just following a target, you should not replan the path. It is possible to patch the path corridor the same way it is patches when the agent moves. I will add this functionality there.

    When a new target is set, the CrowdManager currently makes the path null (target = current pos) and fires a path request. There is currently artificial limiter on how many path requests are made per update. As you can see from PathQueue::update(), only one path update is processed for very 4 frames. No wonder if your agents are not moving :) The path queries never catch up.

    So, a temporary solution is to flush all path queries every frame (which is super expensive!) until I get the path corridor target moving code done. Just remove that 'break' and the delay counter.

    ReplyDelete
  13. I welcome the idea of this set of classes.

    I just completed reintegrating the crowdtool/crowdmanager, this time by going the way of derivation.
    It was a very painful process because i had to exclude a lot of files responsible for OpenGL drawing, which I did not want to include into my project and didn't want to compile.
    But now I am done and I hope updating will be easier for me now, although I can already sense the upcoming pain of integrating big changes in the feature, which are sure to come :), but I will go through it.

    Anyhow:
    The temporary solution you suggested, I just tried and it is just the same as before. I removed break and the update limiter.

    I couldn't figure by myself so far what other changes could be needed, do you have any idea?


    Also about the single crowd member never stopping - it works fine in the recast demo, but in my application which basically uses the same navmesh and code, it didn't stop, but I can check on that once i fixed the update issue.

    ReplyDelete
  14. *future instead of feature


    Okay i m doing a double update now and now the character moves super-slowly. Taking from this i assume that what you suggested me as temp fix fixes the "having a valid path" problem, but however somewhere the velocity and acceleration seems to be reset nevertheless when having a new path. Could this be the case?

    ReplyDelete
  15. I would first check that the steering velocity is ok. That is, temporarily disable local avoidance. If that is the case, then double check the obstacle avoidance parameters. I have changed them few times.

    ReplyDelete
  16. - Debugged velocity in "// Calculate steering."
    Is always zero
    - Disabled Obstacle Avoidance where "m_obstacleQuery" is used - velocity stays zero
    - Disabled handle collisions - still no velocity

    There is also no blue and black vector drawn in my debug view. Usually it is always shown correctly. So i guess i debug-checked the velocity correctly (0 vector on velocity).

    I guess disabling the collision and obstacle avoidance wouldn't help anyways since the steering velocity is 0 from start.

    I could further check inside the steering velocity calculations, but if you have any further ideas why velocity stays 0 for constant pathing refreshes i welcome that. I welcome any temporary fix for this. And of course i look forward to the release of the ability to patch corridors which should make constant refreshes performant and my temp fix redundant :D

    thx

    ReplyDelete
  17. The only thing that immediately comes to my mind is that MAX_QUEUE should be at least as large as max agents.

    Other than that I would need more information to get further. Check the corner and steering velocity calculations to see if there is something that sets the velocity to zero.

    I will have some Recast time of friday, I will take a look at the follow thing then.

    ReplyDelete
  18. After debugging a lot i found out the following:

    The target position for the agent isnt set correctly.

    Further i found out this is due to the behaviour inside the function updateMoveRequest(...).

    The folling happens:
    1. All move requests get updated. But they are each updated just for one state. For example MR_TARGET_REQUESTING.
    2. Next time the state is MR_TARGET_WAITING_FOR_PATH, but the path requests are updated at the bottom of the function.
    Logically this way it can never happen that a request is completly processed in a single update step.

    So i changed the function to this:

    http://pastebin.com/TgQDYtxV

    and to sum it up:
    Problem i saw:
    - Not possible to process move request fully in 1 step --- because: if-else instead of if + if and also an update has to be between. My solution: First run through all requests for MR_TARGET_REQUESTING. Update pathqueue. Run through all requests for the other states.

    Sorry for being repetitive :). Well, maybe this is not a bug, I can't tell for sure since i m no expert on the functionality of this code, as you are. But it seemed wrong to me and with my change which seemed logical to me, i immediately got 3 corners for my agent now (instead of 1 which seemed to be himself ? ), and also i get a blue vector. With uncommenting everything i commented out before, i now also get a black vector shown and am having correct movement. And in debug build the agent stops at the target. WHOOO! (in release however he seemed to get very very rapidly shaking on close distance before stopping after a few sec)

    Still: Happy times.

    Now i remember you said flushing all path queues causes very bad performance. I ll check on my current performance later, when my eyes won't feel like someone pierced them with a burning piece of sharp metal. Yes, do not buy a 15,6" laptop if it has 1920 x 1080 resolution. Really, do not. Your eyes will hate you and torture you with pain and always getting tired fast. Well back to topic. The solution you mentioned for this performance thing (which i did not fully understand) will have to come from your side right? So until then I have to wait, anyways.

    Thanks so far.

    ReplyDelete
  19. awesome.

    Now i made everything on my code side like it was before updating my recast dependencies. So now i m setting my position as target position again, if not moving. Now it works! now it all works! The agents stop when they should, the agents follow correctly, and i can move my character nicely. The code updates also make a visible difference. I liek.

    About performance: So far it is really acceptable, i lose about 4% fps as far as i checked.

    ReplyDelete
  20. Lukas, check the SVN. Crowdmanager now supports two functions to deal with targets: requestMoveTarget() and adjustMoveTarget().

    The idea is that you first call requestMoveTarget() when you start following something and then on each frame call adjustMoveTarget() to adjust the move target.

    The adjustment function expects small increments. The adjustments are stored as move requests and update along with them every update. You can also adjust requests which are currently being processed, although the max adjustment is not too big (32 polys currently).

    You can test it in the recast demo by using the "Move Target" too. Bad naming, I know :) I need to clean up the test a bit.

    You probably need to implement some kind of logic to check of the path corridor target deviates too much from the target you are following and fire requestMoveTarget() in that case.

    There are some cases where the target moving could be improved. For example if you have quite small tile size and you zig-zag in an open field, then some of the corners are not always optimized away.

    We probably should move this conversation over to google groups [1] as it might be useful for other folks too :)

    [1] http://groups.google.com/group/recastnavigation

    ReplyDelete
  21. Mikko, I'm currently very busy with my study (unfortunately there I do not work with Recast/Detour ;) ) Once i will have some space to breath again, I will do an update on the dependencies and check what has changed. Maybe I can also provide my drawing functions for Ogre, if I manage to seperate them in a "nice" way from my current managment classes. I can also try to design a more generic approach of how to use the Recast system for my game, using the new functions. Maybe I can also then give away these to be used in connection with Ogre.


    By the way, I am also thinking of applying some changes on the way the character moves over the navmesh. I use WASD keys for movement (relative to camera orientation in xy plane). The old system was very responsive. With the navmesh it feels like sometimes you do not have full control. I thought of some changes that could be made to make it feel a lot like a fully responsive system, as if using physics, but still using the navmehs for moving (thus overgoing the problems of being able to move somewhere where actors cannot move, if using physics , or movement speed differences etc.).

    When I have had the time to apply the updates, I will make a thread in the mentioned link.

    By the way, I was looking for something like this discussion site for a long time, and I just could not find it. I am not familiar with those google sites. Also i seemed to have overlooked it a couple of times on the main page of the google code site. Maybe you should link to it in a more emphasized way (also under wiki/links), I think other people might also have issues finding that. (or I was just blind)

    ReplyDelete