The bad news is that the performance is bad! The good news is that it's ok.
There are two times tracked in the above picture. The red-ish line shows how much time is spent in the brute force RVO sampling, and the lime-ish line shows the time taken by the total navigation loop calculation.
My goal is to get this case to around 0.5 ms, and I think it is doable.
So what youre saying is that if you improve the performance of the RVO, then the total time will pretty much follow (according to the graph).
ReplyDeleteAnyway, looking as useful as ever. Great work!
Yes. That difference is probably a quarter of a millisecond. And that is the the time spent on optimizing the path corridor, finding next corner and moving along the mesh plus some house keeping.
ReplyDeleteHi, I discovered your project few days ago and I've a question.
ReplyDeleteCan I pathfinding units with different size on the same navmap?
For now I think(maybe I'm wrong?) that is possible only if you create a second navmap for the new unit size...It would be better if different units can coexist in the same map.
Anyway your project is great and very useful for me :) thanks a lot
Andrea, only one units size is supported per generated navmesh. If you have a couple of almost same sized units, often using the largest size is fine for all. Also if the unit sizes vary greatly, then using the second navmesh is usually faster in practice too. Supporting multiple units sizes on single mesh complicates the algorithms a lot.
ReplyDeleteI'm trying to do that... My idea is to write an online correction algorithm that do this:
ReplyDelete1) Create path to end point
2) For each waypoint and some random points along the path calculate wall distance
3) If unit radius is greater than wall distance, move unit along the normal of hit point to fix the distance and set a waypoint.
4) Recalculate wall distance ... if unit radius is again greater than wall distance, put the tile that contains original point into exclude list
5) loop that 3-4 times before sending failure.
In this way I think that we can build a list of tile that can't navigate by a unit with that radius.
Once stored these info in every tile we can have similar performance.
One more question: Is always tile width related to maximum size unit can pass on that tile? Can I build these info with an offline method?
That sounds like a lot of trouble.
ReplyDeleteThe first problem you encounter with multiple agent radii is that how do you determine if a point is navigable by the unit. The next thing is how to find a point which is navigable. The second question is already quite complicated. By navigable I mean a location on the navmesh which is required distance from walls.
Then you need to do pathfinding. This means that as you do your A* you need to always check if the agent can fit inside the new polygon you expand to. The finally, you do the string pulling, gladly there is existing algorithm which provides good starting point.
The best method I know so far is this:
Shortest Paths with Arbitrary Clearance from Navigation Meshes
http://graphics.ucmerced.edu/projects/10-sca-tripath/
Compared to the single agent navmesh I use, that above looks really complicated. And it seems really slow too in practice.
Pathfinding is one quarter of the whole navigation problem. Path following is complicated matter too. Plus you often need bunch of other features too for a game.
My solution to path following is the Navigation Loop (see few June/july posts on this blog). You want to build navigation system, which solves 99.99% of the cases.
My suggestion to you is to profile. Basically, just implement you idea and try to get it working in your game. Then profile it. How much slower it is? Then compare how much more memory you would need for the second navmesh. It usually is not much extra memory, but it makes things fast and simple. Plus you can control the memory pretty well using the tile mesh (just load the data you really need).
Given the alternatives, I think using one mesh for different units sizes is not worth the trouble.
Oh, and one more thing. Roland Geraerts [1] has some interesting paper on hte subject too. There are quite a few things in that method which does not please me, thought. Like how to create the data so that it covers more than just a 2D plane. And the performance is not impressive at all (3.56ms!)
ReplyDelete[1] http://people.cs.uu.nl/roland/
Thanks a lot for help, I'll have a look.
ReplyDeleteNavigation loop isn't suitable for my problem, if a unit can't pass through the best path the only way to find another path is to exclude the polygon from the search.
That's the first time I see those algorithms in practical case, I have no idea of what is "performance".
The only way I have is to try various solution, I've already implemented multiple meshes since my first reply, it's so simple doing that and memory goes fine, but I'm curious to try other solutions for the problem :) I think that can be called youthful curiosity.
The above paper [1] describes a way to adjust the navmesh so that you can precalculate what is the max agent radius that can pass a triangle (local clearance triangulation).
ReplyDeleteBy performance I mean how much time it takes to calculate the results. Looking at the timings given in the above mentioned papers (both [1] and [2]), radius expanded navmesh like the one used in Detour is over 10 times faster. Unless you are running out of memory, I think multiple navmeshes are worth it because of the speed.
But, that should not stop you trying! Youthful curiosity is good. I recommend studying and testing the method described in [1] and [2]. I'm interested to see what you come up with. Also if you find other good papers, let me know.
Be aware: If you start to work on the path following and trying to make multiple units to avoid each other, the whole problem changes completely!
[1] Shortest Paths with Arbitrary Clearance from Navigation Meshes: http://graphics.ucmerced.edu/projects/10-sca-tripath/
[2] http://people.cs.uu.nl/roland/