Warp Speed: Path Planning for Star Trek reg.: Armada

Artificial Intelligence and Interactive Entertainment

Volume

Papers from the 2000 AAAI Spring Symposium

Contents

Star Trek®: Armada is a Real Time Strategy game (RTS) involving space combat between fleets of Federation, Romulan, Klingon, and Borg starships. Each side can have up to approximately 30 capital ships on its side, and maps can vary considerably in aspect ratio and size. Obstacles in space include moving asteroid belts (with gaps through which ships can pass), nebulae which can slow ships down and cripple ships’ systems, starbases, black holes, ion storms, other ships, etc The nature of a 3D RTS is that it must be fast, and the path planning must be considerate with its CPU usage. Core algorithms such as the A* search algorithm are becoming widely accepted in the game industry. However, the key to efficient path planning is how the environment is spatially decomposed, what is left to search-based planning, what is avoided with reactive collision avoidance, and what is simply prevented with collision prevention. Star Trek®: Armada uses a quadtree decomposition of the playing field which greatly reduces the number of cells that A* needs to search. However, care must be taken to perform some kind of rubber-banding to make the paths look natural. We also use reactive avoidance for most moving objects, and as a final safety measure we actually prevent ships from having overlapping shield ellipsoids in a post-simulation step. In this paper we shall describe the implementation of the path planning system in detail.