Algoritmos Juego Match-3

Meleagant #1 Abr '14 :psyduck:

Estoy buscando información sobre algoritmos para el típico juego de conectar 3 fichas en línea, tipo Bejeweled o Candy Crush.

Básicamente hay dos casos que calcular:

1 - Detectar todos los grupos de 3 o más casillas del mismo color alineados.

2 - Detectar si existen movimientos siguientes posibles para un estado concreto del tablero.

El primer punto es relativamente sencillo, leo que recomiendan usar un algoritmo "Flood fill", y no parece muy complicado. El punto 2 es el que no sé muy bien cómo resolver.

Me parece un caso bastante típico y supongo que se conocerán los algoritmos habituales usados para esto, pero por más que busco en Internet no encuentro nada.

¿Alguien tiene alguna idea?

Postmortem #2 Abr '14

No podrías tener un 2º tablero por parte de programación, en el que haces el movimiento siguiente y compruebas si hay grupo de 3 con el primer punto? y si lo hay devuelves true y ya en tu tablero real lo que veas

Y para todos los posibles movimientos, lo mismo, iteras sobre todos los posibles movimientos y lo sacas, aunque sería un coste de cómputo relativamente caro

o no entiendo a que te refieres

Neyko #3 Abr '14

#1 Lo de los posibles movimientos supongo que podrás afrontarlo analizando las variables de tu estado actual y filtrandolas en base a las reglas que establecen si un movimiento es factible o no.
Posiblemente guardando una definición de los posibles estados y asociando cada estado a un movimiento la complejidad sería menor, ¿no?

YaW #4 Abr '14

Yo estoy haciendo ahora mismo un match3 y lo que comentas lo tengo bastante solucionado desde hace tiempo, mañana te explico un poco por encima que ahora estoy con el móvil

Hacer un juego de estos tiene más complicación de lo que parece en un principio, sobretodo cuando te metes con powerups, tipos de tablero, etc las combinaciones son muchísimas y muchos casos raros xD

YaW #5 Abr '14

Bien, suponemos que el tablero está definido en un array bidimensional de objetos que tienen todas las características que necesitas (posición en el tablero, tipo, etc).
Para el punto 1 tienes dos posibilidades para hacerlo.

La primera es recorrerte todo el mapa entero cada vez que no estés moviendo fichas y no tengas animaciones a medias de fichas cayendo, o rompiéndose o lo que sea. Comprobando todas las casillas solo tienes que mirar los matches hacia la izquierda y hacia arriba (suponiendo que recorras el mapa comenzando por la izquierda y arriba). Desde la casilla que estés comprobando vas mirando hacia la izquierda y si encuentras una coincidencia sumas uno al contador de matches, si ese contador llega a 3 o más es que has encontrado un match. Y por arriba lo mismo.

La segunda posibilidad es solo comprobar matches cuando una casilla se mueva. Esto es más eficiente que lo anterior pero puede llevarte a algunos problemas y quebraderos de cabeza cuando tengas un montón de fichas desmoronándose por pantalla. Cada vez que una ficha se mueva (porque la muevas tú o porque se mueva luego al rellenar el tablero) tienes que añadirlo a un array para luego recorrerlo y por cada ficha ir comprobando en las cuatro direcciones.

Luego comprobar si quedan matches posibles o no es algo más complicado y hay varias formas de hacerlo. Yo lo que he hecho y funciona bastante bien es recorrer el tablero buscando parejas de 2 y una vez que tienes una pareja de dos tienes que mirar todas las casillas de alrededor de los finales para ver si alguna es del mismo tipo y por lo tanto se podría mover para hacer el match.

1 respuesta

Meleagant #6 Abr '14 :psyduck:

Muchas gracias a todos.

#5 La verdad es que pensaba que este tipo de algoritmos estarían trilladísimos y sería fácil encontrar en Internet soluciones óptimas en pseudocódigo, pero por lo que veo apenas hay información de ese tipo.

Así que al final he hecho como tú, pensar el algoritmo por mi cuenta. Para los matches posibles mi primera idea fue como la tuya, buscar grupos de 2 y luego comprobar los alrededores. El problema es que puede haber 3 fichas que no se toquen para nada entre ellas, pero que con mover la ficha central se alineen las 3.

Así que al final lo que estoy haciendo es recorrer todo el tablero ficha por ficha, y comprobar si algún movimiento de esa ficha genera una cadena válida. No necesito detectar todos los movimientos válidos, sino que con encontrar el primero válido puedo parar, y en el caso peor (no hay movimientos) tendré que recorrer N² fichas, que siendo N un número no muy alto, quizá 10, creo que es asequible hacerlo así.

Potito #7 Abr '14 Inocente

Propongo una solucion bastante buena, y es confiar en el usuario, q tenga una funcion para borrar las fichas que el vea q estan agrupadas en 3 o mas.

De esta manera confiando en la buena voluntad del jugador ahorrarias mucho trabajo.

1

Hynack #8 Abr '14 Inocente

Manipulando el algoritmo de Pathfinding A* se podría hacer, jugando con las puntuaciones de cada tipo de casilla ( o eso creo )

eZpit #9 Abr '14 Juntabrackets

#1 Para el punto 2 veo dos soluciones, la primera es iterar todos los posibles movimientos y aplicar el punto 1 sobre cada iteración. A lo bruto.

La segunda es utilizar el mismo algoritmo de 1 pero en vez de buscar 3 en linea buscar fichas colocadas en la posicion previa a alinearse, por ejemplo:

XXA
BCX

o

XA
CX
XB

Si encuentras una coincidencia de este caso puedes proponer un intercambio de las fichas en la 3ª columna como movimiento valido. Básicamente buscarías todos los movimientos validos y ofrecerias uno al azar. Tambien sirve para detectar cuando no se puede hacer un movimiento y remezclar las fichas.

Algoritmos Juego Match-3

Usuarios habituales

Tags