Building Exospecies AI: Inductor HTN in Exospecies

Next:

Previous:

!!!! Spoiler Alert !!!!

Learning how the AI works in a game removes some of the “magic” as well as the fun of trying to figure out how to beat it. This post talks about a lot of specifics that could spoil your fun…

!!!! Spoiler Alert !!!!

In the previous post we went through building an HTN using the Inductor HTN Engine using a simple example. This post will go though real code from the Exospecies game AI to show some of the complexities that can happen.

Before we get into details, here are some high level facts about building the Exospecies AI using HTNs:

A couple of unexpected side benefits of using HTNs:

Using the HTN engine in Exospecies was exactly like integrating HTNs into any app (like the simple example from the previous blog post), there were three steps:

  1. Convert the app state you need to process into Prolog Facts
  2. Write the HTN Axioms, Methods, and Operators you need and use the Facts
  3. Convert the Operators that get generated into changes, moves, or whatever makes sense in your app

Let’s go step by step and see how this was done in Exospecies.

Step 1: Convert the app state you need to process into Prolog Facts

The engine needs to operate on Prolog facts. To do this, there is a simple class in Exospecies that walks through the structure of the game and converts the state into text, which is really straightforward code. Turns out this is a surpisingly small set of facts and most of them can be computed once, when the game first starts, and just reused. It is a very small amount of CPU work each turn.

When this class is done, in the current build, here are all the facts that serve as input into the engine:

/* Created once and cached: Facts about unit actions that never change */
player(Player2). enemyPlayer(Player1). 
supplyUnit(Queen). action(Queen,Move,3). 
  moveSpeed(Queen,1). action(Queen,Attack,10). 
  attackDistance(Queen,Attack,1,1,0). 
  attackDamage(Queen,Attack,30). 
  action(Queen,Transport,24). 
supplyUnit(Dynamo). action(Dynamo,Move,3). 
  moveSpeed(Dynamo,1). action(Dynamo,Attack,10). 
  attackDistance(Dynamo,1,1,0). attackDamage(Dynamo,30). 
  action(Dynamo,Transport,24). action(Dynamo,Disrupt,7). 
  disruptDistance(Dynamo, 2).
action(Worker,Move,6). moveSpeed(Worker,2). 
  action(Worker,Attack,13). attackDistance(Worker,Attack,1,1,0). 
  attackDamage(Worker,Attack,61). action(Worker,Tunnel,6). 
action(Warrior,Move,3). moveSpeed(Warrior,1). 
  action(Warrior,Attack,30). attackDistance(Warrior,Attack,2,3,0). 
  attackDamage(Warrior,Attack,75). action(Warrior, StoreEnergy, 21). 
  action(Warrior, ReleaseEnergy, 0). storeEnergyDistance(Warrior, 6).
action(Drone,Fly,13). moveSpeed(Drone,4). action(Drone,Attack,14). 
  attackDistance(Drone,Attack,1,1,0). attackDamage(Drone,45). 
  action(Drone, Scare, 20). scareDistance(Drone, 3). 
action(Inducer,SlugTrail,1). action(Inducer,Move,25). 
  moveSpeed(Inducer,5). action(Inducer,Attack,14). 
  attackDistance(Inducer,Attack,1,1,0). attackDamage(Inducer,Attack,45). 
  action(Inducer,Galvanize,28). perTickDamage(Inducer, SlugTrail, 5). 
action(Larva,Move,3). moveSpeed(Larva,1). 
  action(Larva,Attack,10). attackDistance(Larva,Attack,1,1,0). 
  attackDamage(Larva,Attack,30). action(Larva,HellJelly,1).
action(Vamp,Move,9). moveSpeed(Vamp,2). 
  action(Vamp,Attack,10). attackDistance(Vamp,Attack,1,1,0). 
  attackDamage(Vamp,Attack,30). action(Vamp, TempTeleport, 26). 
  tempTeleport(Vamp, 6, -1). action(Vamp, DrainEnergy, 27). 
  action(Vamp, ReleaseEnergy, 0). drainEnergyDistance(Vamp, 3).
action(Maxwell,Move,3). moveSpeed(Maxwell,1). 
  action(Maxwell,Artillery,42). attackDistance(Maxwell,Artillery,1,6,1). 
  attackOdds(Maxwell,Artillery,0.2). attackHitDamage(Maxwell,Artillery,61). 
action(Bender,Move,8). moveSpeed(Bender,2). 
  action(Bender,Attack,10). attackDistance(Bender,Attack,1,1,0).
  attackDamage(Bender,Attack,30). action(Bender, SpaceBend, 13). 
spaceBendDistance(Bender, 2).
initialLife(Worker, 66). initialLife(Warrior, 100). 
initialLife(Queen, 53). initialLife(Drone, 53). 
initialLife(Larva, 33). initialLife(Maxwell, 100). 
initialLife(Bender, 53). initialLife(Vamp, 53). 
initialLife(Inducer, 66).

/* Created once and cached: The tiles in the current map 
(this one is a simple map that is a 8x8 grid) */
tile(0,0).tile(1,0).tile(2,0).tile(3,0).
  tile(4,0).tile(5,0).tile(6,0).tile(7,0).
tile(0,1).tile(1,1).tile(2,1).tile(3,1).
  tile(4,1).tile(5,1).tile(6,1).tile(7,1).
tile(0,2).tile(1,2).tile(2,2).tile(3,2).
  tile(4,2).tile(5,2).tile(6,2).tile(7,2).
tile(0,3).tile(1,3).tile(2,3).tile(3,3).
  tile(4,3).tile(5,3).tile(6,3).tile(7,3).
tile(0,4).tile(1,4).tile(2,4).tile(3,4).
  tile(4,4).tile(5,4).tile(6,4).tile(7,4).
tile(0,5).tile(1,5).tile(2,5).tile(3,5).
  tile(4,5).tile(5,5).tile(6,5).tile(7,5).
tile(0,6).tile(1,6).tile(2,6).tile(3,6).
  tile(4,6).tile(5,6).tile(6,6).tile(7,6).
tile(0,7).tile(1,7).tile(2,7).tile(3,7).
  tile(4,7).tile(5,7).tile(6,7).tile(7,7).
startingPosition(Player1,tile(0,0)). 
startingPosition(Player2,tile(7,7)).

/* Created each turn: These are facts that can change turn to turn, 
  things like position of units, etc */
/* There are only three units in this example game. */
energy(Player1,53). energy(Player2,53).
unit(Inducer_8-8,Inducer,Player2). at(Inducer_8-8,tile(8,8),0). 
  unitIdle(Inducer_8-8). life(Inducer_8-8,66). 
  attackUnitDamage(Inducer_8-8,Attack,65). slugTrailTiles(Inducer_8-8,5). 
unit(Worker_8-9,Worker,Player2). at(Worker_8-9,tile(8,9),0). 
  unitIdle(Worker_8-9). life(Worker_8-9,66). 
  attackUnitDamage(Worker_8-9,Attack,81). 
unit(Queen_9-9,Queen,Player2). at(Queen_9-9,tile(9,9),0). 
  unitIdle(Queen_9-9). life(Queen_9-9,53). 
  teleportUnits(Queen_9-9,0). attackUnitDamage(Queen_9-9,Attack,30).

That’s it! The entire state of the game used by the AI. It was surpisingly small to me at least.

Note that, just like for players, the AI doesn’t get to know about the type and positions of units it can’t see. That’s why you don’t see any Player1 units as facts above – they aren’t visible yet.

Step 2: Write the HTN Axioms, Methods, and Operators you need and use the Facts

This is obviously the bulk of the work. Just like any type of coding, there are a bizillion ways to go about this, but I took the simplest approach I could think of: Teach the AI to play using my own personal best strategy. This clearly limits how good it can get – it’ll play as well as I’d play if I was playing “my perfect game”. This points out a pro and a con of using HTNs: The Pro is that it is easy to make them act “naturally” (i.e. like a human) if you make the rules based on how a human would play. The con is that they will only play as good as that human would play. In reality the HTN does a much better job of checking alternatives than a human would, so in practice it comes up with things that are surpising. But still…

So, here’s how my approach works: The most abstract task, the one at the top of the hierarchy is called pickStrategy. Here is (some of) the real code from the current build:

pickStrategy(?Player) :- if(),
do(
    // If someone is attacking us now, defend!
    try(trace(attackSupplyUnitAttackers), dealWithSupplyUnitAttackers(?Player)),
    // If we can knock out the enemy now or in one turn, do it!
    try(trace(attackSupplyUnit), attackSupplyUnit2(?Player)),
    try(trace(moveInOneTurnToFinalAttack), moveInOneTurnToFinalAttack(?Player)),
    // Otherwise, defend ourselves against near term threats
    try(trace(attackAlmostSupplyUnitAttackers), attackAlmostSupplyUnitAttackers2(?Player)),
    
  ... etc ...
  
  ).

pickStrategy has no criteria so that all the tasks will execute. The tasks are all surrounded by try() which is a built-in directive that makes the engine attempt to execute that rule but ignore it and continue if it fails. This is how I dealt with the fact that you have limited energy in Exospecies: spend maximum energy on highest priority stuff first and then keep trying other things with anything that remains. The try() clauses allow you to keep trying lower priority things once you are close to running out in case there is something cheap, but lower priority, that you can still do.

I’ve also used the trace operator inside of each try. That operator is included in the Solution but ignored by the engine. The traces tell me why the AI did something. As an example, here’s part of a Solution given by the HTN for a game turn that I ran recently (comments added by me):

// First, defend the supply unit: don't move the Inducer, it is in the right place
trace(defendSupplyUnit), lockMove(Inducer_6-5),
// Next, Transport new units in: Do this with the Queen on position 6,6
trace(transportAll), transport(Queen_6-6, Player2, 52, 28),
// Then, Find the enemy: move the Warrior at 5,5 from 5,5 to 0,0 using the Move command
trace(findAllEnemySupplyUnit), move2(Warrior_5-5, tile(5,5), tile(0,0), Move, 0, Player2, 28, 25)
...etc...

You can see how the trace operators let me know why the AI is doing what it is doing. It is also the basis for the hint system I alluded to above. It would be simple to translate each trace into a description when the user asks for a turn hint.

That’s the highest level of the hierarchy. What happens next? Let’s go through a juicy example Method that is a Subtask in many places called moveClosestAttackerToAttackTile. If our supply unit is about to be attacked, or someone is blocking us and we can’t attack them, or for any number of other reasons, we will execute this task.

The interesting Methods below will be explained in detail later. If you know SQL, think of this just like a big SQL Query:

moveClosestAttackerToAttackTile(?Player, ?TargetUnitType, ?TargetTile, ?TargetUnitHeight) :- 
if(
    // sortBy is a built-in rule that sorts all the attackers found 
    // by a value (?DistanceToAttackRange), smallest to largest (<)
    // Thus, we'll try the closest ones first
    sortBy(?DistanceToAttackRange, <(
      // This is just standard Prolog: get all the units for ?Player,
      // their type, position, etc. unit() and at() are facts.
      unit(?Unit, ?UnitType, ?Player), at(?Unit, ?UnitTile, ?UnitHeight),
      //  Only move non-supply units.  supplyUnit() is a fact.
      not(supplyUnit(?UnitType)),
      // Get the name of the other player so we can use it later.  This is a simple rule.
      otherPlayer(?Player, ?DefenderPlayer),
      // Only move units that *cannot* already attack this tile
      // with any attack they have. We don't want to move units that can
      // already attack. attackDamage defines who can attack whom 
      not(attackDamage(?Player, ?UnitType, ?NotAttackName, 
        ?UnitTile, ?UnitHeight, ?DefenderPlayer, ?TargetUnitType, 
        ?TargetTile, ?TargetUnitHeight, ?Damage)), 
      // Returns the closest tile (?ClosestTile) that 
      // puts ?Unit in attack range of ?TargetTile
      // given the attack specified, etc
      closestTileThatPutsUnitInAttackRange(?Unit, ?AttackName, 
                            ?TargetUnitType, ?TargetTile, 
                          ?TargetUnitHeight, ?ClosestTile),
      // Finally, do pathfinding to that tile which avoids poison, etc
      // And return the best place to move in ?SafeMoveTo given all that
      findSafePathAnyAction(?Unit, ?ClosestTile, ?MoveAction, ?SafeMoveTo, 
                  ?NextTile, ?DistanceToAttackRange)
  ))
),
// Here we execute the moveCheck Subtask for any units that meet all that criteria
do( moveCheck(?Unit, ?SafeMoveTo, ?MoveAction) ).

There is a lot to describe here, but let’s start by noticing that a lot of the criteria is just looking up facts. The only Axioms called are:

And there is only one subtask:

Let’s go through all 5 to understand how it works together.

attackDamage Axiom

The attackDamage task is a workhorse of the AI. It is where I taught the AI about all the different attacks that are available. For each type of attack I wrote an alternative attackDamage Method that determines if that attack can be used (i.e. can this unit do this attack? Is the attack in range? etc) and, if so, returns the damage that attack can do. If not, it fails. Using this approach attackDamage fulfills two roles: It will tell you if unit X can attack unit Y by succeeding or failing and it will give you the damage done.

This is key: All the complexity of the different attacks (like Inducer being able to Galvanize a set of tiles that electrocute anything on them) is hidden in the implementation of these tasks, of which there are many. Callers just ask “Can X attack Y” and the right thing happens.

Here’s the real code for the simplest variant from the build, including a couple of Axioms it uses:

// Here's the simplest variant that is true for all units 
// that have a classic Attack action that just does damage 
// at some distance
attackDamage(?AttackerPlayer, ?AttackerType, ?AttackName, 
        ?AttackerTile, ?AttackerHeight, ?DefenderPlayer, 
        ?DefenderType, ?DefenderTile, ?DefenderHeight, ?Damage) :-
  // Only applies when the ?AttackName is "Attack"
  =(?AttackName, Attack),
  // Make sure the attack is in range given the unit (see Axiom below)
  unitInRange(?AttackerPlayer, ?AttackerType, ?AttackerTile, 
         ?AttackerHeight, ?DefenderPlayer, ?DefenderType, 
         ?DefenderTile, ?DefenderHeight, ?AttackName),
  // This is just a fact that is looked up
  attackDamage(?AttackerType, ?AttackName, ?Damage).
  
  
unitInRange(?AttackerPlayer, ?AttackerType, ?AttackerPosition, 
      ?AttackerHeight, ?DefenderPlayer, ?DefenderType, 
      ?DefenderPosition, ?DefenderHeight, ?AttackName) :-
  // Get all the tiles that put us in attack range of ?DefenderPosition
  // (see below)
  tilesInRangeOfTiles(?AttackerPlayer, ?AttackerType, ?AttackName, 
            ?DefenderPosition, ?Tile),
  // Then see if any is the one we're on
  =(?AttackerPosition, ?Tile).


tilesInRangeOfTiles(?Player, ?UnitType, ?AttackName, 
            ?TargetTile, ?Tile) :-
  // This is just a fact
  attackDistance(?UnitType, ?AttackName, ?MinDistance, 
           ?MaxDistance, ?AttackRadius),
  // This is a simple rule that returns all the tiles
  // in a square of radius ?MinDistance to ?MaxDistance 
  // around ?TargetTile
  square(?TargetTile, ?MinDistance, ?MaxDistance, ?Tile).

There is a version of the attackDamage Method for each attack any of the units can do.

closestTileThatPutsUnitInAttackRange Axiom

Next up is closestTileThatPutsUnitInAttackRange. No new axioms are required for this, it just uses the ones described above. Again, code is straight from the build:

// Returns closest unoccupied tile that puts a unit in attack range of ?TargetTile 
// with any attack Will only return the single best ?AttackName and the 
// ?ClosestTile that goes with it
closestTileThatPutsUnitInAttackRange2(?Unit, ?AttackName, ?TargetUnitType, 
                    ?TargetTile, ?TargetUnitHeight, ?ClosestTile) :-
  // This is just standard Prolog: get all the units for ?Player 
  // their type, position, etc. unit() and at() are just facts.
  unit(?Unit, ?UnitType, ?Player), at(?Unit, ?UnitPosition, ?UnitHeight),
  // Just return the first, closest tile
  first(sortBy(?SortValue, <(
    // Get all tiles in range for attacks (described in the previous section)
    tilesInRangeOfTiles(?Unit, ?AttackName, ?TargetTile, ?ClosestTile),
    // Axiom that estimates distance just for performance, Trivial straight line math
    distance(?UnitPosition, ?ClosestTile, ?DistanceToTile),
    // Make sure nobody is on that tile (but ourselves is OK).
    // Just checking facts
    not(at(?BlockingUnit, ?ClosestTile, ?BlockingHeight), \\==(?BlockingUnit, ?Unit)),
    // Trivial Axiom that just returns Player2 if ?Player is Player1
    // and vice versa
    otherPlayer(?Player, ?DefenderPlayer),
    // See if this unit can attack, and if so 
    // get the damage that will theoretically be done
    // Calls the attackDamage Method described above
    attackDamage(?Player, ?UnitType, ?AttackName, ?ClosestTile, 
            ?UnitHeight, ?DefenderPlayer, ?TargetUnitType, 
            ?TargetTile, ?TargetUnitHeight, ?Damage),
    // Put a pair of values in ?SortValue so we sort by both:
    // Sort by best distance, then by best attack if attacks have the same distance
    =(?SortValue, value(?DistanceToTile, ?Damage))
  ))).

So, this Axiom:

  1. Starts by getting the position of ?Unit using at
  2. Gets ALL the tiles that would put ?Unit in attack range of ?TargetTile for any attack it can do (unless one is passed in, then just for that one). So now, we have a potentially large list of tiles!
  3. Gets rid of any of those tiles that has a unit on it because we couldn’t move there
  4. Gets the damage that each attack/tile pair will do using attackDamage
  5. Sorts by how far away the tile is (?DistanceToTile), and then by damage done (?Damage) so that we’ll always pick the higher damage attack if there are multiple at the shortest distance
  6. Grabs the first, shortest attack usingfirst(sortBy(...))
  7. Returns the ?Attack and ?ClosestTile

Yes, this Method goes through a lot of alternatives, but I’ve found in practice that the engine is very efficient at it. That’s what it is good at.

findSafePathAnyAction Axiom

The final Axiom is findSafePathAnyAction. The magic here is that there are alternative versions since some units can move in different ways (like teleporting instantaneously). I’ll just describe the simplest one here which basically says “If this unit has a classic Move action, call the built in C++ function called findSafePath to figure out which is the safest tile to go to”. Not all that interesting.

findSafePathAnyAction(?Unit, ?DestinationTile, ?MoveAction, ?SafeDestinationTile, 
            ?NextTile, ?PathTileCount) :-
  // There are alternative Methods for different kinds of move, this just handles the
  // simplest Move action that most units have. Check to make sure
  unit(?Unit, ?UnitType, ?Player), =(?MoveAction, Move), action(?UnitType, ?MoveAction, ?Cost),
  // OK, this is kind of a cheat :-) findSafePath() is a built in C++ function, it was
  // just simpler to build that way...
  findSafePath(?Unit, ?DestinationTile, ?SafeDestinationTile, ?NextTile, ?PathTileCount).

moveCheck Method

If the full criteria for moveClosestAttackerToAttackTile is met, a single Subtask is executed called moveCheck:

moveClosestAttackerToAttackTile(?Player, ?TargetUnitType, ?TargetTile, ?TargetUnitHeight) :- 
if(
  // sortBy is a built-in rule that sorts all the attackers found 
  // by a value (DistanceToAttackRange), smallest to largest (<)
  // Thus we'll try the closest ones first
  sortBy(?DistanceToAttackRange, <(
    // This is just standard Prolog: get all the units for ?Player (an argument
    // to this Method), their type, position, etc. unit() and at() are facts.
    unit(?Unit, ?UnitType, ?Player), at(?Unit, ?UnitTile, ?UnitHeight),
    
    ...etc...full text earlier in this post...
    
  ))
),
// Here we execute the moveCheck Subtask for any units that meet all that criteria
do( moveCheck(?Unit, ?SafeMoveTo, ?MoveAction) ).

moveCheck is designed to be the lowest level Method for movement that gets executed as a Subtask in many different places. The goal is for it to do “whatever it takes” to move a unit from one place to another and fail if it can’t. It is another “workhorse” Method that has 7 different alternatives in the current build. The alternatives are designed to handle all the interesting cases like:

Here’s the alternative that executes if the unit can simply move without anything blocking:

moveCheck(?Unit, ?ToTile, ?MoveAction) :- if(
  // Simple axiom that ensures the unit has the energy available and isn't already
  // doing something else
  canPerformMove(?Unit, ?MoveAction, ?Player, ?Energy, ?NewEnergy), 
  // A fact that gets the location
  at(?Unit, ?FromTile, ?UnitHeight),
  // Make sure we're not being blocked by a friendly.  
  // If so, another version of this Method will be used
  not(friendlyUnitBlockingNextTile2(?Unit, ?ToTile, ?MoveAction, ?BlockingUnit)),
  // Make sure there isn't an enemy blocking us. If so, another Method will
  // be used
  not(enemyUnitBlockingPathNextTile2(?Unit, ?ToTile, ?MoveAction, ?BlockingUnit)),
  // Finally, pick a good target tile that avoids any poison, etc if possible
  safePathDestination(?Unit, ?ToTile, ?SafeToTile) ),
  // Call an operator to actually do the move
  do( move(?Unit, ?FromTile, ?SafeToTile, ?MoveAction, 
        ?UnitHeight, ?Player, ?Energy, ?NewEnergy) ).

The only significant Axioms here are: friendlyUnitBlockingNextTile2 and enemyUnitBlockingPathNextTile2 and safePathDestination. All of these call out to C++ code since they involve pathfinding and it was much easier to reuse the code the game uses for pathfinding than to reimplement it in Prolog.

The Subtask move is an Operator, so no further hierarchy gets run, we finally have the solution (for this part)!

Step 3: Convert the Operators that get generated into changes, moves, or whatever makes sense in your app

The Solution to an HTN is an ordered list of Operators. So, Exospecies just needs to interpret the Operators and do whatever they say to do.

Here is an actual Solution generated by the AI for a recent game:

trace(defendSupplyUnit), lockMove(Inducer_6-5),
trace(transportAll), transport(Queen_6-6, Player2, 52, 28),
trace(findAllEnemySupplyUnit), move2(Warrior_5-5, tile(5,5), 
    tile(0,0), Move, 0, Player2, 28, 25)

Each of the top level terms like trace(), lockMove() and transport() are Operators. Exospecies simply loops through each one and “does the right thing”:

As you can see, the output of the HTN is a set of Operators that should be very simple to translate into “real game actions”. That is basically the definition of an Operator!

Summary

Above you got to see some real-life HTN code running in production for the Exospecies AI. It was about 6 Tasks/Axioms/Operators and there are 112 in the full AI. So, yeah, there are a lot of things to write. To give you an idea of scope: Then entire Exospecies AI was about 850 “lines of code” ignoring comments, where a line of code is anything with a carriage return in it and it is all formatted like the above examples. Using this methodology, the moveClosestAttackerToAttackTile Method above is 12 “lines of code”.

Here are the original goals I set for myself when I started out:

I believe the resulting Exospecies AI is challenging, feels natural, does very few “dumb moves” and doesn’t cheat. I call it a success from that standpoint. I do think the code will be easy to maintain, and (after I built the Prolog and HTN engines!), writing the HTN rules was…well…relatively easy to implement. Compared to writing the C++ code by hand at least. I’m going to call that part a success too.

See for yourself by installing the game and trying it out! Visit the Exospecies site for more details!

Next:

Previous:

Leave a comment or question