|
|
|
|
|
|
|
|
Navigation has always been a challenge for bot programmers. There are several ways for implementing navigation skills into your bot, this article will give you some insight in navigation techniques.
Tracing Algorithms
Tracing algorithms are routines which make a bot roam through a level by walking (tracing) along the walls. A good example of a bot that uses a tracing algorithm is the Tutor Bot. The Tutor Bot is basically just strafing and when it hits a wall it will make a 90-degree turn and strafe on untill it hits another wall. The Tutor Bot has proven to strafe all through a level with this coffee_move() algorithm, named after the Tutor Bot author Coffee.

coffee_move()
A tracing algorithm will be easy to implement into a bot, but it may not be very satisfying to play with. The bot will not be acting very intelligent, because the bot will just roam through the level, ignoring that it has a goal to move to like a quad, rocketlauncher or a sweet fragging spot.
Waypoints
A bot must know an item or spot, and a path to get there. A common way to let a bot navigate to an important spot is by using waypoints. Waypoints are simple nodes (positions) placed in a level. The nodes are connected to eachother, wich result in a path.
Paths can be used to calculate a route to a goal. When a correct route is plotted, the bot can walk it order to get to the destination.
Some bots annotate the nodes with additional information, like they will have to jump, duck, use a button or camp. Paths can also be annotated, examples are paths for flag capture, offense, defense and sniping.

Frikbot waypoints and paths
Waypoints and paths are often defined in a separate waypoint file, which is loaded when the map starts. Sometimes they are just hard-coded in the bot's source or stored in the map bsp file. Bots who use waypoints to navigate are the Frogbot and the Cbot based Eliminator.
Dynamic level learning
Dynamic level learning (also called dynamic mapping) is used by a lot of the newer bots. This technique is based on normal waypointing, the difference is that the waypoints are not predefined, but they are created on the fly in a 'bread crumbs' kind of way. The player(s) and in some cases the bots, by using tracing algorithms, drop nodes in the level while they are playing. Automatically generated paths will be created to link the waypoints to eachother.

Xreaper 'bread crumbs'
The bot's navigation will improve while playing, the longer you play the level, the better the bot gets to know it. Of course, the most ideal situation is that when the game ends, all generated waypoints and paths are stored, so the bot's experience can be loaded the next time the level starts. However, the quake engine does not allow to write files, that is why there are no classic quake bots who store their experience automatically, it can be done manually or the bot will have to learn the level every time. Bots who use dynamic level learning are the Reaper (and clones), Zeus, Omicron and the Frikbot.
These three techniques are the main ways of navigation, they are not only used by classic quake bots, but also by the 'modern' bots of these days. The best way of navigation seems to be a mix, using different techniques, like static waypointing and dynamic level learning. The Frikbot and the Omicron are good examples, some levels are predefined, and other maps have to be learned while playing. This way the bot is very flexible and can play any level you like.
mephisto |
|
|
 |
|