What is the optimal algorithm for placing compatible tiles adjacent to each other?

user_1266109 0
Viewed 69

I have a number of tiles, each with a unique ID (1,2,3....)

Each tile has information about which other tiles (there can be more than one option) are allowed to be placed directly north, south,east or west of this tile. All other tiles may not be placed in these positions.

There is no information about which tiles may or may not be placed diagonally(North East, South West etc), since that would depend on the tiles which are North,South,East or West etc of the adjacent tiles anyway.

Given a grid of size (NxM), and an initial tile in position (0,0) what is the optimal algorithm for placing tiles in a compatible manner ?

At present I have this brute force solution:

class Tile {
public:
int id;//From 0 to any number
//Each of the following vectors contain ids of which tiles may be placed immediately adjacent in that direction. If no tiles may be placed, then that vector is empty.
std::vector<int> northTiles;
std::vector<int> southTiles;
std::vector<int> eastTiles;
std::vector<int> westTiles;
}

class Layout{
public:

std::unordered_map<int,Tile> _tileIdToTile;
std::vector<std::vector<int>> tileIds; //Which tile id is placed at which coordinate

    Layout(int N,int M){

    }
}

Algorithm in pseudocode, to keep it concise:

  • Pick some tile id to start with
  • Start with coordinate 0,0
  • Place first compatible tile to the east of this tile (1,0), and keep placing compatible tiles east (2,0), (3,0) etc
  • If we reach the last tile in the current row, then move up a row (eg: 0,1) and continue as before, by placing tiles, that are compatible both with the tile immediately below (south), and to the west (previous tile)
  • If we do not have any compatible tile, then we go backwards to the last successful coordinate, and choose a different tile from remaining options. Likewise, if there is no more compatible tiles, then we go backwards to the next previous successful coordinate before this, and choose a different tile to place next.
  • If we are at the origin, then we choose a different starting tile
  • If we have placed a compatible tile at the top right coordinate, then we have a successful placement.

Since we use a vector for storing compatible tile ids, we do not need to keep track of our position, since the tile used is already stored in the layout, and we can lookup the index in the vector, to determine which tile to try next, or if we have run out of compatible tiles.

This is a simple but brute force solution, so the performance is very poor. I have glanced at other solutions which are more complex to understand.

autotile algorithm c++
1 Answers

This is a Constraint Satisfaction Problem, so you may want to apply some typical strategies/heuristics, although this will probably require to implement a full backtracking mechanism.

  • constraint propagation: block all assignments that are incompatible with the ones you already made
  • most constrained variable, also known as fail-first heuristic: try to assign a tile in the place where the maximum number of constraints apply. This will prune the search tree faster
  • least constraining value: once you selected which place you want to assign, try first to set the tile that leaves more open possibilities

There are lots of more complex techniques but the three above should represent a good start

user_158442960
Related