Contrary to what TankTrouble.com would have you believe, the TankTrouble AI is not actually run by a resurrected Russian canine, I’m sure the RSPCA would have a thing to say about that for one thing. Whilst far less exciting I thought I would write a post giving a rough overview of how the AI in the mobile version actually works. As for the online version I haven’t looked at the code for it and so can’t comment on how it works.
The first thing to note is that Laika’s processing occurs in a background thread, independent of the OpenGL rendering thread. Whilst on most devices the AI’s update function takes less than the 33ms required to maintain an update rate of 30Hz (the capped frame rate), on low end devices it occasionally takes longer. This is most noticeable on larger maps when Laika computes a path to the player. On a 4th gen iPod touch it averages about 27Hz, so just enough below the desired 30Hz to be significant. Thread safety is achieved by means of a mutex locked cache of all the data that Laika requires. This is updated on the main thread after every background update of the AI. Whilst this is a bit of an ugly solution as it involves copying data every frame that may not even be used, it was preferable to rewriting a large portion of Box2D to make it threadsafe.
The way Laika decides what to do every update is very simple but nonetheless effective. It has a list of behaviours it can perform and every update it iterates through these until it finds one for which the conditions are met. In total there are 6 unique behaviours and I’ll go over them in the order that Laika iterates over them.
Wait After Map
This behaviour simply stops Laika from doing anything for a short period after a new map has started, to simulate a person’s reaction time. The exact amount of time Laika waits depends on the difficulty.
This is one of the more complex behaviours and also the one that has had to be nerfed the most heavily during development. Unfortunately, because bullets can bounce it isn’t sufficient to simply raycast between the player and Laika to see if there is a valid shot. Such a system would only allow Laika to fire when it had direct line of sight, which would make it far too easy to beat. Instead Laika performs a total of 23 raycasts in a 230 degree arc in front of it. The number of bounces it will anticipate depends on the difficulty: It will predict 1 bounce on Normal, two bounces on Insane and no bounces on Easy. If it finds a shot that will hit the player (and of course not it) it will take it.
The image below show the raycasts Laika is performing. Raycasts that hit Laika are red, that hit the player are green and that don’t hit either are blue. As you can see Laika has found a valid shot (the green line), rotated to the correct angle and fired along it. It is also worth noting that the red wall borders are all offset by 5px. This is to deal with the width of the bullets, as otherwise the bullets would appear to clip into the walls. The wall borders also overlap with each other by 5 px, to stop bullets passing along the seam that would result if they didn’t overlap. The square boxes around the tanks are axis-aligned bounding boxes which Laika uses to speed up its calculations.
The observant will notice a red raycast is passing through the player in the above image, this is because the raycast passed too close to Laika and so the algorithm stopped considering it before computing where it actually impacts the player. More precisely it intersected a square around Laika with a side length the same as its diagonal. This is to prevent Laika from rotating into the path of the bullet.
Just this method alone, however, leads to an impossibly hard AI which is no fun to play against. Laika rotates instantly to the required angle and fires the moment there is a valid shot. To deal with this Laika will line up a shot and then wait before firing and will also wait a certain period of time before it will fire again. The exact length of these delays depends on the difficulty and ranges from 0.6 to 0 seconds and 3 to 1 seconds respectively.
Laika is also programmed to miss from time to time, with the probability and magnitude of the miss dependent on the difficulty. On the Easy setting there is a 50% chance that any given shot will miss.
Occasionally when pathing, part of Laika will clip against a wall and prevent Laika from moving. This behaviour detects such a situation and will move Laika towards the centre of the grid square it is currently in in order to free it. It will only do this, however, if there aren’t any bullets passing nearby Laika.
Whenever, bullets are going to pass close by to or hit Laika this behaviour gets invoked. Detecting such a situation is, however, complicated by the fact that bullets have width. A simple approach is to perform two raycasts either side of the bullet. Unfortunately, whilst this works most of the time, it falls down at the edges of walls. This is because there is the possibility of the two rays hitting and then reflecting off different sides of the wall or even worse one ray not hitting the wall altogether. In order to deal with this Laika performs the raycast for the centre of the bullet, to determine the path the bullet will actually take first. Then if this raycast passes close to Laika it will perform 2 more raycasts for each segment of the path to determine if the bullet actually is going to hit Laika. It will of course not perform these additional raycasts if the initial raycast hits Laika.
To dodge a bullet the first technique Laika tries is to iteratively search the surrounding area for a safe location through which no bullets pass. For each safe location it checks to see if it can actually get there without hitting a bullet and if so it will then travel there. Whilst this behaviour did at one point vary the rotation of Laika it was simply too effective and so it currently only checks the two orthogonal orientations.
If this search doesn’t find a safe location or is disabled by the difficulty level (it is disabled in Easy and Normal) Laika then proceeds to try to dodge the nearest bullet based on the direction it is traveling. This is an ineffective method of dodging, however, as it cannot deal with multiple bullets close together. Its main purpose though is to just make sure that Laika doesn’t sit still and wait for the bullet to hit it, which looks stupid.
Path To Player & Loiter
The final two behaviours in the list do exactly what they say on the tin. The pathing behaviour uses a simple A* search to find a quick path to the player and then follows it and the loiter behaviour does nothing at all aside from stop Laika from moving. As a result of the Dodge Bullets behaviour being invoked even when bullets only pass close by to Laika, Laika won’t try to path towards the player and in so doing drive into a bullet.
Depending on the difficulty level an EXP value is assigned to Laika and this is used to calculate the awarded EXP when the player wins. The same formula is used as the game on TankTrouble.com –
AwardedEXP = round(min(20, max(1, 10 (LaikaExperience - PlayerExperience) / 100)))
The current EXP settings for Laika are (Easy = 500, Normal = 1000 and Insane = 2000).
All of these behaviours combine together to form a challenging but not impossible AI, a video of which can be found below.
Whilst the method described in this post is by no means the model way to do AI, I hope that you have found something useful in this post. At the very least I hope it might help you to beat the Insane difficulty!