Randomised Terrain Generation

In the last blog post, we managed to convert the isometric demo from Vanilla.js into Pixi.js in React. It was a great success but I found it a bit boring with just grass tiles floating around.

Why don’t we add some variety of blocks ?

Let’s modify the sprite sheet loading code to introduce some new blocks into the scene.

function generateFrameData(x: number, y: number) {
  return {
    frame: { x: 18 * x, y: 18 * y, w: 18, h: 18 },
    sourceSize: { w: 18, h: 18 },
    spriteSourceSize: { x: 0, y: 0, w: 18, h: 18 }
  }
}

const atlasData = {
  frames: {
    pale_green_grass: generateFrameData(0, 0),
    dark_green_grass: generateFrameData(1, 0),
    dark_green_grass_with_seedling: generateFrameData(2, 0),
    dark_green_grass_with_budding: generateFrameData(3, 0),
    sand: generateFrameData(4, 0),
    sand_with_crack: generateFrameData(5, 0),
    dry_dirt: generateFrameData(6, 0),
    dry_dirt_with_crach: generateFrameData(7,0),
    dirt: generateFrameData(8, 0),
    dark_green_grass_dirt: generateFrameData(0, 1),
    dark_green_grass_dirt_with_seedling: generateFrameData(1, 1)
  },
  meta: {
    image: `${process.env.PUBLIC_URL}/sprites/structural_blocks.png`,
    format: 'RGBA8888',
    size: { w: 180, h: 180 },
    scale: "0.25",
  },
};

We can then randomise the block’s texture by picking a random texture from the textures when rendering the block

const textureTypes = Object.keys(atlasData.frames);

// ...skipped 

function App() {

  // ...skipped

  const grid = useMemo(() => generateGrid(16, 16, (x, y) => ({ 
    x, 
    y,
    textureType: textureTypes[Math.floor(Math.random() * textureTypes.length)]
  })), [])

  return (
    <Stage
      height={window.innerHeight}
      width={window.innerWidth}
      options={{ resizeTo: window }}>
      {textures
        ? grid.map(({ x, y, textureType }) => (
          <GrassBlock
            x={x}
            y={y}
            texture={textures[textureType]}
          />
        ))
        : null
      }
    </Stage>
  );
}

And there you have it, a randomised terrain! Each block will be different every time you refresh the page!

A truly randomised terrain

However, something just doesn’t seems quite right… It is indeed a randomised terrain but it is not realistic — One would not expect a sand block appears next to a grass block and a dry dirt block pop out of nowhere.

To generate terrain that resemble real life, we can apply some rules to our randomness or what’s called Wave Function Collapse in the field of Quantum Mechanics.

Consider we have a 16 x 16 grid, from the start each block would be in superposition — state where is in all possible states at once, meaning each block can be in any of the texture.

In such scenario, we describe the block as having higher value of entropy as it can possibly become any of the block. We also need to introduce a rule set to reduce the entropy of neighbouring block by defining we can be and cannot be next to the current block.

The rule set

If current block is a pale_green_grass block, the neighbouring block cannot be any of the sand block. Thus, the possible state of neighbouring block is reduced hence reducing the entropy.

Keep in mind when defining the rule set, if pale_green_grass cannot have any sand block as neighbour, the same goes to sand block — it cannot have pale_green_grass as neighbour. This is important otherwise some block on your screen might appear empty as there are contradictions.

The algorithm works like follow:

1. Find the cell with lowest entropy
2. “Collapse” it
3. Propagate the changes to neighbouring cell following the rule set
4. Repeat until all cell are collapsed

// utils.ts

export const blockExclusionRules: Record<string, string[]> = {
    'pale_green_grass': ['sand', 'sand_with_crack'],
    'dark_green_grass': ['sand', 'sand_with_crack', 'dry_dirt', 'dry_dirt_with_crack'],
    'dark_green_grass_with_seedling': ['sand', 'sand_with_crack', 'dry_dirt', 'dry_dirt_with_crack'],
    'dark_green_grass_with_budding': ['sand', 'sand_with_crack', 'dry_dirt', 'dry_dirt_with_crack'],
    'sand': ['pale_green_grass', 'dark_green_grass', 'dark_green_grass_with_seedling', 'dark_green_grass_with_budding', 'dirt'],
    'sand_with_crack': ['pale_green_grass', 'dark_green_grass', 'dark_green_grass_with_seedling', 'dark_green_grass_with_budding', 'dirt'],
    'dry_dirt': ['dark_green_grass', 'dark_green_grass_with_seedling', 'dark_green_grass_with_budding'],
    'dry_dirt_with_crack': ['dark_green_grass', 'dark_green_grass_with_seedling', 'dark_green_grass_with_budding'],
    'dirt': ['sand', 'sand_with_crack']
}

export const directions = [
    [0, -1],
    [-1, 0],
    [0, 1],
    [1, 0]
]

function createMatrix<T>(rows: number, cols: number, itemProvider: (x: number, y: number) => T): T[][] {
    return Array(rows).fill(undefined).map((_, yIndex) =>
        Array(cols).fill(undefined).map((_, xIndex) => itemProvider(xIndex, yIndex)));
}

export function collapse(state: State): string {
    const unwrappedPossibilities = Array.from(state.possibilities);
    // pick a random block from the possibilities
    return unwrappedPossibilities[Math.floor(Math.random() * state.possibilities.size)];
}

export function waveFunctionCollapse(rows: number, cols: number, textureTypes: string[]) {
    const space: State[][] = createMatrix(rows, cols, () => ({ possibilities: new Set(textureTypes) }));
    // use queue to keep track of the block to collapse
    const queue: [number, number][] = [[0, 0]];
    while (queue.length > 0) {
        const [x, y] = queue.shift()!;
        const block = space[x][y];
        // skip if current block is collapsed
        if (block.possibilities.size === 1) continue;
        // collapse the state
        const collapsedState = collapse(block);
        block.possibilities.clear();
        block.possibilities.add(collapsedState);
        // get blocks to exclude
        const blocksToExcluded = blockExclusionRules[collapsedState];
        if (!blocksToExcluded) continue;
        // propagate changes to nearby block's entropy
        for (const direction of directions) {
            const nextX = x + direction[0];
            const nextY = y + direction[1];
            if (nextX < 0 || nextY < 0 || nextX >= rows || nextY >= cols) {
                continue;
            }
            const neighbourBlock = space[nextX][nextY];
            if (neighbourBlock.possibilities.size > 1) {
                // reduce entropy of neighbour block
                blocksToExcluded.forEach((textureType) => neighbourBlock.possibilities.delete(textureType));
                // enqueue neighbour for next collapse
                queue.push([nextX, nextY])
            }
        }
        // sort the queue each iteration to 
        // make sure we are collapsing the block with lowest entropy
        queue.sort(([x1, y1], [x2, y2]) => {
            return space[x1][y1].possibilities.size - space[x2][y2].possibilities.size
        });
    }
    // unwrap the possiblities into a matrix with settled state.
    return space.map((row) => row.map(block => {
        const possibilities = Array.from(block.possibilities);
        return possibilities[0] 
    }));
}

Applying the wave function collapse function to our rendering scene, we get the following:

function App() {

  // ... skipped

  const space = useMemo(() => waveFunctionCollapse(16, 16, textureTypes), []);

  const grid = useMemo(() => generateGrid(16, 16, (x, y) => ({ 
    x, 
    y,
    textureType: space[x][y]
  })), [space])

  return (
    <Stage
      height={window.innerHeight}
      width={window.innerWidth}
      options={{ resizeTo: window }}>
      {textures
        ? grid.map(({ x, y, textureType }) => (
          <GrassBlock
            x={x}
            y={y}
            texture={textures[textureType]}
          />
        ))
        : null
      }
    </Stage>
  );
}

Thanks to Wave Function Collapse, we now have a realistically distributed randomised terrain! Isn’t that amazing!

Bravo!

Obviously, there are room for improvement to make things smoother when transition from one biome to another ( grass -> sand ). There are few things we could do:

1. Tweak the probability of collapsing into different type of blocks based on surrounding as right now every possible block share the same probability
2. Refine the rule set so there are less variation between different blocks

I will leave the door open for your imagination to kick in but for the time being I shall wrap this up!

Stay tune for the next part for more isometric pixel fun!

Reference:

• https://www.youtube.com/watch?v=qRtrj6Pua2A
• https://www.youtube.com/watch?v=TO0Tx3w5abQ
• https://www.youtube.com/watch?v=2SuvO4Gi7uY