I have previously calculated the A* node locations on the fly to save memory. That is when I expand to neighbour polygons, I calculate the edge mid location on the fly. While profiling the filter change proposal, I also tested caching the A* nodes locations. This gave me the benefit to also being able to draw them.
There was one particular location in one of my test levels which always bothered me. I had plotted it out few times in Photoshop, but now I can finally see what was going on.
The above picture also illustrates the reason why navmeshes sometimes produce unoptimal paths. The A* is actually ran on that "skeleton". The problems pretty much always occur where small and large polygon are next to each other.
To answer the question in the picture. That detour is selected because the route along the skeleton is shorter than crossing through that large polygon. When you see the skeleton it is easy to understand, but when it is not visible, it looks plain odd.
Have you tried to use the approach from TA* [1] yet? TA* gives some overhead as you might need to trace Polygons multiple times and their close-list replacement is a binary tree that you need to trace back to the root (at least thats my idea of how to do it). I haven't compared it against a plain A*, but it's guarantied to find the shortest path.
ReplyDelete[1] http://skatgame.net/mburo/ps/tra.pdf
Greetings, Mene
Mene,
ReplyDeleteI know the paper, but I the trace back sounds so scary that I have not bothered to try that.
I had an idea earlier where the pathfind would be combination of A* and funnel algorithm. That way the previous nearest corner would be always shortest, very much like how the dead reckoning distance field calculation works. I was not just sure how to handle the final segment where the "current point" is a whole edge.
This probably does not make much sense without a picture :) I think one of the any-angle pathfinders used similar trick.
Yes, the trace back is sort of scary. In my final approach I'd also like to include D*-lite or something similar, which seems to be impossible with the TA* approach.
ReplyDeleteAlso I think finding the shortest path is often irrelevant. I currently distinct two cases: (1) the agent "sees" where it should go and takes a detour (like on your image) and (2) the agent doesn't see the target. (2) would be the case if the agent walks through a forest. In my opinion (2) is irrelevant as humans would probably take detours, too. Thus a (good) approximation to the optimal path is sufficient. However (1) should be prevented because... well it looks stupid ;D
I think my current idea is the same as your earlier idea. In TA* instead of following both branches when a cell that's in the "closelist" is encountered I use funnel to determine which is better. As a start/end point for the funnel I conciser the previous cell where the detour has started and the best cell after the cell in which the the branches reunite (or the respective edges).
Just an idea so far, but it should prevent (1) and allows the use of D*-lite.
By the way, have you any further references for the "Weirdo spline hack" you use for smoothing the agent movement?
The case 1 becomes irrelevant too when you add multi-agent navigation. There the agent may be pushed around or your movement style makes the agent to take detour.
ReplyDeleteThe result is that even the best initial guess does not matter. Though, I think the initial path should be as good as possible, without adding too much extra work.
My current grand scheme is that at the highest level, I would do path find across the tiles, and initially just figure out which tiles to use.
Then I would find path the next few tiles ahead only. When new tile is reached, another is searched forward. The idea is to limit the A* queries to as little data as possible.
On top of that I would like to do local refinements as the agent follows the path. In the RecastDemo crowd test I use raycast a long the navmesh for these fixes. Basically it is doing your case 1 on the fly. I don't know that kind of performance hit it gives yet.
I have noticed that things get quite a bit more interesting when you add the movement into the equation. Suddenly you cannot trust anything anymore :) When you add dynamic changes to the navmesh to that, there is even less trust left.
So in my scheme when data changes, the path data changes should be relatively small and thus can be recomputed. IIRC D* lite needs open/closed list for each path too.
You can find a bit cleaner implementation of the weirdo spline hack in RecastDemo. It also sports some debug draw so it is easier to understand.
The basic idea is that first I calculate tangent of the next corner. This is usually calculated as ta = p[i+1] - p[i-1], I I further scale the tangent so that its' length is half the distance to the next corner.
The goal was to find a steering direction which would anticipate the next segment so that if an agent has limited acceleration, it will not overshoot the corners so badly. It usually works well, sometimes it anticipates too much, but I've never seen it fail.
Yes, the more agents you add the less likely it is that the initial path (or even the channel) will be followed. And the less relevant is how good the paths are (for me), since a human observing it will simply loose track of all the agents.
ReplyDeleteAnd I also like your approach with using funnel to find the next few waypoints (using it, too).
The problem I meant is more clear in the TA* paper on p. 65 where the initial triangles found go into the wrong direction in an (for humans) obvious case.
The reason I'd like to have D*-lite (which needs no close list btw, but needs to store the search states and the open list for each agent) is because you're right on your other point, too, you cannot trust the initial channel found. The case I try to solve arises when reactive behavior deadlocks (e.g two agents on opposite end of a narrow tunnel unable to pass each other). So if in the case from the TRA* paper another agents comes crossing from the opposite direction it can be totally reasonable for one agent to choose the upper way and for one to choose the lower way. But both agents choosing the lower one and deadlocking in there is not good ;D
Oh and one note to the tracing in TA*. As I said I build a binary tree of the ancestors. More exactly that means: each time a state is expanded it expands either to one or two new states (going back makes no sense). If it expands to two states it becomes the founder of a new subtree in the binary tree, thus the two new states have a pointer back to this state. Otherwise it's expanded to one state, in this case it points back to the founder of the state currently being expanded (thus the tree doesn't grow). The point is now: The tree grows only if you expand a level 3 node (or the root of a level 2 if you come from inside a level 1 tree, which happens at most twice per query), which is relatively rare (see p. 103).
Maybe a hybrid would be good: using TA* for areas wheres not much going on if they are observed and using a regular A* for the rest.
Thanks for the spline hack reference, I'll have a look in the RecastDemo.
Theta* (http://aigamedev.com/open/tutorials/theta-star-any-angle-paths/) might be helpful since it "short circuits" little jogs like that if there is a clear line of sight.
ReplyDelete