The Unexpected Consequence of Incremental Design Changes

Nathan R. Sturtevant, Nicolas Decroocq, Aaron Tripodi, Matthew Guzdial

Introduction

Designing a compelling puzzle level is a delicate balancing act. A single block placed incorrectly can turn a masterpiece of logic into a trivial exercise or, conversely, an impossible chore. Human designers, while creative, often struggle to predict the "butterfly effect"—how a localized change ripples through the game's mechanics to alter the optimal solution. This paper investigates how Exhaustive Procedural Content Generation (EPCG) can be used to map these consequences, helping designers refine their work by identifying hidden shortcuts and untapped potential for challenge.

Methodology: Exhaustive Search for Design Insights

The researchers employed an EPCG framework to analyze the popular indie puzzle game Snakebird. Unlike traditional Procedural Content Generation (PCG), which often seeks to generate entirely new content from scratch using stochastic methods, EPCG focuses on methodical, incremental variation of existing designs.

The system operates in three distinct stages:

  1. Generation: For a given level, the generator identifies all non-essential tiles (those not part of the core bird or exit mechanics). It then produces every possible variation where exactly one tile is swapped for another type, such as Sky, Ground, or Spike.
  2. Evaluation: A Breadth-First Search (BFS) solver calculates the shortest possible solution for every generated variation to measure the impact of the change.
  3. Selection: The system flags the "Max" change (the swap that most increases solution length) and the "Min" change (the swap that most decreases it).

The Butterfly Effect in Puzzle Design

The most significant finding of the study was the sheer impact of a single-tile modification. In many cases, swapping just one tile could more than double the solution length. For example, in one analyzed level, changing a "Ground" tile to a "Spike" increased the optimal move count from 27 to 58.

Figure 2: A single tile modification in a Snakebird level. Even minor changes to a single tile (a vs b) can drastically alter the optimal path and bird positioning required to solve the puzzle.

This sensitivity suggests that human designers often operate with "blind spots." In Snakebird Level 39, the EPCG tool discovered a shortcut that allowed players to bypass the intended core mechanic of the puzzle. By highlighting these "Min" changes, the tool can alert designers to unintended solutions that undermine the level's difficulty.

Human Perception of AI-Modified Levels

A key question was whether longer solutions actually translated to a better player experience. To test this, the researchers conducted a user study with 58 participants, comparing original levels with their "Max" EPCG-modified counterparts.

Figure 5: Comparison of level variations where small shifts in block placement (a vs b) create new obstacles or remove shortcuts, significantly impacting the solution length and navigable space.

The results were telling: 65% of players preferred the EPCG-modified levels. Participants rated these versions as significantly more "interesting" and "challenging." While frustration levels also rose, the lack of a significant difference in "fun" or "enjoyability" suggests that the AI successfully increased the intellectual depth of the puzzles without making them tedious or unfair.

Conclusion and Future Directions

The study demonstrates that incremental, exhaustive search is a powerful tool for "mixed-initiative" design. By providing real-time feedback on the consequences of every tile placement, such tools can help designers navigate the complex state spaces of modern puzzle games.

Future work will focus on overcoming the computational limits of BFS solvers, potentially through A* search or heuristic-based approaches, to allow for the analysis of even more complex levels. The ultimate goal is a "consequence heatmap" integrated directly into level editors, making the invisible ripples of design changes visible to the creator in real-time.

Summary updated

Abstract

Human designers may find it difficult to anticipate the impact of small changes to some games, particularly in puzzle games. However, it is not difficult for computers to simulate all mechanical impacts of such small changes. This suggests that computers might be able to aid humans designers as they build and analyze game levels. This paper takes one step towards this larger goal by studying how Exhaustive Procedural Content Generation (EPCG) can be used for analysis of incremental changes of existing game levels. Using an incremental EPCG approach, we analyze all of the levels in the popular puzzle game Snakebird, showing that incremental variations in the level designs can significantly increase the length of the shortest possible solution. A user study on a subset of these modified levels shows that the modified levels are both interesting and challenging for humans to play. Thus, through the analysis of Snakebird, we demonstrate the broader potential for incremental applications of EPCG.
BibTeX
@inproceedings{sturtevant2020unexpected,
  author = {Nathan R. Sturtevant and Nicolas Decroocq and Aaron Tripodi and Matthew Guzdial},
  title = {{The Unexpected Consequence of Incremental Design Changes}},
  booktitle = {AIIDE},
  year = {2020},
}
Figure