7

I'm looking for an algorithm for placing tiles of different sizes within a complex area (all 2D) as randomly but efficiently as possible. I know the different dimensions of the tiles provided and the quantity of each. What I need to do is to place these tiles within an irregular area, such that:

  • Tiles are placed so that only one edge aligns if possible.
  • There are no 'cross' junctions (i.e. four edges converging) only 'T' junctions.
  • The pattern of laying appears to be random with similarly sized tiles not being placed together (excepting the next point)
  • Tiles can be rotated 90 degrees (all tiles are rectangular and plain, so are symmetrical over 180 degrees)
  • The tiles may overlap the boundaries, but this should be kept to a minimum as the most efficient use of the tiles should be made.

The following tile sizes may be used (measured in cm):

  • 900 x 600
  • 750 x 600
  • 600 x 600
  • 600 x 450
  • 450 x 450
  • 600 x 300
  • 450 x 300
  • 300 x 300

Any number of each of these tiles can be used. An equal supply of each tile can be used (say 35 of each). The shape to fill can be arbitrary, but as an example, the red bordered area in the following layout is typical of the kind of complex area to fill.

Example area to cover

The goal is to create a layout that fills (including overlaps if necessary) the given area as a efficiently as possible with a random, or pseudo-random pattern using only the given tile sizes to achieve a layout similar to the following:

Example random tile pattern

By efficient, I mean with as little tile wastage as possible. I'm not sure if there's already algorithms to achieve this kind of thing - a search didn't uncover one - but I would be really interested in any algorithms that could be applied to this problem.

7
  • 1
    The goal is always easily reachable using one type of tile in half-aligned manner. Define efficient. Is that cheap? With minimum waste? To make this a meaningful question you would either need a fixed ratio of availabitity between the different tiles (and for practical and estethic purposes the number of different tiles shoud be limited) or a known repeatable pattern. Mar 27, 2022 at 10:11
  • 1
    Out of curiosity, I implemented an algorithm that does the basics. Without lack of generality, ignore the complex ground floor plan and waste requirements, instead lay out tiles in a rectangle and cut at the edges (of course, you don't need to cut tiles that are completely outside). Tile layers are used to cut tiles and may re-use cut off parts. My algorithm then proceeds by processing the area row by row, placing tiles randomly while avoiding getting itself into unresolvable dead ends. If the question gets reopened, I'll add some more detail as an answer. Mar 28, 2022 at 10:49
  • 1
    Here's a JS fiddle of my algorithm (essentially uncommented): jsfiddle.net/hrj8u3p5/29 Mar 28, 2022 at 15:49
  • 1
    I "cheated" by reducing the actual tile width and height by the gap width, so with a unit size of 10 the 2x2 tile is actually 19x19 pixels, and the 3x3 is 29x29 pixels. I believe that tile sets which are intended to be used together are (or should be) similarly sized to allow for a consistent gap width, but I've never actually tiled a floor myself, so I may be wrong. Mar 29, 2022 at 12:09
  • 1
    @Hans-MartinMosner The manufacturer could make each side of each tile a bit shorter than its nominal width like you have done and they typically do. This would work but it would also dictate the gap width for arbitrary complicated patterns. This is why you don't see very complicated patterns a lot. If you go with a checkerboard pattern you are free to apply any gap width and still make everything align nicely. With this particular problem you would be bound to a particular (and likely very narrow) gap width which is a nightmare to lay down. Mar 30, 2022 at 5:57

1 Answer 1

6

As I've commented already, this question made me curious, and the problem looks simple enough that it should be possible to solve it with a relatively simple algorithm.

TL;DR: Here's the JS fiddle that shows how the tiling of a rectangular area looks: https://jsfiddle.net/hrj8u3p5/29

enter image description here

Step 1: Cleaning up the problem statement

Your problem statement contains some apparent inaccuracies, some areas that can be improved to get to the core, and some difficult and probably not so important constraints that we're going to ignore for a first solution attempt.

Units of measurement

Your maximum tile size is certainly not 900x600 cm. That would be around 30x20 ft, a somewhat unwieldy size for a single tile. I suppose those are mm, not cm, which makes the biggest tile 3x2 ft, still a bit big but plausible. Anyway, that does not matter for the algorithm, due to the second point:

Removing unnecessary detail

If you look at the tile sizes, you quickly see that they have a largest common denominator of 150. Divide your sizes by that number to achieve small integer sizes, which are much easier to deal with: 6x4, 5x4, 4x4, 4x3, 3x3, 4x2, 3x2, 2x2. Note that the absence of a 1x1 tile makes the algorithm a little complicated, as it needs to do a bit of lookahead to avoid getting into an inresolvable situation.

Ignoring (possibly unimportant) constraints

Integrating the complex boundary of your floor plan into an algorithm would complicate it significantly. Instead, I propose to tile a rectangular area that can be overlaid with the actual floor plan to see which areas actually need to be tiled.

The requirement to keep cut-off residue to a minimum is likely very hard to satisfy, so I'd propose to cut tiles arbitrarily and re-use the cut-off parts if possible. Tilers do that anyway when necessary. In some cases, they might replace a tile proposed by the algorithm with one that fits with less waste, but I'd leave that to their discretion.

Step 2: Algorithm outline

As a first step, I'd choose a very simple "greedy" algorithm without backtracking. Backtracking could possible lead to somewhat better looking results and a simplification of the lookahead checks, but it would make the algorithm more complex.

Tiling in rows

We're working along rows, trying to fill them with random tiles while observing the aesthetical constraints if possible.

Hard and soft constraints

I've grouped the constraints into hard and soft to enable the algorithm to always find a solution, even if it does not look perfect. Hard constraints are those that are required to make a tiling possible at all, while the aesthetic constraints are soft and may be broken if otherwise a tile cannot be placed.

Possible improvements

A limited backtracking feature could help to avoid some aestetic constraint violations in the last row, but it's not clear whether the additional effort would be justified.

Step 3: The code

The javascript code at https://jsfiddle.net/hrj8u3p5/29 renders a 60x60 area using random tile colors and placements. To keep it available in case the JS fiddle expires, I've included it here:

HTML

<html>
<head>
<title>Tiling</title>
</head>
<body>
<canvas id="canvas" width="601" height="601"></canvas>
</body>
</html>

Javascript

let c = document.getElementById("canvas");
let ctx = c.getContext("2d");
let scale = 10;

function rnd(min, max) {
    return Math.floor(Math.random()*(max-min))+min;
}
function rndColor() {
    return "rgb(" + rnd(80,200) + "," + rnd(80,200) + "," + rnd(80,200) + ")";
}
function shuffle(arr) {
  arr.sort(() => Math.random() - 0.5);
}

class Tile {
    constructor(column, row, width, height, color) {
    this.column = column;
    this.row = row;
    this.width = width;
    this.height = height;
    this.color = color
  }
  renderOn(ctx) {
    ctx.fillStyle = this.color;
    let x = this.column*scale;
    let y = this.row*scale;
    let w = this.width*scale;
    let h = this.height*scale;
    ctx.fillRect(x+1, y+1, w-1, h-1)
  }
  is_similar(other) {
    return this.width == other.width && this.height == other.height;
  }
  is_left_similar(other) {
    return other.row == this.row && this.is_similar(other);
  }
  is_top_similar(other) {
    return other.column == this.column && this.is_similar(other);
  }
  transposed() {
    return new Tile(this.column, this.row, this.height, this.width, this.color);
  }
  placed_at(columnIndex, rowIndex) {
    return new Tile(columnIndex, rowIndex, this.width, this.height, this.color);
  }
}

class Floor {
    constructor(width, height) {
    this.width = width;
    this.height = height;
    this.reset();
    this.tileTypes = [];
    let sizes = [[2,2],[3,2],[4,2],[3,3],[4,3],[4,4],[5,4],[6,4]];
    for (let s of sizes) {
        let tile = new Tile(0,0,s[0], s[1], rndColor());
      this.tileTypes.push(tile);
      this.tileTypes.push(tile.transposed());
    }
  }
  reset() {
    this.rows = [];
    this.tiles = [];
    for (let i = 0; i < this.height; i++) {
        this.rows.push(new Array(this.width))
    }
  }
  place(tile) {
    this.tiles.push(tile);
    for (let rowIndex = tile.row; rowIndex < tile.row+tile.height; rowIndex++) {
      for (let columnIndex = tile.column; columnIndex < tile.column+tile.width; columnIndex++) {
        this.rows[rowIndex][columnIndex] = tile;
      }
    }
  }
  // return whether we can legally place a tile
  canPlace(tile) {
    if (tile.column + tile.width > this.width) {
        return false;
    }
    if (tile.column + tile.width + 1 == this.width) {
        return false;
    }
    if (tile.row + tile.height > this.height) {
        return false;
    }
    if (tile.row + tile.height + 1 == this.height) {
        return false;
    }
    let row = this.rows[tile.row];
    if (row[tile.column+tile.width] == undefined && row[tile.column+tile.width+1] !== undefined) {
        return false;
    }
    for (let r = tile.row; r < tile.row + tile.height; r++) {
        for (let c = tile.column; c < tile.column + tile.width; c++)
        if (this.rows[r][c] !== undefined) {
            return false
        }
    }
    return true;
  }
  // return whether we should aesthetically place a tile (legality should already be established)
  shouldPlace(tile) {
    if (tile.column > 0 && tile.is_left_similar(this.rows[tile.row][tile.column-1])) {
        return false;
    }
    if (tile.row > 0) {
        if (tile.is_top_similar(this.rows[tile.row-1][tile.column])) {
            return false;
      }
      let nextColumn = tile.column + tile.width;
      if (nextColumn < this.width) {
        let topRight = this.rows[tile.row-1][nextColumn];
        if (topRight.column == nextColumn && topRight.row + topRight.height == tile.row) {
            return false;
        }
      }
    }
    return true;
  }
  placeAny(columnIndex, rowIndex) {
    shuffle(this.tileTypes);
    let possible = this.tileTypes
                .map(x => x.placed_at(columnIndex, rowIndex))
          .filter(x => this.canPlace(x));
    for (let tile of possible) {
        if (this.shouldPlace(tile)) {
        this.place(tile);
        return
      }
    }
    if (possible.length > 0) {
        this.place(possible[0]);
      return;
    }
    console.log("could not place tile at row " + rowIndex + " column " + columnIndex);
  }
  fillRow(rowIndex) {
    let row = this.rows[rowIndex];
    for (let c = 0; c < this.width; c++) {
        if (row[c] === undefined) {
        this.placeAny(c, rowIndex);
      }
    }
  }
  fill() {
    for (let r = 0; r < this.height; r++) {
        this.fillRow(r);
    }
  }
  renderOn(ctx) {
    ctx.fillStyle = "#000";
    ctx.fillRect(0,0,601,601);
    for (let t of this.tiles) {
        t.renderOn(ctx)
    }
  }
}

var floor = new Floor(60,60);
floor.fill();
floor.renderOn(ctx);
1
  • This is a super solution, Hans-Martin, thank you for going to so much trouble. I was considering an iterative rotational algorithm (i.e. take a random tile, place it and then place other random tiles around it until fully surrounded, then go through each one of them and do the same. A little similar to "paint area fill" algorithms, but hadn't had a chance to take it further. It might allow (a) for placing smaller tiles at the edges to be more efficient and (b) to fill irregular shapes such as the one proposed rather than just a rectangle, but that's another step. Thanks again! Mar 29, 2022 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.