Wave Collapse

A simple wave collapse algorithm implementation that is used to populate a grid of a defined size with tiles that have certain connection rules. This is useful for generating a random pattern that follows certain rules.

Wavefunction Collapse and how it works: https://robertheaton.com/2018/12/17/wavefunction-collapse-algorithm/

How-to use?

First you have to define the tiles that make up your grid. For example:

const myTiles = [
    new Tile(0, new Map())
];

The map here contains the "connectors" that the tile is compatible with. Normally you want to define an enum to specify what kind of connectors you want to have:

const ConnectorType = Object.freeze({
    SINGLE_LINE: 0,
    // ...
});

So, for example, if we have three tiles that look like this:

    ┌──────┐  ┌──────┐  ┌───┬──┐
    │      │  │      │  │   │  │
    │      │  ├──────┤  ├───┘  │
    │      │  │      │  │      │
    └──────┘  └──────┘  └──────┘
id   0         1         2

They would be defined like this:

const myTiles = [
    // no connections possible from this tile, so this tile can only
    // connect to some other tile that also has no connection pointing
    // to its neighbor
    new Tile(0, new Map()),
    
    // has one connection to the left, and one to the right, each
    // as the single line connector type
    new Tile(1, new Map(
        [Direction.LEFT, new Set([ConnectorType.SINGLE_LINE])],
        [Direction.RIGHT, new Set([ConnectorType.SINGLE_LINE])],
    )),
    
    // has one connection to the left, and one pointing upwards, each
    // as the single line connector type
    new Tile(1, new Map(
        [Direction.LEFT, new Set([ConnectorType.SINGLE_LINE])],
        [Direction.UP, new Set([ConnectorType.SINGLE_LINE])],
    )),    
];

Now you can use the wave collapse algorithm to get a solution like this:

// for a consistent result you can initialize the random number generator with
// a fixed seed. Comment this out in case you want a new solution everytime you
// run the script
random.use(12345);

// create all rotation variants of my tiles (note that this generates rotation
// variants even for when it is not really required, like with tile 0
const myTilesRotated = generateRotatedTiles(myTiles);

// create a 10x10 grid of our possible tiles (all variants are possible in all grid positions, a.k.a. superposition)
const grid = generateGrid(myTilesRotated, 10, 10);

// tries to find a solution and returns that solution if found (otherwise null is returned)
const solution = collapseWave(grid);

if (solution !== null) {
    console.log("solution found")
    console.log(gridToString(solution))
} else {
    console.log("no solution found :(")
}