I have implemented the navigation-loop stuff, simple steering, simple dynamic constraint, and simple collision handling. I need to rethink the way stuff is organized so that it is easier to grab the necessary code to your own projects.
It's always so amazing when it works the first time, even if it just barely does.
Wow, its look really good! keep up the good work!
ReplyDeleteKeep on the good work Mikko !
ReplyDeleteI'm quite amused 'cause I'm currently at the same stage on rebuilding the navigation part of Golaem Path on top of our revamped environment representation !
looks like I need to throw away big (and buggy) part of my code. When do you plan to insert it into Recast?
ReplyDeleteThanks!
ReplyDeleteClodéric, are you guys still using navmesh of sorts or are you moving to different direction for the representation?
Yakov, I will submit something this week, but I think it will still take a while to make it good and usable.
I currently in the stage of trying to get all the stuff in. Then there will be a couple of rewrites to make the code easier to plugin to your existing projects and I bet there is room for optimizations too.
The path choices made at 0:35 seem kind of odd. Nobody goes through the middle gap? Or is that blocked and I can't see it?
ReplyDeletenothings, it is the famous problem with navigation meshes.
ReplyDeleteIn Detour the A* graph is build so that the links pass through the edge mid points between polygons. And shortest path along is evaluated through these points. Sometimes this produces odd choices, especially when there are large and small polygons next to each other.
Here's a blog post describing the situation and one potential improvement:
http://digestingduck.blogspot.com/2010/05/towards-better-navmesh-path-planning.html
That visibility optimized version is on my (frustratingly long) todo list.
There are several more accurate solutions too, usually in form of shortest geodesic path, but even the papers which promote their solution as efficient are at most siggraph realtime efficient (i.e. not for practical use).
It is a problem I'm constantly looking to solve, but I have not yet found a good solution to it.
In fact we're switching from multiple 2,5D navmeshes to a full 3D navmesh.
ReplyDeleteConcerning the pathfing problems of navmeshes, I think a good option is the following:
- use the middle of edges as roadmaps nodes
- have a good path optimization (for example, our path follower perform a decent implicit path optimization)
Clodéric, How do you differentiate 2.5D an full 3D? Are you still using the geometric method to build the mesh?
ReplyDeleteSome people have used Detour navigation raycasts to optimize the path results and have had good results with it:
http://groups.google.com/group/recastnavigation/browse_thread/thread/867a1065aafd8c23
Can you tell more about your path optimizations?
In the current version of Golaem Path, The 3D representation of the navigation space was in fact several overlapping 2D navmesh-like structures. Optimized but sometimes difficult to explain and inducing a small overhead when dealing with the overlapped sections.
ReplyDeleteOur 3D mesh is still an exact geometric representation based on the input geometry.
Concerning our path follower, I can't tell much but its relatively similar to what you use (or at least presented at AIGD10) : try to reach the farthest point in the path that's reachable in straight line using some form of raycasting on the the surface of the navmesh.
"Sometimes this produces odd choices, especially when there are large and small polygons next to each other."
ReplyDeleteUgh. I've only ever done A* on grids, which don't really have this problem (though they may require more effort in string pulling to get quality paths). I hadn't realized the error induced for navmeshes were so easily visible. That really kind of undermines the appeal. Hmm.
I read the paper linked there previously, I think (if it's the one that tries to directly solve for wide objects and to do so requires a true delauney triangulation). That requirement would seem to make tiling difficult, plus I dunno the runtime overhead.
I guess recast was trying to avoid expensive precomputation, but am I right in thinking there isn't any known even-arbitrarily-expensive precomputation that can "fix" this and give true (non-Siggraph) real-time performance for the path find?
- stb
Hmm, no, I take it back, grid search would make the exact same error, and string-pulling doesn't help, visibility/raycasting is required to fix it.
ReplyDeleteNothing, depending on your application, I think in practice it is not as horrible as it looks and sounds
ReplyDeleteI often find that the shortest path is more problematic than the problems caused by polygons. For example it is really hard to make guys follow roads efficiently. You can tinker with weights and stuff, but it will look at at some point anyways. Social rules + A* does not compute well.
A* on grid is more miserable as on polygons. There is a class of pathfinders called any angle pathfinding (theta*, etc) which tries to solve this. If you want good straight path on a grid, then you will need to calculate distance field (i.e. fast marching with eikonal stuff), and that is beyond realtime again.
So the bottom line is that for games, there are only approximations available. I think the visibility optimized thing or something similar should improve the situation a notch. Plus it seems that it is necessary to optimize the path corridor at runtime anyways.
Hmm. I don't have any real experience with road-following, so I suppose that's possible. I seem to recall playing with something like a 4:1 weighting ratio in some test cases and getting reasonable results, but I'm sure there's probably busted cases like a road that loops back.
ReplyDeleteAnyway, obviously all we care about is visually sensible paths, not optimally short paths. It's just that IMO the only reason we've been using A* in the first place was to find the optimally short path, since if you do find the optimally short path you guarantee the agent doesn't do anything overtly stupid (although it may be surprising). So I'm a little hesitant to accept the idea that using A* to compute a (potentially visually poor) approximation to the shortest possible path, and then trying to fix that up, is necessarily the right thing, since we're already hobbling A* from doing the right thing (shortest distance under any human-visible metric).
Then again, as you say, maybe this is the best we've got.
-stb
@Stb, I used to think that you must get the path correct too. But the more I have worked on the whole problem [1], the less I have come to appreciate the correctness of A*.
ReplyDeleteI'm not sure how to explain it, but here's one try nonetheless. Pathfinding through the static world structure (=navmesh+A*) is a solution that is valid at one single point in time. The moment you advance the world state by a delta time, the solution becomes a good guess. So even if you calculate perfect path the first time, it will become imperfect the next frame.
There are tons of literature which describe navigation just as graph + A* + string-pull and stops right there after you have the nice straight path figured out. In practice, that is just a tiny part of the problem and actually not very good formulation of the problem at all. The picture of a tight rope dancing naked scotsman in my presentation references to this misconception.
My goal is to also take into account the dynamic changes in the game world and at the same time try to make it fast. Dynamic changes can happen at many levels (static graph, other moving agents, etc), and they all undermine the perfection of the initial perfect path. Making things fast means that I need to split the workload to similar sized chunks to make the processing more parallel.
The stuff I have worked on starts to handle multi-agent situations pretty well. I almost have solution to the the changes in the static navmesh too, but there is tons of work to refine that.
On the speed side of things, I have a lot of work to do to fix the A* so that the work it does per call is much more manageable. In think in the future it will be some kind of hiearchical search. I have had a lot of good progress on making customized searches which work on fixed set of local data [2], [3].
That sort of LOD search is yet another thing that will make the paths less perfect.
So that whole process has made me to think that the initial A* path does not matter much. To me it is the first rough guess and linearization and simplification of the problem, much like broad phase in physics engines. Then based on how things evolve during simulation, you refine the results and adjust.
Sort of teleporting back to your initial observation. If you desired a group of characters to move along similar paths, it would be better to first find path to the goal from one of the character's position, and the the others would find path to that character's position. That would lead to imperfect paths, but the characters would behave similarly, which is probably the desired result in that case. Modeling behaviors is hard.
Navigating around is huge pile of work to do, and adding meaningful behaviors on top of that is a pile several magnitudes larger on top of that.
--mikko
[1] My "solution" to the whole navigation problem is dubbed Navigation Loop: http://digestingduck.blogspot.com/2010/07/my-paris-game-ai-conference.html
[2] Local navigation grids: http://digestingduck.blogspot.com/2010/03/local-navigation-grids.html
[3] Constrained movement along navmesh: http://digestingduck.blogspot.com/2010/07/constrained-movement-along-navmesh-pt-3.html
thanks for your thoughts, i guess that makes a lot of sense as a big picture.
ReplyDelete-stb