Map Tiling Algorithm

Question

The basic idea of this algorithm is to use a pre-processing step to find all edges and then select the correct smoothing tile according to the shape of the edge.

The first step would be to find all edges. In the example below the edge tiles marked with an X are all green tiles with a tan tile as one or more of their eight neighbouring tiles. With different types of terrain this condition could translate to a tile being an edge tile if it has neighbours of lower terrain-number.

Once all edge tiles are detected the next thing to do is to select the right smoothing tile for each edge tile. Here is my representation of your smoothing tiles.

Note that there are actually not that many different types of tiles. We need the eight outer tiles from one of the 3x3 squares but only the four corner squares from the other since the straight-edge tiles are already found in the first square. This means that there in total are 12 different cases we must distinguish between.

Now, looking at one edge tile we can determine which way the boundary turns by looking at its four closest neighbour tiles. Marking an edge tile with X just as above we have the following six different cases.

These cases are used to determine the corresponding smoothing tile and we can number the smoothing tiles accordingly.

There is still a choice of a or b for each case. This depends on which side the grass is on. One way to determine this could be to keep track of the orientation of the boundary but probably the simplest way to do it is to pick one tile next to the edge and see what colour it has. The image below shows the two cases 5a) and 5b) which can be distinguished between by for example checking the colour of the top right tile.

The final enumeration for the original example would then look like this.

And after selecting the corresponding edge tile the border would look something like this.

As a final note I might say that this would work as long as the boundary is somewhat regular. More precisely, edge tiles that do not have exactly two edge tiles as their neighbours will have to be treated separately. This will occur for edge tiles on the edge of the map which will have a single edge neighbour and for very narrow pieces of terrain where the number of neighbouring edge tiles could be three or even four.

The following square represents a metal plate. There is a "heat vent" by the top right corner. We can see how as the temperature of this point remains constant, the metal plate converges to a constant temperature at each point, being naturally hotter near the top:

The problem of finding the temperature at each point can be solved as a "Boundary value problem". However the simplest way to work out the heat at each point is to model the plate as a grid. We know the points on the grid at constant temperature. We set the temperature of all unknown points to be room temperature (as if the vent had only just been turned on). We then let the heat spread through the plate until we reach convergence. This is done by iteration: we iterate through each (i,j) point. We set point(i,j) = (point(i+1, j)+point(i-1,j)+point(i, j+1)+point(i,j-1))/4 [unless point(i,j) has a heat vent of constant temperature]

If you apply this to your problem, it is very similar, just average colors instead of temperatures. You would probably need about 5 iterations. I suggest using a 400x400 grid. Thats 400x400x5 = less than 1 million iterations which will be fast. If you only use 5 iterations you probably won't need to worry about holding any points constant color, as they wont shift too much from their original (in fact only points within distance 5 from the color can be effected by the color). Pseudo code:

iterations = 5
for iteration in range(iterations):
    for i in range(400):
        for j in range(400):
            try:
                grid[i][j] = average(grid[i+1][j], grid[i-1][j],
                                     grid[i][j+1], grid[i][j+1])
            except IndexError:
                pass

Ok, so first thoughts are that automating a perfect solution to the problem requires some rather meaty interpolation maths. Based on the fact that you mention pre-rendered tile images, I assume that the full interpolation solution is not warranted here.

On the other hand as you said, finishing off the map by hand will lead to a good result... but I also assume that any manual process to fix glitches is also not an option.

Here's a simple algorithm that does not give a perfect result, but that is very rewarding based on the low effort it takes.

Instead of trying to blend EVERY edge tile, (which means that you need to either know the result of blending the adjacent tiles first - interpolation, or you need to refine the whole map several times and can't rely on pre-generated tiles) why not blend tiles in a alternating checker-board pattern?

[1] [*] [2]
[*] [1] [*]
[1] [*] [2]

I.e. only blending the tiles starred in the matrix above?

Assuming that the only permitted steps in value are one-at-a-time, you only have a few tiles to design...

A    [1]      B    [2]      C    [1]      D    [2]      E    [1]           
 [1] [*] [1]   [1] [*] [1]   [1] [*] [2]   [1] [*] [2]   [1] [*] [1]   etc.
     [1]           [1]           [1]           [1]           [2]           

There will be 16 patterns in total. If you take advantage of rotational and reflectional symmetry there will be even fewer.

'A' would be a plain [1] style tile. 'D' would be a diagonal.

There will be small discontinuities at the corners of the tiles, but these will be minor compared to the example you gave.

If I can I'll update this post with images later.

I was playing around with something similar to this, it wasn't finished off for a number of reasons; but basically it would take a matrix of 0 and 1, 0 being the ground and 1 being a wall for a maze generator application in Flash. Since AS3 is similar to JavaScript it wouldn't be difficult to rewrite in JS.

var tileDimension:int = 20;
var levelNum:Array = new Array();

levelNum[0] = [1, 1, 1, 1, 1, 1, 1, 1, 1];
levelNum[1] = [1, 0, 0, 0, 0, 0, 0, 0, 1];
levelNum[2] = [1, 0, 1, 1, 1, 0, 1, 0, 1];
levelNum[3] = [1, 0, 1, 0, 1, 0, 1, 0, 1];
levelNum[4] = [1, 0, 1, 0, 0, 0, 1, 0, 1];
levelNum[5] = [1, 0, 0, 0, 0, 0, 0, 0, 1];
levelNum[6] = [1, 0, 1, 1, 1, 1, 0, 0, 1];
levelNum[7] = [1, 0, 0, 0, 0, 0, 0, 0, 1];
levelNum[8] = [1, 1, 1, 1, 1, 1, 1, 1, 1];

for (var rows:int = 0; rows < levelNum.length; rows++)
{
    for (var cols:int = 0; cols < levelNum[rows].length; cols++)
    {
        // set up neighbours
        var toprow:int = rows - 1;
        var bottomrow:int = rows + 1;

        var westN:int = cols - 1;
        var eastN:int = cols + 1;

        var rightMax =  levelNum[rows].length;
        var bottomMax = levelNum.length;

        var northwestTile =     (toprow != -1 && westN != -1) ? levelNum[toprow][westN] : 1;
        var northTile =         (toprow != -1) ? levelNum[toprow][cols] : 1;
        var northeastTile =     (toprow != -1 && eastN < rightMax) ? levelNum[toprow][eastN] : 1;

        var westTile =          (cols != 0) ? levelNum[rows][westN] : 1;
        var thistile =          levelNum[rows][cols];
        var eastTile =          (eastN == rightMax) ? 1 : levelNum[rows][eastN];

        var southwestTile =     (bottomrow != bottomMax && westN != -1) ? levelNum[bottomrow][westN] : 1;
        var southTile =         (bottomrow != bottomMax) ? levelNum[bottomrow][cols] : 1;
        var southeastTile =     (bottomrow != bottomMax && eastN < rightMax) ? levelNum[bottomrow][eastN] : 1;

        if (thistile == 1)
        {
            var w7:Wall7 = new Wall7();
            addChild(w7);
            pushTile(w7, cols, rows, 0);

            // wall 2 corners

            if      (northTile === 0 && northeastTile === 0 && eastTile === 1 && southeastTile === 1 && southTile === 1 && southwestTile === 0 && westTile === 0 && northwestTile === 0)
            {
                var w21:Wall2 = new Wall2();
                addChild(w21);
                pushTile(w21, cols, rows, 270);
            }

            else if (northTile === 0 && northeastTile === 0 && eastTile === 0 && southeastTile === 0 && southTile === 1 && southwestTile === 1 && westTile === 1 && northwestTile === 0)
            {
                var w22:Wall2 = new Wall2();
                addChild(w22);
                pushTile(w22, cols, rows, 0);
            }

            else if (northTile === 1 && northeastTile === 0 && eastTile === 0 && southeastTile === 0 && southTile === 0 && southwestTile === 0 && westTile === 1 && northwestTile === 1)
            {
                var w23:Wall2 = new Wall2();
                addChild(w23);
                pushTile(w23, cols, rows, 90);
            }

            else if (northTile === 1 && northeastTile === 1 && eastTile === 1 && southeastTile === 0 && southTile === 0 && southwestTile === 0 && westTile === 0 && northwestTile === 0)
            {
                var w24:Wall2 = new Wall2();
                addChild(w24);
                pushTile(w24, cols, rows, 180);
            }           

            //  wall 6 corners

            else if (northTile === 1 && northeastTile === 1 && eastTile === 1 && southeastTile === 0 && southTile === 1 && southwestTile === 1 && westTile === 1 && northwestTile === 1)
            {
                var w61:Wall6 = new Wall6();
                addChild(w61);
                pushTile(w61, cols, rows, 0); 
            }

            else if (northTile === 1 && northeastTile === 1 && eastTile === 1 && southeastTile === 1 && southTile === 1 && southwestTile === 0 && westTile === 1 && northwestTile === 1)
            {
                var w62:Wall6 = new Wall6();
                addChild(w62);
                pushTile(w62, cols, rows, 90); 
            }

            else if (northTile === 1 && northeastTile === 1 && eastTile === 1 && southeastTile === 1 && southTile === 1 && southwestTile === 1 && westTile === 1 && northwestTile === 0)
            {
                var w63:Wall6 = new Wall6();
                addChild(w63);
                pushTile(w63, cols, rows, 180);
            }

            else if (northTile === 1 && northeastTile === 0 && eastTile === 1 && southeastTile === 1 && southTile === 1 && southwestTile === 1 && westTile === 1 && northwestTile === 1)
            {
                var w64:Wall6 = new Wall6();
                addChild(w64);
                pushTile(w64, cols, rows, 270);
            }

            //  single wall tile

            else if (northTile === 0 && northeastTile === 0 && eastTile === 0 && southeastTile === 0 && southTile === 0 && southwestTile === 0 && westTile === 0 && northwestTile === 0)
            {
                var w5:Wall5 = new Wall5();
                addChild(w5);
                pushTile(w5, cols, rows, 0);
            }

            //  wall 3 walls

            else if (northTile === 0 && eastTile === 1 && southTile === 0 && westTile === 1)
            {
                var w3:Wall3 = new Wall3();
                addChild(w3);
                pushTile(w3, cols, rows, 0);
            }

            else if (northTile === 1 && eastTile === 0 && southTile === 1 && westTile === 0)
            {
                var w31:Wall3 = new Wall3();
                addChild(w31);
                pushTile(w31, cols, rows, 90);
            }

            //  wall 4 walls

            else if (northTile === 0 && eastTile === 0 && southTile === 1 && westTile === 0)
            {
                var w41:Wall4 = new Wall4();
                addChild(w41);
                pushTile(w41, cols, rows, 0);
            }

            else if (northTile === 1 && eastTile === 0 && southTile === 0 && westTile === 0)
            {
                var w42:Wall4 = new Wall4();
                addChild(w42);
                pushTile(w42, cols, rows, 180);
            }

            else if (northTile === 0 && northeastTile === 0 && eastTile === 1 && southeastTile === 0 && southTile === 0 && southwestTile === 0 && westTile === 0 && northwestTile === 0)
            {
                var w43:Wall4 = new Wall4();
                addChild(w43);
                pushTile(w43, cols, rows, 270);
            }

            else if (northTile === 0 && northeastTile === 0 && eastTile === 0 && southeastTile === 0 && southTile === 0 && southwestTile === 0 && westTile === 1 && northwestTile === 0)
            {
                var w44:Wall4 = new Wall4();
                addChild(w44);
                pushTile(w44, cols, rows, 90);
            }

            //  regular wall blocks

            else if (northTile === 1 && eastTile === 0 && southTile === 1 && westTile === 1)
            {
                var w11:Wall1 = new Wall1();
                addChild(w11);
                pushTile(w11, cols, rows, 90);
            }

            else if (northTile === 1 && eastTile === 1 && southTile === 1 && westTile === 0)
            {
                var w12:Wall1 = new Wall1();
                addChild(w12);
                pushTile(w12, cols, rows, 270);
            }

            else if (northTile === 0 && eastTile === 1 && southTile === 1 && westTile === 1)
            {
                var w13:Wall1 = new Wall1();
                addChild(w13);
                pushTile(w13, cols, rows, 0);
            }

            else if (northTile === 1 && eastTile === 1 && southTile === 0 && westTile === 1)
            {
                var w14:Wall1 = new Wall1();
                addChild(w14);
                pushTile(w14, cols, rows, 180);
            }

        }
        // debug === // trace('Top Left: ' + northwestTile + ' Top Middle: ' + northTile + ' Top Right: ' + northeastTile + ' Middle Left: ' + westTile + ' This: ' + levelNum[rows][cols] + ' Middle Right: ' + eastTile + ' Bottom Left: ' + southwestTile + ' Bottom Middle: ' + southTile + ' Bottom Right: ' + southeastTile);
    }
}

function pushTile(til:Object, tx:uint, ty:uint, degrees:uint):void
{
    til.x = tx * tileDimension;
    til.y = ty * tileDimension;
    if (degrees != 0) tileRotate(til, degrees);
}

function tileRotate(tile:Object, degrees:uint):void
{
    // http://www.flash-db.com/Board/index.php?topic=18625.0
    var midPoint:int = tileDimension/2;
    var point:Point=new Point(tile.x+midPoint, tile.y+midPoint);
    var m:Matrix=tile.transform.matrix;
    m.tx -= point.x;
    m.ty -= point.y;
    m.rotate (degrees*(Math.PI/180));
    m.tx += point.x;
    m.ty += point.y;
    tile.transform.matrix=m;
}

Basically this checks every tile around it going from left to right, top to bottom and assumes that edge tiles are always 1. I've also taken the liberty of exporting the images as a file to use as a key:

This is incomplete and probably a hacky way to achieve this, but I thought it might be of some benefit.

Edit: Screenshot of the result of that code.

I would suggest a few things:

• it doesn't matter what the "center" tile is, right? it could be 2, but if all the others are 1, it would show 1?

• it only matters what the corners are, when there is a difference in the immediate neighbors to the top or side. If all the immediate neighbors are 1, and a corner is 2, it would show 1.

• I would probably precalculate all the possible combinations of neighbors, creating an 8 index array with the first four indicating the values of the top/bottom neighbors, and the second indicating the diagonals:

edges[N][E][S][W][NE][SE][SW][NW] = whatever offset into sprite

so in your case, [2][2][1][1][2][2][1][1] = 4 (the 5th sprite).

in this case, [1][1][1][1] would be 1, [2][2][2][2] would be 2, and the rest would have to be worked out. But the lookup for a particular tile would be trivial.