This paper examines the problems with current "path finding" solutions, showing their limitations and how they labour to handle complex dynamic scenarios. A navigation system inspired by humans is described [Champandard02], revealing how existing knowledge and experience in game AI development fits together. Specific details about the interface to the navigation component and its implementation are radically changed in order to handle intricate storylines in a simpler and more flexible fashion.
2 Movement in Games
Motion as always been a key element in computer games, from the first pioneers (like Pong and Pacman ) to the latest state-of-the-art productions. Now, the possibility for increased complexity in game environments is of great benefit to designers, who can make the most of their imaginations. Human players also enjoy the sophistication and realism of such environments. However, when it comes to the AI, compromises often have to be made due to the complications entailed.
The inability of AI characters to deal with the intricacies of the environment causes serious design limitations. Entire storylines have to be designed to hide the inability of the navigation; AI units often are just cannon fodder, and their behaviour away from the current viewpoint is irrelevant. Competent sidekicks are all too rare for this reason.
3 Realistic Environments
Complex game worlds are more and more common. These include intricate features such as doors, platforms, and collapsing bridges. Together with this, the rules of the game generally have real-time repercussions on the way the game is played (danger areas, good cover points).
This dynamic nature of the environment improves the experience of the player, but also makes navigation much harder to achieved with artificial intelligence. Whence comes the need for a more sophisticated solution, based on a better understanding of the whole problem of human-level movement.
4 Human-Like Navigation
One of the major goals of the AI developer is to achieve human standards. This is especially crucial for movement as it is so obvious. The best model to help reproduce this skill is naturally the real thing: human navigational behaviour.
A wide variety of natural and learnt abilities combine to allow humans to move purposefully. Some of these capabilities need to be duplicated by the AI for the simulation to work. Others simply improve the final result. For example path-planning is fundamental, while the abilities to make dynamic decisions or to combine paths together are simply an added benefit.
5 Functional Decomposition
Abstract study of human behaviour allows different skills to be isolated. These provide a better conceptual understanding of the problem, which can be used to craft a simpler and more efficient solution.
Three different components of human navigation are discussed in this paper.
Motion Control - Responsible for the low-level aspects of movement : control of the body in a reliable fashion. Things such as steering and speed control are included. Reactive tasks such as obstacle avoidance are possible here, without any additional help. This is the most simple skill, but yet fundamental.
Terrain Model - Memory is an important part of intelligence, and intelligent navigation also benefits from it. Humans have the ability to remember their environments, and build complex internal models.
Planning - In many situations, there is no doubt that elaborate forms of cognition are required. To find a path through an intricate environment to a distant target is only possible when a plan is made.
These three components combine to form human navigation. When one is ignored, the ability of the whole system is seriously compromised. This is one of the main reasons for unsatisfactory AI movement in games: either the first or the last two components are ignored or glossed over.
6 AI : The Big Picture
Modularity in agents is an important concept. Increasingly, AI is created as a set of interacting components. Just like object-oriented paradigms, this deals with complexity in a much simpler fashion. This practice is widespread in academia, but still in its infancy in computer games (A* and FSM).
The benefits of a navigation component is obvious. Much of the complexity to create an intelligent agent for games goes into synthesising movement. If this can be abstracted out into a black box, little work remains to be done to obtain a fully functioning AI creature. Even for more complex AI designs, there are significant benefits in separating the navigation code.
To develop a useful module capable of navigation, two things need to be taken into account. First, the interface with the rest of the system could be specified the. Second, the details of the underlying computation and how it will be implemented are considered.
7 Interfaces
7.1 Current Paradigm
Many existing solutions rely on a concept popularised in the early 60s: single-pair shortest path problems. These are scenarios where an optimal sequence of edges needs to be found between a source and a single target.
Requiring a single destination is a simple and effective way to pass information to the navigation system. However, having one unique destination is an extremely limiting factor. This implicitly requires a destination selection process which determines where to go next based on the current state. The target also needs to be chosen by the AI based on current motivations or desires. This is a difficult problem in its own right, and is often done with a single function.
When the AI is relatively sophisticated, this function becomes overly complex -- and will no doubt be unfeasible as AI characters improve in realism. Compromises are often made here, as single destinations are not the best way to express complex paths; this would require it to be specified step-by-step. The only alternative to step-by-step control would be to artificially adjust edge costs to get the desired outcome. This is no trivial operation, as a traversal of the graph is required to modulate costs simply to prepare for the planner. This process in itself requires serious thought during development.
This almost beats the point of A*, as it struggles to handle more advanced path planning problems; if it works at all, you will have written a lot of movement-related code outside of navigation system. While there are other possible AI solutions to create a better destination selection function (e.g. arbitration, voting), increases in the complexity are an unavoidable implication of the interface specification.
This results in a bottleneck for the AI, behaviourally speaking. The sophistication of higher-level AI cannot be passed in full to the navigation system with single pair problems. This leads to aliasing, as most of the quality of the behaviour is lost when movement is requested. Using more capable AI techniques to counter this problem is possible, but these require more information from the navigation system (e.g. travel times to determine the best next target). This exchange of information further blurs the boundary between navigation code and the rest of the AI, defeating the point of the modular approach. Such decisions about where to move in space should be left to the navigation system, since it is the best informed to make the decision.
7.2 Suggested Approach
A much simpler solution is possible when the interface specification is changed. The new specification should be flexible enough to allow sophisticated AI behaviours to be communicated to the navigation system without exposing a bottleneck. It should also not make the distinction clear between movement code and the rest of the AI, by simplifying the interface.
Pathematics attempts to express complex paths in their most primitive form using implicit destinations. Weighted rewards are used to specify each and every desired targe. (this is superset of the single pair interface where only one destination is specified with a weight of 1).
Paths are also returned in their most fundamental form : step-by-step. This allows the navigation system to provide dynamic decisions in a lazy fashion (which actually suits path-planning ?as discussed later). Precomputed static paths are also supported by this paradigm, so A* would still work with this interface.
Both these concepts remove the AI bottleneck, prevent behavioural aliasing, and place all the decisions about movement within the navigation system.
7.3 Specification
The following requests and queries should be implemented as part of the interface to the navigation system :
Weighted Destinations -- Used to influence the path to make detours via points that are of interest to the agent. These not are taken as a sequence of waypoints, since the navigation system will decide which is the best order for them.
Next Step -- The computed path are returned incrementally, which offers the most flexibility and power to the underlying algorithm.
Distance Estimate -- While all the decisions about movement and the selection of next target is left to the navigation system, in some cases the agent might require an estimate of the distance to particular point (e.g. in general planning). This should not be used to trade-off targets, as the navigation system will do that best.
Full Path -- In some rare cases, the agent might decide it needs a complete path to a specific target, for prediction purposes for example. This query allows that when necessary, but should not be used for common operations instead of the step-by-step approach.
Such an interface allows the navigation system to deal with the complexity of the environment in the best possible way.
8 Implementation
The development of the underlying system will be modelled upon the analysis of human behaviour. The three components discussed above are to be used in their original roles.
8.1 Terrain Model
There is a variety of possible representations that can be used to describe the environment. These range from standard waypoints to floor meshes based on polygons, or even biomimetic approaches like place cells. This decision is mostly independent from the rest of the navigation system.
Terrain model mainly needs to provide connectivity information, to allow the planner to formalise paths through the graph. Each of these edges should be given an appropriate cost. A sense of space is also required to materialise the path precisely enough in space, and guide the agent safely to the destination. All the other navigation components are independent of the other details of the terrain representation.
To handle the complex scenarios mentioned, the terrain model needs to handle dynamic changes. Incremental changes correspond to edge insertions, or cost decreases; decremental changes correspond to edge deletions or cost increases. Not all of these updates need to affect the data structure itself, but the terrain model needs to alert the planning component when something does.
8.2 Motion Control
This component must provide reliable lower-level movement. This includes avoiding dynamic obstacles and generally getting out of trouble as necessary. Well-known steering techniques can be used to do this [Reynolds99], although some modifications may be needed to handle sidesteps or jumps.
The second aspect of motion control, and probably the most important, is the execution of plans. When given details about the path in an incremental fashion, this behaviour should be capable of following it -- while still avoiding dynamic obstacles.
The combination of these behaviours (avoid & seek) may seem challenging, but there have been many solutions to this problem in Robotics over the past decades. Subsumption architectures [Brooks91], schemas or vector fields [Arkin98], neural networks [Champandard02] or even steering behaviours [Reynolds99] (again) can do this. Once this is done, most of the properties of human emotion can be modelled.
The effect of dynamic entities on the path can be computed globally (if the agent can cheat), but this is often quite expensive. Instead, motion control is in the unique position to determine the effect of moving creatures locally. As such, it must provide feedback up to the planner before it to update its decision as appropriate. This can take the form of incremental positive feedback when things are going right, or even negative feedback when the agent has to turn around.
In turn, this information can be passed to the terrain model (directly or not) in order for it to be memorised. Future plans will thereby take into account problems encountered to date.
8.3 Planning
The planning is responsible for taking into account all the information provided by the agent's AI, and computing appropriate/optimal paths through the environment. These should be passed incrementally to the motion control, which will execute them step-by-step. Planning must use up-to-date information as determined by the terrain model, and also take into account feedback from the motion control.
Cached storage of plans is often required, as the agents queries need to be as efficient as possible. Also, when data is kept it can potentially be reoptimised dynamically. This is necessary when the terrain model changes; such a task cannot always be ignored or discarded, as the potential effects of any terrain change on the plans are tough to determine (needs specific data structures, or complex algorithms).
9 Solution
Applicable techniques for both motion control and the terrain model have been briefly discussed. These can mostly draw upon existing knowledge and experience. The planning, however, needs to be rethought in order to make the most of the new interface.
9.1 Autonomous Agent Navigation
Path planning is one of those required elements of game AI development. Yet rarely is it taken beyond concepts decades old. There are many properties about intelligent agents that can be drawn upon to devise a new solution [Champandard02]:
Egocentricity -- Intelligent creatures are always at the centre of their world model, and things are no different for artificial agents.
Sub-optimality -- Humans make decisions that are not perfect, which distinguishes their behaviour from computer models. This is often tolerable for agents too.
Quality Trade-off -- In some cases it is necessary to make quick decisions, but in others a more considered plan is required. Humans have the ability to make such compromises.
Persistence -- World models change incrementally, which also reflects the speed of cognition.
9.2 Heuristic Process
The pathematics approach is based on a heuristic rather than an algorithm. This is used to build a spanning tree, which contains paths from a single source to all the other nodes. The final result is in fact the same as Dijkstra's algorithm [Dijkstra59], as optimality is reached when the heuristic is applied repeatedly.
Fundamentally, a greedy traversal of the graph is used to correct the distance estimates at each node. A node is selected (at random or sequentially), and all its neighbours are relaxed (i.e. their distance estimates are improved if possible). The neighbour where the biggest correction was applied is selected as the current node. If no neighbours can be corrected, a new starting point is selected. The process can repeat, and all distances estimates will monotonously decrease to the exact value (as in the Bellman-Ford-Moore algorithm [Bellman58]).
The greedy nature of the process implies that the quality of the results improve the most at the first. The more sub-optimality is tolerated, the faster the result can be generated. The heuristic can also beat a naive O(n^2) algorithm, and be competitive with the modified versions. However, pathematics shine when the conditions are continually changing, requiring continuous re-optimisation (where the greedy heuristic can have its full effect).
The heuristics relies on the precondition that estimates are always further than the exact distance (similar to BFM). This precondition becomes invalid when decremental changes are applied to the terrain model. A cheap O(n) can be applied in this case, and also when the root of the spanning three changes; the estimates are simply increased by the worst-case change, see [Champandard02] for more details.
9.3 Reward Percolation
A second heuristics takes care of building paths according to the implicit destinations specified by the higher-level AI. Typically, this is done by a simple traversal of the data structure, but this would simply return the optimal path to a single fixed destination. The pathematics approach actively percolates the weighted rewards towards the root.
This is achieved by a direct reversal of the graph from selected nodes (randomly or sequentially) towards the origin of the spanning tree. This is extremely efficient as the distance estimates are already in place, forming a perfect look ahead heuristic.
The reward is accumulated and combined during the traversal, which can done by multiplication or addition of the rewards, depending on the kind of behaviour required (i.e. prefer large objects to small ones). Generally, this makes sure that the reward flow is more important in areas where the agent wants to go. Then at the root, a decision can be made where to head based on the biggest reward flow. Movement is thereby influenced by the implicit destinations.
10 Discussion
10.1 Advantage
Flexibility -- The solution decomposes the specification of paths into primitive elements. This offers great control to the AI developer.
Simplicity -- The improved interface provides a better way to pass requests the navigation system, which greatly simplifies the creation of higher level AI.
Power -- Behaviour can be controlled with very simple orders that are combined intrinsically by the navigation system.
Implementation -- The programming of the solution is also very straightforward, almost becoming a matter of writing down an interface and coding a few equations.
10.2 Disadvantages
Personalisation -- Each agent requires its own spanning tree; this solution does not work globally for all agents. This is partly a consequence of the nature of dynamic navigation.
Spanning trees -- The representation chosen to store the path has many advantages, but it also becomes a limiting factor. When path that are not in the spanning tree need to be combined, the solution picks the best one first and moves from there.
Dynamic costs -- The use of weighted rewards is extremely simple, but in some cases it is necessary to locally modulate edge costs (it easier to indirectly influence movement without setting targets this way). Such an approach is similar to the hacks necessary to obtain good behaviours from A*, but it seems unavoidable.
Understanding -- Despite being fundamentally simple, the different requests can combine into complex patterns within the navigation system. This can be difficult to understand at the first, but experimentation with the use of visual aids will help.
11 Conclusion
Realistic dynamic environments have become commonplace, yet current AI solutions struggle to make the most of them. A* based solutions can be strained into handling such scenarios, but there are many overheads from the development point of view which make this task much harder than necessary.
Having a conceptual understanding of human movement allows a navigation system to be created to solve this problem in a more convincing fashion. Once it has been made into a component of the AI, it is much simpler to develop around.
The interface to the navigation system needs to be rethought, allowing more than just fixed paths and single destinations to be handled.
For implementation, a few details need to be changed and the planning algorithm needs to be replaced. Solution based on properties of intelligent agents will offer more flexibility and provide more realistic results. With such an improved model, the AI is no longer the problem in the game development process, as it will be able to handle all the intricacies the world designers can throw at it -- and even be able to rival the best human players.
12 References
[Arkin98] Arkin, R.C., "Behaviour-Based Robotics", MIT Press, 1998.
[Bellman58] Bellman, R., "On a routing problem", Quarterly Applied Mathematics 16, 87-90, 1958.
