He creado una especie de juego de rompecabezas en el que el objetivo es eliminar todas las fichas blancas. Puedes probarlo al final de la pregunta.
Cada vez, el tablero se genera aleatoriamente con fichas blancas en lugares aleatorios en una cuadrícula de 5 * 5. Puede hacer clic en cualquier mosaico de esa cuadrícula y alternará su color y todos los mosaicos que lo toquen en sus lados. Mi dilema es el hecho de que no sé si generará un tablero imposible. ¿Cuál es la mejor manera de verificar cosas como esta?
function newgame() {
moves = 0;
document.getElementById("moves").innerHTML = "Moves: "+moves;
for (var i = 0; i < 25; i++) {
if (Math.random() >= 0.5) {
$(document.getElementsByClassName('block')[i]).toggleClass("b1 b2")
}
}
}
newgame();
function toggle(a,b) {
moves += 1;
document.getElementById("moves").innerHTML = "Moves: "+moves;
$(document.getElementsByClassName('block')[a+(b*5)]).toggleClass("b1 b2");
if (a<4) {$(document.getElementsByClassName('block')[(a+1)+(b*5)]).toggleClass("b1 b2")}
if (a>0) {$(document.getElementsByClassName('block')[(a-1)+(b*5)]).toggleClass("b1 b2")}
if (b<4) {$(document.getElementsByClassName('block')[a+((b+1)*5)]).toggleClass("b1 b2")}
if (b>0) {$(document.getElementsByClassName('block')[a+((b-1)*5)]).toggleClass("b1 b2")}
}
body {
background-color: #000000;
}
.game {
float: left;
background-color: #000000;
width: 300px;
height: 300px;
overflow: hidden;
overflow-x: hidden;
user-select: none;
display: inline-block;
}
.container {
border-color: #ffffff;
border-width: 5px;
border-style: solid;
border-radius: 5px;
width: 600px;
height: 300px;
text-align: center;
}
.side {
float: left;
background-color: #000000;
width: 300px;
height: 300px;
overflow: hidden;
overflow-x: hidden;
user-select: none;
display: inline-block;
}
.block {
transition: background-color 0.2s;
float: left;
}
.b1:hover {
background-color: #444444;
cursor: pointer;
}
.b2:hover {
background-color: #bbbbbb;
cursor: pointer;
}
.row {
width: 300px;
overflow: auto;
overflow-x: hidden;
}
.b1 {
display: inline-block;
height: 50px;
width: 50px;
background-color: #000000;
border-color: #000000;
border-width: 5px;
border-style: solid;
}
.b2 {
display: inline-block;
height: 50px;
width: 50px;
background-color: #ffffff;
border-color: #000000;
border-width: 5px;
border-style: solid;
}
.title {
width: 200px;
height: 50px;
color: #ffffff;
font-size: 55px;
font-weight: bold;
font-family: Arial;
display: table-cell;
vertical-align: middle;
}
.button {
cursor: pointer;
width: 200px;
height: 50px;
background-color: #000000;
border-color: #ffffff;
border-style: solid;
border-width: 5px;
color: #ffffff;
font-size: 25px;
font-weight: bold;
font-family: Arial;
display: table-cell;
vertical-align: middle;
border-radius: 5px;
transition: background-color 0.3s, color 0.3s;
}
.button:hover {
background-color: #ffffff;
color: #000000;
}
.sidetable {
padding: 30px 0px;
height: 200px;
}
#moves {
width: 200px;
height: 50px;
color: #aaaaaa;
font-size: 30px;
font-weight: bold;
font-family: Arial;
display: table-cell;
vertical-align: middle;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<center>
<div class="container">
<div class="game"><div class="row"><div onclick="toggle(0,0);" class="block b1"></div><div onclick="toggle(1,0);" class="block b1"></div><div onclick="toggle(2,0);" class="block b1"></div><div onclick="toggle(3,0);" class="block b1"></div><div onclick="toggle(4,0);" class="block b1"></div></div><div class="row"><div onclick="toggle(0,1);" class="block b1"></div><div onclick="toggle(1,1);" class="block b1"></div><div onclick="toggle(2,1);" class="block b1"></div><div onclick="toggle(3,1);" class="block b1"></div><div onclick="toggle(4,1);" class="block b1"></div></div><div class="row"><div onclick="toggle(0,2);" class="block b1"></div><div onclick="toggle(1,2);" class="block b1"></div><div onclick="toggle(2,2);" class="block b1"></div><div onclick="toggle(3,2);" class="block b1"></div><div onclick="toggle(4,2);" class="block b1"></div></div><div class="row"><div onclick="toggle(0,3);" class="block b1"></div><div onclick="toggle(1,3);" class="block b1"></div><div onclick="toggle(2,3);" class="block b1"></div><div onclick="toggle(3,3);" class="block b1"></div><div onclick="toggle(4,3);" class="block b1"></div></div><div class="row"><div onclick="toggle(0,4);" class="block b1"></div><div onclick="toggle(1,4);" class="block b1"></div><div onclick="toggle(2,4);" class="block b1"></div><div onclick="toggle(3,4);" class="block b1"></div><div onclick="toggle(4,4);" class="block b1"></div></div></div>
<div class="side">
<center class="sidetable">
<div class="title">Tiles</div>
<br>
<div class="button" onclick="newgame()">New Game</div>
<br><br>
<div id="moves">Moves: 0</div>
</center>
</div>
</div>
</center>
game-design
logic
puzzle
playtesting
QWERTY
fuente
fuente
Respuestas:
Este es el tipo de juego donde el mismo movimiento realizado dos veces invierte el tablero a su estado anterior. Por lo tanto, para garantizar que un tablero sea solucionable, generarlo jugando al revés. Comience con un tablero resuelto (en blanco), luego comience "haciendo clic" mediante programación aleatoriamente, ya sea un cierto número de veces, o hasta que el tablero tenga el número deseado de casillas blancas. Una solución es simplemente realizar los mismos movimientos en el orden inverso. Pueden existir otras soluciones más cortas, pero se garantiza que tendrá al menos una.
Otra solución mucho más compleja es definir un algoritmo de resolución que atraviese todos los estados posibles del juego desde su posición inicial para tratar de encontrar la solución. Esto llevaría mucho más tiempo implementarlo y ejecutarlo, pero permitiría que las placas se generen realmente al azar. No entraré en detalles de esta solución, porque simplemente no es una buena idea.
fuente
Si bien las respuestas anteriores son inteligentes (y probablemente cómo lo haría de todos modos), este juego en particular es muy conocido. Se llama Lights Out y se ha resuelto matemáticamente. Hay una solución si y solo si dos sumas de varios elementos (dados en la página de wikipedia) se suman a cero mod 2 (es decir, un número par). En general, un poco de álgebra lineal debería dar condiciones de solución similares para los juegos en cualquier tablero.
fuente
Dé la vuelta al generar su rompecabezas.
En lugar de seleccionar aleatoriamente los mosaicos y convertirlos de blanco a negro, comience desde una pizarra en blanco, luego seleccione los mosaicos, pero en lugar de convertir ese mosaico en negro, hágalo como si el usuario lo hubiera seleccionado, dando como resultado voltear todos los otros mosaicos alrededor.
De esta manera, se le garantizará tener al menos una solución: el usuario tendrá que deshacer lo que hizo su jugador "AI" para crear el nivel.
fuente
Ed y Alexandre tienen derecho.
Pero si usted no quiere saber si cada solución es posible, hay maneras.
Hay un número finito de rompecabezas posibles
Hacer clic en el mismo cuadrado dos veces produce el mismo resultado que no hacer clic en él, sin importar cuántos clics se hayan hecho entre ellos. Eso significa que cada solución se puede describir dando a cada cuadrado un valor binario de 'clic' o 'no clic'. Del mismo modo, cada rompecabezas se puede describir dando a cada cuadrado un valor binario de 'activado' o 'no activado'. Eso significa que hay 2 ^ 25 posibles acertijos y 2 ^ 25 posibles soluciones. Si puede probar que cada solución resuelve un rompecabezas único, entonces debe haber una solución para cada rompecabezas. Del mismo modo, si encuentra dos soluciones que resuelven el mismo rompecabezas, entonces no puede haber una solución para cada rompecabezas.
Además, 2 ^ 25 es 33,554,432. Eso es bastante, pero no es un número inmanejable. Un buen algoritmo y una computadora decente probablemente podrían aplicar una fuerza bruta en un par de horas, especialmente cuando consideras que la mitad de los rompecabezas son inversos de la otra mitad.
fuente
Respuesta generalizada:
fuente
Otros ya han mencionado formas de determinar si su rompecabezas generado aleatoriamente tiene solución. Sin embargo, la pregunta que también debes hacerte es si realmente quieres rompecabezas generados al azar.
Todos los rompecabezas generados aleatoriamente tienen el mismo defecto central: su dificultad es prácticamente impredecible. Los posibles acertijos que puede obtener pueden variar desde ya resueltos, a triviales (la solución es obvia) a difíciles (la solución no es obvia) a imposibles (el rompecabezas no se puede resolver en absoluto). Debido a que la dificultad es impredecible, se convierte en una experiencia insatisfactoria para el jugador, especialmente si hacen múltiples rompecabezas seguidos. Es muy poco probable que obtengan una curva de dificultad suave, lo que puede aburrirlos o frustrarlos dependiendo de los acertijos que obtengan.
Otro problema de la generación aleatoria es que el tiempo que tarda el rompecabezas en inicializarse es impredecible. En términos generales, obtendrá un rompecabezas solucionable (casi) de inmediato, pero con algo de mala suerte, sus rompecabezas generados al azar podrían terminar en una racha de rompecabezas sin solución.
Una forma de resolver ambos es tener vectores predefinidos de cada rompecabezas solucionable disponible, organizados en grupos de dificultad, y luego seleccionar un rompecabezas aleatorio de los acertijos solucionables en función de la dificultad. De esta manera, estará seguro de que cada rompecabezas es solucionable, que la dificultad es predecible y que la generación se realizará en tiempo constante.
fuente