Dynamic Object AvoidingNowadays, some game developers force their AI implementation to recalculate the best path when an object is intersecting the current path of an NPC. Fortunately, not all developers use this approach. The outcomes of that action, speaking in terms of credibility of the NPC and about performance, are definitely negative. Dynamic Objects in Path Finding is a strange issue, and in my opinion is a non-problem. We should first divide the issue into two main cases: 1. an object is moving toward the current path of an NPC 2. an object has moved and been placed along the current path of an NPC The way to react to these two cases should be different. In fact, if an object is moving, we have to worry about the possibility of a collision with this object. A possible collision, though, never should lead us to change the path, unless there is a high amount of moving objects in the same place. If this case happens, you shall check your game or simulation setup. In fact, a place in which there can be multiple moving objects should have lines of the graph with a higher weight. When an object (or another NPC) is moving toward a line of a path used by an NPC, the only problem to face with is avoiding it. This though must not change anything in the decision, already taken, of the path to follow. A similar problem you'll have with an object that has moved and placed along a line of the path used by an NPC. In this case, unless the object is so wide to block completely the passage, you need to treat it with the Object Avoidance algorithm. How should be a proper Object Avoidance algorithm for the BPF? There is no preference or precaution to consider. You should use the algorithm 'only' to avoid object. When the NPC has avoided the object, the algorithm must go to its end. After that, the Path Finding system will be active again, and the NPC will go straight toward its next focal point. What if the object that is blocking the path is so wide that makes impossible any trial to turn it? Do we need to find another path? I absolutely prefer avoiding this solution. Humans, when inside a real and physical problem, are not dominated by logic. Even if it's difficult to understand, emotions manages our actions. Only after having filtered events with emotions, we may think and then use logic. A human, when started on a path, if there is a problem along it, tries to imagine (not calculate!) a sub-path that helps him to turn the problem and continue along the same path. It's too complicated considering to change path, and the time is never enough for a human walking along the road. Only a danger can change this way to do, but it's something that has not to do directly with the path finding system. So, even in the worst case, there is no need to start the path finding calculation from the current position to the target. The correct solution for a proper human simulation is finding the "simplest" sub-path from the current position to the first focal point beyond the object, or using the Object Avoidance algorithm. In the human approach to the PF problem, there is never a sort of calculation, but rather estimations. Estimations consider the number of turns and the number of focal points: in our mind there is no continuous registration (like a video, for example) of the path, but only flashes about the focal points. Thus, if the human saw a map, he will have a better chance to make a better estimation of the length of each path. Any focal point is close to a micro-environment. This helps us, because it's impossible that an object occupies more than one micro-environment (unless is a giant object!).
Smoothing MovementsEspecially in case of complex or wide and open paths, I reckon that grid and mesh navigation don't give enough NPC credibility because of the number of nodes in the map. There are, substantially, four grades of quantities of nodes in a path:
- Too few nodes, or/and placed in senseless positions: it's not possible for the NPC to walk as a human, and then it will have unpredictable results; [possible with the Waypoint approach]
- Few nodes placed in the "focal points": the NPC reacts like humans do; [currently proposed only by Biological Path Finding];
- Many nodes: the behaviour of the NPC is far from being similar to the one of humans. Without a good (and sometimes time-expensive) smoothing algorithm, the NPC will have a behaviour similar to one of a drunken man [can happen with the current navigation solutions].
- Too many nodes (from dozens to hundreds of times more than the focal points): the behaviour of the NPC comes back to seem similar to the one of humans. The off-line and run-time calculations, though, become really expensive [can happen with NavGrid].