Share
I denna handledning kommer jag att gå igenom hur du analyserar en kakel av kakel, iterera genom dem och hitta matchningar. Vi kommer att skapa ett spel där du behöver koppla samman linjer för att bilda helt stängda vägar utan öppna ändar. För att förenkla saker använder vi bitmaskning som en del av vår algoritm genom att tilldela varje kakel (plus dess rotation) sitt eget bitmasknummer. Oroa dig inte om du inte vet vilken bitmaskering som är. Det är faktiskt väldigt enkelt!
relaterade inläggJag kommer att skapa projektet i C # med hjälp av Unity with the Futile-ramverket, men koden kommer att tillämpas på nästan alla 2D-ramar med få ändringar. Här är Github repo med hela Unity-projektet. Och nedan är en spelbar demo av spelet som vi ska göra:
När jag började skapa Polymer ville jag skapa något annat än ett match-3-spel. Mitt interna smeknamn för det var ett "match-any" -spel. Match-3 pusselspel är överallt. Medan de verkligen kan vara roliga, kan en orsak till att de är så vanliga bero på att algoritmen för att hitta en matchning av tre kakel är ganska enkel.
Jag ville kunna matcha flera plattor som skulle kunna väva in och ut ur rader och kolumner och snarka sig över hela linjen. Inte bara det, men jag ville inte ha ett enkelt färg matchande spel. Jag ville att matcherna skulle baseras på specifika sidor av plattorna (till exempel kan en form bara ansluta till andra former på vänster och höger sida, men inte över och under.) Det visade sig vara mycket mer komplext än bara en normal match-3-algoritm.
Denna handledning delas upp i tre sektioner: Tile, Matchgruppen och Spelbrädet. I denna handledning kommer jag att försöka undvika så mycket Futile-specifik kod som möjligt. Om du vill se de Futile-specifika sakerna, kolla källkoden. Jag kommer inte heller att visa alla metoder och variabler i det här inlägget. Bara de viktigaste. Så om du tror att något saknas, titta igen på källkoden.
Ordet "bitmask" hänvisar till hur du kan lagra en serie sanna / falska värden i en enda numerisk variabel. Eftersom siffror representeras av en och nollor när de representeras i binär, genom att ändra numret kan du slå på eller av värden genom att växla om en bit är 1 eller 0.
För mer detaljer, se den här artikeln om bitvis operatörer och den här artikeln om binära nummer.
Vår första klass heter LineTile. Innan klassens början, låt oss definiera varje typ av kakel.
// De olika plattformarna: Public Enum LineTileType Nub, Line, Corner, Threeway, Cross, MAX
Så här ser bitarna ut:
Därefter, då vi bara tillåter rotationer på 90 grader, låt oss göra en enum för rotation.
// Jag använder det här istället för exakta grader eftersom // plattorna bara ska ha fyra olika rotationer: public enum RotationType Rotation0, Rotation90, Rotation180, Rotation270, MAX
Nästa är a struct kallad TileIndex, vilket är i grunden detsamma som a Vector2, utom med ints istället för flottor. Det kommer att användas för att hålla reda på var en kakel finns i spelbrädet.
public struct TileIndex public int xIndex; offentliga int yIndex; public TileIndex (int xIndex, int yIndex) this.xIndex = xIndex; this.yIndex = yIndex;
Slutligen, låt oss definiera de tre typerna av kopplingar mellan två plattor.
public enum TileConnectionType // En mismatch. Ogiltigt, // Plattorna kopplas inte direkt, // men inte på grund av en oöverträffad kant. ValidWithOpenSide, // Plattorna kopplas direkt. ValidWithSolidMatch
Därefter definierar du en bitmask i varje klass av en generisk kakel i klassen.
// Här är de bitar som jag tilldelade varje sida av plattan: // ===== 1 ===== // | | // | | // 8 2 // | | // | | // ============ // 1 == 0001 i binär // 2 == 0010 i binär // 4 == 0100 i binär // 8 == 1000 i binär offentlig konst int kBitmaskNone = 0; offentliga const int kBitmaskTop = 1; offentliga const int kBitmaskRight = 2; offentliga const int kBitmaskBottom = 4; offentliga const int kBitmaskLeft = 8;
Definiera sedan de instansvariabler som varje kakel ska ha.
// Tegelrepresentationen av plattan: public FSprite sprite; // Typ av kakel: allmän LineTileType lineTileType get; privat uppsättning; // Rotationen av plattan: allmän RotationType rotationType get; privat set; // Den bitmask som representerar kakel med sin rotation: public int bitmask get; privat set; // Kakelens placering på brädet: public TileIndex tileIndex = new TileIndex ();
För konstruktören, skapa sprite och sätt upp den vid rätt rotation. Det finns viss Futile-specifik kod här men det ska vara väldigt lätt att förstå.
Accentsconagua
public LineTile (LineTileType lineTileType, RotationType rotationType) this.lineTileType = lineTileType; this.rotationType = rotationType; // Ställ in sprite: switch (lineTileType) case LineTileType.Nub: sprite = new FSprite ("lineTileNub"); ha sönder; fall LineTileType.Line: sprite = nytt FSprite ("lineTileLine"); ha sönder; fall LineTileType.Corner: sprite = nytt FSprite ("lineTileCorner"); ha sönder; case LineTileType.Threeway: sprite = ny FSprite ("lineTileThreeway"); ha sönder; fall LineTileType.Cross: sprite = nytt FSprite ("lineTileCross"); ha sönder; standard: kasta ny FutileException ("ogiltig linje kakel typ"); AddChild (sprite); // Ställ in spritrotation: switch (rotationType) fall RotationType.Rotation0: sprite.rotation = 0; ha sönder; fall RotationType.Rotation90: sprite.rotation = 90; ha sönder; fall RotationType.Rotation180: sprite.rotation = 180; ha sönder; fall RotationType.Rotation270: sprite.rotation = 270; ha sönder; standard: kasta ny FutileException ("ogiltig rotationstyp"); Nu, en av de viktigaste delarna. Vi tilldelar varje kakel, i kombination med sin rotation, en bitmask som bestäms av vilken av sidorna är fasta och vilka är öppna.
// Ställ in bitmask genom att göra bitvis ELLER med varje sida som ingår i formen. // Så till exempel, en kakel som har alla fyra sidor fasta (t ex korset) skulle vara // 1 | 2 | 4 | 8 = 15, vilket är detsamma som 0001 | 0010 | 0100 | 1000 = 1111 i binär. om (lineTileType == LineTileType.Nub) if (rotationType == RotationType.Rotation0) bitmask = kBitmaskTop; om (rotationType == RotationType.Rotation90) bitmask = kBitmaskRight; om (rotationType == RotationType.Rotation180) bitmask = kBitmaskBottom; om (rotationType == RotationType.Rotation270) bitmask = kBitmaskLeft; om (lineTileType == LineTileType.Line) om (rotationType == RotationType.Rotation0 || rotationType == RotationType.Rotation180) bitmask = kBitmaskTop | kBitmaskBottom; om (rotationType == RotationType.Rotation90 || rotationType == RotationType.Rotation270) bitmask = kBitmaskRight | kBitmaskLeft; om (lineTileType == LineTileType.Corner) om (rotationType == RotationType.Rotation0) bitmask = kBitmaskTop | kBitmaskRight; om (rotationType == RotationType.Rotation90) bitmask = kBitmaskRight | kBitmaskBottom; om (rotationType == RotationType.Rotation180) bitmask = kBitmaskBottom | kBitmaskLeft; om (rotationType == RotationType.Rotation270) bitmask = kBitmaskLeft | kBitmaskTop; om (lineTileType == LineTileType.Threeway) om (rotationType == RotationType.Rotation0) bitmask = kBitmaskTop | kBitmaskRight | kBitmaskBottom; om (rotationType == RotationType.Rotation90) bitmask = kBitmaskRight | kBitmaskBottom | kBitmaskLeft; om (rotationType == RotationType.Rotation180) bitmask = kBitmaskBottom | kBitmaskLeft | kBitmaskTop; om (rotationType == RotationType.Rotation270) bitmask = kBitmaskLeft | kBitmaskTop | kBitmaskRight; om (lineTileType == LineTileType.Cross) bitmask = kBitmaskTop | kBitmaskRight | kBitmaskBottom | kBitmaskLeft;
Våra plattor är uppbyggda och vi är redo att börja matcha dem tillsammans!
Matchgrupper är just det: grupper av kakel som matchar (eller inte). Du kan börja på någon kakel i en matchgrupp och nå någon annan kakel genom sina anslutningar. Alla dess plattor är anslutna. Var och en av de olika färgerna indikerar en annan matchgrupp. Den enda som är klar är den blåa i mitten - den har inga ogiltiga anslutningar.
Matchgruppen klassen är faktiskt extremt enkel. Det är i grund och botten bara en samling kakel med några hjälpfunktioner. Här är det:
Public Class MatchGroup Public Listplattor; allmän bool isClosed = true; public MatchGroup () plattor = ny lista (); public void SetTileColor (Färgfärg) foreach (LineTile brickor i plattor) tile.sprite.color = color; public void Destroy () tiles.Clear ();
Detta är den mest komplicerade delen av denna process. Vi måste analysera hela styrelsen, dela upp den i sina enskilda matchgrupper och bestämma vilka som är helt stängda. Jag ska ringa den här klassen BitmaskPuzzleGame, eftersom det är huvudklassen som omfattar spellogiken.
Innan vi kommer in i dess genomförande men låt oss definiera ett par saker. Först är det enkelt enum att pilarna kommer att tilldelas baserat i vilken riktning de står inför:
// För att hjälpa oss att bestämma vilken pil som trycks in: Public Enum Direction Upp, Right, Down, Left
Nästa är a struct som kommer att skickas från en pil som pressas så vi kan avgöra var det finns i brädet och vilken riktning den står inför:
// När en pil trycks in kommer den att innehålla dessa data för att ta reda på vad man ska göra med styrelsen: public struct ArrowData public Direction direction; offentligt int index offentlig ArrowData (riktningsriktning, int index) this.direction = riktning; this.index = index;
Därefter definierar vi de instansvariabler vi behöver i klassen:
// Innehåller alla kartans kakel: public LineTile [] [] tileMap; // Innehåller alla grupper av anslutna plattor: Public ListmatchGroups = ny lista (); // När en rad / kolumn flyttas är den här inställd så att HandleUpdate vet att uppdatera: privat bool matchGroupsAreDirty = true; // Hur många brickor breda brädet är: privat int tileMapWidth; // Hur många brickor som är höga brädet är: privat int tileMapHeight;
Här är en funktion som tar en kakel och returnerar alla dess omgivande plattor (de ovan, nedan, till vänster och till höger om det):
// Helpermetod för att få alla kakel som är över / under / höger / vänster på en viss kakel: privat listaGetTilesSurroundingTile (LineTile-flis) Lista surroundingTiles = ny lista (); int xIndex = tile.tileIndex.xIndex; int yIndex = tile.tileIndex.yIndex; om (xIndex> 0) surroundingTiles.Add (tileMap [xIndex - 1] [yIndex]); om (xIndex < tileMapWidth - 1) surroundingTiles.Add(tileMap[xIndex + 1][yIndex]); if (yIndex > 0) surroundingTiles.Add (tileMap [xIndex] [yIndex - 1]); om (yIndex < tileMapHeight - 1) surroundingTiles.Add(tileMap[xIndex][yIndex + 1]); return surroundingTiles;
Nu två metoder som returnerar alla plattor i antingen en kolumn eller rad så vi kan flytta dem:
// Helpermetod för att få alla plattor i en viss kolumn: Private LineTile [] GetColumnTiles (int columnIndex) if (columnIndex < 0 || columnIndex >= tileMapWidth) kasta ny FutileException ("ogiltig kolumn:" + columnIndex); LineTile [] columnTiles = new LineTile [tileMapHeight]; för (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) kasta ny FutileException ("ogiltig kolumn:" + rowIndex); LineTile [] rowTiles = ny LineTile [tileMapWidth]; för (int i = 0; i < tileMapWidth; i++) rowTiles[i] = tileMap[i][rowIndex]; return rowTiles; Nu två funktioner som faktiskt kommer att flytta en kolumn eller en rad kakel i en specifik riktning. När en kakel skiftar av en kant, slingrar den runt till andra sidan. Till exempel kommer en högerskift på en rad med Nub, Cross, Line att resultera i en rad med Linje, Nub, Cross.
// Skift kakelarna i en kolumn antingen uppåt eller nedåt (med omslag). privat tomt ShiftColumnInDirection (int kolumnIndex, Direction dir) LineTile [] currentColumnArrangement = GetColumnTiles (columnIndex); int nextIndex; // Flytta kakelarna så att de finns i rätt fläckar i plattan till kakel. om (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; När vi klickar på en pil (dvs när pilknappen släpps) måste vi bestämma vilken rad eller kolumn som ska skiftas, och i vilken riktning.
// När en pil trycks och släpps, skift en kolumn upp / ner eller en rad höger / vänster. public void ArrowButtonReleased (FButton-knapp) ArrowData arrowData = (ArrowData) button.data; om (arrowData.direction == Direction.Up || arrowData.direction == Direction.Down) ShiftColumnInDirection (arrowData.index, arrowData.direction); annars om (arrowData.direction == Direction.Right || arrowData.direction == Direction.Left) ShiftRowInDirection (arrowData.index, arrowData.direction);
De två följande metoderna är de viktigaste i spelet. Den första tar två plattor och bestämmer vilken typ av anslutning de har. Det baserar anslutningen på först kakel in i metoden (kallad baseTile). Detta är en viktig skillnad. De baseTile kan ha en ValidWithOpenSide anslutning till otherTile, men om du anger dem i omvänd ordning kan den återvända Ogiltig.
// Det finns tre typer av anslutningar två plattor kan ha: // 1. ValidWithSolidMatch-det betyder att plattorna matchas exakt med sina fasta sidor anslutna. // 2. ValidWithOpenSide-det här betyder att basTilen har en öppen sida som rör den andra plattan, så det spelar ingen roll vad den andra plattan är. // 3. Ogiltigt-det betyder att basTiles solida sida matchas med den andra plattans öppna sida, vilket resulterar i en felaktig matchning. privat TileConnectionType TileConnectionTypeBetweenTiles (LineTile baseTile, LineTile otherTile) int baseTileBitmaskSide = baseTile.bitmask; // Bitmask för den specifika basTile-sidan som rör den andra plattan. int otherTileBitmaskSide = otherTile.bitmask; // Bitmask för den specifika otherTile-sidan som rör basplattan. // Beroende på vilken sida av grundplattan som den andra plattan är på, bitvis och varje sida tillsammans. med // den bitvisa konstanten för den enskilda sidan. Om resultatet är 0, är sidan öppet. Annars, // sidan är fast. om (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; annars om (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; om (baseTileBitmaskSide == 0) returnera TileConnectionType.ValidWithOpenSide; // baseTile sida rörande otherTile är öppen. annars om (otherTileBitmaskSide! = 0) returnerar TileConnectionType.ValidWithSolidMatch; // baseTile sida och otherTile sida är solida och matchade. annars returnerar TileConnectionType.Invalid; // baseTile-sidan är fast men andraTile-sidan är öppen. Missanpassning!
Till sist, UpdateMatches. Detta är den viktigaste metoden för alla. Det här är det som går igenom styrelsen, analyserar alla bitar, bestämmer vilka som är kopplade till varandra, och vilka matchningsgrupper är helt stängda. Allt förklaras i kommentarerna.
// Gå igenom brädet och analysera alla brickor, letar efter matcher: Private void UpdateMatches () // Matchgrupper uppdateras så att de inte längre är smutsiga: matchGroupsAreDirty = false; // Eftersom glidande kolumner och rader kan förstöra allt, måste vi bli av med de gamla matchgrupperna och börja om. // Kom ihåg att det förmodligen finns ett sätt att använda algoritmen där vi inte behöver bli av med alla matcher och / / starta över varje gång (säg bara uppdatera matcherna som störs av ett skifte), men det kan komma senare om // du behöver förbättra prestanda. foreach (MatchGroup matchGroup i matchGroups) matchGroup.Destroy (); matchGroups.Clear (); // Vi börjar analysera brädet från den nedre vänstra plattan. Nuvarande basplattor kommer att vara den // som vi för närvarande börjar och bygger matchgrupper utanför. LineTile currentBaseTile = flikMap [0] [0]; ListatileSurrounders; // Variabel som kommer att lagra omgivande plattor av olika plattor. Lista checkedTiles = ny lista (); // Vi lagrar basplattor här när de har analyserats så vi inte omanalyserar dem. MatchGroup currentMatchGroup; // Den matchningsgrupp vi analyserar som innehåller aktuell basplatta. // Gå kontinuerligt genom brädet, gör matchgrupper tills det inte finns fler brickor för att skapa matchgrupper från. medan (currentBaseTile! = null) // Skapa en ny matchgrupp, lägg till den aktuella basplattan som sin första kakel. currentMatchGroup = ny MatchGroup (); currentMatchGroup.tiles.Add (currentBaseTile); // Loop genom kakel som börjar med nuvarande basplatta, analysera deras anslutningar, hitta en ny basplatta, // och loop igen och så vidare tills du inte hittar några fler anslutningar med någon av plattorna i matchgruppen bool stillWorkingOnMatchGroup = true; medan (stillWorkingOnMatchGroup) // Populera lista över brickor med alla plattor som omger den aktuella grundplattan: tileSurrounders = GetTilesSurroundingTile (currentBaseTile); // Iterera genom alla omgivande plattor och kontrollera om deras fasta sidor är i linje med bottenplattans fasta sidor: foreach (LineTile surroundingTile in tileSurrounders) TileConnectionType connectionType = TileConnectionTypeBetweenTiles (currentBaseTile, surroundingTile); // Om det finns en solid match lägger du till överskridaren till matchgruppen. // Om det inte finns en matchning är matchgruppen inte en perfekt "sluten" matchgrupp. // Om det finns en otillbörlig matchning på grund av en öppen sida av basplattan, så spelar det ingen roll då / då det inte går att klippa en fast sida (det kallas TileConnectionType.ValidWithOpenSide). om (connectionType == TileConnectionType.ValidWithSolidMatch) currentMatchGroup.tiles.Add (surroundingTile); annars om (TileConnectionTypeBetweenTiles (currentBaseTile, surroundingTile) == TileConnectionType.Invalid) currentMatchGroup.isClosed = false; // Om basplattan har en sluten / fast sida som rör kanten på brädet, kan matchgruppen inte stängas. om ((currentBaseTile.bitmask & LineTile.kBitmaskTop)! = 0 && currentBaseTile.tileIndex.yIndex == tileMapHeight - 1) || ((currentBaseTile.bitmask & LineTile.kBitmaskRight)! = 0 && currentBaseTile.tileIndex.xIndex == tileMapWidth - 1) || ((currentBaseTile.bitmask & LineTile.kBitmaskBottom)! = 0 && currentBaseTile.tileIndex.yIndex == 0) || ((currentBaseTile.bitmask & LineTile.kBitmaskLeft)! = 0 && currentBaseTile.tileIndex.xIndex == 0)) currentMatchGroup.isClosed = false; // Lägg till vår basplatta i en array så vi kontrollerar inte den igen senare: om (! CheckedTiles.Contains (currentBaseTile)) checkedTiles.Add (currentBaseTile); // Hitta en ny basplatta som vi har lagt till i matchgruppen men har inte analyserat än: för (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;
Allt vi har kvar är HandleUpdate fungera! Varje ram uppdaterar matchgrupperna om de behöver uppdateras (dvs.. matchGroupsAreDirty == true) och ställa in sina färger.
public void HandleUpdate () if (matchGroupsAreDirty) UpdateMatches ();
Här är vad algoritmen skulle se ut om varje steg var animerat:
Och det är allt! Medan vissa av koden i detta är specifik för Futile, borde det vara ganska tydligt hur man utökar det till något annat språk eller motor. Och för att upprepa, det finns många icke-väsentliga saker som saknas i det här inlägget. Vänligen kolla källkoden för att se hur allt fungerar tillsammans!
