Stuck in the Middle: Generating Levels without (or with) Softlocks

When generating game levels, it is desirable for them to be completable.Depending on the designer's goals, it may also be desirable to generate levels without softlocks.A softlock is a situation where the player has not won or lost, but cannot make progress toward the goal, and is thus stuck (unless they reset, or possibly lose the level).In this work we present a constraint-based approach to generating 2D tile-based levels that are completable and do not have areas where the player can get stuck.The approach uses a constraint-based reachability categorization of locations during level generation.This categorization can be used to prevent softlocks by ensuring that all locations reachable going forward from the start of the level are also reachable going backward from the goal, unless they are sinks (areas where the player will inevitably lose the level, e.g.falling off the bottom).Using this approach, it is also possible to intentionally generate levels with softlocks and to repair levels to remove softlocks.