Posts RSS Comments RSS Del.icio.us Digg Technorati Blinklist Furl reddit 65 Posts and Comments till now
This wordpress theme is downloaded from wordpress themes website.

Monster AI mode

I made lots of progress in 2016, but there’s more work to be done for this to become a robust playable experience.  My goal for this project is to make a reasonably complete playable game – and to get experience making it with Unreal (UE4).  To achieve that goal in 2017, the AI doesn’t need to be super advanced.  However, it needs to be functional. and I’d prefer that it makes mostly reasonable moves.

So I’d like the AI to do some of the obvious strategic things.  Pick a good attack target (eg the hero with the lowest body).  If Zargon has a room full of monsters, then surround the door entrance – don’t just blindly charge and attack through the door (a counter to door camping).  In the normal situation, we want the maximum number of monsters to get an attack, so monsters already adjacent to a hero may do (attack then move) so that another monster can take their spot via (move then attack).

Most of this can be done using branching AI rules (conditionals), though I may need to iterate through possible moves (and pick a best move using a heuristic).  Each individual monster has a set of moves.  And Zargon’s entire turn can be referred to as a “move”.  That’s because Zargon can move the monsters in any order (unlike the Heroes who have to pick a turn order at the start of the quest).  So more advanced AI would need to iterate through possible Zargon moves (rather than just individual monster moves).  Beyond that, there may be scenarios where it’s useful to consider not just the current Zargon move, but also multiple moves in advance (and possible hero moves).

My high level plan is to start with something simple.  Simple AI is enough to make the game fully playable.  Anything beyond that is really an additional feature.  I can iterate on it, and gradually decide later how much effort (for 2017) to put into improving the AI.

For now, I implemented a first pass of a simple but functional AI mode.  Previously the monsters were controlled by the player (just like heroes), and I had implemented A* – which did nothing except display a path.  In this next step, I refactored monster control to be done by an AI.

On Zargon’s turn, player control and UMG menus are disabled.  Instead, monster AI creates a list of monster AI actions (strategy design pattern).  For each hero lowest-to-highest hero body, monster AI checks for a path using A*.  If there’s a path, then add move and attack to our monster-actions queue.  Once the monster AI is done with this “planning” stage, it moves to an “execution” stage.  The turn logic state machine takes input from either the player (for Heroes) or from AI (for Monsters).  The monster-action state machine executes one monster-action in the queue at a time – execute A, wait for done A, execute B, wait for done B, etc.

For this first AI pass, the AI just blindly charges at the hero with the lowest body and attacks.  This can lead to some blatantly non-optimal Zargon moves, but it’s still a milestone because it’s arguably sufficient (in terms of AI) to make the game “complete”.  Monsters are now fully controlled by AI, and they use A* to find a path to a hero, then move to the hero and attack him/her.  Here’s a video showing the new AI mode in action:

I haven’t decided what I’ll work on next.  Some ideas are – more AI, wandering monsters, traps, spells, basic systems for win/lose, or start looking at the HeroScribe source code.  The latest release of HeroScribe was December 25th 2004, so that’s pretty old, but I still love it, and it comes with source code, so I may add some enhancements to make map editing faster.  Whatever I go with, updates will be in my next post.

I’ll definitely do some more AI in 2017, but the priority is TBD.  If I decide not to invest too heavily in making the AI more difficult, then difficulty can be increased via simpler mechanisms – more monsters, higher stats, or limiting hero power.  A highly skilled AI would be cool, though it doesn’t necessarily make the game “better”.  It could even be argued that having the monster AI be less than perfect is more enjoyable than having a flawless Zargon AI that always does the most optimal move.  To increase difficulty, it’s arguably more fun to add more monsters (rather than by raising AI skill).  On the other hand, having a really “dumb” Zargon AI as the only AI option does seem a bit lame 😉

The rest of this post is just some quick brain storming notes on ideas for how I can improve the Zargon AI.

Hero(es) in a Room

image

Monsters can (move then attack) or (attack then move).  The mummies can only move four squares, so they can’t reach the barbarian.  The orcs should attack the barbarian, then move out of the way so that the goblins can attack the barbarian.  The skeletons should attack the wizard, then move out of the way so that the mummies can attack the wizard.  If the AI system does the monsters one-at-a-time and the goblins happened to be first in the monster turn list (because they spawned first), then they would fail to attack a hero.

For Zargon’s turn, he does a number of monster moves (“move” meaning move-then-attack or attack-then-move).  The number of possible Zargon moves is limited by monster movement – mummies move 4 spaces, goblins move 10, etc.  Different paths to the same square can be considered the same monster move, so that also limits the search space.

Let’s refer to the above monsters using “north” and “south” eg orc-north and orc-south.  Orc-north can move 8 (anywhere in the room), so if Orc-north goes first, then Orc-north has 20 possible moves.  It’s actually 40 because the orc-north can attack-then-move or move-then-attack (no available attacks).  The mummy only moves 4 squares max, but to keep it simple, let’s just say 8 monsters and 40 possible moves each.  If monster turn order was pre-determined, that would be 40^8 = 6,553,600,000,000 (or ~6.5 trillion).  The total number of possible Zargon moves is actually a lot more than that because monster order is not pre-determined.

How many turn orders are there?  The number of ways to order N objects is called a permutation.  Eg six permutations of the set {1,2,3}, namely: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1).  The number of permutations is n! (aka n factorial).  8! = 40,320.  So the number of possible Zargon moves in this example is something like 6.5 trillion * 40,320 = 262,080,000,000,000,000, which is ~262 quadrillion.  And that’s for our single room with 8 monsters.  I think that’s kind of on the high end (above average), but there definitely exist scenarios in the game with more than 8 monsters and/or more than 20 possible moves per monster.  And that’s assuming we only consider Zargon’s current turn.

I’m not sure how long it would take on my Kindle Fire’s 1.2 GHz dual-core Cortex-A9 (ARMv7), but 1.2 GHz is 1.2 billion Hz.  MIPS depends on various factors such as type of instructions, execution order, presence of branch instructions, etc.  But for what it’s worth, wikipedia lists Cortex-A9 as 1.5 GHz dual-core at 7500 MIPS.  So if we checked 262 quadrillion moves and each move took 20 instructions, then maybe we’d get 375 million moves per second, so 262 quadrillion moves would take 698,666,666.67 seconds or ~22.14 years.

To improve performance and to simplify debugging, we obviously don’t need to iterate all possible Zargon moves.

One way to narrow our search space is to only consider monster moves where the monster gets an attack.  For goblin-north, this means there’s a maximum of four possible moves, or less (depending on which monsters moved out of the way before goblin-north’s turn).  For the mummies, it’s only a maximum of two.  If a monster can’t make any attacks, then we can have it move towards a hero (such as the hero with the lowest body that isn’t blocked).

Another way to narrow down our search space is that for adjacent monsters (orcs, skeletons), they can attack then move out of the way – to the nearest space that’s not adjacent to a hero.  That means the adjacent monsters (orcs, skeletons) only have one move each.  Plus, adjacent monsters can go first.

So each orc has one move, each skeleton has one, each mummy has two, and each goblin has four.  If we assume a pre-determined turn order (that puts adjacent monsters first), then that’s only 1^4 * 2^2 * 4^2 = 64 possible Zargon moves.  64 is a lot less than 6.5 trillion!

Each of these turn orders has less than 64 possible Zargon moves.  But how many trimmed monster turn orders do we have?  Orcs and Skeletons move first – they just attack then move, so we only care about the Goblins and Mummies.  That’s just 4! = 24.  So 64 * 24 = 1536.  1536 is a lot less than 262 quadrillion!

We could then search through each possible Zargon move (that we didn’t trivially skip) and use a heuristic to calculate a guess at which Zargon move is the “best”.  One idea for a simple heuristic is just to make sure we get the maximum number of attacks.  If the goblins attack the wizard first, then the mummies wouldn’t get an attack – because they can’t reach the barbarian with only 4 move.

If the mummies were orcs (with an attack of 3, and enough move to reach the barbarian), then our heuristic might prefer higher attack dice against the wizard since a good Zargon strategy is to focus on killing a hero with the lowest body (especially if the wizard has lower defense and lots of unused spells, but lets ignore that for simplicity).  So orcs would attack the wizard (with 3 attack) and goblins would attack the barbarian (with 2 attack).  If the first orc killed the wizard, then that would trigger the AI to to recalculate (the rest of) Zargon’s move.

One scenario that “breaks” the above AI is if we have an Orc next to the Barbarian and an Orc next to the Wizard.  We’d prefer that both Orcs attack the Wizard.  If the Wizard is blocked, then we may need one Orc to attack the Wizard then move out of the way, so that the other Orc can move then attack the Wizard.

So we may want to consider the possible turns with adjacent monsters going first (and non-adjacent monsters going second).  That’s less than 8! = 40,320.  Instead, it’s 4! * 4! = 576.  So our algorithm could iterate through those 576 possible Zargon moves and pick one that maximizes the number of monster attacks (in our example it’s 4 attacks).  Because some attacks are better than others (eg more higher attacks on our favorite target is better), we could include that as part of our heuristic.  We could have the heuristic calculate the move with the best odds of doing the most Body Points of damage.  However, a better Zargon strategy is to focus on killing the weakest Hero.

This scenario assumes we have monsters in only one room and there’s heroes in the room.

No Heroes in a Room

image image

But things are different if there are no heroes in the room.  Because we don’t want to let the heroes door camp.  Our game even has modified rules to prevent door camping – can’t shoot crossbow or spells through a door.  If there’s no heroes in the room, then our AI should surround the door.  It’s also nice to block corners to make it harder for the wizard to move into the room, cast a spell, then be protected by two other heroes.

If a monster is able to attack the wizard in the hallway, then it might be worth it, because the wizard is the best target (the glass cannon).  An effective hero strategy is for the wizard to move into the room, cast a spell, then the other three heroes move adjacent to the wizard to protect the wizard from Zargon attacks (or kill all the monsters before Zargon’s turn).  So going after an open wizard might be a corner case (an exception) to the standard surround-the-door strategy.

The same idea applies to another big target – a hero with low body.  We could say 3 body is “low body”, so a big target can be defined as a hero with the lowest body (the wizard starts with 4 body).  Or we could say the big target is the hero that’s easiest to kill (account for the hero’s defend dice).  Or maybe the lowest body, and prioritize the wizard as a tie breaker.  Another consideration (for prioritizing Hero targets) besides current Body is number of attack dice, number of defense dice, and number of remaining spells.

Multiple Rooms

For game balance, I already designed rule tweaks that encourage players to do one room at a time.  When attacking (or casting a spell) through a door, you can only target adjacent.  When you enter a room, the doors have a Zargon force field that prevents you from leaving until all monsters in that room are dead.  So the standard situation is one room at a time.

But for AI, we need to realize that’s not always the situation.  If the heroes don’t optimize their strategy, then they might not do one room at a time.  The game also has scenarios where a trigger causes a room to be revealed – so we can end up with monsters in more than one room.  Ideally our AI will handle other scenarios too.

If two rooms have monsters, then…  If both rooms have no heroes, then surround the doors.  If only one monster-room has heroes and the two monster-rooms are adjacent, then consolidate your monsters into one room.  If the room is full (or blocked), then wait by the door to the monster room, or surround the other door(s).

Room Camping AI

Another corner case is…  Usually monsters can wait in the room they were spawned in, because heroes will have to attack.  But in some scenarios, the heroes could open the door, look in the room, then decide to go somewhere else.  Or in some cases, a quest trigger reveals a monster room, but the heroes aren’t obliged to enter that room.  If the AI is programmed not to leave the room to chase them, then that could result in some scenarios that make the AI look bad.  We could “fix” this by not letting the heroes complete a quest until they’ve completed all rooms (eg killed all monsters), in which case we could just say the monster’s preference to stay in their rooms is actually a “feature”.

Or we could have a (should we leave the room) check to the AI.  But be careful because if the (leave the room) check is something like (wait until the nearest hero is 10 squares away), then this would be easy for the player to exploit.  One idea is to have two modes that are specified per room (in each map).  If it’s a room we want to defend, then the AI will room camp.  Else, we chase the heroes based on some trigger such as (the nearest hero is 10 squares away).  In either mode, we will still chase the heroes if they reveal a nearby room with monsters in it.  In either mode, if there’s a good target in the hallway that we can immediately attack (eg Wizard or any Hero with less than 3 Body), then we make an exception.

Trackback this post | Feed on Comments to this post

Leave a Reply