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
September 15, 2019
arrowPress Releases
September 15, 2019
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 2 of 3 Next
 

Solver: Theory

The solver is implemented as a breadth-first tree search. It will explore the states of the game, until we met our goal of approaching the end of a quest. These goals will be extracted from the quest book, since the finishing point of a quest contains the associated variables and matching values. States represent nodes in the tree. Events are branches that can be followed, to reach a new state.

It will therefore list the events of a scene, taking one and running it to build a new state of the game. This process will be repeated until a goal is reached or a search depth becomes too great. When a goal is reached, the tree is followed in reverse order to get an efficient way to reach it.

Solver: Practice

The search is done by brute force, so it is necessary to lighten up its execution. First, we need to change the architecture of the game to isolate the logic: we split the operations of the script from the rest of the game to allow their execution without loading the corresponding scene resources or the corresponding entities.

We load all the logic information of the game at one time (global information and information of each scene: the number and identification of entities and their properties) at the beginning of the solving. We create an object that gathers information on the state of the game, GameState. We can then proceed to the main loop:

1. Test end of recursion: goal achieved, depth reached;

2. Test special cases: Scene initialization;

3. Test special cases: Check combination of inventory objects;

4. List the events of the scene;

5. For each event:

  • Test event parameters (items available in inventory);
  • Execute the event;
  • Recursively call solver with new state (going to step 1.).

Solver: Challenges

This approach quickly showed its limits and many problems arose.

The first problem was the state of entities.

We assumed that the script can interact with any entity in the scene, but this is not always the case. An entity may be invisible or non-interactive, and this can change during the course of the game. The entities states are not present in the game state. Indeed, when we load a game state, the entire scene is reset, as if the player had just entered. Consequently, before each event's evaluation, we must do scene initialization. However, this solution also exhibits several problems:

  • If the script is bugged, scene initialization may fail and the solver may get stuck in a loop (this is a behavior we can wish for under some circumstances -- but it is not our goal in this situation).
  • Initializing the scene systematically associates an introduction sequence that must be executed, so the solver will spend time on useless actions.

The solution was to add the entities' state information in the game state, in compact form, to avoid doing again scene initialization after each step.

Another batch of problems came from the fact that the solver was quickly lost in useless calculations. After a quick profiling, we identified several simple optimizations:

State loop cutting. The brute force approach will fail very quickly if we waste time. We are looping on previously explored scenes during the search; we return to a scene already visited, even without game modifications. Our solution: we use a table containing a fingerprint (hash) of the game states already explored. This worked very well. Hash was faster than a full memory compare. We stop the search if we match a previously explored state.

No side effects cutting. We stop the search if an event had no side effects. This way we avoid searches done in other branches. In the same way, but this time with static information, we can check if an event's actions have a possible side effect under any conditions. If not, we filter the events that have no side effects.

Solving dialogue. In our game, dialogue is separated from the script system; it is handled by a different subsystem. However, they have the ability to check and change the game variables, hence changing the game state. Dialogues can also be seen as a tree: questions (propositions) are branches that may lead to other branches or sentences (or leaves). Some propositions are available only under some conditions. Variables can also be modified when a line of dialogue is shown.

The solver quickly finds itself stuck in the dialogues. One solution is to set up a second solver which will work with the same game data, but produce specific actions in the associated context. This solution is attractive, but necessitates some heavy work. Furthermore, only few cases were a problem for the game solver.

We used a simpler solution: the dialogue is completely covered, sequentially. All propositions will be selected, one by one. In our game, the exit of the dialog was easily found, as it was always the last proposition. This approach worked, except for the very special case of puzzles in dialogues.

Some puzzles are solved in a dialogue, but are not very common. For example, we had a story split into parts, and we needed to select the right proposition in the right order. We also had dialogues that triggered re-initialization of the scene, leading to an endless loop. We have solved these few cases by hard-coding them. This may not work in every case (the solution must be static; using a dialogue for scene navigation will fail here), but it proved simple and reliable in our case.


Article Start Previous Page 2 of 3 Next

Related Jobs

HB Studios
HB Studios — Lunenburg/Halifax, Nova Scotia, Canada
[09.13.19]

Experienced Software Engineer
AfterThought
AfterThought — Henderson, Nevada, United States
[09.11.19]

Unreal Engine 4 Programmer
Disbelief
Disbelief — Chicago, Illinois, United States
[09.11.19]

Junior Programmer, Chicago
Disbelief
Disbelief — Chicago, Illinois, United States
[09.11.19]

Senior Programmer, Chicago





Loading Comments

loader image