TankTrouble Single Player AI

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.

Shoot Player

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.

LaikaRaycast

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.

Unstick Laika

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.

Dodge Bullets

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.

Experience

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).

Conclusion

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!

9 Responses to “TankTrouble Single Player AI”

  1. Intriguing. As I do want to become a game designer and programmer myself, I defiantly learned from this.

    Now one thing. There are many newcomers to TankTrouble who really believe Laika is hard, and there are many Legionaries who believe Laika is easy. Do you think these methods of difficulty could be applied to the original PC game?

    Reply
    • Tustvold

      I don’t really know enough about how the PC game’s AI works to comment. However, I think, given the number of people complaining about the difficulty level, that if such a feature were easy to implement they would have done it. That said I don’t think it would be that hard to make Laika easier, but making Laika harder could be more of a challenge.

      Reply
      • revengexx1

        Cool, so about just game design in general, where did you learn this, and for programming, did you use a certain program to create this game and make it come to life?

        Reply
        • Tustvold

          The behaviour system isn’t something I learnt somewhere but rather something I came up with as a logical way to make an AI. It made sense not only from a code readability standpoint but also from a functional perspective to split the code for different actions into separate classes (behaviours). Then the simplest way to select one to perform was to iterate through them until the conditions for one of them was met. It was effective and therefore I didn’t change it. I guess you could argue that this system is similar to a finite state machine, which resets itself every frame, but I wasn’t really thinking about it that way when I wrote it.

          For the fairly generic algorithms such as raycasting and pathing there are plenty of online resources which I made use of. However, for the more specific algorithms, like bullet dodging, I simply worked them out on a whiteboard.

          As for what I used to write it, I used Xcode for iOS and Eclipse for Android. Most work was done in Xcode and then I would switch back to Eclipse to test it. This was for two main reasons: Firstly Eclipse is terrible at understanding C++ and also because I needed to use Makefiles to compile the C++ code for Android. As I didn’t want to have to add every new class to the makefile manually I created a makefile that would compile everything in a Classes directory. This makefile, however, didn’t search subfolders and so I couldn’t use them to organise my code. Xcode, however, lets you group files independently of their actual location and so the majority of the work was done using it.

          I do now own a copy of IntelliJ but haven’t really tried using it for Android development despite it being a far superior IDE to Eclipse. This is largely because I’ve gotten used to using Eclipse and haven’t found time to migrate the project across.

          Reply
          • So for all the art, did you use the same Actionscript file that the web game used or made your own?

          • Tustvold

            The artwork is a combination of TankTrouble graphics and my own. I’m no artist and so tried to avoid creating graphics where possible. For this reason some of the assets are pieced together from assets within the TankTrouble flash files, for example the tanks. However, I had to create most of the graphics for the various menus myself. Discounting time spent on the AI I probably spent more time preparing and arranging graphics than actually programming the game… This was only made worse by having to create 4 sizes of graphics to support different devices.

      • I Installed TankTrouble On my android device and it Got deleted can i re-download the app 4 free now i purchased it?????

        Reply
  2. ben314

    Cool! The way of doing the dodging is interesting, and your methods of dumbing down the AI are quite creative. I’ve often thought of how I would program Laika to use the special weapons; have you put any thought into whether those will make it in?

    Reply
    • Tustvold

      There isn’t a solid plan as to when features such as powerups will be implemented. Preliminary versions of the frag bomb, RC missile and Gatling gun have been implemented, but they all need more polish before they’d be ready for release.

      Making Laika use the powerups, however, would be rather more of a challenge. The RC missiles I can foresee being a little too potent in the hands of an AI which doesn’t get confused about which way the rocket is facing. Generally I find RC missiles one of the hardest powerups to use effectively and it would be very hard to program Laika to have similar difficulty.

      As for the gatling gun, it doesn’t really fit with the way that Laika works. Laika relies on bullets firing along a specific path whereas the gatling gun fires a spread. The Gatling Gun also relies on stopping and charging up for a time and I’m not sure how Laika would asses what a “safe” or “advantageous” place to do that would be.

      The frag bomb is the only powerup that I could foresee being easy enough to implement. One could perform two additional raycasts at every bounce of the plotted shot. One to see if there is a wall between the bomb and the player and one to see if there is a wall between the bomb and Laika. But again there are problems with this approach. The raycasts are to the centre of the tanks and so it is still possible for a fragment to clip the edge of Laika. Also, and more importantly, there is no easy method to stop Laika from pathing towards the player and into range of the frag bomb.

      So in answer to your question, whilst powerups are likely to come out in a future update, I doubt that Laika will be programmed to use them. One possibility is to add a special mode in which Laika is even harder but you get to use powerups against him, but I’d need to discuss that with the people behind TankTrouble.com.

      Reply

Leave a Reply

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>