Gamasutra is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

Gamasutra: The Art & Business of Making Gamesspacer
Automated Testing: Building A Flexible Game Solver
View All     RSS
March 1, 2021
arrowPress Releases
March 1, 2021
Games Press
View All     RSS

If you enjoy reading this site, you might also want to check out these UBM Tech sites:


Automated Testing: Building A Flexible Game Solver

October 27, 2011 Article Start Previous Page 3 of 3

Fedex quests. In some cases, we must walk through several scenes to complete an action, repeatedly. This quickly overflowed our search depth limit. This is a problem that may also affect the player, and we have solved it by using the same trick as used in the gameplay. We used the custom object "map" that is obtained in the third chapter of the game. We add the ability to shorten displacements using map's hotspots. This solution is interesting, as we show that the CPU's solving limits can be the player's limits, too.

Goals that are too far away from the current point. Sometimes it takes many actions before you can open or close a quest. The quest book gives us some goals far away from our game state. To solve this, we added the content of the inventory as mid-objectives; each inventory change becomes a goal accomplished. Since we are a point 'n' click game, gathered items are meaningful.

Inventory loop and quest loop. This problem is related to the state loop, in that unfortunately, some items can be consumed, and obtained again with very little action. Plus, some items are stackables -- up to 99 of an item.

We first tried to solve this by only using dropped items as goals. However, this will shortcut the cases where we must drop an object to continue the adventure. The solver will add it and remove it instantly (as a new short goal) in a loop.

As a solution, since only a few items of the inventory can lead to this problem, we chose to blacklist theses. In the same fashion, some quests can be reopened after being closed. A similar blacklist solution successfully removed these cases.

Another idea is to keep a full solving history through fingerprints, and stop the search if a previously explored game state is met. We didn't try it, as blacklisting proved sufficient. However, this may be an interesting development, avoiding hard coding.

Finally, here are some numbers from the game:

  • Backup (game state) size: approximately 2kb
  • Number of scenes 70
  • Number of characters 75
  • Number of Boolean variables 1272
  • Number of integer variables 49
  • Branching factor: about 3.5
  • Maximum depth search: 17 (may be quite long on a Nintendo Wii)
  • Test time: about 30 minutes to complete the adventure (with game sped up 4x) on a Nintendo Wii.


As we saw, the execution of a game solver requires the processing of game logic data. This leads to load multiple levels / scenes together (if not all), so there may be some significant changes in the game engine. Furthermore, this technique is depends of the use of the quest dictionary to search.

For another type of game, another provider for goals has to be found. This method allowed a continuous logic test of the game. This gave us a very high value at a reasonable cost. We tested continuously from early in the development phase to final test phase. The final test phase has far less bugs from this method, and reduced the time to polish.

As an extension, we added the ability to dynamically create variants of the adventure by adding random events. The solver is able to resume execution from any state of the game. A wide variety of solutions, including testing non-linear level design is now possible at low cost! It makes better use of testers: they are no longer blocked due to a crash on the critical path. So we can spare time on bug fixing.

This method can be combined with other methods like those seen in "Mario AI Competition" by Sergey Karakovskiy Togelius and Julian, to solve skill-related gameplay. A pathfinder could also be useful if some events are locked by spatial access. Many action or adventure games could use such tools to do automatic test.

To conclude, the good performance of this solver gives the possibility to use it to help the player in his quest if blocked, similar to the "super guide" that can be seen in New Super Mario Bros. Wii. The advantage is to use the player context: in an RPG, the solver will suggest different solutions if the hero is a barbarian or a magician.

Another possibility is full tree exploration. This way we can certify that no sequence of actions can lead to blocking the main quest. We can also collect some metrics, like depth from quest solving, identifying hard quests to solve.

Thanks to Wizarbox, Sébastien Duperron, Aurélien Pocheville, and Claire Roger.

Article Start Previous Page 3 of 3

Related Jobs

Crate Entertainment
Crate Entertainment — Boston (Work Remotely), Massachusetts, United States

Senior Gameplay / Engine Programmer
Bitwise Alchemy
Bitwise Alchemy — Austin, Remote, Remote

Senior Software Engineer (Remote)
Sucker Punch Productions
Sucker Punch Productions — Bellevue, Washington, United States

Audio Programmer
Square Enix Co., Ltd.
Square Enix Co., Ltd. — Tokyo, Japan

Experienced Game Developer

Loading Comments

loader image