Share
En este tutorial, te mostraré cómo analizar un tablero de mosaicos, recorrerlos y encontrar coincidencias. Crearemos un juego en el que deberás conectar líneas para formar rutas completamente cerradas sin extremos abiertos. Para simplificar las cosas, usaremos las máscaras de bits como parte de nuestro algoritmo asignando a cada casilla (más su rotación) su propio número de máscara de bits. No te preocupes si no sabes lo que es la máscara de bits. En realidad es muy simple!
Artículos RelacionadosCrearé el proyecto en C # usando Unity con el marco de trabajo de Futile, pero el código será aplicable a casi cualquier marco de 2D con pocos cambios. Aquí está el repositorio de Github con todo el proyecto de Unity. Y a continuación se muestra una demo jugable del juego que haremos:
Cuando comencé a crear Polymer, quería crear algo más que un juego de match-3. Mi apodo interno era un juego "match-any". Juegos de rompecabezas Match-3 están en todas partes. Si bien pueden ser divertidos, una de las razones por las que son tan comunes puede ser que el algoritmo para encontrar una combinación de tres fichas es bastante simple..
Quería poder hacer coincidir varias baldosas que podían entrar y salir de filas y columnas, abriéndose paso a través del tablero. No solo eso, sino que no quería un juego simple de combinación de colores. Quería que las coincidencias se basaran en lados específicos de las baldosas (por ejemplo, una forma solo podía conectarse a otras formas en los lados izquierdo y derecho, pero no en la parte superior e inferior). Esto resultó ser mucho más complejo que solo un algoritmo normal de match-3.
Este tutorial se dividirá en tres secciones: The Tile, The Match Group y The Game Board. En este tutorial, trataré de evitar la mayor cantidad posible de códigos específicos de Futile. Si quieres ver las cosas específicas de Futile, mira el código fuente. Además, no voy a mostrar todos los métodos y variables en esta publicación. Sólo los más importantes. Así que si crees que falta algo, mira el código fuente.
La palabra 'máscara de bits' se refiere a la forma en que puede almacenar una serie de valores verdaderos / falsos en una sola variable numérica. Debido a que los números se representan con unos y ceros cuando se representan en binario, al cambiar el número puede activar o desactivar los valores al alternar si un bit es 1 o 0.
Para obtener más detalles, consulte este artículo sobre operadores bitwise y este artículo sobre números binarios..
Nuestra primera clase se llama LineTile. Antes del comienzo de la clase, definamos cada tipo de mosaico.
// Los diferentes tipos de azulejos: enumeración pública LineTileType Nub, Line, Corner, Threeway, Cross, MAX
Así es como se ven las piezas:
A continuación, como solo permitiremos rotaciones de 90 grados, hagamos una enumerar para rotacion.
// Estoy usando esto en lugar de grados exactos, ya que los // mosaicos solo deben tener cuatro rotaciones distintas: público enum RotationType Rotation0, Rotation90, Rotation180, Rotation270, MAX
El siguiente es un estructura llamado TileIndex, que es básicamente lo mismo que un Vector2, Excepto con ints en lugar de flotadores. Se utilizará para realizar un seguimiento de dónde hay una ficha en el tablero de juego.
public struct TileIndex public int xIndex; public int eIndex; público TileIndex (int xIndex, int yIndex) this.xIndex = xIndex; this.yIndex = yIndex;
Finalmente, definamos los tres tipos de conexiones entre dos mosaicos..
public enum TileConnectionType // Una discrepancia. No válido, // Los mosaicos no se conectan directamente, // pero no debido a un borde incomparable. ValidWithOpenSide, // Los mosaicos se conectan directamente. ValidWithSolidMatch
A continuación, dentro de la clase, defina una máscara de bits a cada lado de un mosaico genérico.
// Aquí están los bits que asigné a cada lado del mosaico: // ===== 1 ===== // | | // | | // 8 2 // | | // | | // ===== 4 ===== // 1 == 0001 en binario // 2 == 0010 en binario // 4 == 0100 en binario // 8 == 1000 en binario público const int kBitmaskNone = 0; public const int kBitmaskTop = 1; public const int kBitmaskRight = 2; public const int kBitmaskBottom = 4; public const int kBitmaskLeft = 8;
Luego define las variables de instancia que tendrá cada pieza.
// La representación del sprite del azulejo: sprite FSprite público; // El tipo de mosaico: public LineTileType lineTileType get; conjunto privado; // La rotación del mosaico: público RotationType rotationType get; conjunto privado; // La máscara de bits que representa el mosaico con su rotación: public int bitmask get; conjunto privado; // La ubicación del mosaico en la pizarra: public TileIndex tileIndex = new TileIndex ();
Para el constructor, cree el sprite y configúrelo en la rotación correcta. Aquí hay un código específico de Futile, pero debería ser muy fácil de entender..
Accentsconagua
lineTile público (LineTileType lineTileType, RotationType rotationType) this.lineTileType = lineTileType; this.rotationType = rotationType; // Configurar sprite: switch (lineTileType) caso LineTileType.Nub: sprite = new FSprite ("lineTileNub"); descanso; caso LineTileType.Line: sprite = new FSprite ("lineTileLine"); descanso; case LineTileType.Corner: sprite = new FSprite ("lineTileCorner"); descanso; caso LineTileType.Threeway: sprite = new FSprite ("lineTileThreeway"); descanso; caso LineTileType.Cross: sprite = new FSprite ("lineTileCross"); descanso; predeterminado: lanzar una nueva FutileException ("tipo de mosaico de línea no válido"); AddChild (sprite); // Configurar la rotación de sprites: switch (rotationType) case RotationType.Rotation0: sprite.rotation = 0; descanso; caso RotationType.Rotation90: sprite.rotation = 90; descanso; caso RotationType.Rotation180: sprite.rotation = 180; descanso; caso RotationType.Rotation270: sprite.rotation = 270; descanso; por defecto: lanzar una nueva FutileException ("tipo de rotación no válido"); Ahora, una de las partes más importantes. Le asignamos a cada baldosa, combinada con su rotación, una máscara de bits que está determinada por cuál de sus lados es sólido y cuál está abierto.
// Configure la máscara de bits haciendo bitwise OR con cada lado que se incluye en la forma. // Entonces, por ejemplo, un mosaico que tiene los cuatro lados sólidos (por ejemplo, el mosaico cruzado) sería // 1 | 2 | 4 | 8 = 15, que es lo mismo que 0001 | 0010 | 0100 | 1000 = 1111 en binario. if (lineTileType == LineTileType.Nub) if (rotationType == RotationType.Rotation0) bitmask = kBitmaskTop; if (rotationType == RotationType.Rotation90) bitmask = kBitmaskRight; if (rotationType == RotationType.Rotation180) bitmask = kBitmaskBottom; if (rotationType == RotationType.Rotation270) bitmask = kBitmaskLeft; if (lineTileType == LineTileType.Line) if (rotationType == RotationType.Rotation0 || rotationType == RotationType.Rotation180) bitmask = kBitmaskTop | kBitmaskBottom; if (rotationType == RotationType.Rotation90 || rotationType == RotationType.Rotation270) máscara de bits = kBitmaskRight | kBitmaskLeft; if (lineTileType == LineTileType.Corner) if (rotationType == RotationType.Rotation0) bitmask = kBitmaskTop | kBitmaskRight; if (rotationType == RotationType.Rotation90) bitmask = kBitmaskRight | kBitmaskBottom; if (rotationType == RotationType.Rotation180) bitmask = kBitmaskBottom | kBitmaskLeft; if (rotationType == RotationType.Rotation270) máscara de bits = kBitmaskLeft | kBitmaskTop; if (lineTileType == LineTileType.Threeway) if (rotationType == RotationType.Rotation0) bitmask = kBitmaskTop | kBitmaskRight | kBitmaskBottom; if (rotationType == RotationType.Rotation90) bitmask = kBitmaskRight | kBitmaskBottom | kBitmaskLeft; if (rotationType == RotationType.Rotation180) bitmask = kBitmaskBottom | kBitmaskLeft | kBitmaskTop; if (rotationType == RotationType.Rotation270) máscara de bits = kBitmaskLeft | kBitmaskTop | kBitmaskRight; if (lineTileType == LineTileType.Cross) bitmask = kBitmaskTop | kBitmaskRight | kBitmaskBottom | kBitmaskLeft;
Nuestros azulejos están configurados y estamos listos para comenzar a combinarlos!
Los grupos de coincidencia son solo eso: grupos de fichas que coinciden (o no). Puede comenzar en cualquier ficha de un grupo de coincidencias y alcanzar cualquier otra ficha a través de sus conexiones. Todos sus azulejos están conectados. Cada uno de los diferentes colores indica un grupo de coincidencia diferente. El único que se completa es el azul en el centro: no tiene conexiones inválidas.
La clase de grupo de partido en sí es en realidad extremadamente simple. Básicamente es solo una colección de azulejos con algunas funciones de ayuda. Aquí está:
Grupo público de MatchGroup Lista públicaazulejos public bool isClosed = true; Grupo público de partidas () tiles = new List (); público void SetTileColor (color de color) foreach (mosaico de LineTile en mosaicos) tile.sprite.color = color; public void Destroy () tiles.Clear ();
Esta es, con mucho, la parte más complicada de este proceso. Tenemos que analizar todo el tablero, dividiéndolo en sus grupos de coincidencias individuales, y luego determinar cuáles, si los hay, están completamente cerrados. Voy a llamar a esta clase BitmaskPuzzleGame, ya que es la clase principal que abarca la lógica del juego.
Sin embargo, antes de entrar en su implementación, definamos un par de cosas. Primero es un simple enumerar que las flechas se asignarán en función de la dirección hacia la que estén orientados:
// Para ayudarnos a determinar qué flecha se presionó: enumeración pública Dirección arriba, derecha, abajo, izquierda
El siguiente es un estructura que se enviará desde una flecha que se presiona para que podamos determinar dónde se encuentra en el tablero y en qué dirección está orientada:
// Cuando se presiona una flecha, contendrá estos datos para averiguar qué hacer con la pizarra: public struct ArrowData public Direction direction; índice de int público; ArrowData pública (Dirección de dirección, índice int) this.direction = direction; this.index = index;
A continuación, dentro de la clase, defina las variables de instancia que necesitamos:
// Contiene todos los mosaicos del mapa: public LineTile [] [] tileMap; // Contiene todos los grupos de fichas conectadas: Lista públicamatchGroups = nueva lista (); // Cuando se desplaza una fila / columna, esto se establece en verdadero, por lo que HandleUpdate debe actualizar: private bool matchGroupsAreDirty = true; // Cuántos azulejos de ancho es el tablero: private int tileMapWidth; // Cuántas fichas tiene el tablero: private int tileMapHeight;
Aquí hay una función que toma una ficha y devuelve todas las fichas que la rodean (las que están arriba, abajo, a la izquierda y a la derecha):
// Método de ayuda para obtener todos los mosaicos que están arriba / abajo / derecha / izquierda de un mosaico específico: Lista privadaGetTilesSurroundingTile (azulejo LineTile) Lista surroundingTiles = nueva lista (); int xIndex = tile.tileIndex.xIndex; int yIndex = tile.tileIndex.yIndex; if (xIndex> 0) surrounding Tiles.Add (tileMap [xIndex - 1] [yIndex]); si (xindex < tileMapWidth - 1) surroundingTiles.Add(tileMap[xIndex + 1][yIndex]); if (yIndex > 0) surrounding Tiles.Add (tileMap [xIndex] [yIndex - 1]); si < tileMapHeight - 1) surroundingTiles.Add(tileMap[xIndex][yIndex + 1]); return surroundingTiles;
Ahora dos métodos que devuelven todos los mosaicos en una columna o fila para que podamos cambiarlos:
// Método auxiliar para obtener todos los mosaicos en una columna específica: privado LineTile [] GetColumnTiles (int columnIndex) si (columnIndex < 0 || columnIndex >= tileMapWidth) lanza una nueva FutileException ("columna inválida:" + columnIndex); LineTile [] columnTiles = new LineTile [tileMapHeight]; para (int j = 0; j < tileMapHeight; j++) columnTiles[j] = tileMap[columnIndex][j]; return columnTiles; // Helper method to get all the tiles in a specific row: private LineTile[] GetRowTiles(int rowIndex) if (rowIndex < 0 || rowIndex >= tileMapHeight) lanza una nueva FutileException ("columna inválida:" + rowIndex); LineTile [] rowTiles = new LineTile [tileMapWidth]; para (int i = 0; i < tileMapWidth; i++) rowTiles[i] = tileMap[i][rowIndex]; return rowTiles; Ahora dos funciones que realmente desplazarán una columna o fila de mosaicos en una dirección específica. Cuando una baldosa se desplaza de un borde, se desplaza hacia el otro lado. Por ejemplo, un cambio a la derecha en una fila de Nub, Cross, Line resultará en una fila de Line, Nub, Cross.
// Desplazar las fichas en una columna hacia arriba o hacia abajo una (con ajuste). private void ShiftColumnInDirection (int columnIndex, Direction dir) LineTile [] currentColumnArrangement = GetColumnTiles (columnIndex); int nextIndex; // Mueva los mosaicos para que estén en los lugares correctos de la matriz tileMap. if (dir == Direction.Up) for (int j = 0; j < tileMapHeight; j++) nextIndex = (j + 1) % tileMapHeight; tileMap[columnIndex][nextIndex] = currentColumnArrangement[j]; tileMap[columnIndex][nextIndex].tileIndex = new TileIndex(columnIndex, nextIndex); else if (dir == Direction.Down) for (int j = 0; j < tileMapHeight; j++) nextIndex = j - 1; if (nextIndex < 0) nextIndex += tileMapHeight; tileMap[columnIndex][nextIndex] = currentColumnArrangement[j]; tileMap[columnIndex][nextIndex].tileIndex = new TileIndex(columnIndex, nextIndex); else throw new FutileException("can't shift column in direction: " + dir.ToString()); // Once the tileMap array is set up, actually visually move the tiles to their correct spots. for (int j = 0; j < tileMapHeight; j++) tileMap[columnIndex][j].y = (j + 0.5f) * tileSize; matchGroupsAreDirty = true; // Shift the tiles in a row either right or left one (with wrapping). private void ShiftRowInDirection(int rowIndex, Direction dir) LineTile[] currentRowArrangement = GetRowTiles(rowIndex); int nextIndex; // Move the tiles so they are in the correct spots in the tileMap array. if (dir == Direction.Right) for (int i = 0; i < tileMapWidth; i++) nextIndex = (i + 1) % tileMapWidth; tileMap[nextIndex][rowIndex] = currentRowArrangement[i]; tileMap[nextIndex][rowIndex].tileIndex = new TileIndex(nextIndex, rowIndex); else if (dir == Direction.Left) for (int i = 0; i < tileMapWidth; i++) nextIndex = i - 1; if (nextIndex < 0) nextIndex += tileMapWidth; tileMap[nextIndex][rowIndex] = currentRowArrangement[i]; tileMap[nextIndex][rowIndex].tileIndex = new TileIndex(nextIndex, rowIndex); else throw new FutileException("can't shift row in direction: " + dir.ToString()); // Once the tileMap array is set up, actually visually move the tiles to their correct spots. for (int i = 0; i < tileMapWidth; i++) tileMap[i][rowIndex].x = (i + 0.5f) * tileSize; matchGroupsAreDirty = true; Cuando hacemos clic en una flecha (es decir, cuando se suelta el botón de flecha), debemos determinar qué fila o columna se debe desplazar y en qué dirección.
// Cuando se presiona y suelta una flecha, desplace una columna hacia arriba / abajo o una fila hacia la derecha / izquierda. public void ArrowButtonReleased (botón FButton) ArrowData arrowData = (ArrowData) button.data; if (arrowData.direction == Direction.Up || arrowData.direction == Direction.Down) ShiftColumnInDirection (arrowData.index, arrowData.direction); else if (arrowData.direction == Direction.Right || arrowData.direction == Direction.Left) ShiftRowInDirection (arrowData.index, arrowData.direction);
Los siguientes dos métodos son los más importantes en el juego. El primero toma dos fichas y determina qué tipo de conexión tienen. Basa la conexión en el primero entrada de baldosas en el método (llamado baseTile). Esta es una distinción importante. los baseTile podría tener un ValidWithOpenSide conexión con el otroTile, pero si los ingresa en el orden inverso, podría regresar Inválido.
// Hay tres tipos de conexiones que pueden tener dos mosaicos: // 1. ValidWithSolidMatch: esto significa que los mosaicos se combinan con precisión con sus lados sólidos conectados. // 2. ValidWithOpenSide: esto significa que la baseTile tiene un lado abierto que toca la otra ficha, por lo que no importa cuál sea la otra ficha. // 3. Invalido: esto significa que el lado sólido de la baseTile se empareja con el lado abierto de la otra ficha, lo que resulta en una falta de coincidencia. privado TileConnectionType TileConnectionTypeBetweenTiles (LineTile baseTile, LineTile otherTile) int baseTileBitmaskSide = baseTile.bitmask; // La máscara de bits para el lado baseTile específico que está tocando el otro mosaico. int otherTileBitmaskSide = otherTile.bitmask; // La máscara de bits para el otro lado de Tile específico que está tocando el mosaico base. // Dependiendo de qué lado de la baldosa base está activada la otra baldosa, en modo de bits y en cada lado. con // la constante bitwise para ese lado individual. Si el resultado es 0, entonces el lado está abierto. De lo contrario, // el lado es sólido. if (otherTile.tileIndex.yIndex < baseTile.tileIndex.yIndex) baseTileBitmaskSide &= LineTile.kBitmaskBottom; otherTileBitmaskSide &= LineTile.kBitmaskTop; else if (otherTile.tileIndex.yIndex > baseTile.tileIndex.yIndex) baseTileBitmaskSide & = LineTile.kBitmaskTop; otherTileBitmaskSide & = LineTile.kBitmaskBottom; else if (otherTile.tileIndex.xIndex < baseTile.tileIndex.xIndex) baseTileBitmaskSide &= LineTile.kBitmaskLeft; otherTileBitmaskSide &= LineTile.kBitmaskRight; else if (otherTile.tileIndex.xIndex > baseTile.tileIndex.xIndex) baseTileBitmaskSide & = LineTile.kBitmaskRight; otherTileBitmaskSide & = LineTile.kBitmaskLeft; if (baseTileBitmaskSide == 0) devuelve TileConnectionType.ValidWithOpenSide; // tocando el lado baseTile el otroTile esta abierto. de lo contrario, si (otherTileBitmaskSide! = 0) devuelve TileConnectionType.ValidWithSolidMatch; // El lado baseTile y el otro lado Tile son sólidos y coincidentes. de lo contrario, devuelve TileConnectionType.Invalid; // El lado baseTile es sólido pero el otro lado está abierto. ¡No coinciden!
Finalmente, ActualizarMatches. Este es el método más importante de todos. Este es el que recorre el tablero, analiza todas las piezas, determina cuáles se conectan entre sí y qué grupos de coincidencias están completamente cerrados. Todo se explica en los comentarios..
// Ir a través del tablero y analizar todos los mosaicos, buscando coincidencias: Private void UpdateMatches () // Los grupos de coincidencia se están actualizando para que ya no estén sucios: matchGroupsAreDirty = false; // Dado que las columnas y filas deslizantes pueden desordenar todo, debemos deshacernos de los antiguos grupos de coincidencias y comenzar de nuevo. // Tenga en cuenta que probablemente hay una forma de usar el algoritmo en el que no tenemos que deshacernos de todas las coincidencias y // volver a empezar cada vez (por ejemplo, solo actualizar las coincidencias interrumpidas por un turno), pero eso puede venir más tarde si // necesitas mejorar el rendimiento. foreach (MatchGroup matchGroup en matchGroups) matchGroup.Destroy (); matchGroups.Clear (); // Comenzaremos a analizar el tablero desde el mosaico inferior izquierdo. El mosaico base actual será el // al que estamos empezando actualmente y desde donde estamos creando grupos de coincidencias. LineTile currentBaseTile = tileMap [0] [0]; ListatileSurrounders; // Variable que almacenará mosaicos circundantes de varios mosaicos base Lista checkedTiles = nueva lista (); // Almacenaremos los azulejos base aquí una vez que hayan sido analizados para no volver a analizarlos. MatchGroup currentMatchGroup; // El grupo de coincidencias que estamos analizando incluye el mosaico base actual. // Recorrer continuamente a través del tablero, haciendo grupos de coincidencias hasta que no haya más fichas para hacer grupos de coincidencias. while (currentBaseTile! = null) // Crear un nuevo grupo de coincidencia, agregar el mosaico base actual como su primer mosaico. currentMatchGroup = new MatchGroup (); currentMatchGroup.tiles.Add (currentBaseTile); // Recorra los mosaicos que comienzan en el mosaico base actual, analice sus conexiones, encuentre un nuevo mosaico base, // y vuelva a realizar el bucle, y así sucesivamente hasta que no encuentre más conexiones posibles con ninguno de los mosaicos en el grupo de coincidencias bool stillWorkingOnMatchGroup = verdadero; while (stillWorkingOnMatchGroup) // Rellene la lista tileSurrounders con todos los mosaicos que rodean el mosaico base actual: tileSurrounders = GetTilesSurroundingTile (currentBaseTile); // Iterar a través de todos los mosaicos circundantes y verificar si sus lados sólidos están alineados con los lados sólidos del azulejo base: foreach (LineTile surroundingTile en tileSurrounders) TileConnectionType connectionType = TileConnectionTypeBetweenTiles (currentBaseTile, surroundingTile); // Si hay una coincidencia sólida, agregue el envolvente al grupo de coincidencia. // Si hay una falta de coincidencia, el grupo de coincidencias no es un grupo de coincidencias "cerrado" perfecto. // Si hay una falta de coincidencia debido a un lado abierto del mosaico base, eso no importa en realidad // ya que no se está cortando un lado sólido (esto se llama TileConnectionType.ValidWithOpenSide). if (connectionType == TileConnectionType.ValidWithSolidMatch) currentMatchGroup.tiles.Add (surroundingTile); else if ((TileConnectionTypeBetweenTiles (currentBaseTile, surroundingTile) == TileConnectionType.Invalid) currentMatchGroup.isClosed = false; // Si la baldosa base tiene un lado cerrado / sólido que toca el borde del tablero, el grupo de coincidencias no se puede cerrar. if (((currentBaseTile.bitmask & LineTile.kBitmaskTop)! = 0 && currentBaseTile.tileIndex.yIndex == tileMapHeight - 1) || (currentBaseTile.it tileMapWidth - 1) || ((currentBaseTile.bitmask & LineTile.kBitmaskBottom)! = 0 && currentBaseTile.tileIndex.yIndex == 0) ((currentBaseTile.bitmask & LineTile.kBitmaskLeft)! = 0 y un paquete de actividades en el que se puede encontrar un paquete relacionado == 0)) currentMatchGroup.isClosed = false; // Agregue nuestro mosaico base a una matriz para que no lo verifiquemos más tarde: if (! CheckedTiles.Contains (currentBaseTile)) checkedTiles.Add (currentBaseTile); // Encuentra un nuevo mosaico base que hemos agregado al grupo de coincidencia pero que aún no hemos analizado: para (int i = 0; i < currentMatchGroup.tiles.Count; i++) LineTile tile = currentMatchGroup.tiles[i]; // If the checkedTiles array has the tile in it already, check to see if we're on the last // tile in the match group. If we are, then there are no more base tile possibilities so we are // done with the match group. If checkedTiles DOESN'T have a tile in the array, it means // that tile is in the match group but hasn't been analyzed yet, so we need to set it as // the next base tile. if (checkedTiles.Contains(tile)) if (i == currentMatchGroup.tiles.Count - 1) stillWorkingOnMatchGroup = false; matchGroups.Add(currentMatchGroup); else currentBaseTile = tile; break; // We're done with a match group, so now we need to find a new un-analyzed tile that's // not in any match groups to start a new one from. So we'll set currentBaseTile to // null then see if we can find a new one: currentBaseTile = null; for (int i = 0; i < tileMapWidth; i++) for (int j = 0; j < tileMapHeight; j++) LineTile newTile = tileMap[i][j]; if (!TileIsAlreadyInMatchGroup(newTile)) currentBaseTile = newTile; break; if (currentBaseTile != null) break;
Todo lo que nos queda es el HandleUpdate ¡función! Cada fotograma, actualice los grupos de coincidencia si necesitan actualización (es decir,. matchGroupsAreDirty == true), y establecer sus colores..
public void HandleUpdate () if (matchGroupsAreDirty) UpdateMatches ();
Así es como se vería el algoritmo si cada paso estuviera animado:
¡Y eso es! Si bien parte del código en este es específico de Futile, debería estar bastante claro cómo extenderlo a cualquier otro idioma o motor. Y para reiterar, hay muchas cosas no esenciales que faltan en esta publicación. Mire el código fuente para ver cómo funciona todo junto!
