AI

• This is part of a series on how this game was implemented technically, as part of the Game Jam it was developed for. It is recommended to read them roughly in-order as later blog entries may refer to earlier ones.

Technical:

1. State Machine
2. Pathfinding/Movement
3. Isometric Rendering
4. API
5. Control Sources
6. AI
7. Networking
8. Fog of War
9. Bit Packing
10. Palette Shifting

Other:

• Portraits
• Scrapped Ideas

----

AI

This AI in this game is very simple, it reads the game state and does one of three actions:

• Idle - selects a unit
• Display move
  • if there's an opponent unit in range, click that unit (this will automatically commit the target)
  • if there's no unit in range, search for opponent units that are closest :
    • it does this by looking at the distance between an opponent and a "blue" movement square
    • distance is calculated as

      |sx-ex|+|sy-ey

    • this is not a normal distance formula, that looks like: 

      sqrt((sx-ex)^2+(sy-ey)^2) 

    • That formula takes into account diagonal distance. We only care about the distance in cells.
    • 
    • By counting the arrows, you can see that moving diagonally takes the same number of steps as moving all the way horizontally then all the way vertically.
    • The AI is comparing all of those blue cells, for the one that's closest to X (in this case, any of the blue squares on the diagonal)
• Select target
  • if the AI is in this state, it simply checks if there's any unit in range, and if so attacks it. If not, it gets set to wait.

-----

A somewhat important distinction is that the AI is not doing proper pathfinding to player units. If there's no player in range, it just moves to minimise distance between the AI and the player. E.g. if there's a wall in the way, it won't navigate around the wall.

Full pathfinding can be implemented, but it's not needed. The maps are small enough that an AI's blue/red grid will readily "box in" the player after 1 or 2 turns, at which point the AI can directly attack without pathfinding. So just moving towards the player is sufficient in most cases.

----

Super Strong AI

This is not implemented, but it was considered.  

A more powerful AI would be to use a Minimax-style search to find an optimal move to make. Minimax is what games like Chess use in their AI systems.

The rudimentary implementation would be:

• save the game state,
  • get all possible moves
  • for each move 
    • evaluate the move
    • if the game's not over, repeat all of the above

Eventually, it would determine the optimal move to make.This would work, but is computationally very expensive.  The rough amount of computation needed is approximately:

(number of moves per turn)^depth

Where the number of moves is approximately:

(size of the movement grid + number of targets)*(number of characters on team)

For example, with 5 units, 13 move cells and 5 targeting cells, this works out to be ~90 options

Looking ahead 5 turns is already: 5,904,900,000 (5 billion options) If you could evaluate 1 board state in a microsecond, it would take over an hour to go through all these moves! Note: there's 2 turns per phase, (player, enemy, player, enemy, player) so it's not looking very far ahead.

This gets even worse when considering that enemy units move order is important. For this game, the damage formula doesn't matter who attacks first. But it's common in games of this genre for units to counter-attack. If that's the case, then movement order is important, and increases the complexity dramatically. (5! times the number of moves per turn)

This is the worst-case, and more generally it could be done in tens of minutes (not hours) because the attack grid won't fill the maximum most of the time. But such strong AI isn't worth the effort. 

A strong AI would quickly realise that it can "wait out" a player, by standing outside the player's movement range and waiting for the player to walk into a bad situation. As long as the AI doesn't move, the player has to advance, which would make them lose. The game becomes a stalemate. 

Using weaker AI means the player is never put into a stalemate situation, the AI will always choose to resolve the situation by advancing forward. 

Ideally this "bad AI" would be compensated by having balance-tested maps. But given the time constraints on a game jam, it was sufficient just to get maps that work, rather than focusing on difficulty or balance.