- What kind of AI can I give to the monsters?
In the game, the monster’s objectives are twofold:
- To collide with the player, causing the player to loose a life. (C)
- To lay tokens that prevent the player from completing a screen. (T)
Of course, the monsters need not be too efficient, otherwise the game wouldn’t be much fun!
Classes of Monster
Ideally, there would be different classes of monster, with different levels of AI. Earlier screens can be inhabited by ‘stupid’ monsters, with more ‘intelligent’ monsters occupying later screens.
Different monsters could combine strategies (see below). They could either:
- Switch strategy at random
- Weight random movement according to one or more strategy
- Try moving according to a strategy, and switch to a less effective one only if the most effective strategy is currently unavailable (eg. because a route is blocked by a wall).
Basic Strategy: Random Walk (RW)
The simplest form of AI is to allow the monster to just wander around at random. For a more ‘realistic’ wander, it would be nice if the monster would dislike reversing, and prefer continuing in the same direction than turning corners.
A monster following this strategy would be very stupid, and only achieve its objectives accidentally.
Collision Strategy: Simple Seek (SS)
The next simplest for of AI is for the monsters to prefer moving in a direction that would bring them nearer to the player. If, for example, the player is below the monster, then the monster would tend to move down.
Some maze designs would allow the player to trap the monsters in cul-de-sacs.
Collision Strategy: A* Seek (SA*)
Using the A* algorithm to seek out the player would overcome the problem with SS where monsters getting stuck in cul-de-sacs.
Unfortunately, A* can be be computationally expensive. I could limit the number of monsters using this strategy at any one time. Alternatively, I could build a A*-like solution in an iterative fashion. Such a strategy would not be optimal, but could still be more effective than SS.
Collision Strategy: Follow (SF)
I could have the player lay an invisible ‘trail’, and if the monster encounters this trail, it would follow it until the player is reached.
Obviously, this would be far from an optimal search strategy, but would overcome the cul-de-sac problem with SS, and be far less ‘cheaper’ than SA*.
Token Strategy: Prefer Locations without Tokens (T)
Monsters could prefer locations without tokens, thus encouraging them to lay more tokens.
Token Strategy: Prefer Corners and Edges without Tokens (T+CE)
Once a corner is taken, it cannot be flipped by the player. Similarly, once an edge is taken, it can only be flipped by a player along one plane.
Token Strategy: Prefer Locations without Tokens but Adjacent Existing Player Tokens (TP)
These locations could induce a flip of player tokens.
Token Strategy: Prefer Locations without Tokens that are Protected (T+CEP)
Once a monster has won a corner, adjacent locations become unflipable, and therefore desirable. This desirability spreads from the corner as tokens are placed.
Similarly, some locations are difficult to flip where they are adjacent edge tokens (but not on the edge themselves). Again, this protection spreads from the edge token.
Token Strategy: Seek the Player (TS)
If there are no other places nearby to lay a token, seeking the player could be a good strategy because she is also likely to be moving towards emply places to lay more tokens.