Zufällige Generierung interessanter Puzzle-Levels?

8

Ich mache ein Sokoban-ähnliches Spiel, dh es gibt ein Gitter mit einigen Kisten, die du schieben kannst, und du musst die Kisten auf Kreuze legen, um das Level zu gewinnen (obwohl ich einige zusätzliche Elemente hinzufügen werde). Gibt es allgemeine Algorithmen oder Lesematerial, nach denen ich suchen kann, wie ich interessante (wie nicht trivial zu lösende) Levels für diesen Spielstil generieren kann? Ich bin mir bewusst, dass es für Sokoban Zufallsgeneratoren gibt, aber ich habe Probleme, die Algorithmusbeschreibungen zu finden.

Ich bin daran interessiert, ein Spiel zu entwickeln, bei dem die Maschine viele Level für mich generieren kann, sortiert nach Schwierigkeitsgrad. Ich bin sogar bereit, die Spielregeln einzuschränken, um die Levelgenerierung zu vereinfachen (z. B. werde ich die Rastergröße wahrscheinlich auf etwa 7x7 beschränken). Ich vermute, dass es hier einige allgemeine Möglichkeiten gibt, Levels zu generieren, wie ich gesehen habe, z. B. Traffic Jam-ähnliche Spiele (bei denen Sie Blöcke um den freien Block verschieben müssen) mit Tausenden von Levels, in denen jedes eine einzigartige Lösung hat.

Eine Idee, die ich hatte, war, eine zufällige Karte im Endzustand zu generieren (dh wo sich alle Kisten oben auf ihren Kreuzen befinden), und dann würde der Computer diese Kisten herumziehen (anstatt zu schieben), um ein Level zu erstellen. Die schöne Eigenschaft hier ist, dass wir wissen, dass das Niveau lösbar ist. Ich würde jedoch einige Heuristiken benötigen, um sicherzustellen, dass das Niveau interessant ist.

game-design level-design random puzzle procedural
quelle
Diese Idee zum Generieren von Levels ist sehr interessant. Ehrlich gesagt würde ich einfach weitermachen und das versuchen, anstatt auf eine Diskussion darüber zu warten. Ich vermute, Sie könnten die Schwierigkeit der generierten Levels einstellen, indem Sie die Anzahl der Züge einstellen. Eine Heuristik, die Sie wahrscheinlich möchten, besteht darin, die Züge auf mehrere Kisten zu verteilen, beide, so dass jede Kiste um einen angemessenen Betrag bewegt wird, aber auch so dass der Spieler manchmal zwischen Kisten hin und her gehen muss (ich vermute, dass diese Art von Verflechtungslogik interessanter ist als eine Kiste nach der anderen).
Schockieren

Antworten:

6

Siehe das Papier: Automatische Herstellung von Sokoban-Problemen

Aus der Zusammenfassung:

Dieses Dokument beschreibt unser Programm, das Sokoban-Probleme automatisch verursacht. Sokoban ist eines der in Japan erfundenen Ein-Personen-Rätsel. Das Programm besteht aus drei Phasen: Generierung, Überprüfung und Bewertung. Zunächst werden Kandidaten für Probleme zufällig aus einem Prototyp und drei Vorlagen generiert. Zweitens werden unlösbare Kandidaten vom Sokoban-Löser entfernt. Schließlich werden triviale oder uninteressante Kandidaten vom Bewerter entfernt. Die Probleme, die das Programm gemacht hat, werden von menschlichen Experten als gut beurteilt. Die Schaffung von Kunst durch Computer ist ein wichtiges Ziel der künstlichen Intelligenz. Unsere Arbeit kann als einer der Versuche charakterisiert werden, einige Künste durch Computer zu schaffen.

CeeJay
quelle
1

Bei lösbaren Rätseln ist es oft einfach, das Spiel in umgekehrter Reihenfolge zu spielen, ausgehend von einem gelösten Zustand und nicht geplanten oder zufälligen Bewegungen (oder in einem Editor).

Sokoban passt sehr gut zu diesem Ansatz und ist viel einfacher zu implementieren als eine Ausschluss- und Lösungsstrategie.

John Haugeland
quelle