I just added first version of path replanning for DetourCrowd. If a polygon becomes invalid along the path, the path is replanned. Invalid polygon means that the polygon just disapperas (i.e. a tile is removed), or its' flags don't match with the filter anymore. In the above video, the red polygons have disabled flags and the agents react to the changes over time.
The way it works on practice is that before the current path is followed, we peek ahead to make sure the next N polygons are valid (I used 10 in the above example). If a any polygon during that sub path is invalid, a replan is issued from the furthest valid position along the path. if the current polygon becomes invalid, or of the target location becomes invalid, the agent will stop.
There are some things I don't like about this method. Firstly, it is quite wasteful in resources. Issues almost a full replan is pretty horrible. I tried some local repair operations, but they ended up being too very complicate and hard to time-slice.
Secondly, the replanning does not react if a new venue becomes available. The topology optimization pass will catch many of these cases, but if the goal was unaccessible when the replannig happened, the current implementation will not try to replan when it reaches the end of the path.
The end of the path could be flagged or some other tricks, but I think I might be missing a bit bigger picture here. What actually does a movement request mean?
Example of nasty case
Here's a simple example which emphasizes one of the problems with replanning. There is a house and it has a door which can be open or closed. The NPC does not have key (cannot open door), and wants to move inside the house. If the door is open, the NPC can walk in, that is path A in the picture. But what should be do if the door is closed?
From navmesh point of view, it looks like the graph is broken at the location of the door. The usual fall back in case no path is found is to return a path which leads to nearest position around the target. In our case that would be the path B in the picture.
It is really hard to tell the A* that there actually is a closed door and that the nearest accessibility to goal location is semantically the door. And this is when things start to slip from a technical issue to a simulation or story issue.
Imagine a case where the agent starts to move to the building, and before it gets there the door is closed. The story seen by the player could be something like this: The bad guard tried to capture the princess, but at the last moment the princess managed to close the door, and then the guard went to hide under the trees.
Game levels are full of cases like this. The AI has no notion of the trees, but when the AI walks under a tree and stands there, the player will give meaning to it.
There are more problems with that case too. For a moment imagine that we could replan the path every time the world changed. Now if we had a situation where the door would open and close every few seconds, the agent would get dead locked at the east side of the building since the solution would flicker between paths A and B.
These are just few examples which happen when you add replanning to your navigation system.
Solution
I think the proper solution to reacting to dynamic changes in the navigable surface is to treat the planned path the same way as any other plan in the AI system. That is, it is very likely to fail, and the plan will be considered as failed, if small adjustments to it cannot fix it. This makes assumptions about the request quite clear. It may not be the best solution, but I think it puts the decision at the right spot.
Request for comments! How do you handle partial paths and replanning?
Mikko,
ReplyDeleteYou mention some really tricky issues here. I´m currently not familiar with your latest changes so I try to give some thought about the "bigger picture" issue you mentioned.
Your princess example leads me to the agents ability to predict things which lie in the future. Specifically when the agent gets to the place (door in this case).
Such a situation could be implemented as follows:
Imagine two sorts of flags for polys. One sort of flags which are always blocking (maybe deep water) and flags which sometimes block (closed door, movable object, a gap with a moving platform)
A shortest path to the target is calculated calling a (remotely implemented) method when reaching a flagged poly providing the poly (and maybe additionally the estimated time of arrival). This method then is in charge to determine if the poly is passable, or better, if the agent thinks its worth a try to take this route.
This could probably solve the problem of oscillating flags (regularly opening/closing doors, elevators, moving platforms etc.). The AI would hopefully have enough understanding of the world to see if it makes sense through this door or another. Ofcourse this some how just shifts the decision elsewhere but my point here is that a basic navigation agent cannot/shouldn´t know if its better to take this route or another but because of its distance. You actually made a good example yourself with the guard chasing the princess. Depending on how smart and conscious the guard is he might predict that the princess will close the door. But maybe not if he is not clever enough or just hopes the the princess isn´t clever enough.
The determination of the shortest path to a target by Detour implicitly assumes that the agent has full knowledge about the world (he knows all possible shortcuts, where the water is etc.).
The issues you just mentioned now involve properties of the world which cannot be determined clearly by geometry and math and need to be predicted/guessed by an extended AI which has much more understanding of the worlds dependencies.
Mirko
PS: The house issue with path A and B seem to be related. The first question is: "Does the agent know that the door is closed?"
Yes -> Invoke the AI to decide for a different strategy (shoot the door :-)
No -> He proceeds to the door (why not?). He reaches it and figures out that the door is:
Closed -> Invoke AI like above.
Open -> Proceed to the target.
Thinking of the navmesh as a temporary knowledgebase of an individual agent or a group sharing its knowledge seems to be reasonable to me.
Hi Mirko,
ReplyDeleteI understand your thinking, but it does not matter where the polygon flag comes from. If you replan and can have potentially greatly varying path each time, then the solution will not converge (or has very uncertain probability to succeed).
Here's quite extreme example: http://vimeo.com/10404328 Each agent replans its' path every frame. It converges, because the outermost agents has paths always.
If some flags could indicate that "this blockage will be closed at most 5 seconds", that is something you could incorporate into your plan and just let the path follower to wait if the poly is blocking*. Most of the difficult cases arise from game rules which feed from player actions, and thus are hard to estimate or give cost.
*) But even that would look silly if a lot of agents would try use that polygon.
Mikko,
ReplyDelete> I understand your thinking, but it does not matter where the polygon flag comes from. If you replan and can have potentially greatly varying path each time, then the solution will not converge (or has very uncertain probability to succeed).
I agree! If I understand correctly thats where a more sophisitcated AI needs to kick in and "understand" that its stupid to go on like that. IMHO this is nothing a pathfinding algorithm can/should decide.
I mean you would need to define some kind of patience parameter which defines how often an agent would switch to significantly different pathes in a certain time until he gives up (could be also cleverness ;-) ) and most important decideswhat to do next instead...
Mirko
Along the lines of what Mirko is suggesting, you can weight edges that pass through obstacles like doors. A* will then try to find alternate paths, but if it fails, it will create a path that goes through the weighted edge. Then, during path following you have to decide what to do with the door.
ReplyDeleteThis is essentially what Dragon Age does -- and is why the NPC's open doors to follow you, unlike earlier games like NWN. But, the final decision is done in scripting, not in the A* search.
For Transformers WFC we also had the path following system understand the concept of a temporary block (which we called a 'gate'). This was flag on the navcell, but unused during the A* pathfind.
ReplyDeleteLike Nathan said, we tried the weighted edge solution, which worked. Our problem with it was, if there was only one possible path, it artificially lengthens the search with no benefit. Since we didn't have any real cases where a second path was needed. I pulled it.
Another problem with it, depending on the weight tuning, you might not find the other possible path. If the weight it to low, it wont search far enough. If to high, you are going to make the searches more expensive.
As a personal rule, I avoid adding weight to edges if the weight doesn't describe the traversal cost. The 'temp blocked' would fall into the avoid category.
Now that being said, if take the case Mikko described with the door closing on an interval. And the weight described the max time one might have to wait at the door. Then it would pass my rule:)
Totallytroy, Thanks for the insights! I have had exactly same experience with weights. The link costs can be quite irregular in navmeshes because of large polygons being next to small ones. That makes extra weighting hard with navmeshes hard to control too.
ReplyDeleteYes, the weight costs being affected by the tessellation of navmesh is very frustrating problem.
ReplyDeleteI like the way that Dwarf Fortress did it.
ReplyDeleteIf a node in the world changed that was in the path of the agent, the agent continues on its' path till it "unexpectedly" hits the change piece of the world. As if it was surprised that the world has changed unexpectedly (say stopping just infront of a locked door to find it locked). This seems a lot more realistic and of expected behaviour for an agent to not predict the future, but instead arrive at the broken piece of the world and then let the application decide what to do next.
Of course this all depends the actual application, some agents may be smarter to replan a path early when 'looking ahead'. Maybe "look-ahead" should be a property before kicking in replanning?
@110715627395507006858, I think that would work sometimes, but sometimes the change can be such that it looks like there is way to walk around easily.
ReplyDeleteI think the annoying thing about this is that what ever I do with replanning, it will define behavior. I think I can even generalize that a bit, path following defines the movement behavior of the agent, thus, there is no right solution to it.
Mikko,
ReplyDeleteI agree with that.
Thats the reason why I would define the NavMesh as the "known" world of one agent (which is not necessarily the real world because certain ways are unkown and open gates are known to be blocked etc.). And define Detour as the agents intention to go to a target location along the shortest path (of the area known).
Defining it like this circumvents most of the issues IMHO. Except:
1. Knowledge about the near future (the agent knows that a path will be blocked before he reaches it)
2. Oscilating blocking objects (these objects should provide data if the agent thinks he can pass it or should avoid it).
3. Reasoning about the likelyhood to find a shorter path through the yet unkown area.
Did I miss something?
PS: I don´t recommend to create a NavMesh per agent here. A tagging/flagging logic on polys etc. might be sufficient to indicate that a given poly is known by Agent X and if the poly is known to be passable by Agent X.
Mirko, how the search (A* or something else) would work in that kinda environment? I like the idea of treating the world as uncertain, but not sure how to manage it. There are a couple of search algos which kinda handle that (D* & co), but they require an "A* search state" per agent which I think is too much memory.
ReplyDeleteHi,
ReplyDeleteFirst of all, thanks for the library and the descriptions! :)
I've just started to learn about navmeshes. I've already done a working prototype with triangle centers, but you can imagine that it wasn't the best solution. :)
So I've downloaded your code and tried to find the corresponding code section. Your findPath function in the Detour folder uses the center of the edges, where the edge is the connection between two neighbor polygon (or in my case, triangle).
My current navmesh is far from the optimal, however I've found some solution (e.g. in Unity) which handles the weird navmeshes as well. Lotds of cases, the edge center algorithm will give me unoptimal path. Here is a picture about the problem:
http://s8.postimg.org/up1hke8md/navmesh_pathfind_error.png
Do you have any advice how should I handle these kind of navmeshes?
Sorry, for writing here, but I can't find any contact and I really want to ask this. :) I hope you'll read this.
Thanks,
Adam
google 1952
ReplyDeletegoogle 1953
google 1954
google 1955
google 1956
google 1957