Bot Navigation: Design Philosophy
By ai-depot | June 30, 2002
Motivation and Requirements
In Practice
To date, the development of the A.I. does not receive as much attention as the graphics engine or the game content. Simple methods are therefore preferred for navigation. This is commonly done by representing the level as a set of static waypoints, and only using this information. This allows simple pre-computed path-finding to be performed very efficiently. Understandably, this does not provide flexible results (for example finding the shortest path to avoid the enemy with the rocket launcher).
Often, bots are allowed to see everything no matter where he is located. This does admittedly simplify the design of the bots. For the player, this can be extremely frustrating, as they constantly know where and when other items are available. They also don’t need to predict the opponents behaviour as they know where he is!
Another observation is that the bots usually ignore the level’s structure, apart from what is provided by the waypoints. The physics collision detection takes care of any problems that may arise (like stepping into walls). A.I. designers can get away with this as levels are usually mostly static, and it would be a waste of time processing this dynamically.
Those few bots that do take into account the immediate surroundings usually do so on a purely reactive basis. This means that their movement is a simple knee-jerk response which is not usually planned (turn left to avoid collision with an enemy, and fall in the lava).
All this amounts to bots that do not move very realistically. I’m thinking of the hostages in Counter Strike, who can be very frustrating to deal with. Not only this, but their abilities are usually very limited, which does not allow them to tackle new levels, or learn new tricks in known maps.
The Theory
The first focus of research is to improve the reactive abilities of robots and agents (computer scientists do not talk about bots like game programmers do ;) This involves finding new ways of taking into account the surroundings, how it can be accurately scanned with simple sensors, and what are the best ways of representing it. Major problems are often encountered: the inability to deal with the noisy data, and the inflexibility of the system which often forces a redesign.
On the other hand, deliberative path-finding has also received a lot of attention. But since the A* algorithm with an accurate heuristic is pretty much optimal, there is little work to be done from that point of view. For some silly reason, a fair bit of research is focused on finding obstacle avoidance algorithms that do not use any additional information (such as waypoint data). This is a fairly na�ve approach, since even the smallest state would allow some problems to be solved very simply. Additionally, different representations of structural data is being elaborated.
Finally, and most importantly, researchers are looking into combining these two previous approaches. This is problematic since reactive and deliberative components often clash. Existing approaches include subsumption, which involves a hierarchy of layers which over-ride previous ones. This often causes problems, as some movement requests may be discarded, and ignored.
Requirements
- Learning of structural knowledge should be automatic, and from a subjective point of view. This avoids the timely manual creation of waypoint data, and allows agent based spatial awareness.
- Information about the immediate surroundings should be used to assist higher level path-planning in a dynamic fashion. Paths should be recomputed if there’s a temporary obstacle in the way. Traps such as lava and electric fences should be avoided at all cost.
- Irrelevant terrain detail should be hidden from the symbolic deliberations. Similarly to humans, this simplifies the reasoning, allowing a more efficient implementation.
- Small obstacles should be avoided in a transparent human-like fashion, allowing the agent to be guided as if on auto-pilot - thereby reproducing habit, reflex and experience.
- High-level symbolic path-finding should be dynamic, allowing adaptation around temporary conditions. The enemy’s location can be taken into account, as well as the presence of unexpected items (dropped by another player).
- An elegant solution for combining high-level goals and instinctive reactions should be provided, without neglecting either orders. This is crucial, since any compromise would cause fatal errors (falling in pits, not picking up items).
- The overhead of the entire solution must be minimal, allowing multiple agents to be simulated efficiently.
Tags: none
Category: essay |
October 7th, 2007 at 8:44 am
thanks .. .good