Designing AI Bots for Doomsday Part 1: Pathfinding.

edited 2006 Aug 26 in Developers
<i>This post was originally made by <b>Yagisan</b> on the dengDevs blog. It was posted under the categories: Blog, Engine, Games, jDoom, jHeretic, jHexen.</i>

<strong>A general overview on how bots could be implemented.</strong>

<strong>Choosing the right type of approach:</strong>

Broadly speaking, there are 3 main approaches to designing bots, these are Server Side, Game Interface, and Client Side. Being an Open Source game and having the source code available means we can immediately exclude Game Interface as an option. This leaves only Server Side and Client Side as the only viable options: The Server Side approach is the most flexible, but needs to be robust. mistakes in here can crash the server, while Client Side emulates a multi-player client. I strongly suggest we take advantage of Server Side to attempt to make a better performing, more intelligent bot.

<strong>Path Finding:</strong>
Initially when a bot starts a level for the very first time, there will be no saved paths. The bot will be required to explore the level and build up an internal path. On successful completion of the level each bot will save it's paths states to a MAPXY.PTH file like the GLBSP plugin does. These pathfinding nodes will contain either a co-op or deathmatch flag indicating the type of path, and flag indicating the character class eg doomguy, corvus etc. In loading a level, if a MAPXY.PTH file exists, each bot will load with a random appropriate path preloaded to be used as the starting path. The aim of this is to get the bots to become "smarter" the more they play each level. It is permissible to load the same starting path into multiple bots if there are less routes available then bots playing. An important note about these paths is that like a human, a bot will know in advance what items are along the path, and what resistance it will encounter.

Even though this is a server side bot, and we potentially have access to all map structures, this sort of preexisting knowledge is often considered as cheating by player. If we can implement this without major and obvious cheating, then we have a successful bot implementation.

Path Finding should be divided into two portions: Collision Avoidance and Path Planning.

<strong>Collision Avoidance</strong> is effectively the "short-term" memory of the bot, as it's name suggests it kicks in to avoid collisions with monsters and other bots, and to pick up spawned items such as clips dropped by zombieguys. These paths, are short term and are not to be saved to the overall path lists. These can most likely be detected by raytracing from the bots current position to the area in front of the bot, similar to how the players view is calculated.

<strong>Path Planning</strong> is the act of planning out the bots route to it's goal. It will either be following a pre-planned path to a goal, or it will be creating a new path by scanning for it's current needs and heading in the direction towards them. All Path Planning routes are to be saved at the end of the map.

<strong>Path Finding Enhancements:</strong>
During play, bots on the same team, if adjacent to each other may exchange pathfinding information. This may greatly increase a bots choice of paths if multiple bots took different paths to a destination. These paths could be "optimised" perhaps using a routing algorithm such as RIP. The optimisation could be done after bots exchange information, and on loading a MAPXY.PTH file. For difficult terrain such as lava or slime, we can assign a higher metric so bots prefer to avoid those areas, and eg teleportation routes a lower metric to encourage bots to teleport into the action. On saving a MAPXY.PTH file, if it is determined that two or more routes are now identical because several bots have the same paths at level exit, the duplicates should not be saved. Eventually there will be a single path list that contains all possible paths though a level with appropriate metrics to allow a bot to navigate anywhere based on it's need.

<strong>Grid Based Pathfinding ?</strong>
Considering that all wads are grid based, a grid based pathfinding algorithm would be a good choice. It would also allows us to utilise data such as the bots current grid position and the bot's team mates current grid positions to make efficient pathfinding choices. This could be used to allow some limited commands such as requesting all bots come to the human player's position.

<strong>Useful Resources:</strong>

The following websites may be useful (in no particular order):

http://theory.stanford.edu/~amitp/GameProgramming/
http://ai-depot.com/GameAI/Bot-Introduction.html
http://ai-depot.com/BotNavigation/Obstacle-Introduction.html
http://ai-depot.com/BotNavigation/Avoidance-Introduction.html
http://ai-depot.com/BotNavigation/Path.html
http://ai-depot.com/FiniteStateMachines/
http://ai-depot.com/Tutorial/PathFinding.html

Questions and comments welcome.
Sign In or Register to comment.