Home   LARC   News   Publication List   Publications by Subject   Procedural Content Generation

Sokoban Generator

Sample levels.

Joshua Taylor and Ian Parberry, "Procedural Generation of Sokoban Levels", Proceedings of the 6th International North American Conference on Intelligent Games and Simulation (GAMEON-NA), pp. 5-12, EUROSIS, 2011.

Abstract

We describe an algorithm for the procedural generation of levels for the popular Japanese puzzle game Sokoban. The algorithm takes a few parameters and builds a random instance of the puzzle that is guaranteed to be solvable. Although our algorithm and its implementation runs in exponential time, we present experimental evidence that it is sufficiently fast for offine use on a current generation PC when used to generate levels of size and complexity similar to those human-designed levels currently available online.

What is Sokoban?

Sokoban (Japanese for "warehouse keeper") is a top-down puzzle in which the player pushes boxes around a grid into specially marked destinations. Only one box may be pushed at a time, and boxes cannot be pulled. For example, the image at right shows how to move a single box to the destination location, which is marked with a cross in the top left corner. The player is represented by the yellow bulldozer. See the Wikipedia article and the Sokoban Wiki for more information about this game.

To play it yourself, download (for example) JSoko, an open source Java implementation of Sokoban. The screenshots in this webpage were taken from JSoko. (Disclaimer: We are not the creators of JSoko, and therefore cannot be held responsible for its content.)

Image.

Four Levels Solved

The following video shows four levels generated by our procedural generator being solved using JSoko's autosolver. These are not necessarily the best solutions, nor are they the best possible, but they are certainly plausible and give some indication of the difficulty of the levels.

Try Our Procedurally Generated Level Sets Yourself

Image

The following level sets were created by our generator. Each one starts with easy (sometimes trivial) instances, and gets harder with each one you solve. To try it out for yourself, first install JSoko if you haven't already, then download one or more of the files below into your JSoko folder. (Note that each level set below is a human-readable text file.)

In JSoko, select Load Level from the menu bar, then External Level. You will see a dialog box containing a list of files. Select one, click the Open button, and start playing.

More Information

Image.

Created January 28, 2011. Written in HTML 4.01 and CSS 3 using vi. Last updated February 10, 2015.

Valid HTML 4.01 Strict Valid CSS!