sábado, 27 de octubre de 2012

Using Tile Masks to Set a Tile’s Type Based on Its Surrounding Tiles

Commonly used in tile-based games, tile masks let you change a tile depending on its neighbours, allowing you to blend terrains, replace tiles, and more. In this tutorial, I’ll show you a scalable, re-usable method for detecting whether a tile’s immediate neighbours match one of any number of patterns that you set.

Note: Although this tutorial is written using C# and Unity, you should be able to use the same techniques and concepts in almost any game development environment.


What Is a Tile Mask?

Consider the following: you’re making a Terraria-like, and you want dirt blocks to turn into mud blocks if they are next to water. Let’s assume that your world has a lot more water than it does dirt, so the cheapest way you can do this is by checking each dirt block to see if it’s next to water, and not vice versa. This is a pretty good time to use a tile mask.

Tile masks are as old as the mountains, and are based on a simple idea. In a 2D grid of objects, a tile can have eight other tiles directly adjacent to it. We’ll call this the local range of that central tile (Figure 1).


Figure 1. The local range of a tile.

To decide what to do with your dirt tile, you’ll compare its local range to a set of rules. For example, you might look directly above the dirt block and see if there’s water there (Figure 2). The set of rules you use to evaluate your local range is your tile mask.


Figure 2. Tile mask for identifying a dirt block as a mud block. The grey tiles can be any other tile.

Of course, you’ll also want to check for water in the other directions as well, so most tile masks have more than one spatial arrangement (Figure 3).


Figure 3. The four typical orientations of a tile mask: 0°, 90°, 180°, 270°.

And sometimes you’ll find that even really simple tile mask arrangements can be mirrored and non-superposable (Figure 4).


Figure 4. An example of chirality in a tile mask. The top row cannot be rotated to match the bottom row.

Storage Structures of a Tile Mask

Storing Its Elements

Each cell of a tile mask has an element inside it. The element at that cell is compared to the corresponding element in the local range to see whether they match.

I use Lists as elements. Lists allows me to perform comparisons of arbitrary complexity, and C#’s Linq provides very handy ways of merging lists into larger lists, reducing the number of changes that I can potentially forget to do.

For example, a list of wall tiles can be combined with a list of floor tiles and a list of opening tiles (doors and windows) to produce a list of structural tiles, or lists of the furniture tiles from individual rooms can be combined to make a list of all furniture. Other games might have lists of tiles that are burnable, or affected by gravity.

Storing the Tile Mask Itself

The intuitive way to store a tile mask is as a 2D array, but accessing 2D arrays can be slow, and you are going to be doing it a lot. We know that a local range and a tile mask will always consist of nine elements, so we can avoid that time penalty by using a plain 1D array, reading the local range into it from top to bottom, left to right (Figure 4).


Figure 5. Storing a 2D tile mask in a 1D structure.

The spatial relationships between elements are preserved if you ever need them (I haven’t needed them so far), and arrays can store pretty much anything. Tilemasks in this format can also be easily rotated by offset read/writes.

Storing Rotational Information

In some cases you may want to rotate the central tile according to its surroundings, such as when placing a wall next to other walls. I like using jagged arrays to hold the four rotations of a tile mask in the same place, using the outer array’s index to indicate the current rotation (more on that in the code).


Code Requirements

With the basics explained, we can outline what the code needs to do:

  1. Define and store tile masks.
  2. Rotate tile masks automatically, instead of us having to manually maintain four rotated copies of the same definition.
  3. Grab a tile’s local range.
  4. Evaluate the local range against a tile mask.

The following code is written in C# for Unity, but the concepts should be fairly portable. The example is one from my own work in procedurally converting roguelike text-only maps to 3D (placing a straight section of wall, in this case).


Define, Rotate and Store the Tile Masks

I automate all of this with one method call to a DefineTilemask method. Here’s an example of usage, with method declaration below.

  public static readonly List<char> any = new List<char>() {};  public static readonly List<char> ignored = new List<char>() {' ', '_'};  public static readonly List<char> wall = new List<char>() {'#', 'D', 'W'};  public static List<char>[][] outerWallStraight = MapHelper.DefineTilemask  (          any,                    ignored,                        any,          wall,                   any,                            wall,          any,                    any,                            any  );  

I define the tilemask in its unrotated form. The list called ignored stores characters that don’t describe anything in my program: spaces, which are skipped; and underscores, which I use to show an invalid array index. A tile at (0,0) (upper left corner) of a 2D array won’t have anything to its North or West, for example, so its local range gets underscores there instead. anyis an empty list which is always evaluated as a positive match.

  public static List<char>[][] DefineTilemask (List<char> nW, List<char> n, List<char> nE, List<char> w, List<char> centre, List<char> e, List<char> sW, List<char> s, List<char> sE)  {          List<char>[] template = new List<char>[9] {                  nW,     n,              nE,                  w,      centre, e,                  sW,     s,              sE          };          return new List<char>[4][] {                  RotateLocalRange (template, 0),                  RotateLocalRange (template, 1),                  RotateLocalRange (template, 2),                  RotateLocalRange (template, 3)          };  }  public static List<char>[] RotateLocalRange (List<char>[] localRange, int rotations)  {          List<char>[] rotatedList = new List<char>[9] {localRange[0], localRange[1], localRange[2], localRange[3], localRange[4], localRange[5], localRange[6], localRange[7], localRange[8]};          for (int i = 0; i < rotations; i++)          {                  List<char>[] tempList = new List<char>[9] {rotatedList[6], rotatedList[3], rotatedList[0], rotatedList[7], rotatedList[4], rotatedList[1], rotatedList[8], rotatedList[5], rotatedList[2]};                  rotatedList = tempList;          }          return rotatedList;  }  

It’s worth explaining the implementation of this code. In DefineTilemask, I provide nine lists as arguments. These lists are placed into a temporary 1D array, and then rotated in +90° steps by writing to a new array in a different order. The rotated tilemasks are then stored in a jagged array, whose structure I use to convey rotational information. If the tilemask at outer index 0 matches, then the tile is placed with no rotation. A match at outer index 1 gives the tile a +90° rotation, and so on.


Grab a Tile’s Local Range

This one is straightforward. It reads the local range of the current tile into a 1D character array, replacing any invalid indices with underscores.

  /*  Usage:          char[] localRange = GetLocalRange (blueprint, row, column);          blueprint is the 2D array that defines the building.          row and column are the array indices of the current tile being evaluated.  */  public static char[] GetLocalRange (char[,] thisArray, int row, int column)  {          char[] localRange = new char[9];          int localRangeCounter = 0;          // Iterators start counting from -1 to offset the reading up and to the left, placing the requested index in the centre.          for (int i = -1; i < 2; i++)          {                  for (int j = -1; j < 2; j++)                  {                          int tempRow = row + i;                          int tempColumn = column + j;                          if (IsIndexValid (thisArray, tempRow, tempColumn) == true)                          {                                  localRange[localRangeCounter] = thisArray[tempRow, tempColumn];                          }                          else                          {                                  localRange[localRangeCounter]  = '_';                          }                          localRangeCounter++;                  }          }          return localRange;  }  public static bool IsIndexValid (char[,] thisArray, int row, int column)  {          // Must check the number of rows at this point, or else an OutOfRange exception gets thrown when checking number of columns.          if (row < thisArray.GetLowerBound (0) || row > (thisArray.GetUpperBound (0))) return false;          if (column < thisArray.GetLowerBound (1) || column > (thisArray.GetUpperBound (1))) return false;          else return true;  }  

Evaluate a Local Range With a Tile Mask

And here’s where the magic happens! TrySpawningTile is given the local range, a tile mask, the wall piece to spawn if the tile mask matches, and the row and column of the tile being evaluated.

Importantly, the method that performs the actual comparison between local range and tile mask (TileMatchesTemplate) dumps a tile mask rotation as soon as it finds a mismatch. Not shown is basic logic defining what tile masks to use for which tile types (you wouldn’t use a wall tile mask on a piece of furniture, for example).

  /*  Usage:      TrySpawningTile (localRange, TileIDs.outerWallStraight, outerWallWall,                       floorEdgingHalf, row, column);  */  // These quaternions have a -90 rotation along X because models need to be  // rotated in Unity due to the different up axis in Blender.  public static readonly Quaternion ROTATE_NONE   = Quaternion.Euler(-90, 0, 0);  public static readonly Quaternion ROTATE_RIGHT  = Quaternion.Euler(-90, 90, 0);  public static readonly Quaternion ROTATE_FLIP   = Quaternion.Euler(-90, 180, 0);  public static readonly Quaternion ROTATE_LEFT   = Quaternion.Euler(-90, -90, 0);  bool TrySpawningTile (char[] needleArray, List<char>[][] templateArray, GameObject tilePrefab, int row, int column)  {          Quaternion horizontalRotation;          if (TileMatchesTemplate (needleArray, templateArray, out horizontalRotation) == true)          {                  SpawnTile (tilePrefab, row, column, horizontalRotation);                  return true;          }          else          {                  return false;          }  }  public static bool TileMatchesTemplate (char[] needleArray, List<char>[][] tileMaskJaggedArray, out Quaternion horizontalRotation)  {          horizontalRotation = ROTATE_NONE;          for (int i = 0; i < (tileMaskJaggedArray.Length); i++)          {                  for (int j = 0; j < 9; j++)                  {                          if (j == 4) continue; // Skip checking the centre position (no need to ascertain that a block is what it says it is).                          if (tileMaskJaggedArray[i][j].Count != 0)                          {                                  if (tileMaskJaggedArray[i][j].Contains (needleArray[j]) == false) break;                          }                          if (j == 8) // The loop has iterated nine times without stopping, so all tiles must match.                          {                                  switch (i)                                  {                                          case 0:                                                  horizontalRotation = ROTATE_NONE;                                                  break;                                          case 1:                                                  horizontalRotation = ROTATE_RIGHT;                                                  break;                                          case 2:                                                  horizontalRotation = ROTATE_FLIP;                                                  break;                                          case 3:                                                  horizontalRotation = ROTATE_LEFT;                                                  break;                                  }                                  return true;                          }                  }          }          return false;  }  void SpawnTile (GameObject tilePrefab, int row, int column, Quaternion horizontalRotation)  {          Instantiate (tilePrefab, new Vector3 (column, 0, -row), horizontalRotation);  }  

Appraisal and Conclusion

Advantages of This Implementation

  • Very scalable; just add more tile masks’ definitions.
  • The checks a tile mask performs can be as complex as you like.
  • The code is fairly transparent, and its speed can be improved by performing a few extra checks on the local range before you start going through tile masks.

Disadvantages of This Implementation

  • Can potentially be very expensive. In the absolute worst case you will have (36 × n) + 1 array accesses and calls to List.Contains() before finding a match, where n is the number of tile mask definitions you’re searching through. It’s essential to do what you can to narrow the list of tile masks down before you begin searching.

Conclusion

Tile masks have uses not only in world generation or aesthetics, but also in elements that affect gameplay. It’s not hard to imagine a puzzle game where tile masks might be used to determine the state of the board or the potential moves of pieces, or editing tools might use a similar system to snap blocks to each other. This article demonstrated a basic implementation of the idea, and I hope you found it useful.



No hay comentarios:

Publicar un comentario