Developing a “good-enough” TBS AI – Mutant Gangland

possible_header_slidedb

Disclaimer: I haven’t dabbled much in Artificial Intelligence before beginning this project. This article is aimed at developers starting out to develop a TBS game with no prior experience, looking for a place to start their journey. I’m not claiming this is the right way to handle AI and I won’t vouch for the sanity of the code (or anyone reading it).

Prologue: Mini Wars – #7DRTS and the AI in Pimps vs Vampires

Artificial Intelligence is, in my opinion, one hell of a Goliath – when you know nothing about it. Up till this point I was scared to approach or research it, thinking that the complexity that resided in it would be far beyond my skills as a need-to-be programmer, and, to some extent – is. The first time I tackled with it I had the luck of needing nothing more complex then an alzheimer behavior for my NPC’s. In Pimps vs Vampires, a 2D roguelike-like, my AI is nothing more then a simple pathfinder implementation and it works something like this:

  • Get the first movable Vampire unit
  • Find a random position on the map that is empty (no unit at those coordinates, no walls or other objects)
  • Find shortest path to goal
  • Movement loop: Is our vampire there? No -> keep moving. Yes? -> find random position, computer path, move towards it.
  • If player.x/.y is on a position inside that vampire’s path and distance between player and vampire is shorter then X/Y then set unit goal to position.x/.y in range of attacking.

And for a game such as PvV things seemed to work out well, especially with the Field of View. The fact that a Vampire would only notice the player based on distance check AND location inside a path unwillingly created the possibility for the player to hide behind a wall, hoping that the enemy will pass him.

Last July I took part in the #7DRTS challenge issued on the Ludumdare website by the lovely @Sorceress. I wanted to design a TBS (I know, RT =/= TB) in two days. And I did. And the AI was so bad, the lack of a proper pathfinder implementation so noticeable that I immediately regretted that I made the game. Thus, I set up to amend for my sins and remake the entire entry. The goal at first was to re-write the implementation for unit behavior and make the game feel more like a TBS. But, before I get into that, let me describe how the AI worked in Mini Wars:

  • Get a random movable unit
  • Get the location of a random healthy enemy unit
  • Check the unit’s move range capabilities (and subtract the cost for each tile from it’s Action Points)
  • Select a random position in range who’s distance check between unit.x/.y and enemy.x/.y is the smallest.
  • If in attacking range, subtract HP for the enemy. If the enemy wasn’t dead, subtract HP from our unit.
  • Remove unit from the list and pick a random movable unit.

What word is most common in the above description? Random. As far as strategy goes, random is not a proper one (unless you are young Goku fighting against Jackie Chun in the first martial art tournament).

Developing a good-enough TBS AI is hard work:

My goal for the AI in Mutant Gangland is be good-enough to challenge a player, not necessarily beat him. I didn’t set up to design a world-class chess-like AI that would stomp over the player and mug his grandmother while at it. And, through out the course of 3 months of development, I came close to achieving that goal. The game is currently at the 8th iteration, code named Harrold (8th letter in the Alphabet). Before I start describing how Harrold functions, post some information regarding the behavior of those that processed paths before him, starting with:

  • Alice:

Lovely Alice (the 1st) was based on a slightly improved version of the Mini Wars AI. Aka, it worked in the same way, but it would check for a proper path and move along it. She was nothing fancy and in no way anything interesting. Units we’re being built at random and she would search for random spots to move towards.

  • Ben

Ben was the second AI I worked on. It used the same code base as Alice but it was taught to react to an opponent unit. And by reacting I mean moving towards it and attacking it. Safe to say, no strategy there. Although Ben did do something slightly “novel” when it came to moving towards a location: He would score each tile in his range (based on distance checks). Scoring worked something like this:

  1. Loop through the available locations in range that were empty
  2. Check to see if on that location there’s a building present (house or temple)
  3. Check to see if on that location there’s a enemy unit
  4. Score location for buildings: score = score + (getBuildingScore( ) ) + (building score modifier) + mapSize – lengthToLocation . Building / enemy score modifier  would increase or decrease based on the type of the building and if it was a building owned by the player, a neutral building or an enemy building.
  5. Score location for enemies: score = score + distanceToEnemy + scoreModifierIfEnemyCanBeKilled.
  6. Check if current score is bigger then the previous score. If true then previous score = current score. Best location = new locations.
  • Christian and Dave

The 3rd and 4th iteration, hacked upon Alice and Ben behavior. Allot of stuff was hard-coded into them using the same principles. Dave would put up a good fight against itself but only on a map with little to no obstacles (square, flat, map). Here’s a video showing Dave fighting against himself: http://www.youtube.com/watch?v=hkT5SG2LiDA

  • Elenoir

The 5th installment, was written from scratch. She would first create a table with all the positions she could move to and score them based on: Terrain Modifiers (attack, range, damage), distance to travel and proximity to buildings and units. It was all fine and dandy, with the exception that she had no sense of self preservation and defense. She would also wonder off trying to reach a factory in the upper part of the map rather than capturing the enemy last remaining hq (hypotesis, she never did manage to play a good enough game to capture all their hqs). In order to get Elenoir to have a better sense of what’s happening around her I added influence maps to the game thus, Francois was born.

You can check out a video of her in action here: http://www.youtube.com/watch?v=mBXpXpzOfnI

  • Francois

Francois (6th AI) had allot of similarities to Elenoir but he also was aware of the battlefield. In order to get him to move across it I’ve point him towards locations of conflict (areas where both players had units on the influence map). This was done based on a small distance check. He would score possible moves and pick the one that was closest (among other factors) to the conflict zone. And it proved to play a nice game. But Francois had one big flaw: He hated gaps and collisions. He would reach a position next to a gap and wait patiently. From his point of view, moving left would take him to a spot further away from the closest possible distance to the conflict zone. Moving right would have the same effect, so he would decide to just stand and wait (for an iPhone 5S) for days (turns).

Francois fighting against himself on a Symetric map: https://www.youtube.com/watch?v=8Bu6Jh7OtzE&feature=player_embedded

What I did not consider is how the AI would perform in a slightly more Asymetric map. At this point, the AI system uses two inputs for information:

  1. A) Influence map wich is seeded each turn
  2. B) Locations of all enemy Headquarters

When no goal can be completed in the same turn (aka no building nearby or no enemy in range) the AI would look at goals further away. Thus it would choose a random HQ owned by the player and searched for a path that passed through a conflict area in the influence map. The problem that arose from here is that the units were moving towards the conflict zone through a distance check, which performed perfectly when there were no deadzones (collision zones). What happened is that the AI would reach a point which it considered closest to the conflict area (that can be 2-3 tiles away from it) but with no way to reach it, so it hanged around in that part of the map. You can see this behavior in this video:

Francois fighting against himself on a Asymetric map: https://www.youtube.com/watch?v=gVn7ogHUFVo&feature=player_embedded

  • Gharcea

The 7th iteration. He seemed to play a better game and was more tactical then his brethren. If I learned something from the previous AI’s is that it’s extremely easy to get a unit to react to something exactly one turn away. Thus the 7th installment decided to abuse this feature. I decided to split the AI into two parts: A Tactical Component, that keeps track of enemies and buildings and sets goals for the units, and an awareness module. When the turn starts the TC selects a unit from the “active units list”. It will then check if the unit can perform an action itself, without any orders. Thus, the unit will check to see if there’s a building in range that it can capture or an enemy unit that it can engage. If none are present then the TC will evaluate the field and point the unit either towards a building or an enemy. The TC will also kick in and override the awareness module if an enemy unit is within range of one of it’s buildings. For now it reacts to threat by selecting a few units with a high enough score (and if none present, any unit it can) to engange the opponent before it can capture a building. I have recorded a video of me playing against Gharcea, trying to see how it reacts to threats and see if I can trick it to send all his units against one of mine. I was surprised to how fast it overwhelmed me and I decided to do a commentary on this (note, I used my laptop’s mic to record it. Audio quality is terrible).

Video featuring me taking on Gharcea: https://www.youtube.com/watch?v=3zXxNeh1YLQ

  • Harrold

With version 0.1.9 I introduced classes to the game: Assault units (which can conquer buildings) and Battle Units (high damage output). Gharcea was in no way prepared for this so a new AI was needed. The 8th iteration was dubbed Harrold. My approach for him was to split the AI modules once again and focus on the class system. Early in the game he will build scout units and focus on capturing buildings in order to gain funds. Later on he will fortify his new territories by sending in Battle Units (Rifle and Rokkit’s).

Assault units:

From Harrold‘s perspective, assault units are only useful to capture buildings. They will only engage enemy units if they can survive the battle. At the start of the turn, Harrold prioritizes enemy and neutral buildings. Then he checks which scout can reach each of them in one turn and sends them appropriately. Here is a code snippet on how an assault unit chooses where to move to.

Battle units:

As opposed to scouts, Harrold uses his Battle Units to engage and clear out enemies that threaten his “supremacy”. He will loop through a list of enemies and prioritize them based on: Proximity to one o his own buildings, proximity to his units in process of conquering, type of the enemy unit and the amount of turns needed to reach said enemy. Another code snippet on how he selects a target.

At this point, I’m happy with how the current AI behaves. It still needs more work though, especially when it comes to creating units based on threats. A next step in getting Harrold to play better is smart creation of units. This will be accomplished by adding another AI module that governs each building individually, creating units based on needs.

Departing words:

That’s how I handle things when it comes to AI in my current game. There’s allot of room to improve and stuff to learn. Hopefully next week I’ll write a follow up article on an improved version of Harrold (probably named Irene). Thank you for reading this article and if you have any questions, suggestions or just want to say Hi, leave a comment bellow. Here’s a departing gif from me, showing the current status of the game:

Advertisements

2 thoughts on “Developing a “good-enough” TBS AI – Mutant Gangland

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s