The General Video Games Artificial Intelligence (GVGAI) is competition where a single AI agent must beat any game given. In this case, I developed, along with Carmen Martín Moreno, an agent able to beat the demo game Boulder Chase. In this game, the character must collect, at least, ten gems and end the level reaching the exit. The level is full of enemies that can kill you and boulders that, if digged under them, will crush you.

Agent behaviour

We decided to make a reactive-deliberative agent that would trace a plan to obtain the 10 most reachable gems and, when performing the plan, would react based on the enemies and boulders that surrounded the agent.

Deliberative behaviour

When spawning the agent, the first thing it does is divide the level into six zones of equal sizes (the levels are always rectangular). Then it gives a heuristic to each zone calculated from:

• The number of gems in the zone.
• The distance from the player to the zone.
• The distance from the portal to the zone.
• The number of enemies in the zone.
• The difficulty of each zone between the agent and This zone (to avoid visiting great zones that can only be accessed through really hostile zones).

After calculating the heuristic of each zone, the agent selects the best zone and launches an A* pathfinding search to the gems of the best zone. This pathfinding algorithm does not take into account if there is an enemy or boulder in the way.

The resulting output from the algorithm is a list of actions that have to be performed to reach its destination (either move in a direction, stay put or dig in a direction).

Reactive behaviour

Once the agent has determined the path to obtain the gems, it starts moving towards that objective. Before performing the next action, the reactive behaviour is launched to assess its surroundings. If any obstacle is found, it reconsiders its actions for the next moves. In other words, the reactive behaviour of the agent is designed to help it overcome critical situations.

For example, if it has to move under a rock, the rock will fall and kill the agent. Therefore, the agent studies what possible alternatives are there. It can dig in that direction, let the rock fall and move above the rock. But if that path is blocked, then it has to find another solution. Maybe it go under the supposed path, avoiding the rock.

If the actions of the agent, or another entity, have disrupted the agent's plans, it will relaunch the A* search to trace a new viable plan to the target gem. If no viable plan is obtained, then it will select the next gem in the zone or the next zone to explore.