Random Tile layout

Question

I need to place tiles on a large grid radiating from a central point in a way that looks organic and random. New tiles will need to find an open space on the grid that is touching at least 1 other tile.

Can anyone point me in the right to direction to anything that might help with this? Or some basic concepts I can read up on that are in this vein?

For example, in this picture, there is a shape already created (yellow) and I may be receiving a new tile, that may be 1x1, 2x2, or 3x3. Trying to find a good way to figure out where I can place the new tile so that it will be touching the maximum amount of current tiles.

Picture: alt text http://osomer.com/grid.JPG

Answer 1

Alternatively, you could approach this problem as the yellow tiles "eroding" away at the blue/background. To do this, at every step, have a yellow tile add a fixed number to the "erosion sum" E of all of the background tiles neighboring it in a cardinal direction (and perhaps maybe a fraction of that to the background tiles neighboring it diagonally).

Then, when it comes time to place a new tile, you can, for each background tile, pick a random number from 0 to E; the greatest one is "eroded" away. Alternatively, you could do a simple weighted random choice, with E being their weights.

For 2x2 or 3x3 tiles, you can pick only from tiles that suitably "fit" a 2x2 or 3x3 square in it (that is, a 2x2 or 3x3 the eroded tile on its edge, so that it doesn't cause overlap with already-placed tiles). But really, you're never going to get something looking as natural as one-by-one erosion/tile placement.

You can save time recalculating erosion sums by having them persist with each iteration, only, when you add a new tile, up the erosion sums of the ones around it (a simple +=). At this point, it is essentially the same as another answer suggested, albeit with a different perspective/philosophy.

A sample grid of Erosion Sums E, with direct cardinal neighbors being +4, and diagonal neighbors being +1:

Erosion Sums http://img199.imageshack.us/img199/4766/erosion.png

The ones with a higher E are most likely to be "eroded" away; for example, in this one, the two little inlets on the west and south faces are most likely to be eroded away by the yellow, followed by the smaller bays on the north and east faces. Least likely are the ones barely touching the yellow by one corner. You can decide which one either by assigning a random number from 0 to E for each tile and eroding the one with the highest random number, or doing a simple weighted random selection, or by any decision method of your choice.

Answer 2

For purely random, you start with an empty grid and a "candidate" list (also empty).

Place the first tile in the centre of the grid, then add each adjacent tile to the one you just placed into the "candidate" list. Then, each turn, choose a random entry in the "candidate" list and place a tile there. Look at each adjancent grid location next to where you just placed the tile, and for each one that is also empty, put it on the "candidate" list for the next time around (if not already there).

To avoid creating holes in your tile grid, increase the probability of selecting a grid location based on the number of adjacent tiles that are already filled (so if only one adjacent tile is already filled, it has low probably. If they're all filled, it'll have a very high probability).

In pseudo code:

grid = new array[width,height];
candidates = new list();

function place_tile(x,y) {
   // place the tile at the given location
   grid[x,y] = 1;

   // loop through all the adjacent grid locations around the one
   // we just placed
   for(y1 = y - 1; y1 < y + 1; y1++) {
       for(x1 = x - 1; x1 < x + 1; x1++) {
           // if this location doesn't have a tile and isn't already in
           // the candidate list, add it
           if (grid[x,y] != 1 && !candidates.contains(x1,y1)) {
               candidates.add(x1,y1);
           }
       }
   }
}

// place the first tile in the centre
place_tile(width/2, height/2);

while (!finished) {
   // choose a random tile from the candidate list
   int index = rand(0, candidates.length - 1);

   // place a tile at that location (remove the entry from
   // the candidate list)
   x, y = candidates[index];
   candidates.remove(index);
   place_tile(x, y);
}

Answer 3

The problem with your question is that 'organic and random' can be many different things. Let me show two links

• generating random fractal terrain (look at section 'Cloudy Skies' and imagine that you turn it to b/w, or in your case yellow/background).
• simulating erosion (look at the image under 'erode')

The two above samples are 'organic and random' to me, but you might not be satisfied with those. So, I think you will have to better define what is 'organic and random'.

For now, I'll take your definition of the guiding rule for adding new tiles (but don't think it is necessarily the same problem), which I read as:

Given two shapes (assuming bitmaps) find the relative position of the shapes such that the number of touching sides is maximum

I will also assume

• overlap is not allowed
• you can leave holes inside the resulting, merged shape
• you can not rotate shapes

Under such conditions you need to test less then xy solutions and in each you need to - discard it if there is an overlap - discard it if they do not touch - if they touch then count the number of edges that are common All three of the above tests can be done in constant time by scanning all the yellow tiles (number of which is konstx*y)

So, the above can be easily done in O(n^4), is that good enough for you?