Tactical Troops: Anthracite Shift is a top-down, turn-based game that mixes tactical skills and the excitement of 80’s sci-fi movies. Created by QED Games Team of QED Software, it features many mechanics posing a great challenge for AI controlled characters, such as gridless movement and the topic of this article – teleportation. Link to Steam.
About Grail technology
Opponent AI in Tactical Troops has been implemented using Grail. Grail is a multi-platform, modular, universal framework, allowing for implementation of advanced AI in video games. Using methods such as Utility AI, Monte Carlo Tree Search or Planners in connection with advanced knowledge representation using blackboards , Grail is able to improve the behavior of machine-controlled players’ and make game experience more challenging. Below you can read how our AI handled teleportation in Tactical Troops: Anthracite Shift.
AI in Tactical Troops: a brief overview
Humanoid opponents in Tactical Troops are implemented by combining Utility AI with Monte Carlo Tree search. First, Utility AI is used to establish high level strategic goals like eliminating a unit or securing an important position.
After assigning such goals to each AI unit, a simplified game representation is generated, consisting of all possible actions that the units can perform. This representation serves as a simulator for Monte Carlo Tree Search, a very clever game tree search algorithm implemented in Grail framework. The inner workings of MCTS are beyond the scope of this article, but if you’re interested, have a look at this Wikipedia page.
For the purposes of this text, you just have to know that we need to somehow produce a set of current and future (but with a limited time horizon) possible actions, based on the current game world state. Below is the explanation of how we generate actions related to one of the most important mechanics in Tactical Troops – teleportation.
How AI handles teleporters
The explanation of our solution to this problem consists of 3 main parts:
- Navigation graph formation
- Move-and-attack actions
- Shooting through teleporters
Navigation graph
For the purposes of AI agent navigation, the terrain is first represented as a regular grid with various movement penalties (e. g. like penalties for obstacle mass concentration). However, to make the use of teleporters possible, regions around them are first “carved out” of the grid, then such modified grid gets converted to directed graph representation and finally we add custom graph nodes (with their positions in centers of teleporters) that are connected to rims of the carved regions and to corresponding paired teleporters. To understand how this “carving out” and connecting is realized, see the picture below.
PICTURE
The details of creating these connections are as follows:
For each teleporter add two graph nodes – an “incoming” node and an “outgoing” one
Connect rims of the carved out region around the teleporter to the “incoming” node. The graph is directed, so the connection can be (and is) entry-only
Connect the “outgoing” node to the rims of the carved out region around the teleporter (exit-only connections)
Add edges between incoming node of teleporter #1 and outgoing node of teleporter #2 (and vice versa)
Move-and-attack actions
To let our AI simulate its possible actions we rely on a pretty elaborate algorithm for continuous space discretization, based on pathfinding to important spots on the map. Describing it in detail would take way too much time (BTW, we’re doing just that in an upcoming paper). Suffice to say that each AI unit is aware of possible paths leading towards their enemies and other important targets through teleporters, so it is able to generate move-and-shot actions by performing all necessary lines of fire checks from points on these paths.
Shooting through teleporters
To generate direct shots through teleporters, we also rely on space sampling by pathfinding, described in the previous section. From each point on a unit’s so-called tactical path (think: a path from the moving unit to an important position, like a control point or an enemy. The points of this path will be called tactical points) the following procedure is carried out:
For each teleporter on map, we check lines of fire to units close enough to said teleporter.
If a line of fire is found, we take the direction vector pointing from the teleporter towards the enemy, move it to the second teleporter and find a point on a circle constructed in such a way that it (meaning: the circle) meets the following conditions: it contains the tactical point; it is centered on the second teleporter; its radius is equal to the tactical point’s distance from the second teleporter. This point becomes our candidate teleporter shot point. This procedure may sound a little bit convoluted, but it’s really simple – see my quick drawing below.
Finally, we check the line of fire between the candidate shot point and the second teleporter. If the line is clear it means that we can safely shoot.
Everything described above also applies to throwing grenades, albeit with some additional complications, like taking into account the explosion radius and other parameters.