Actualmente tengo un juego simple similar al Tetris y me he encontrado con un problema que no puedo resolver.
A diferencia de Tetris, donde hay una sola forma de caída, tengo varias formas potencialmente entrelazadas que deben caerse; Necesito calcular sus posiciones finales. Considera lo siguiente:
Para calcular la posición final de la forma verde, simplemente escaneo hacia abajo para cada cuadrado hasta que golpee otro cuadrado o el borde del tablero. Hecho
Para formas múltiples y simples, trabajo hacia ARRIBA del tablero. Por lo tanto, se descubre que el rojo no necesita moverse, el naranja baja en uno y el verde en tres. Hecho
No sé cómo tratar las formas verdes y rojas entrelazadas. Usando la lógica del # 2, terminaríamos "atrapados" flotando en el aire. Si escaneo hacia abajo para encontrar la forma verde, encuentro el rojo y, por lo tanto, no me muevo, y viceversa para el rojo. La solución podría ser tratar las dos formas como una sola.
Similar al # 3, en este escenario también podría tener éxito al tratar los objetos como uno solo.
A diferencia de # 3 y # 4, no podría tratar la forma como una, ya que la forma naranja terminaría flotando un cuadrado demasiado alto ...
Otra variación del problema # 6.
Podría haber otros escenarios en los que tengo muchas formas que se entrelazan en escenarios cada vez más complejos, pero creo que lo anterior cubre las partes más fundamentales del problema.
Siento que hay una solución elegante que todavía tengo que encontrar / pensar y estaría muy agradecido por cualquier idea, idea o recurso.
SOLUCIÓN
La solución que se me ocurrió es elegante, basada en la respuesta de @ user35958 a continuación, he creado la siguiente función recursiva (pseudocódigo)
function stop(square1, square2){
// Skip if we're already stopped
if(square1.stopped){
return;
}
// Are we comparing squares?
if(!square2){
// We are NOT comparing squares, simply stop.
square1.stopped = true;
} else {
// Stop IF
// square1 is directly above square2
// square1 is connected to square2 (part of the same complex shape)
if(square1.x == square2.x && square1.y == (square2.y+1) || isConnected(square1, square2)){
square1.stopped = true;
}
}
// If we're now stopped, we must recurse to our neighbours
stop(square1, squareAbove);
stop(square1, squareBelow);
stop(square1, squareRight);
stop(square1, squareDown);
}GIF animado que muestra cada paso de la solución
Resumir:
- Cuando "paramos" un cuadrado, también paramos:
- CUALQUIER cuadrado encima de él. SIEMPRE.
- Cuadrado vecino al que estamos conectados (es decir, la misma forma).
- Paramos toda la fila inferior y la función se repite a través de los cuadrados.
- Repetimos hasta que se detengan todos los cuadrados.
- Entonces nos animamos.
fuente
Respuestas:
Bueno, no es necesario que trates las formas como si fueran una distinción entre las formas que se mueven y las que están en reposo. Una forma (A) podría detectar una forma (B) directamente debajo de ella y si se está moviendo, entonces la forma B podría ver si hay algo directamente debajo de ella, y si hay una forma en reposo, entonces A y B ahora están descansando, y si no hay nada, ambos se mueven hacia abajo, pero si hay una forma en movimiento, entonces esta nueva forma será tratada por A y B como A tratada a B, por lo que es algo recursivo. Tenga en cuenta que para cada paso, las formas más bajas deben verificar primero las formas debajo de ellas.
Entonces, para el problema # 6, la forma verde es la forma más baja en movimiento, y vería que la única forma que está directamente debajo es la forma roja, por lo que la forma roja no detectaría nada directamente debajo y se moverían hacia abajo . Una vez que la forma verde es adyacente a la forma naranja, descansaría, y la forma roja se movería hacia abajo y luego detectaría la forma verde en reposo, y también descansaría.
fuente
Parece que el problema con los casos n. ° 5 y n. ° 6 proviene de una sola raíz: solo está realizando una pasada de comprobaciones de movimiento. Debes seguir moviendo cosas hacia abajo (llamémosle un "paso de gravedad") hasta que sepas que nada se movió.
Por ejemplo, en el caso 6, esto es lo que sucedería si usara varios pases:
Esta estrategia de pases de gravedad múltiple también podría resolver el n. ° 5, aunque no ayudará con los casos n. ° 3 y n. ° 4, donde parece que debe tratarlos como si fueran una sola pieza.
Para distinguir cuándo dos o más piezas deben tratarse como una sola pieza, creo que el algoritmo más fácil es verificar si hay "agujeros" en el espacio combinado de todas las piezas. Si los hay, se pueden tratar como piezas múltiples.
fuente