Nach dem Zufallsprinzip Ebenen für Sokoban Spiel zu generieren?

Question

Ich mache ein Spiel im Sokoban-Stil (dh es ist nicht genau dasselbe wie Sokoban, also kann ich keine bestehenden Level verwenden) und möchte zufällige Level erstellen, damit ein Spieler weiterspielen kann und immer Levels haben muss . Gibt es irgendwelche Möglichkeiten, wie ich den Computer dazu bringen kann, automatisch oder halbautomatisch Level für mich zu erzeugen (halb, ich könnte ihm vielleicht die ursprüngliche Karte geben, aber ohne die Kistenpositionen)?

Eine Idee, die ich hatte, war zufällig eine Karte zu erzeugen, die Kisten in ihren Endzustand (d. H. Auf den Kreuzen) zu platzieren und dann die Kisten willkürlich zu bewegen, als ob sie vom Spielcharakter gezogen würden. Dies garantiert mir, dass das Level lösbar sein sollte. Das Hauptproblem wäre jedoch zu wissen, ob das Niveau einfach/hart und interessant/langweilig ist. Zum Beispiel ist Sokoban NP-hart, so dass ich die Maschine nicht realistisch fragen konnte, ob es eine einfache Lösung gab.

Ich weiß, es wäre schwer, zufällige Level zu schaffen, die mit menschlichen Experten konkurrieren würden, aber ich suche nur nach etwas, das anständig ist.

Edit: By the way, würde ich mehr interessiert sein kleine, aber interessante Sokoban-ähnliche Ebenen, z. 5x5 Stufen statt 50x50 Stufen. Dies kann die Dinge rechnerisch realisierbar machen.

Answer 1

Diese Seite hat eine Reihe von Sokoban Ebene Generatoren: http://www.erimsever.com/sokoban7.htm

Sie finden es vielleicht sinnvoll zu sehen, wie sie funktionieren.