Algorithm to create Sokoban levels

[Janis]

An algorithm to create Sokoban levels seems not to be too hard :-]

This topic comes up every so often. Sokoban is NP hard, so, unless
somebody proves P=NP, you'll have your machine try every possibility.
There are some generators around, but they are of course limited by your

Though they are NP hard to solve I think you don't need to solve an
NP hard problem to generate Sokoban levels.

But to my YANI: Sokoban maps are far easier to generate than to solve.

I think so, too.

An idea to solve the task is to treat the problem backwards...

1.) Create a bounded random dungeon with standard NH routines.
1a.) The dungeon *may* have some fixed part(s) connected, e.g. hallway(s)
that must be passed and which are leading to the room with the stairs
to the next level.
"N holes":
2.) Select a point on the map as close as possible to the room with
the stairs up. Search from a valid "unvisited" path to that point
starting from the entry stairs.(+)
2a.) Alternatively select a random point. (Path search as in 2.)
3.) Determine the position of a virtual Reyalp(*) adjacent to the
selected point on the opposite side of the room with the stairs.
4.) Create a hole at the selected point. Mark point as visited.
5.) Let the Reyalp drag a virtual boulder from the selected point.
Reyalp may not enter points already marked.
"One boulder":
6.) Select an adjacent point for Reyalp, that is not already marked.
7.) Move Reyalp, move virtual boulder, mark boulder position visited.
8.) Iterate "One boulder" for a (random) number Z of turns, while
moves are possible and a path to the entry stairs is existing.
8a.) Undo last move if no path to the entry stairs is existing.
9.) Make the virtual boulder a real one.
10.) Iterate "N holes" for a (random) number N of holes to be filled.
11.) Remove (virtual) Reyalp.
Finish.

(+) Step 2a) needs a bit more work: a valid path to Reyalp(*) must
also be existing, otherwise select a new point or stop interation.

(*) Reyalp: player backwards.

Though the resulting levels may not have an appealing design, I think
the above algorithm will work. The levels of course can not have the
finesse of the constructed elaborated levels, they are random. But
depending on whether you chose to allow fixed dungeon parts (1a.) and
whether you allow random holes (2a.) there may be quite interesting
new topologies generated. And the level difficulty may be tuned by
selecting appropriate values for N and Z.

(I'm currently working on a lot of sokoban related stuff, so who
knows? maybe I can do it one day)

If I have not made any mistakes - that's of course unlikely, I just
hacked it onto the paper ;-) - you might want to try that algorithm.

Feedback and hints to errors made are welcome.

Janis, the Reyalp, smashed by a boulder

[Sam Dennis]

Post by Janis
An algorithm to create Sokoban levels seems not to be too hard :-]
[simplistic algorithm]

Unless I'm mistaken, ignoring the unsought technical mistakes that may
or may not have been present, your levels would all be solvable with a
player interacting with each boulder only for a single, unbroken time.

To say that this would create dull levels is an understatement of very
rarely matched or bettered magnitude (although this particular will be
rectified with little change to the algorithm).

Even if fixed, the levels it produces are probably still quite boring,
partly because of the standard NetHack map generation but likely for a
great many other reasons. The method is simple enough so you might be
able to prove me and other sceptics wrong with a demonstration, if you
still think it might be a reasonable approach.

[Michal Brzozowski]

Post by Sam Dennis

Post by Janis
An algorithm to create Sokoban levels seems not to be too hard :-]
[simplistic algorithm]

Unless I'm mistaken, ignoring the unsought technical mistakes that may
or may not have been present, your levels would all be solvable with a
player interacting with each boulder only for a single, unbroken time.

You are not mistaken.

Post by Sam Dennis
To say that this would create dull levels is an understatement of very
rarely matched or bettered magnitude (although this particular will be
rectified with little change to the algorithm).
Even if fixed, the levels it produces are probably still quite boring,
partly because of the standard NetHack map generation but likely for a
great many other reasons. The method is simple enough so you might be
able to prove me and other sceptics wrong with a demonstration, if you
still think it might be a reasonable approach.

Altough the algorithm above produces levels that are pretty easy to
solve, the general idea behind it is a good approach. You start with
all builders in their holes, and make the "reyalp" pull them instead
of pushing. After a random number of turns he leaves one builder and
goes to another one (random), and pulls it in some random directions.
After a finite number of turns, he stops and stairway is created at the
square he is standing on. The problem with this might be that quite
often the levels will still be too easily solvable. But I think that
adding this feature to nethack would be a great idea. If I have some
free time, I will implement this and see how it does.

[Roger Broadbent]

Post by Janis
An algorithm to create Sokoban levels seems not to be too hard :-]
[simplistic algorithm]

[the algorithm presented is insufficient to generate interesting soko
levels but could be redeemed]
Even if fixed, the levels it produces are probably still quite boring,
partly because of the standard NetHack map generation but likely for a
great many other reasons.

I've seen a non-nethack sokoban puzzle generator on the internet that uses
this reverse-time technique. IIRC, given a map with finishing positions for
the crates, it explored all non-trivially different and valid player moves
in backwards time then chose the starting position with the longest optimal
solution. I think it could be applicable to nethack, but you'd need to
generate levels in a new way. I did wonder whether you could divide a level
into four quarters and provide several sokoban-style alternatives for each
quarter. On entering a level, the RNG would choose one alternative for each
quarter, then do the backwards algorithm. You'd want to have an element of
randomness in choosing a particular starting position of course, otherwise
the number of different levels would still be relatively small.

I think the challenges here are creating a sufficiently efficient algorithm
to explore enough possible solutions without making the player wait too
long, and creating map segments that combine to allow sufficiently
interesting solutions.

For the first problem, I would consider a simple algorithm that explored
all possible moves and kept a list of all previously-visited positions,
indexed with a hash table. Any node that duplicated a previously-visited
position would be abandoned. The current route to get there would replace
the original if it was more efficient. Any node where the player is on the
stairs would be marked as a valid starting position. Any other node with no
valid moves would be abandoned. When all possible moves had been explored,
a starting position would be chosen randomly, with each starting position
weighted by the number of moves required to solve it.

You might be able to adapt this to run only until sufficient solutions or a
given time interval/number of iterations had elapsed then choose from the
solutions found so far. The problem here would be to ensure that the entire
space of possible starting positions is given a reasonable chance of being
considered.

As the RNG would necessarily know the solution, one could introduce items
that gave the solution if used on a sokoban level before a boulder was
moved, or perhaps be given solutions through prayer, like the Castle tune.


Roger

[Janis]

Thank you, Sam, for your feedback.

[...] your levels would all be solvable with a
player interacting with each boulder only for a single, unbroken time.

Yes, you are right. That's an unnecessary flaw, that I've overlooked to
write it down. And, as you mention briefly, that may be fixed by making
Reyalp at some point lose grip and search for another virtual boulder to
continue with.

And no, it is also not *quite* true, because you don't know which boulder
would be the first to take and what path to choose. Boulder paths and
locations interfer. Nevertheless, the flaw is to be fixed.

To say that this would create dull levels is an understatement of very
rarely matched or bettered magnitude (although this particular will be
rectified with little change to the algorithm).
Even if fixed, the levels it produces are probably still quite boring,
partly because of the standard NetHack map generation

Hmm.. you *may* be right, but I see no evidence that support your words.

but likely for a
great many other reasons.

Which are in your opinion?

The method is simple enough so you might be
able to prove me and other sceptics wrong with a demonstration, if you
still think it might be a reasonable approach.

I wanted a discussion (I don't want to prove anything to you :-), whether
it is an appropriate approach or not. If there is a strong argument that
the suggested approach is trash, then why should we bother programming it?
You seem to have massive doubts. I'd be happy if there is any fundamental
and substantiated reason to prevent me from wasting time with coding.

And yes, I still think the approach is reasonable if the requirement is
*random* levels as opposed to sophisticated *designed* levels.
If a requirement is polynomial algorithm and not an exponential algorithm.
If a requirement is quite simple code and not a full blown A.I. system.

(Your requirements may vary. I've got the impression from other posts
that you might like a Sokoban quality as in the original game; I'd abstain
from such a project, it's too heavy.)

But a random Sokoban level, even if not as sophisticated - "dull" as you
despised - as the original Sokoban game, would introduce more diversity
and less boredom.

Janis

[Sam Dennis]

Post by Janis

[...] your levels would all be solvable with a
player interacting with each boulder only for a single, unbroken time.
[and wouldn't be interesting]

And no, it is also not *quite* true, because you don't know which boulder
would be the first to take and what path to choose.

I can't speak for you, but I would. It's utterly trivial to solve the
problem if you only have to look for a path from a boulder to its hole
until all of them are plugged.

Post by Janis

Even if fixed, the levels it produces are probably still quite boring,
partly because of the standard NetHack map generation

Hmm.. you *may* be right, but I see no evidence that support your words.

NetHack map generation is designed for fun monster bashing, not puzzle
solving fun; you are correct that I provide no evidence, there is none
to give yet.

Post by Janis

but likely for a great many other reasons.

Which are in your opinion?

Creating a Sokoban puzzle that can be solved, as your approach (which,
by the way, is the obvious approach; if it was sufficient, it would be
in place already) does, is not the problem at all. The problem is how
to create a fun puzzle, a challenging puzzle but still a possible one.

As it happens, while reading this thread, I have thought of a possible
way to do this... maybe. If I can sort out the details, it might make
the kind of levels I am looking for, boulders, holes, walls and all in
two stages. If I don't get anywhere, you probably won't here about it
again from me.

Post by Janis
If there is a strong argument that the suggested approach is trash,
then why should we bother programming it?

Well, I'd quite like to see just how bad its results are; I suspect it
to be pretty dire but I'm curious to see the output anyway, not enough
to code it myself, though. It's certainly a waste of time by a normal
standard but someone here might not mind.

Post by Janis
You seem to have massive doubts. I'd be happy if there is any fundamental
and substantiated reason to prevent me from wasting time with coding.

Okay: by generating a puzzle like Sokoban by a reverse solution you'll
likely end up with the optimal solution being much simpler most of the
time unless the map its generated on biases the method against this.

Again: no proof, just intuition.

Post by Janis
(Your requirements may vary. I've got the impression from other posts
that you might like a Sokoban quality as in the original game; I'd abstain
from such a project, it's too heavy.)

I'd love it but I do know that it's unreasonable to expect it from any
mere computational method if the problem is anywhere near as hard as I
think it is. I do think, for now, that the fun line can be crossed by
a good approach, though.

Post by Janis
But a random Sokoban level, even if not as sophisticated - "dull" as you
despised - as the original Sokoban game, would introduce more diversity
and less boredom.

Not if one doesn't have to engage one's brain to solve it.

[Janis]

Post by Sam Dennis
NetHack map generation is designed for fun monster bashing, not puzzle
solving fun;

Strange definition. I thought that they are just rectangular rooms
connected by random corridors with preference of straight or zigzag
orientation. The mines are amorphic, random shaped, with smoothed
walls. The mazes are, well, mazes. I would not call that designed.
The quests and Sokoban, yes, these are designed, as are all the other
fixed predefined levels.

Post by Sam Dennis
Creating a Sokoban puzzle that can be solved, as your approach (which,
by the way, is the obvious approach;

Maybe, but no one talked about it before in r.g.r.n.

Post by Sam Dennis
if it was sufficient, it would be
in place already)

Don't think so. Sokoban is a quite new (new in my time scale) feature.
And you read about people considering to implement it testwise now.

Post by Sam Dennis
does, is not the problem at all. The problem is how
to create a fun puzzle, a challenging puzzle but still a possible one.

Do you really need a sophisticated Sokoban *in* NH?

Post by Sam Dennis
Okay: by generating a puzzle like Sokoban by a reverse solution you'll
likely end up with the optimal solution being much simpler most of the
time unless the map its generated on biases the method against this.
Again: no proof, just intuition.

ok.

Post by Sam Dennis

Post by Janis
But a random Sokoban level, even if not as sophisticated - "dull" as you
despised - as the original Sokoban game, would introduce more diversity
and less boredom.

Not if one doesn't have to engage one's brain to solve it.

Yes. The question is, IMO, where it's feasable to draw the line and
what you intend with the Sokoban level. How much brain you want to
invest into a branch.

I have the impression our main difference is that you prefer to make
a cut and play high-quality Sokoban during NH. My preference is not
to solve high-quality Sokoban in NH - actually I do, I have to do, but
I don't want to do that time consuming digression. I would accept a
not so sophisticated Sokoban type level if it only differs from game to
game. And if, eventually, I die due to a YASD then I switch to real
Sokoban, play a game or two and come back to start a new NH session.

Maybe (as the mines are) one designed harder solvable level surrounded
by a couple of random generated levels would be a reasonable solution
to serve most Nethackers?

Happy hacking!

Janis

[David Ploog]

Janis wrote:
[snip discussion if the proposed Sokoban level generator
produced worthwhile results]

Post by Janis
Maybe (as the mines are) one designed harder solvable level surrounded
by a couple of random generated levels would be a reasonable solution
to serve most Nethackers?

I can wholeheartedly second that. IMHO levels should be nontrivial to
solve but not necessarily difficult. Actually I never had problems with
the original levels but I'd gladly swap design perfection with
randomness.

And it would be cool if the random levels would get harder monsters
(eg. make them neutral like the Oracle) so that they provide a tactical
challenge).

David

[Dylan O'Donnell]

David Ploog <***@mi.uni-koeln.de> writes:

[Sokoban]

Post by David Ploog
And it would be cool if the random levels would get harder monsters
(eg. make them neutral like the Oracle) so that they provide a tactical
challenge).

Umm. Sokoban is _already_ biased neutral. (Effectively, since 3.4.1.)
The monsters generated on its bottom level should be comparable to
those on the Oracle level (and are, in my experience); it'll get
somewhat easier as you go up, unless you gain levels commensurately.

[David Damerell]

David Ploog <***@mi.uni-koeln.de> wrote:
[Sokoban]

Post by David Ploog
I can wholeheartedly second that. IMHO levels should be nontrivial to
solve but not necessarily difficult.

Not too lengthy, either! The BoH ending has much more work than the puzzle
justifies.

[C #M]

Post by Dylan O'Donnell
[Sokoban]

Post by David Ploog
I can wholeheartedly second that. IMHO levels should be nontrivial to
solve but not necessarily difficult.

Not too lengthy, either! The BoH ending has much more work than the puzzle
justifies.

Really? I've always found the 'oR level to be much, much harder. But
yes, that level is a bit too long (it wouldn't really hurt the puzzle
if one of the "layers" were taken off).

[David Damerell]

Post by C #M

Post by David Damerell
Not too lengthy, either! The BoH ending has much more work than the puzzle
justifies.

Really? I've always found the 'oR level to be much, much harder.

Yes, the AoR level is harder. That's part of my point. The size of the BoH
ending wouldn't matter if there was plenty of puzzling to be done.