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.