I exposed my previous attempt at local obstacle avoidance to some more challenging situations and oh boy did it explode! For example the above shows really complicated case, which looks really innocent. There are a couple of problematic cases.
Firstly, the obstacles that reach to the sides are problematic to handle. The sides needs to classified regarding the goal direction (blue) but they can reach back to over 180 degrees in certain cases. I had to make a lot of special case code to make sure to detect when right is still right even if it is on left side. Yeah!
The second problem case is how to handle the terminator nodes (those red dots, which indicate that an obstacle touches a wall). Initially I thought just to use the line to goal to split detect if a terminator is left or right. It worked well for many of my tests, but there are cases like in the above video, where the terminator changes sides!
So anyhow, hours of hacks and tricks later, I thought I'd give up a little.
Few days later, I thought why not try the old local grid pathfinder I made some time ago. I took a well tested rasterizer, changed it to support convex polygon and in no time I had working prototype of local obstacle avoidance in DetourCrowd.
The code is pretty simple to understand, it should be pretty fast too. I did not test the impact yet, but my previous tests indicate that it is fast.
The local pathfinder operates on the yellow area you can see in the video. If the blocking obstacle is larger than that, path cannot be found. The navmesh and the obstacles are updated every now and then, I could potentially use lower update rate too.
There a couple of problems still left to be solved. Firstly, the currently is no reliable way to detect that the agent is stuck. Secondly, in some cases the local pathfinder finds a bit different route, which leads to flicker.
_
We'll see how this all works out. I hope to speed up the navmesh temp obstacle baking a little. It is still the best choice. I think the local grid path planner could be usable for simpler games or those who cannot spend the extra memory required by the tile cache.
I didn't understand why you switch to the second approach when you do, Mikko.
ReplyDelete_Any_ local behavior will find situations it can't solve. So don't give up on the first approach yet!
Can you say more about the 'reaching back' issue? My attempt at this kind of approach just worked in each direction independently, no special case code. So it had no idea until the end that minus 180=180. So there is no 'left' and 'right', just clockwise and anticlockwise, which are orientation independent. Am I misunderstanding?
I ended up in this approach having to do some more complex weighting by distance to make sure the agent went in the correct direction. Which in turn meant the clustering of objects generated some more data (in particular information about the circumference of the convex hull of the cluster). And ultimately what that led to is a data structure tracking points of visibility on those hulls. And that is just a silhouette / points of visibility based navigation data structure. Eventually all local obstacle avoidance algorithms become more complex to the point where they're path planning.
The second version is solving a dramatically simpler problem than the first, isn't it? How would your pathfinder solve the first problem at about the two second mark? Are you assuming that the local pathing grid is large enough to go beyond the edges of the nearby cluster?
Its a neat approach, though, and it does look more parametric (if you could figure out the stuck problem, you could expand the grid until you can get free). The nearest I've come to it before is to do a similar dynamic nav-data generation on the lowest level of a hierarchical navigation problem.
Hi Ian, I'm not sure if I can properly express the frustration I got from my earlier attempt. I think the bottom line is that I have tried to make it work quite a few times and eventually the code has always become really complicated.
ReplyDeleteI think I usually end up in a situation where I would need to "precompute" more data, which in turn ends up being some kind of variation of points of visibility graph.
There are numerous papers from robotics which use similar "whisker" idea. I think the biggest problem is how to deal with distance. The whiskers deal with angles only usually. When the depth complexity grows, it is more important to find even more local discontinuity. Or something. I think I need to sleep on it, to make a better assessment.
Ideally I would like to have really fast way to change the navmesh, and I have done quite a few things in that field too. Navmeshes are inflexible to dynamic changes, though. My intuition keeps telling me that there are other solutions too, hence my adventures in local navigation stuff. It forces me to think very defensively against changes in data.
I understand the limitations of local navigation. Both methods have the same problem that they have only a narrow window to the world.
I like the grid representation because it allows me to really quickly change the topology, whilst allowing me to do a full search, and really fast string pulling to find the solution, not just some poking around in different directions.
Though, my ultimate goal is to combine the local and global navigation in some form and at the same time allow really fast changes to the navigable area.
My view on path planning has changed quite radically over the last few years. Every time I add one more dynamic component to the system, things get exponentially more complicated, barriers fade a way and some more emerge. Sometimes a solution that seemed stupid the first time around is suddenly becomes interesting, but I always end up changing bit or two about the old stuff to make it solve the problem better. You know, the z-buffer syndrome :)
Yeah, exactly the issue I hit - you end up having to solve a) the distance to first visibililty [of the goal relative on the hull of the current obstacle cluster] and b) the visibility connections between cluster. Wasn't an efficient solution.
ReplyDeleteHow about something like this. Using a hierarchical graph: at the lowest level the goal and current location will be in the same area (because the goal is on the border, if the actual goal is in a different chunk). Throw a narrow strip from source to goal, path it. If a route is found, you're done. If not, then widen the strip. Continue until either the whole chunk is included, or the route is found. If the whole chunk is included and no path is possible, mark the chunk impassable and replan from the top level.
I've never done it with grid at the lowest level, only with a finer grained nav-mesh (you can use a Delaunay triangulator to produce max-size well conditioned triangles, our of your coarse mesh, for example) but that's basically the approach I take on very large worlds (though admittedly they don't tend to have a lot of dynamic obstacles).
"barriers fade a way and some more emerge. Sometimes a solution that seemed stupid the first time around is suddenly becomes interesting"
ReplyDeleteI know that feeling well! I even ended up using an O(n^3) algorithm a couple of years ago. [http://idm.me.uk/ai/wfi.pdf] in my experience algorithms are rarely totally useless.
I think I identified one of the key problem of my earlier method. It basically boils down to which side to select. Or actually which of all the potential sides to select, there is many!
ReplyDeleteI think the solution for a given start and end location would be to first find the visibility polygon [1] of the start point. Then each each vertex of the polygon which may lead "out"1 is added to a stack. Then pick a corner at a time, find its' visibility polygon, add vertices, rinse and repeat until you have found the target or failed.
I guess I was trying to squeeze more mileage from the initial visibility polygon using a graph in my previous method. It turns out it worked in some cases but failed on others. I also found out that the graph things only works if all the obstacles are same size. I cannot prove this, but I was able sketch some scenarios which fail.
When ever I hear Delaunay triangulation, or any kind of triangulation, or boolean operations, I get shivers :) Those algorithms are just so tricky to implement correctly. That is one reason I favor discretization, let it be voxels or grids.
Currently I see navmeshes as a nice way to compress grids :) The "compression" is usually around 1:100 or more compared to same data as 2.5D a grid.
[1] http://en.wikipedia.org/wiki/Visibility_polygon
"When ever I hear Delaunay triangulation, or any kind of triangulation, or boolean operations, I get shivers :)" Yes, 100% agree. Not ready for runtime.
ReplyDeleteYour approach in the comment is a depth-first search in a (implicit) visibility graph. I've seen (and built) a lot algorithms in AI that grow to the point where they are implementing terribly suboptimal search strategies. I would go with your implicit admission from the post: best to start knowing you need (a good) search, and work out how best to apply it.
The point of throwing a channel across your grid is that, assuming the costs on your graph are metric [i.e. if w(a,c) <= w(a,b)+w(b,c)], the channel will be the optimum solution in the absence of obstacles. As you widen the channel the optimum solution will be the first one found. The algorithm expected execution speed is lower than just a regular search, but if the speed is dominated by casting the grid over the obstacles (as I suspect), it will win.
Does that channel idea take into account the situation that the agent may need to backtrack? I.e. it is inside an U shape, and the goal is under the bottom arc?
ReplyDelete"Your approach in the comment is a depth-first search in a (implicit) visibility graph."
ReplyDeleteYes, one of the problems is that since it is not a rigid structure, it will be really hard to check if certain solution has been tried already. In that case a faster solution is to build visibility graph.
The problem I have with visibility graphs is that it is hard to guess the upper limit of required memory and computation time. The performance on that grid on the other hand is very predictable and controllable, as long as the grid is small.
Mikko, yes, you expand the channel in a capsule shape, because the amount of backtrack can be no bigger than the width of the channel, if the width of the channel is acting as an upper bound on the path length it can find.
ReplyDeleteVisibility graphs: yup. Performance wise they tend to be very good, actually, better than grids and meshes, because the number of nodes is small compared to the number of edges. But as always you trade that against memory use, and in the case of visibility graphs they typically have high performance costs for generating the graph, as you point out.
I should be clear though: the channel approach is based on the assumption that the final path will be approximately a straight line between source and goal. The expansion heuristic is making that assumption. For paths that are very much not this (where the actual path length is not well approximated by the straight line distance), this will do far more work than needed. I'd never do this across a whole level, only at the last level of the hierarchy. It is a solution for dynamic local obstacles.
ReplyDeleteIt also has the rather nice feature of looking quite believable when the way is blocked. So a pathing character walks into a room, then 'sees' that the path to the exit point of that chunk is blocked, so replans and goes out the way they came.
Though, as I said, I've never done it with very dynamic worlds, nor with grids.
google 476
ReplyDeletegoogle 477
google 478
google 479
google 480
google 481
Thanks! And thanks for sharing your great posts every week!
ReplyDelete카지노사이트
메리트카지노
샌즈카지노
퍼스트카지노