Introduction
This post is intended to help fill in a few of the gaps I found while trying to implement autotiles into my game engine. While they are a relatively simple concept, I was having difficulty finding clear soup-to-nuts explanations for all stages of using autotiles; having clear explanations at all stages is crucial if you want to mix different types of autotiles together under a common convention as I wanted to do. Prior to reading this post it is recommended that you have a rough understanding of what autotiles are.
Let's take at the autotiles we'll be examining here:
- Wall autotiles
- RPG Maker VX-style
- RPG Maker XP-style (also covers chipsets)
These are common formats if you're working with some of the common free tilesets out there (e.g. First Seed Material/REFMAP/Mack autotiles) that are compatible with RPG Maker. Hopefully at the end of this post you will have all you need to import, split up, and use these formats within your game engine. All code provided should be considered public domain - no need to credit or provide a license; copy/paste away!
Classifying Autotiles
First, a general note about how to classify autotiles. Autotiles are a subset of much more generalized tiling algorithms common in other related fields such as the creation of mazes. In general, autotiling algorithms consider which tile to use from a tileset based on the neighbors around the current tile. This has the potential to be quite generalized as you could have many different types of tiles and the radius with which to check neighbors could in theory be quite large. We are looking at a very small subset here that will only consider immediate neighbors and only whether or not the neighbor is present. When mixing types of autotiles together, one could simply say that a neighbor is present if it is the same type. That is the scheme we will assume here.
Given a tile and eight possible neighbors (assuming the center tile is filled), we then have a total of 2^8 = 256 possible combinations of neighbors. While this is the general case, the formats we are looking at restrict the space still further.
The first subset is quite simple. Rather than considering all eight possible neighbors, we only consider the neighbor of the cardinal directions (north, east, south, west). This gives 2^4 = 16 possible combinations. This is how wall autotiles are structured.
The second subset is a little more complex. Suppose that you use the wall subset, but then additionally allow for corner points only with the condition that the two neighboring cardinal directions are present. So for example, a valid combination would be north/northwest/west because north and west are present. An invalid combination would be north/northwest - west is not present so northwest is not a valid corner to include. This set of combinations is more difficult to state succinctly, but gives a total of 47 possible combinations. This is called a "blob" tileset and is used in both RPG Maker VX, RPG Maker XP, and chipset style terrain autotiles.
The Path to Integration
Integrating autotiles in your game engine takes a few stages:
- Import - Convert assets into engine format
- Usage - Find correct tile to use
- Create neighbor code
- Filter neighbor codes
- Convert filtered neighbor code to tile index
Step one depends on the neighbor codes in step two, so we will start with step two first.
Usage - Neighbor Codes
Calculating a neighbor code is quite simple. Each of the eight points is simply treated as a bit flag, and then the whole bit set is the neighbor code; one byte represents the full code. This seems to be commonly used by almost all implementations. However, different implementations seem to choose different conventions for starting direction etc. I have chosen to start with west (as LSB) and work clockwise around the circle. So suppose that a tile has a west neighbor and a northeast neighbor. Then the neighbor code is:
W NW N NE E SE S SW
1*2^0 + 0*2^1 + 0*2^2 + 1*2^3 + 0*2^4 + 0*2^4 + 0*2^6 + 0*2^7 = 9
Usage - Filtered Neighbor Codes
How a neighbor code is filtered depends on the type of autotile it is targeting. For wall autotiles, only the four cardinal directions are considered so the NW, NE, SE, and SW bits can be masked out; more on this in the next step. For blob autotiles, the corner should be masked out if one of the two neighboring cardinal directions is not present - code is given below in C# to accomplish this. Note we don't care if the corner was set, we just mask it out regardless.
private static byte NorthAndWest = 0x05; //-----N-W
private static byte EastAndNorth = 0x14; //---E-N--
private static byte SouthAndEast = 0x50; //-S-E----
private static byte WestAndSouth = 0x41; //-S-----W
private static byte CornerNWMask = 0xFD; //Not ------C-
private static byte CornerNEMask = 0xF7; //Not ----C---
private static byte CornerSEMask = 0xDF; //Not --C-----
private static byte CornerSWMask = 0x7F; //Not C-------
public static byte FilterNeighbors(byte neighbors)
{
if ((neighbors & NorthAndWest) != NorthAndWest)
neighbors &= CornerNWMask;
if ((neighbors & EastAndNorth) != EastAndNorth)
neighbors &= CornerNEMask;
if ((neighbors & SouthAndEast) != SouthAndEast)
neighbors &= CornerSEMask;
if ((neighbors & WestAndSouth) != WestAndSouth)
neighbors &= CornerSWMask;
return neighbors;
}
You can probably come up with fancier bitmasking code but I chose this for clarity.
Usage - Tile Index
The end goal is to turn the filtered neighbor code into an index suitable for looking up in a tileset that represents how the game engine has imported the autotile.
For wall autotiles, a 4x4 array of tiles is chosen with row major numbering. That is:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
In the wall autotile case, filtering the neighbor code and then converting to a tile index may seem too cumbersome, so it is quite reasonable to do the conversion from a raw neighbor code into a tile index all in one shot. Note the preservation of cardinal direction order.
private const byte West = 0x01;
private const byte North = 0x04;
private const byte East = 0x10;
private const byte South = 0x40;
private const byte WestFour = 0x01;
private const byte NorthFour = 0x02;
private const byte EastFour = 0x04;
private const byte SouthFour = 0x08;
//Converts 8 bit format to 4 bit.
public static byte GetFourBitNeighbors(byte n)
{
byte filtered = 0;
if ((n & West) > 0) filtered |= WestFour;
if ((n & North) > 0) filtered |= NorthFour;
if ((n & East) > 0) filtered |= EastFour;
if ((n & South) > 0) filtered |= SouthFour;
return filtered;
}
//How to use the it by row and column if desired
byte n = (byte)neighbors;
byte filtered = GetFourBitNeighbors(n);
int row = filtered / 4;
int col = filtered % 4;
In the case of a blob autotile, we will use an 8x6 array in the same way, e.g.:
0 1 2 3 4 5 6 7
8 ..................
16 .................
24 .................
32 .................
Since there are only 47 tiles, the last slot is unused.
Now a very important note. How will we tie the ordering of the neighbor code to the ordering within the 8x6 array? We simply order by the raw neighbor code. I found the easiest way to do this was to iterate through all 256 possible neighbor codes and discard neighbor codes that weren't valid by checking each corner (here "tile index" and "atlas index" are being used as interchangeable terms):
public static readonly Dictionary NeighborsToAtlasIndex = CreateNeighborsToAtlasIndex();
public static Dictionary CreateNeighborsToAtlasIndex()
{
//Very simple - just go through all 256 neighbor combos and find the valid
//ones, incrementing as we go.
//By convention, we will say the LSB -> MSB represents clockwise rotation
//with the LSB being the left spoke "west"
var result = new Dictionary();
int tileIndex = 0;
for (int i = 0; i < 256; i++)
{
var cornerScores = GetCornerScores(i);
bool isValid = true;
for (int j = 0; j < 4 && isValid; j++)
isValid = IsValidCornerScore(cornerScores[j]);
if (isValid)
{
result.Add(i, tileIndex);
tileIndex++;
}
}
return result; //Should be 47
}
public static int[] GetCornerScores(int neighborBits)
{
//Returns an array of "corner" scores, that is the the 3-bit
//flags for the directions determining that quad in
//clockwise order.
//So bit runs 0-2, 2-4, 4-6, 6-"8" clockwise (A,B,D,C)
//However, the return is in A,B,C,D to make things easier upstream
int n = (neighborBits << 8) | neighborBits; //extend one copy to wrap easier
return new int[]
{
(n & 0x7), //A
( (n>>2) & 0x7), //B
( (n>>6) & 0x7), //C
( (n>>4) & 0x7) //D
};
}
private static bool IsValidCornerScore(int score)
{
//Bit 0 is a cardinal direction, 1 is the corner, 2 is the next cardinal direction
//So the corner cannot be on unless both cardinals are on. While this could be
//done bit-masky, we just statically rule out 110, 011, 010
return (score != 6 && score != 3 && score != 2);
}
public static int GetTileIndex(int neighbors)
{
//First, filter the neighbors of invalidly set corners
byte filtered = FilterNeighbors((byte)neighbors);
//Then get the index into the 47-tile set
return NeighborsToAtlasIndex[filtered];
}
This is hardly the most efficient way to achieve this, but it was a way that seemed straightforward to me and seems simple to explain without simply resorting to a lookup table.
So at this point, as long as we have the eight bit neighbor code, we should be able to get the appropriate tile index into whatever tileset we will use to represent the autotile. Now we just need to return to step one and convert the raw assets into the correct formats.
Import
The steps for converting input formats to engine formats have certain similarities across autotile types but of course vary per format.
There are three general similarities of note:
- Quarter-tiles (or as I'll call them q-tiles) are reassembled from the input in quads to form tiles in the engine format.
- Input formats themselves are broken into quads of quarter tiles, and the location within the quad partially constrains which other quarter tiles may neighbor it. These quads of quarter tiles will be labelled A, B, C, and D, and solution tiles must consist of exactly an A, B, C, and D quarter tile.
- Every output tile solution is not only constrained by the ABCD designation above but also at least in part by considering a "corner" (or "edge") score for each q-tile independently (more on this later). In the case of wall and VX autotiles, this in combination with the ABCD designation above exactly determines the solution, with XP autotiles it gets most of the way there.
Import - Wall Autotiles
The input format is a 4x4 series of quarter tiles. For RPG Maker XP/VX, the end tile size is 32 pixels, so the quarter tiles are 16 pixels. The input can be overlaid with A, B, C, D as described above.
A B A B
C D C D
A B A B
C D C D
The ABCD designation and the constraints that it puts on the system are probably beginning to be more apparent from a quick look at the artwork. A is always left of B, but A must always be right of B, etc. Of course it is also clear that the letter designation is not enough as for example tile 0 and tile 6 obviously can't go together.
Now the desired output in the engine format must satisfy the ABCD designation and has sixteen tiles, so we already know the output looks roughly like this:
AB AB AB AB
CD CD CD CD
AB AB AB AB
CD CD CD CD
AB AB AB AB
CD CD CD CD
AB AB AB AB
CD CD CD CD
So to find the solution for each output tile we already have some constraints. Next come the "corner" scores. With only cardinal directions present, there really are no corners so perhaps it is more appropriate to call it an "edge" score. This is a somewhat tricky concept but is crucial to finding the solution.
So how does this work?
Well consider a solution tile from above. Based on the ordering of the engine tileset, each index number corresponds to a certain expectation about which neighbors are present e.g. tile at index 1 should have only the west neighbor set.
Additionally, we know that the solution tile is broken into q-tiles. Each q-tile only cares about the neighbors it borders on its outside edges. The neighbors that it expects to be set can be coded into a two-bit number, which is the edge score. If we are careful about the construction of this two-bit number, it essentially follows naturally as a subset of the overall neighbor code.
Similarly, for each q-tile in the input format, we can assign an edge code by visually examining what the tile expects to be bordering. We assign a 0 for no neighbor, and a 1 for a neighbor. Here's an example of a small slice from the excellent First Seed Materials TileA3 showing both the ABCD designation and the edge code all in one neighbor, this will be used in the code below.
At this point, we make an interesting observation. There are 4 letter designations (ABCD) and 4 possible edge codes (0-3), which just happens to line up nicely as 4x4 = 16 input q-tiles. So each combination of letter and edge code is covered.
This means that if the solution tile can key off a letter and edge code for each q-tile, we have a unique solution, hurrah.
So the first step is to get the edge scores for a given neighbor code - this is for the solution tile side request:
//Repeated from above but shown for context
//Converts 8 bit format to 4 bit.
public static byte GetFourBitNeighbors(byte n)
{
byte filtered = 0;
if ((n & West) > 0) filtered |= WestFour;
if ((n & North) > 0) filtered |= NorthFour;
if ((n & East) > 0) filtered |= EastFour;
if ((n & South) > 0) filtered |= SouthFour;
return filtered;
}
public static int[] GetEdgeScores(byte fourBitNeighbors)
{
//Returns an array of "edge" scores, that is the the 2-bit
//flags for the directions determining that quad in
//clockwise order.
//So bit runs 0-1, 1-2, 2-3, 3-"4" clockwise (A,B,D,C)
//However, the return is in A,B,C,D to make things easier upstream
int n = (fourBitNeighbors << 4) | fourBitNeighbors; //extend one copy to wrap easier
return new int[]
{
(n & 0x3), //A
( (n>>1) & 0x3), //B
( (n>>3) & 0x3), //C
( (n>>2) & 0x3) //D
};
}
So now for each neighbor code, we can find out which edge scores it is asking for and which letters. But we still need to map out the input tile format; code is provided below with the necessary constants. Note some of your integrations will look different than mine but this should convey the point:
private static readonly Dictionary QuarterTileLookup = new Dictionary()
{
//Put a key for each tile by what quadrant A-D it is
//and the edge score
{ 0xA0, 0 }, { 0xB2, 1 }, { 0xA1, 2 }, { 0xB0, 3 },
{ 0xC1, 4 }, { 0xD3, 5 }, { 0xC3, 6 },{ 0xD2, 7 },
{ 0xA2, 8 }, { 0xB3, 9 }, { 0xA3, 10}, { 0xB1, 11},
{ 0xC0, 12 },{ 0xD1, 13}, { 0xC2, 14 },{ 0xD0, 15}
};
private static int[] GetAtlasQuarterTilesForNeighborMask(int fourBitNeighbors)
{
//Each tile in the atlas is composed of 4 quarter tiles,
//call them by quadrant:
// A B
// C D
//The QuarterTileLookup matches the requested quadrant and edge score
//to the quarter tile index inside the AutoTile texture, numbering like this
// 0 1 2 3
// 4 5 6 7
// 8 9 10 11
// 12 13 14 15
var e = FourBitAutoTileHelper.GetEdgeScores((byte)fourBitNeighbors);
return new int[]
{
QuarterTileLookup[0xA0 + e[0]],
QuarterTileLookup[0xB0 + e[1]],
QuarterTileLookup[0xC0 + e[2]],
QuarterTileLookup[0xD0 + e[3]]
};
}
public StaticTile[] GetTile(int neighbors, int frameIndex)
{
var key = FourBitAutoTileHelper.GetFourBitNeighbors((byte)neighbors);
var quarterTiles = GetAtlasQuarterTilesForNeighborMask(key);
var result = new StaticTile[4];
for (int i = 0; i < 4; i++)
{
int qIndex = quarterTiles[i];
var qTop = qIndex / 4;
var qLeft = (frameIndex * 4) + (qIndex % 4);
result[i] = SourceMap.Get((short)qLeft, (short)qTop);
}
return result;
}
And finally, the full mapping from input to output:
So that's wall autotiles, the simplest of the three. As you can see, there is perhaps more complexity than one would expect in constructing the solution. But constructing the solution from scratch gives us the ability to ensure that the neighbor code and engine formats can remain as consistent as possible across different types of input. Also, much of the code here can be flattened down into lookup tables if desired.
Import - VX-Style Autotiles
At this point, the path to the VX-style autotiles should be much clearer as it builds heavily on the wall autotile methodology. The key difference here is that the VX autotile is capable of corners as well as edges. The "edge scores" are replaced by 3 bit numbers that represent the edges and the corner instead. Other than that, the solution remains the same. Conveniently, the each solution is still unique given the letter and number keys.
The input format is a 4x6 series of quarter tiles. The quarter tiles are 16
pixels. The input can be overlaid with A, B, C, D as described previously. The key difference here is that the upper left quad is completely unused for the end autotile but provides a preview image for the autotile. That's a pretty potent 64x96 pixel patch to have both the information and a preview!
X X A B
X X C D
A B A B
C D C D
A B A B
C D C D
The code:
private static readonly Dictionary VXQuarterTileLookup = new Dictionary()
{
//Put a key for each tile by what quadrant A-D it is
//and the "corner" score (see below)
{ 0xA5, 2 }, { 0xB5, 3 },
{ 0xC5, 6 }, { 0xD5, 7 },
{ 0xA0, 8 }, { 0xB4, 9 }, { 0xA1, 10}, { 0xB0, 11},
{ 0xC1, 12 },{ 0xD7, 13}, { 0xC7, 14 },{ 0xD4, 15},
{ 0xA4, 16}, { 0xB7, 17}, { 0xA7, 18}, { 0xB1, 19},
{ 0xC0, 20 },{ 0xD1, 21}, { 0xC4, 22 },{ 0xD0, 23}
};
private static int[] GetAtlasQuarterTilesForNeighborMask(int neighbors)
{
//Each tile in the atlas is composed of 4 quarter tiles,
//call them by quadrant:
// A B
// C D
//The VXQuarterTileLookup matches the requested quadrant and corner score
//to the quarter tile index inside the VX AutoTile texture, numbering like this
// 0 1 2 3
// 4 5 6 7
// 8 9 10 11
// 12 13 14 15
// 16 17 18 19
// 20 21 22 23
//Where 0,1,4,5 are not used, 2,3,6,7 are the "270 degree" tiles
//and 8-23 are the main pattern
var c = EightBitAutoTileHelper.GetCornerScores(neighbors);
return new int[]
{
VXQuarterTileLookup[0xA0 + c[0]],
VXQuarterTileLookup[0xB0 + c[1]],
VXQuarterTileLookup[0xC0 + c[2]],
VXQuarterTileLookup[0xD0 + c[3]]
};
}
public StaticTile[] GetTile(int neighbors, int frameIndex)
{
var key = EightBitAutoTileHelper.FilterNeighbors((byte)neighbors);
var vxQuarterTiles = GetAtlasQuarterTilesForNeighborMask(key);
var result = new StaticTile[4];
for (int i = 0; i < 4; i++)
{
int vxQIndex = vxQuarterTiles[i];
var vxQTop = vxQIndex / 4;
var vxQLeft = (frameIndex * 4) + (vxQIndex % 4);
result[i] = SourceMap.Get((short)vxQLeft, (short)vxQTop);
}
return result;
}
The full mapping from input to output:
Import - XP/Chipset-style Autotiles
CORRECTION! I haven't had a chance to update the description below but it - and the pictures - are flawed! Basically the problem is that edges aren't all the same, you need to split into vertical and horizontal to break certains ties. Additionally, the "quad type" code needs to be corrected. Good news: the code IS fixed so look there.
The format here is a little more complicated.
First, there are more tiles. This format is 6x8 q-tiles.
Here, letters and corner scores are not enough to provide a unique solution, so we supplement it by also adding a "type" of corner (c), edge (e) or fill (f). This allows us to rank the multiple solutions that exist by their fit based on type.
X X X X Ac Bc
X X X X Cc Dc
Ac Bc Ae Be Ac Bc
Cc Dc Ce De Cc Dc
Ae Be Af Bf Ae Be
Ce De Cf Df Ce De
Ac Bc Ae Be Ac Bc
Cc Dc Ce De Cc Dc
Additionally, the q-tiles can 16 pixels wide (XP) or 8 pixels wide (chipset).
This
format seems to have predated the VX style (or at least chipsets and XP
came before VX), so was the move simply to make the programming easier?
What advantages did this older style have? Well, it appears that you
can achieve much better corner detail by having dedicated corner blocks. The RPG
Maker forums seem to have discussed this at length.
The corner scores are assigned in the same way as the VX autotiles, but the logic for choosing now becomes a little more complex as it takes the type into account.
The code:
//Similar to the VX version BUT now there can be multiple solutions to a given tile
//This is handled by preferring "in 4 tile" solution as a tie breaker
//The index into the tile map for the q-tile is just implicit
//An additional quadrants "type" marker is specified for corner, edge (horizontal), edge (vertical), or fill ("c,e,b,f")
//This allows for solution uniqueness further on with the exception
//of the odd ball "5" series, which is an exception
private static readonly List<int> QuarterTileLookup = new List<int>()
{
0x000, 0x000, 0x000, 0x000, 0xA5c, 0xB5c,
0x000, 0x000, 0x000, 0x000, 0xC5c, 0xD5c,
0xA0c, 0xB4c, 0xA1e, 0xB4e, 0xA1c, 0xB0c,
0xC1c, 0xD7c, 0xC7e, 0xD7e, 0xC7c, 0xD4c,
0xA4b, 0xB7b, 0xA7f, 0xB7f, 0xA7b, 0xB1b,
0xC1b, 0xD7b, 0xC7f, 0xD7f, 0xC7b, 0xD4b,
0xA4c, 0xB7c, 0xA7e, 0xB7e, 0xA7c, 0xB1c,
0xC0c, 0xD1c, 0xC4e, 0xD1e, 0xC4c, 0xD0c
};
private static int[] GetAtlasQuarterTilesForNeighborMask(int neighbors)
{
//By removing the middle, we have exactly one or two solutions
//for any given q-tile AND we are guaranteed that at least
//one q-tile in the four has a unique solution to help disambiguate
var c = EightBitAutoTileHelper.GetCornerScores(neighbors);
var qt = QuadType(neighbors);
return new int[]
{
Find(0xA, c[0], qt),
Find(0xB, c[1], qt),
Find(0xC, c[2], qt),
Find(0xD, c[3], qt)
};
}
private static int Find(int quadrant, int corner, int quadType)
{
if (corner == 5)
quadType = 0x00c; //could be c or e, we just pick c
int quadrantPlusCornerScorePlusType = (quadrant << 8) | (corner << 4) | (quadType);
for (int i = 0; i < QuarterTileLookup.Count; i++)
if (QuarterTileLookup[i] == quadrantPlusCornerScorePlusType)
return i;
throw new InvalidOperationException("Could not find solution for " + quadrantPlusCornerScorePlusType);
}
private const int West = 0x01;
private const int North = 0x04;
private const int East = 0x10;
private const int South = 0x40;
private const int Cardinals = 0x55;
private static int QuadType(int neighbors)
{
if ((neighbors & Cardinals) == Cardinals)
return 0x00f;
bool w = (neighbors & West) > 0;
bool e = (neighbors & East) > 0;
bool n = (neighbors & North) > 0;
bool s = (neighbors & South) > 0;
if (w && e && (n || s)) return 0x00e;
if (n && s && (w || e)) return 0x00b;
return 0x00c;
}
public StaticTile[] GetTile(int neighbors, int frameIndex)
{
var tileIndex = EightBitAutoTileHelper.GetTileIndex(neighbors);
var tileTop = tileIndex / 8;
var tileLeft = frameIndex * 8 + (tileIndex % 8);
return new StaticTile[] { SourceMap.Get((short)tileLeft,(short)tileTop) };
}
The final mapping from input to output:
Conclusion and Final Source
So that about covers it! Hopefully you too can now incorporate autotiles into your next RPG engine project.
Unfortunately a number of conclusions here were pieced together from multiple sources and/or worked out myself so there are likely some bugs; so far it seems to be working out well in my game though so I wanted to share my findings.
Because of the methodology we used here, it should be entirely feasible to incorporate new types of autotiles into the mix as long as they 1) have 16-pixel q-tiles and 2) only depend on immediate neighbors. I imagine that one extension one might need in the future is a mapping from someone else's 47 tile blob palette ordering to the one chosen here - hopefully that type of extension is entirely possible without changing the interfaces etc.
Regarding the final source listing - the source is part of a large project, so I'll try to include the important bits of code.
IAutoTile is the main interface and accepts the raw neighbor code and returns the q-tiles in a row-major array of 2x2. The "frameIndex" parameter is to allow for animated autotiles and indicates which horizontally tiled "frame" to pull from. StaticTiles are basically pointers to sprites that are q-tiles, and IStaticTileMap is basically a 2D array of StaticTiles. The underlying graphics library is SFML with a few of my own extensions. One quirk here exists around the ChipsetAutoTile. Because its q-tiles are 8 pixels and my StaticTiles are fixed at 16 pixels, there is a CreateTexture that creates the full map for later use; other autotile types don't need this because they directly pull q-tiles from the source bitmaps. Good luck!
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using SFML.Graphics;
namespace sharper_core.engine.tile
{
public interface IAutoTile : IDisposable
{
StaticTile[] GetTile(int neighbors, int frameIndex);
int TileSize { get; }
int FrameCount { get; }
int FrameMillis { get; }
IStaticTileMap GetPreview();
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using SFML.Graphics;
using System.Diagnostics;
namespace sharper_core.engine.tile
{
//This class has utilities and sets standards for the traditional "47-tile" 8-bit auto tiles
//The conventions chosen here:
//-The output is an 8x6 map of "tileSize" tiles
//-The "neighbors" value is chosen to be the sum of the directions starting at "West"
//and going clockwise ending in "SW" e.g. "West"=1, "NW" = 2, etc.
//-Corners are disregarded in calculations unless the two neighboring cardinal directions
//are also set.
//
//These are common conventions in the industry and we will map to them for 8-bit calculations
public static class EightBitAutoTileHelper
{
public static readonly Dictionary NeighborsToAtlasIndex = CreateNeighborsToAtlasIndex();
public static Dictionary CreateNeighborsToAtlasIndex()
{
//Very simple - just go through all 256 neighbor combos and find the valid
//ones, incrementing as we go.
//By convention, we will say the LSB -> MSB represents clockwise rotation
//with the LSB being the left spoke "west"
var result = new Dictionary();
int tileIndex = 0;
for (int i = 0; i < 256; i++)
{
var cornerScores = GetCornerScores(i);
bool isValid = true;
for (int j = 0; j < 4 && isValid; j++)
isValid = IsValidCornerScore(cornerScores[j]);
if (isValid)
{
result.Add(i, tileIndex);
Debug.WriteLine("47: " + i + "->" + tileIndex);
tileIndex++;
}
}
return result; //Should be 47
}
public static int[] GetCornerScores(int neighborBits)
{
//Returns an array of "corner" scores, that is the the 3-bit
//flags for the directions determining that quad in
//clockwise order.
//So bit runs 0-2, 2-4, 4-6, 6-"8" clockwise (A,B,D,C)
//However, the return is in A,B,C,D to make things easier upstream
int n = (neighborBits << 8) | neighborBits; //extend one copy to wrap easier
return new int[]
{
(n & 0x7), //A
( (n>>2) & 0x7), //B
( (n>>6) & 0x7), //C
( (n>>4) & 0x7) //D
};
}
private static bool IsValidCornerScore(int score)
{
//Bit 0 is a cardinal direction, 1 is the corner, 2 is the next cardinal direction
//So the corner cannot be on unless both cardinals are on. While this could be
//done bit-masky, we just statically rule out 110, 011, 010
return (score != 6 && score != 3 && score != 2);
}
private static byte NorthAndWest = 0x05; //-----N-W
private static byte EastAndNorth = 0x14; //---E-N--
private static byte SouthAndEast = 0x50; //-S-E----
private static byte WestAndSouth = 0x41; //-S-----W
private static byte CornerNWMask = 0xFD; //Not ------C-
private static byte CornerNEMask = 0xF7; //Not ----C---
private static byte CornerSEMask = 0xDF; //Not --C-----
private static byte CornerSWMask = 0x7F; //Not C-------
//Note, uses tileSize instead of qSize
public static IntRect GetTile(int neighbors, int tileSize, int frameIndex)
{
//First, filter the neighbors of invalidly set corners
byte filtered = FilterNeighbors((byte)neighbors);
//Then get the index into the 47-tile set
int tileIndex = NeighborsToAtlasIndex[filtered];
int row = tileIndex / 8;
int col = tileIndex % 8;
return new IntRect(tileSize * (col+frameIndex*8), tileSize * row, tileSize, tileSize);
}
public static int GetTileIndex(int neighbors)
{
//First, filter the neighbors of invalidly set corners
byte filtered = FilterNeighbors((byte)neighbors);
//Then get the index into the 47-tile set
return NeighborsToAtlasIndex[filtered];
}
public static byte FilterNeighbors(byte neighbors)
{
//One way this could be done is to get each corner score and ensure that if the
//middle bit is set, then the other two are as well or don't count it
//Then reassemble the corner scores.
//However, that involves allocating an array at runtime, so we'll do a similar trick
//with bit masking
//So, we have West = 0, NW = 1, etc. clockwise around.
//We basically want to check that e.g. NW is masked out if W/N aren't set.
//So we can simply mask out the four corners if the relevant cardinals aren't set unconditionally.
if ((neighbors & NorthAndWest) != NorthAndWest)
neighbors &= CornerNWMask;
if ((neighbors & EastAndNorth) != EastAndNorth)
neighbors &= CornerNEMask;
if ((neighbors & SouthAndEast) != SouthAndEast)
neighbors &= CornerSEMask;
if ((neighbors & WestAndSouth) != WestAndSouth)
neighbors &= CornerSWMask;
return neighbors;
}
public static void SaveMap(IAutoTile t, IStaticTileProvider provider, string filename)
{
var neighborsInOrder = NeighborsToAtlasIndex.Keys.OrderBy(k => k).ToList();
using (var render = new RenderTexture(StaticTile.Size * 2 * 8, StaticTile.Size * 2 * 6))
{
render.Clear(SFML.Graphics.Color.Black);
for (int n = 0; n < neighborsInOrder.Count; n++)
{
var tiles = t.GetTile(neighborsInOrder[n], 0);
var c = n % 8;
var r = n / 8;
for (int x = 0; x < 2; x++)
{
for (int y = 0; y < 2; y++)
{
var myX = c * StaticTile.Size * 2 + x*StaticTile.Size;
var myY = r * StaticTile.Size * 2 + y*StaticTile.Size;
var qTile = tiles[y * 2 + x];
var states = RenderStates.Default;
states.Transform.Translate(myX, myY);
provider.Render(render, states, qTile);
}
}
}
render.Display();
using (var image = render.Texture.CopyToImage())
{
image.SaveToFile(filename);
}
}
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using SFML.Graphics;
namespace sharper_core.engine.tile
{
//Keeps the same "neighbors" calculation convention as the 8-bit version,
//but this one only regards the four cardinal directions
//Uses a 4-by-4 tileset that starts with tile index 0 being no neighbors,
//tile index 1 being only a western neighbor, etc.
public static class FourBitAutoTileHelper
{
private const byte Cardinals = 0x55; //-S-E-N-W
private const byte West = 0x01;
private const byte North = 0x04;
private const byte East = 0x10;
private const byte South = 0x40;
private const byte WestFour = 0x01;
private const byte NorthFour = 0x02;
private const byte EastFour = 0x04;
private const byte SouthFour = 0x08;
public static IntRect GetTile(int neighbors, int tileSize, int frameIndex)
{
byte n = (byte)neighbors;
byte filtered = GetFourBitNeighbors(n);
int row = filtered / 4;
int col = filtered % 4;
return new IntRect((col+4*frameIndex) * tileSize, row * tileSize, tileSize, tileSize);
}
//Converts 8 bit format to 4 bit.
public static byte GetFourBitNeighbors(byte n)
{
byte filtered = 0;
if ((n & West) > 0) filtered |= WestFour;
if ((n & North) > 0) filtered |= NorthFour;
if ((n & East) > 0) filtered |= EastFour;
if ((n & South) > 0) filtered |= SouthFour;
return filtered;
}
public static int[] GetEdgeScores(byte fourBitNeighbors)
{
//Returns an array of "edge" scores, that is the the 2-bit
//flags for the directions determining that quad in
//clockwise order.
//So bit runs 0-1, 1-2, 2-3, 3-"4" clockwise (A,B,D,C)
//However, the return is in A,B,C,D to make things easier upstream
int n = (fourBitNeighbors << 4) | fourBitNeighbors; //extend one copy to wrap easier
return new int[]
{
(n & 0x3), //A
( (n>>1) & 0x3), //B
( (n>>3) & 0x3), //C
( (n>>2) & 0x3) //D
};
}
public static void SaveMap(IAutoTile t, IStaticTileProvider provider, string filename)
{
using (var render = new RenderTexture(StaticTile.Size * 2 * 4, StaticTile.Size * 2 * 4))
{
render.Clear(SFML.Graphics.Color.Black);
for (int n = 0; n < 16; n++)
{
var tiles = t.GetTile(n, 0);
var c = n % 4;
var r = n / 4;
for (int x = 0; x < 2; x++)
{
for (int y = 0; y < 2; y++)
{
var myX = c * StaticTile.Size * 2 + x * StaticTile.Size;
var myY = r * StaticTile.Size * 2 + y * StaticTile.Size;
var qTile = tiles[y * 2 + x];
var states = RenderStates.Default;
states.Transform.Translate(myX, myY);
provider.Render(render, states, qTile);
}
}
}
render.Display();
using (var image = render.Texture.CopyToImage())
{
image.SaveToFile(filename);
}
}
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using SFML.Graphics;
namespace sharper_core.engine.tile
{
public class SerFourBitAutoTile
{
public UInt32 StaticTileMapId { get; set; }
}
public class FourBitAutoTile : IAutoTile
{
//qSize = quarter tile size
//At the moment I don't know of formats other than the usual 16-quarter tile one
//and I don't know that format is really RPG Maker specific; I think it predates it.
private static readonly Dictionary QuarterTileLookup = new Dictionary()
{
//Put a key for each tile by what quadrant A-D it is
//and the edge score
{ 0xA0, 0 }, { 0xB2, 1 }, { 0xA1, 2 }, { 0xB0, 3 },
{ 0xC1, 4 }, { 0xD3, 5 }, { 0xC3, 6 },{ 0xD2, 7 },
{ 0xA2, 8 }, { 0xB3, 9 }, { 0xA3, 10}, { 0xB1, 11},
{ 0xC0, 12 },{ 0xD1, 13}, { 0xC2, 14 },{ 0xD0, 15}
};
private static int[] GetAtlasQuarterTilesForNeighborMask(int fourBitNeighbors)
{
//Each tile in the atlas is composed of 4 quarter tiles,
//call them by quadrant:
// A B
// C D
//The QuarterTileLookup matches the requested quadrant and edge score
//to the quarter tile index inside the VX AutoTile texture, numbering like this
// 0 1 2 3
// 4 5 6 7
// 8 9 10 11
// 12 13 14 15
var e = FourBitAutoTileHelper.GetEdgeScores((byte)fourBitNeighbors);
return new int[]
{
QuarterTileLookup[0xA0 + e[0]],
QuarterTileLookup[0xB0 + e[1]],
QuarterTileLookup[0xC0 + e[2]],
QuarterTileLookup[0xD0 + e[3]]
};
}
public StaticTile[] GetTile(int neighbors, int frameIndex)
{
var key = FourBitAutoTileHelper.GetFourBitNeighbors((byte)neighbors);
var quarterTiles = GetAtlasQuarterTilesForNeighborMask(key);
var result = new StaticTile[4];
for (int i = 0; i < 4; i++)
{
int qIndex = quarterTiles[i];
var qTop = qIndex / 4;
var qLeft = (frameIndex * 4) + (qIndex % 4);
result[i] = SourceMap.Get((short)qLeft, (short)qTop);
}
return result;
}
public int TileSize { get; private set; }
public int FrameCount { get; private set; }
public int FrameMillis { get; private set; }
public IStaticTileMap SourceMap { get; private set; }
public static FourBitAutoTile Create(IStaticTileMap autoTile, int frameMillis = 500)
{
int frameCount = (int)(autoTile.Bounds.Width/4);
return new FourBitAutoTile(autoTile, frameCount, frameMillis);
}
private FourBitAutoTile(IStaticTileMap sourceMap, int frameCount, int frameMillis)
{
SourceMap = sourceMap;
FrameCount = frameCount;
FrameMillis = frameMillis;
TileSize = 32;
}
public void Dispose()
{
}
public IStaticTileMap GetPreview()
{
return new ViewStaticTileMap(SourceMap, new IntRect(0, 0, 4, 4));
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using SFML.Graphics;
namespace sharper_core.engine.tile
{
public class SerVXAutoTile
{
public UInt32 StaticTileMapId { get; set; }
public int FrameMillis { get; set; }
}
public class VXAutoTile : IAutoTile
{
private static readonly Dictionary VXQuarterTileLookup = new Dictionary()
{
//Put a key for each tile by what quadrant A-D it is
//and the "corner" score (see below)
{ 0xA5, 2 }, { 0xB5, 3 },
{ 0xC5, 6 }, { 0xD5, 7 },
{ 0xA0, 8 }, { 0xB4, 9 }, { 0xA1, 10}, { 0xB0, 11},
{ 0xC1, 12 },{ 0xD7, 13}, { 0xC7, 14 },{ 0xD4, 15},
{ 0xA4, 16}, { 0xB7, 17}, { 0xA7, 18}, { 0xB1, 19},
{ 0xC0, 20 },{ 0xD1, 21}, { 0xC4, 22 },{ 0xD0, 23}
};
private static int[] GetAtlasQuarterTilesForNeighborMask(int neighbors)
{
//Each tile in the atlas is composed of 4 quarter tiles,
//call them by quadrant:
// A B
// C D
//The VXQuarterTileLookup matches the requested quadrant and corner score
//to the quarter tile index inside the VX AutoTile texture, numbering like this
// 0 1 2 3
// 4 5 6 7
// 8 9 10 11
// 12 13 14 15
// 16 17 18 19
// 20 21 22 23
//Where 0,1,4,5 are not used, 2,3,6,7 are the "270 degree" tiles
//and 8-23 are the main pattern
var c = EightBitAutoTileHelper.GetCornerScores(neighbors);
return new int[]
{
VXQuarterTileLookup[0xA0 + c[0]],
VXQuarterTileLookup[0xB0 + c[1]],
VXQuarterTileLookup[0xC0 + c[2]],
VXQuarterTileLookup[0xD0 + c[3]]
};
}
public StaticTile[] GetTile(int neighbors, int frameIndex)
{
var key = EightBitAutoTileHelper.FilterNeighbors((byte)neighbors);
var vxQuarterTiles = GetAtlasQuarterTilesForNeighborMask(key);
var result = new StaticTile[4];
for (int i = 0; i < 4; i++)
{
int vxQIndex = vxQuarterTiles[i];
var vxQTop = vxQIndex / 4;
var vxQLeft = (frameIndex * 4) + (vxQIndex % 4);
result[i] = SourceMap.Get((short)vxQLeft, (short)vxQTop);
}
return result;
}
public int TileSize { get; private set; }
public int FrameCount { get; private set; }
public int FrameMillis { get; private set; }
public IStaticTileMap SourceMap { get; private set; }
public static VXAutoTile Create(IStaticTileMap vxAutoTile, int frameMillis = 1600)
{
int frameCount = (int)(vxAutoTile.Bounds.Width / 4);
return new VXAutoTile(vxAutoTile, frameCount, frameMillis);
}
private VXAutoTile(IStaticTileMap sourceMap, int frameCount, int frameMillis = 500)
{
SourceMap = sourceMap;
FrameCount = frameCount;
FrameMillis = frameMillis;
TileSize = 32;
}
public void Dispose() { }
public IStaticTileMap GetPreview()
{
return new ViewStaticTileMap(SourceMap, new IntRect(0, 0, 2, 2));
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using SFML.Graphics;
using sharper_core.engine.tile.tilemaps;
using sharper_core.engine.tile.providers;
namespace sharper_core.engine.tile.autotile
{
public class SerXPAutoTile
{
public UInt32 StaticTileMapId { get; set; }
public int FrameMillis { get; set; }
}
public class XPAutoTile : IAutoTile
{
private const int QTileSize = 16;
//Similar to the VX version BUT now there can be multiple solutions to a given tile
//This is handled by preferring "in 4 tile" solution as a tie breaker
//The index into the tile map for the q-tile is just implicit
//An additional quadrants "type" marker is specified for corner, edge (horizontal), edge (vertical), or fill ("c,e,b,f")
//This allows for solution uniqueness further on with the exception
//of the odd ball "5" series, which is an exception
private static readonly List<int> QuarterTileLookup = new List<int>()
{
0x000, 0x000, 0x000, 0x000, 0xA5c, 0xB5c,
0x000, 0x000, 0x000, 0x000, 0xC5c, 0xD5c,
0xA0c, 0xB4c, 0xA1e, 0xB4e, 0xA1c, 0xB0c,
0xC1c, 0xD7c, 0xC7e, 0xD7e, 0xC7c, 0xD4c,
0xA4b, 0xB7b, 0xA7f, 0xB7f, 0xA7b, 0xB1b,
0xC1b, 0xD7b, 0xC7f, 0xD7f, 0xC7b, 0xD4b,
0xA4c, 0xB7c, 0xA7e, 0xB7e, 0xA7c, 0xB1c,
0xC0c, 0xD1c, 0xC4e, 0xD1e, 0xC4c, 0xD0c
};
private static int[] GetAtlasQuarterTilesForNeighborMask(int neighbors)
{
//By removing the middle, we have exactly one or two solutions
//for any given q-tile AND we are guaranteed that at least
//one q-tile in the four has a unique solution to help disambiguate
var c = EightBitAutoTileHelper.GetCornerScores(neighbors);
var qt = QuadType(neighbors);
return new int[]
{
Find(0xA, c[0], qt),
Find(0xB, c[1], qt),
Find(0xC, c[2], qt),
Find(0xD, c[3], qt)
};
}
private static int Find(int quadrant, int corner, int quadType)
{
if (corner == 5)
quadType = 0x00c; //could be c or e, we just pick c
int quadrantPlusCornerScorePlusType = (quadrant << 8) | (corner << 4) | (quadType);
for (int i = 0; i < QuarterTileLookup.Count; i++)
if (QuarterTileLookup[i] == quadrantPlusCornerScorePlusType)
return i;
throw new InvalidOperationException("Could not find solution for " + quadrantPlusCornerScorePlusType);
}
private const int West = 0x01;
private const int North = 0x04;
private const int East = 0x10;
private const int South = 0x40;
private const int Cardinals = 0x55;
private static int QuadType(int neighbors)
{
if ((neighbors & Cardinals) == Cardinals)
return 0x00f;
bool w = (neighbors & West) > 0;
bool e = (neighbors & East) > 0;
bool n = (neighbors & North) > 0;
bool s = (neighbors & South) > 0;
if (w && e && (n || s)) return 0x00e;
if (n && s && (w || e)) return 0x00b;
return 0x00c;
}
//This is used internally, and is handy for any situation where quarter tiles are used
//to compose the final atlas
public static void Copy(int frame, int qSize, Texture xpSrc, int xpQIndex, RenderTarget tileDest, RenderStates tileStates, int tileIndex, int tileQIndex)
{
//Copy the quarter tile from the XP/chipset texture to the specified tile atlas' tile index and quarter tile index within
var xpQTop = xpQIndex / 6;
var xpQLeft = (frame * 6) + (xpQIndex % 6);
var vxSprite = new Sprite(xpSrc, new IntRect(xpQLeft * qSize, xpQTop * qSize, qSize, qSize));
var tileQTop = (tileIndex / 8) * 2 + (tileQIndex / 2);
var tileQLeft = (frame * 8 * 2) + (tileIndex % 8) * 2 + (tileQIndex % 2);
tileStates.Transform.Translate(tileQLeft * qSize, tileQTop * qSize);
tileDest.Draw(vxSprite, tileStates);
}
public StaticTile[] GetTile(int neighbors, int frameIndex)
{
var key = EightBitAutoTileHelper.FilterNeighbors((byte)neighbors);
var xpQuarterTiles = GetAtlasQuarterTilesForNeighborMask(key);
var result = new StaticTile[4];
for (int i = 0; i < 4; i++)
{
int xpQIndex = xpQuarterTiles[i];
var xpQTop = xpQIndex / 6;
var xpQLeft = (frameIndex * 6) + (xpQIndex % 6);
result[i] = SourceMap.Get((short)xpQLeft, (short)xpQTop);
}
return result;
}
public int TileSize { get; private set; }
public int FrameCount { get; private set; }
public int FrameMillis { get; private set; }
public IStaticTileMap SourceMap { get; private set; }
public static XPAutoTile Create(IStaticTileMap sourceMap, int frameMillis = 1000)
{
//Note the change to div/8 for frame count - this is because we are in full
//8x6 tile mode now
int frameCount = (int)(sourceMap.Bounds.Width / 6);
return new XPAutoTile(sourceMap, frameCount, frameMillis);
}
private XPAutoTile(IStaticTileMap sourceMap, int frameCount, int frameMillis)
{
SourceMap = sourceMap;
FrameCount = frameCount;
FrameMillis = frameMillis;
TileSize = 32;
}
public void Dispose()
{
}
public IStaticTileMap GetPreview()
{
return new ViewStaticTileMap(SourceMap, new IntRect(0, 0, 2, 2));
}
}
}
References
Blob Tileset
Anatomy of an Autotile
RPG Maker XP vs. VX Autotiles
Discussion of Superiority of XP Autotiles vx. VX (see Felix Trapper's illustrations several posts in)
