Table of Contents

Motivation

I recently found a video in which someone was explaining world generation for a video game based on a concept they called wave collapse. The basic idea is to have a bunch of tile types that are compatible with other tiles as their neighbors. For example, if we had tiles with four sides and we look at a bottom-to-right curve tile then the neighbor on the bottom needs to be connecting upwards and the neighbor on the left needs to be connecting to the left to fit, while the top/left neighbor cannot connect to the bottom/right. With those basic rules, we can just start on an empty field, pick a starting tile and position at random, check which tiles would fit into adjacent spaces and then choose one space and choose a random fitting tile to put into that space. To fill the entire space like that we would just repeat this process until the field is filled; we do not need to pick a new start tile every turn but just look at the new neighbors after every round.

To make our vocabulary fit the concept of wave collapse we will call choosing a tile at random at a position where it fits collapsing a tile. Since just an empty labyrinth would look very boring I also put in some little figures to chase around in it.

Implementation

Wave Collapse

First, we would need to come up with a way to define the tile rules efficiently. My tiles can connect to four directions which I decided to implement as bit flags.

LEFT = 0b0001
TOP = 0b0010
RIGHT = 0b0100
BOTTOM = 0b1000

To encode which tile connects in which direction I now just need a dictionary with the tile names as keys and the directions it connects to as value, since our directions are implemented as bit flags we can bitwise-or multiple directions to encode that the tile connects in all those directions.

// eslint-disable-next-line no-restricted-syntax, no-labels
connections: Record<string, number> = {
  cross: Tiles.LEFT | Tiles.TOP | Tiles.RIGHT | Tiles.BOTTOM,
  horizontal: Tiles.LEFT | Tiles.RIGHT,
  vertical: Tiles.TOP | Tiles.BOTTOM,
  topToLeft: Tiles.LEFT | Tiles.TOP,
  topToRight: Tiles.TOP | Tiles.RIGHT,
  bottomToLeft: Tiles.LEFT | Tiles.BOTTOM,
  bottomToRight: Tiles.BOTTOM | Tiles.RIGHT,
  bottomThreeway: Tiles.BOTTOM | Tiles.RIGHT | Tiles.LEFT,
  topThreeway: Tiles.RIGHT | Tiles.LEFT | Tiles.TOP,
  leftThreeway: Tiles.BOTTOM | Tiles.LEFT | Tiles.TOP,
  rightThreeway: Tiles.BOTTOM | Tiles.RIGHT | Tiles.TOP,
  bottomDeadend: Tiles.BOTTOM,
  topDeadend: Tiles.TOP,
  leftDeadend: Tiles.LEFT,
  rightDeadend: Tiles.RIGHT,
  wall: 0,
}

To find out if a given tile connects to a given direction we can use a simple bitwise-and operation.

static function canConnect(tilename: string, direction: number): boolean {
  return Tiles.connections[tilename] & direction > 0
}

A collapse cycle works by taking all tiles that already have a collapsed neighbor and choosing one of these tiles to collapse next.

function collapse(): Boolean {
  // find candidates for collapse
  const collapsableTilesCoordinates = findCollapsableTiles()

  if (collapsableTilesCoordinates.length === 0) {
    return false
  }

  // find tiles that would fit for each candidate
  const fittingTilesArray = collapsableTilesCoordinates.map(coord =>
    getFittingTilesAt(coord)
  )

  // chose which one to collapse
  const collapsingTileIndex = pickCollapsingTile(fittingTilesArray)

  const collapseOptions = fittingTilesArray[collapsingTileIndex]
  const collapsingTileCoordinates
    = collapsableTilesCoordinates[collapsingTileIndex]

  // chose a fitting tile at that place
  const choice = pickTileFrom(collapseOptions)

  // collapse
  grid[collapsingTileCoordinates.x][collapsingTileCoordinates.y] = choice

  return true
}

findCollapsableTiles just loops through the grid and picks the places where there is no tile set yet and where there is a neighbor that is already set and getFittingTilesAt just finds the tiles that fit, considering the neighbors around the position as well as if the position is on the edge of the field, which we can think of as next to a wall; the other functions are more interesting.

pickCollapsingTile decides the index of the tile we collapse in the collapsableTileCoordinates-Array. We could just use a random index but I found that taking one of the indices with the smallest amount of fitting tiles at random is more visually interesting. I also noticed this choice also impacts how connected the resulting graph is, when we set a position in the grid to be a specific tile we weigh the tile types differently, as detailed in the next paragraph. We will see that we can not always pick a tile according to its weight, so collapsing at a position that already has only a few options for possible tiles increases the number of times we actually use the weight of the tile when we make this decision.

function pickCollapsingTile(fittingTiles: number[][]): number {
  let currMin = fittingTiles[0].length
  for (let i = 1; i < fittingTiles.length; i++) {
    if (fittingTiles[i].length <= currMin) {
      currMin = fittingTiles[i].length
    }
  }
  const result = []
  for (let i = 0; i < fittingTiles.length; i++) {
    if (fittingTiles[i].length === currMin) {
      result.push(i)
    }
  }
  return randomElement(result)
}

pickTileFrom can also be quite interesting depending on the implementation. We could again just pick one tile at random but we can also give each tile a weight to control how likely it is that it should be picked. For the weights, we can just use another dictionary, called rates…

// eslint-disable-next-line no-restricted-syntax, no-labels
rates: Record<string, number> = {
  cross: 0,
  horizontal: 8,
  vertical: 8,
  topToLeft: 8,
  topToRight: 8,
  bottomToLeft: 8,
  bottomToRight: 8,
  bottomThreeway: 2,
  topThreeway: 2,
  leftThreeway: 2,
  rightThreeway: 2,
  bottomDeadend: 0,
  topDeadend: 0,
  leftDeadend: 0,
  rightDeadend: 0,
  wall: 4,
}

and then pick the tile with probability based on the rates:

function pickTileIndexWeightedFrom(collapseOptions: number[]) {
  const tile = Random.randomFromListWeighted(collapseOptions, Tiles.rates)
  if (tile === undefined) {
    return collapseOptions[0]
  }

  return tile
}

In this case, we need to check if there is a valid choice for the tiles since some of the rates are zero, so if the only matching tiles have rate zero we just pick the first tile in the list of possible tiles. This means we will not always be able to take the weights into account as we described earlier. This means if there are only options left that have a weight of zero, we will still need to pick one of these options. This happens when the adjacent tiles limit the options we have left, thus it makes sense to always collapse the tiles at positions with the fewest options first, as we do in pickCollapsingTile.

Figures Movement

The movement of the yellow figures on the map is almost random, specifically, they chose a random direction at intersections but will always prefer to walk straight so they do not walk back and forth on a small amount of tiles. We achieve this by choosing their direction randomly weighted towards walking straight. The turquoise figure will always walk towards the closest yellow figure using the A*-Algorithm to find the shortest path towards it.

The basic idea of the A*-Algorithm is to get from a start to an end node in a graph by taking the node that currently has the shortest path approximation and then estimating the length of the paths of each neighbor to the end node. We can approximate the length of the path by adding the length of the way to the current node and a heuristic of how long it will take to the end.

function aStar(
  start: Vertex,
  end: Vertex,
  graph: { vertices: Vertex[]; edges: Edge[] }
) {

  const stack: Vertex[] = []
  const done: Vertex[] = []
  const d: Record<Vertex, number> = {}
  const origin: Record<Vertex, Vertex> = {}

  // setup distance and origin of the first node
  stack.push(start)
  d[start] = 0
  origin[start] = null

  while (stack.length > 0 && !origin.containsKey(end)) {
    // get the vertex off the stack where the approximated distance
    // is shortest
    const curr
      = popVertexWhereSmallest(
        stack,
        vertex => d[vertex] + heuristic(vertex, end))

    // get the neighbors of curr we didnt visit yet
    const notDoneNeighbors
      = curr.neighbors(edges)
        .filter(neighbor => !done.includes(neighbor))

    // mark curr as visited
    done.push(curr)

    for (let i = 0; i < notDoneNeighbors.length; i++) {
      // set the distance that it takes to get to this neighbor
      d[notDoneNeighbors[i]] = d[curr] + edgeLength(curr, neighbor)

      // set how to get to this neighbor and put the neighbor on
      // the stack
      origin[notDoneNeighbors[i]] = curr
      stack.push(notDoneNeighbors[i])
    }
  }

  // get the full path
  const path: Vertex[] = []
  let curr = end
  while (curr !== null) {
    path.push(origin[curr])
    curr = origin[curr]
  }

  return path
}

In this case, the heuristic is the air-line distance between the two nodes or more performantly we can use the distance squared since all we want is a function that generally gets smaller the closer we get to the end because we just want to avoid walking further away from the end (generally speaking on the shortest path, we should on most steps get closer to the end). If we decide to not use a heuristic which is equivalent to using the zero function as a heuristic we call this version of the algorithm “Dijkstra-Algorithm”. Generally, the A*-Algorithm finds the shortest path faster, if we have a good heuristic, which is what we would expect since we are considering more information about the lengths of the paths.

Here edgeLength is always equal to 1, but in a general graph like a city map, this would not be the case.