8
\$\begingroup\$

I'm making a Sokoban-like game i.e. there's a grid that has some crates on it you can push and you have to get the crates on crosses to win the level (although I'm going to add some extra elements to it). Are there any general algorithms or reading material I can look at for how I could go about generating interesting (as in, not trivial to solve) levels for this style of game? I'm aware that random level generators exist for Sokoban but I'm having trouble finding the algorithm descriptions.

I'm interested in making a game where the machine can generate lots of levels for me, sorted by difficulty. I'm even willing to constrain the rules of the game to make the level generation easier (e.g. I'll probably limit the grid size to about 7x7). I suspect there are some general ways to do level generation here as I've seen e.g. Traffic Jam-like games (where you have to move blocks around the free some block) with 1000s of levels where each one has a unique solution.

One idea I had was to generate a random map in its final state (i.e. where all crates are on top of their crosses) and then the computer would pull (instead of push) these crates around to create a level. The nice property here is that we know the level is solvable. However, I'd need some heuristics to ensure the level was interesting.

Improve this question
\$\endgroup\$
1
  • \$\begingroup\$ That idea you have for generating levels is very interesting. Honestly I'd just go ahead and try that, rather than waiting for discussion about it. I'm guessing you could tune the difficulty of the generated levels by setting the number of pulls, and one heuristic you'd probably want is to distribute the pulls over multiple crates, both so that every crate is moved a fair amount, but also so that the player sometimes has to go back and forth between crates (I'm guessing that sort of intertwining logic is more interesting than one-crate-at-a-time). \$\endgroup\$
    – jhocking
    Sep 24, 2014 at 13:31

2 Answers 2

Reset to default
6
\$\begingroup\$

See the paper: Automatic making of Sokoban problems

From the abstract:

This paper describes our program that makes Sokoban problems automatically. Sokoban is one of one-person puzzles invented in Japan. The program consists of three stages: generation, checking and evaluation. First, candidates for problems are generated randomly by a prototype and three templates . Second, unsolvable candidates are removed by the Sokoban solver. Finally trivial or uninteresting candidates are removed by the evaluator. The problems that the program made are judged good by human experts. Creation of art by computer is an important target of Artificial Intelligence. Our work can be characterized one of the attempts to create some arts by computers.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

For solvable puzzles, it's often easy to just play the game in reverse, starting from a solved state and un-making moves either planned or at random (or in an editor.)

Sokoban fits this approach very well, and will be much easier to implement than an exclude-and-solve strategy.

Improve this answer
\$\endgroup\$

You must log in to answer this question.