Wilson

pick a language to open the code

def wilson_maze(w, h, rng):
    links = [0] * (w * h)
    in_tree = [False] * (w * h)
    in_tree[rng.below(w * h)] = True
    for start in range(w * h):
        if in_tree[start]:
            continue
        walk = {}
        room = start
        while not in_tree[room]:
            d = rng.below(4)
            other = neighbor(room, d)
            if other < 0:
                continue
            walk[room] = d
            room = other
        room = start
        while not in_tree[room]:
            d = walk[room]
            other = neighbor(room, d)
            carve(links, room, other, d)
            in_tree[room] = True
            room = other
    return links

function wilsonMaze(w, h, rng) {
  const links = new Array(w * h).fill(0);
  const inTree = new Array(w * h).fill(false);
  inTree[rng.below(w * h)] = true;
  for (let start = 0; start < w * h; start++) {
    if (inTree[start]) continue;
    const walk = new Map();
    let room = start;
    while (!inTree[room]) {
      const d = rng.below(4);
      const other = neighbor(room, d);
      if (other < 0) continue;
      walk.set(room, d);
      room = other;
    }
    room = start;
    while (!inTree[room]) {
      const d = walk.get(room);
      const other = neighbor(room, d);
      carve(links, room, other, d);
      inTree[room] = true;
      room = other;
    }
  }
  return links;
}

void wilson_maze(int links[], int w, int h) {
    int n = w * h;
    char* in_tree = calloc(n, 1);
    int* walk = malloc(sizeof(int) * n);
    in_tree[rand() % n] = 1;
    for (int start = 0; start < n; start++) {
        if (in_tree[start]) continue;
        int room = start;
        while (!in_tree[room]) {
            int d = rand() % 4;
            int other = neighbor(room, d);
            if (other < 0) continue;
            walk[room] = d;
            room = other;
        }
        room = start;
        while (!in_tree[room]) {
            int d = walk[room];
            int other = neighbor(room, d);
            carve(links, room, other, d);
            in_tree[room] = 1;
            room = other;
        }
    }
    free(in_tree);
    free(walk);
}

void wilson_maze(std::vector<int>& links, int w, int h, std::mt19937& rng) {
    int n = w * h;
    std::vector<char> in_tree(n, 0);
    std::vector<int> walk(n, -1);
    std::uniform_int_distribution<int> any_room(0, n - 1);
    std::uniform_int_distribution<int> any_dir(0, 3);
    in_tree[any_room(rng)] = 1;
    for (int start = 0; start < n; start++) {
        if (in_tree[start]) continue;
        int room = start;
        while (!in_tree[room]) {
            int d = any_dir(rng);
            int other = neighbor(room, d);
            if (other < 0) continue;
            walk[room] = d;
            room = other;
        }
        room = start;
        while (!in_tree[room]) {
            int d = walk[room];
            int other = neighbor(room, d);
            carve(links, room, other, d);
            in_tree[room] = 1;
            room = other;
        }
    }
}

static int[] WilsonMaze(int w, int h, Random rng) {
    int n = w * h;
    int[] links = new int[n];
    bool[] inTree = new bool[n];
    int[] walk = new int[n];
    inTree[rng.Next(n)] = true;
    for (int start = 0; start < n; start++) {
        if (inTree[start]) continue;
        int room = start;
        while (!inTree[room]) {
            int d = rng.Next(4);
            int other = Neighbor(room, d);
            if (other < 0) continue;
            walk[room] = d;
            room = other;
        }
        room = start;
        while (!inTree[room]) {
            int d = walk[room];
            int other = Neighbor(room, d);
            Carve(links, room, other, d);
            inTree[room] = true;
            room = other;
        }
    }
    return links;
}

static int[] wilsonMaze(int w, int h, Random rng) {
    int n = w * h;
    int[] links = new int[n];
    boolean[] inTree = new boolean[n];
    int[] walk = new int[n];
    inTree[rng.nextInt(n)] = true;
    for (int start = 0; start < n; start++) {
        if (inTree[start]) continue;
        int room = start;
        while (!inTree[room]) {
            int d = rng.nextInt(4);
            int other = neighbor(room, d);
            if (other < 0) continue;
            walk[room] = d;
            room = other;
        }
        room = start;
        while (!inTree[room]) {
            int d = walk[room];
            int other = neighbor(room, d);
            carve(links, room, other, d);
            inTree[room] = true;
            room = other;
        }
    }
    return links;
}