Background
Pixel Space Horror (PSH) is a very streamlined strategy game: units can only move and attack. For movement, they have a fixed range they can move. Attacks are more varied – every unit has some special qualities when it attacks, such as whether attacks do explosion damage or whether they require line of sight.
Being turn-based, the AI doesn’t have the complications of many other games: we have plenty of time to calculate pathfinding and decisions without the player noticing any lag. We don’t have to rely on as much estimation and can take a more complete view of the scene. Further, we don’t have to respond in real-time to a changing game – the player can’t move out of the way mid-action.
However, being a strategy game, the AI comes under extra scrutiny: it has to make solid tactical decisions to wipe out an enemy team. Everything it does can be seen at all times, and if it does something stupid, players will immediately notice.
Goals
The goals for the AI system were the following:
- Don’t be stupid – enemies don’t need to think 10 moves ahead, but they can’t stupidly move back and forth every turn.
- Don’t be predictable – the game should play differently each time, and the enemies should respond differently to the exact same situations.
- Don’t be boring – if there’s one over-powered enemy, that enemy should not move every time even though it may make tactical sense.
Pathfinding
The pathfinding is crazy-simple, but no AI article would be complete without mentioning it. PSH doesn’t have the real-time, large-scale needs of many games: we have plenty of time to consider movement possibilities, and the slow speed of the units makes the decision space pretty small.
PSH uses a simple breadth-first search to evaluate all the different spaces a unit can walk. It starts at the unit and evaluates every neighboring space for walkability. Once all the neighboring spaces have been evaluated, it then repeats the process starting at those neighboring spaces, and then repeats that process again until it has reached the unit’s maximum distance and/or exhausted all walkable spaces.
This produces paths which are good enough – they may not be quite the most natural paths, but for our purposes the player won’t notice.
Decision Making
PSH uses a brute-force mechanism to determine the next action. It evaluates every possible action for every unit and uses some priority-based decision making rules to determine which action to take next.
There are three varieties of actions for the AI system to consider:
- Move
- Attack
- Move + Attack
Strictly speaking, Move + Attack is two actions, but we group them because it often looks more natural for a unit to move and then attack immediately after (it looks like the unit moved with the intention of attacking).
We evaluate an action based on the following parameters:
- Does this action kill anyone? These actions take the highest priority. If an obvious kill is left dangling, players will notice.
- How long has it been since the unit last moved? We want to spread out actions over all the units so the system doesn’t get boring.
- Does this action involve an attack? Actions that hurt the opponent take priority over actions that are simple movements.
- If this action involves an attack, how much total damage does it do? Attacks which do a lot of damage to multiple units take priority over attacks which only hit one unit for a little.
- If the action involves an attack, what kind of units are we attacking? We may want to hurt healers more than other units.
- How close will this bring the unit to the enemies?
Each of these criteria is weighted so that some are more important than others. If the unit just moved, it might move a second time in a row if that move can do a lot of damage. If it has moved three times in a row, the odds are unlikely it’ll move again even if it could do a lot of damage.
We add up all those weights to calculate a priority and then pick an action based on that priority. We don’t necessarily pick the action with the highest priority – instead, we randomly pick an action, but the actions with the higher priorities are more likely to be selected. Obviously non-ideal actions can still happen, but it’s more likely the system will pick something better. This gives us our unpredictability.
Results and Future Work
The system isn’t yet perfect. There are edge cases that aren’t being handled gracefully. For instance, if there is only a single unit left to attack, sometimes the system thinks it’s more valuable to just move away than it does to attack. This leaves it possible for the player to gain victory over an obvious defeat. Some of this can be fixed by tweaking the weights on all our criteria, but some special handling will be required to be safe.
We also don’t yet account for special units – units which heal or which apply stat bonuses. These will introduce new edge cases and new weighting considerations.
Still, the AI is producing reasonable results. It’s moving and attacking and killing left and right. It’s taking reasonable actions. I can beat it every time (some of this is the product of immature level design), but it usually takes down several of my units on the way. I’m happy thus far with the results.
