Making Sokoban Levels

Disclaimer: I am not an expert in game design or in puzzle games. I just share my experience and my thoughts of how I make levels and how I think they should be made.

How do I make levels for Ailin: Traps and Treasures (ATnT)? Well, that is a good question.

ATnT is a block-pushing puzzle game that is heavily inspired by Sokoban (which basically created the whole genre). There are several important elements to each level:

1. There are walls and obstacles. In the original Sokoban, all obstacles are just walls, but in my game, I added various props and objects that act as obstacles (more on those later).

2. There are boxes that you can push.

3. There are destination points.

4. And, of course, there are clear paths (empty cells).

That's it. Every Sokoban level can be described in these terms. While working on my game, I found a website that contains a collection of Sokoban levels from different games. It really helped me during the development and acted as an inspiration point.

Sokoban level 1

I also did some research on how to make Sokoban level procedurally. Here is what I found (briefly):

1. In general, all puzzles can be divided into two categories: hand-made (Sokoban) and procedural (Minesweeper, Sudoku). The difference is that for procedural puzzles, there are deterministic algorithms that can create levels with a given complexity/difficulty, and those levels will be playable and fun.

2. There were attempts to create level-generator algorithms for Sokoban. There were two approaches: generate a random level and then figure out if it is solvable (if not, create again), and create a solvable level by backtracking from the end state (place boxes on destination points and then "pull" them in different directions, creating tracks).

3. The first approach has two general drawbacks. First, it requires a lot of computations. While generating random levels is not hard, testing them is really demanding because of all the possible movements that a player can take. In the early stages of ATnT development, I wrote a recursive algorithm to solve Sokoban levels, and if the level is larger than 10 by 10 squares, it can easily consume all 32Gigs of RAM on my Desktop. The second drawback is that even if the level is solvable, it does not mean that it would be fun to play.

4. The second approach is more promising since it does not require testing levels. However, it is still very hard to implement, and there is no guarantee that generated levels will be fun to play.

When I was doing my research, I came to this question: how to define fun in block-pushing games? What is an interesting level? Or, what is a boring level?

Let's take a look a the most basic level (in ATnT level editor):

There is only a character, a treasure chest, and a destination point. There are even no walls (except for the so-called south wall that delimits the level). To clear this level, a player needs to make only one move - push the chest to the right. This level is boring because it does not provide any challenge. Let's make it a bit more complex.

You will have to make more moves now, but the challenge is relatively the same: you just need to push the box to the yellow dot, and that's it! There is no puzzle in here. Let's add some more details.

That is more interesting. There is now an obstacle that you need to navigate around. Still, it is not a challenging level, but it can explain the basic mechanics of the game: you can push chests but not pull them. We need to make the level more demanding, and more challenging.

Now, here we introduce a room for error. Left-to-right movement is very natural in games, so we can expect at least some players to move this chest to the right, putting it in a dead-end position. This introduces some frustration if the game does not have an UNDO function (ATnT does, just press the Z button).

To make levels more challenging, we need to add complexity: for example, we can make more complex navigation in the level and more possible paths:

I think this level can serve as a good introductory level, but it is a bit too boring. Why is it boring? You can solve this puzzle in your head before it is solved in the game. For this level, you will have to take 20+ turns moving the player around obstacles, but the movement itself is going to be too predictive, so, at some point, it will start feeling like doing nothing in the game, meaning not playing it.

So, here are the ground rules which I apply during the level design:

1. Try to provide challenges that can not be solved in the head.

2. Try to avoid meaningless movements.

These very general "rules" can be translated into more specific principles that I tried to follow (sometimes, I unfortunately failed).

Keep the level smaller rather than larger.

Large levels lead to more movement, including meaningless movement that could be avoided by making the level smaller while keeping the level of complexity. There are still large levels in ATnT, but they are pretty complex and often offer many ways of solving them.

Introduce additional interactive elements

Such as movable boxes to increase complexity. And combine them. Cognitive science says that people can follow around 4-7 discrete objects at the same time, so having more objects forces people to plan and think about their actions ahead. In ATnT, I have additional mechanics that player needs to think of when solving the levels:

1. Movable boxes. They can block your way, or they can clear the way if you move them on top of spikes.

2. Spikes. They will damage Ailin causing instant GameOver, but you can move boxes of chests on top of them to disarm them. It will take 12 turns for a spike trap to recharge, leading to interesting situations in which you have to plan your moves carefully or risk being stuck.

3. Spiders and torches. Spiders block paths, and the player can not come close to them unless holding a torch. A torch on the ground would block the path for boxes as chests, so you need to plan where to put the torch. Also, boxes and chests will block spiders who got scared by a torch from reappearing.

4. Mines. A mine will explode if you put a box or a chest on top of it. You can detect mines with the scanner and place a marker on the ground (red X sign), which will block the boxes and chests.

In general, each mechanic can be seen as an obstacle and an opportunity. This is an approach that I developed through the months I spent working on ATnT.

Avoid repetition

Here is the first level of Sokoban recreated in the ATnT level editor:

At some point, I was even considering including this level as a tribute to the original Sokoban but eventually decided not to do that. The reason is simple: this level has a lot of repetition. Specifically, to solve it, you need to move six chests along these two red lines:

This is the kind of repetition I try to avoid by introducing alternative paths. For example, in the 3rd Level of ATnT, there are two general paths, each for a pair of chests.

Avoid early mistakes that become obvious only later

In general, this means the following. There are sometimes moves that a player can make and block themselves from solving the level, but this mistake might not be obvious when it is made. Specifically, I had to remake several levels that had this situation: the player moves a box or a chest to a particular cell which seems irrelevant for solving the rest of the levels, and several minutes after, this cell is needed as a part of a path, but it is already occupied, and there is nothing you can do with it. For example, in Level 48, there is a "bottleneck" that is not obvious from the very beginning, but it becomes very visible when you move more and more chests to destination points. By the end of this level, each cell at this choking point becomes crucial, and if you place a box in the wrong cell at the very beginning, you might have to restart the level.

As I mentioned, I can not always follow all of these rules. Some of them are ignored intentionally to create an additional challenge for players. However, I think, in general, they should work fine for a Sokoban-inspired game.