¿Generación aleatoria de niveles de rompecabezas interesantes?

8

Estoy haciendo un juego similar a Sokoban, es decir, hay una cuadrícula que tiene algunas cajas que puedes empujar y tienes que poner las cajas en cruces para ganar el nivel (aunque voy a agregarle algunos elementos adicionales). ¿Hay algún algoritmo general o material de lectura que pueda ver para saber cómo podría generar niveles interesantes (como triviales para resolver) para este estilo de juego? Soy consciente de que existen generadores de nivel aleatorio para Sokoban, pero tengo problemas para encontrar las descripciones del algoritmo.

Estoy interesado en hacer un juego donde la máquina pueda generar muchos niveles para mí, ordenados por dificultad. Incluso estoy dispuesto a restringir las reglas del juego para facilitar la generación de niveles (por ejemplo, probablemente limitaré el tamaño de la cuadrícula a aproximadamente 7x7). Sospecho que hay algunas formas generales de generar niveles aquí como he visto, por ejemplo, juegos similares a Traffic Jam (donde tienes que mover bloques alrededor del bloque libre) con miles de niveles donde cada uno tiene una solución única.

Una idea que tuve fue generar un mapa aleatorio en su estado final (es decir, donde todas las cajas están encima de sus cruces) y luego la computadora tiraría (en lugar de empujar) estas cajas para crear un nivel. La buena propiedad aquí es que sabemos que el nivel es solucionable. Sin embargo, necesitaría algunas heurísticas para asegurar que el nivel fuera interesante.

game-design level-design random puzzle procedural
fuente
Esa idea que tienes para generar niveles es muy interesante. Honestamente, simplemente seguiría adelante e intentaría eso, en lugar de esperar a que se discutiera al respecto. Supongo que podría ajustar la dificultad de los niveles generados al establecer el número de tirones, y una heurística que probablemente desee es distribuir los tirones en múltiples cajas, ambas para que cada caja se mueva una cantidad justa, pero también de modo que el jugador a veces tiene que ir y venir entre cajas (supongo que ese tipo de lógica entrelazada es más interesante que una caja a la vez).
jhocking

Respuestas:

6

Ver el artículo: Creación automática de problemas de Sokoban

Del resumen:

Este documento describe nuestro programa que hace que los problemas de Sokoban sean automáticos. Sokoban es uno de los rompecabezas de una persona inventados en Japón. El programa consta de tres etapas: generación, verificación y evaluación. Primero, los candidatos a problemas se generan aleatoriamente mediante un prototipo y tres plantillas. Segundo, los candidatos insolubles son eliminados por el solucionador de Sokoban. Finalmente, los candidatos triviales o poco interesantes son eliminados por el evaluador. Los expertos humanos consideran que los problemas que generó el programa son buenos. La creación de arte por computadora es un objetivo importante de la Inteligencia Artificial. Nuestro trabajo puede caracterizarse como uno de los intentos de crear algunas artes por computadoras.

CeeJay
fuente
1

Para los acertijos solucionables, a menudo es fácil jugar el juego en reversa, comenzando desde un estado resuelto y haciendo movimientos no planificados o al azar (o en un editor).

Sokoban se ajusta muy bien a este enfoque y será mucho más fácil de implementar que una estrategia de exclusión y resolución.

John Haugeland
fuente