Prim

pick a language to open the code

def prim_maze(w, h, rng):
    links = [0] * (w * h)
    seen = [False] * (w * h)
    seen[0] = True
    frontier = [(0, d) for d in range(4) if neighbor(0, d) >= 0]
    while frontier:
        i = rng.below(len(frontier))
        room, d = frontier.pop(i)
        other = neighbor(room, d)
        if other < 0 or seen[other]:
            continue
        carve(links, room, other, d)
        seen[other] = True
        for nd in range(4):
            far = neighbor(other, nd)
            if far >= 0 and not seen[far]:
                frontier.append((other, nd))
    return links

function primMaze(w, h, rng) {
  const links = new Array(w * h).fill(0);
  const seen = new Array(w * h).fill(false);
  seen[0] = true;
  const frontier = [];
  for (let d = 0; d < 4; d++) {
    if (neighbor(0, d) >= 0) frontier.push([0, d]);
  }
  while (frontier.length > 0) {
    const i = rng.below(frontier.length);
    const [room, d] = frontier.splice(i, 1)[0];
    const other = neighbor(room, d);
    if (other < 0 || seen[other]) continue;
    carve(links, room, other, d);
    seen[other] = true;
    for (let nd = 0; nd < 4; nd++) {
      const far = neighbor(other, nd);
      if (far >= 0 && !seen[far]) frontier.push([other, nd]);
    }
  }
  return links;
}

void prim_maze(int links[], int w, int h) {
    int n = w * h;
    char* seen = calloc(n, 1);
    int* rooms = malloc(sizeof(int) * n * 4);
    int* dirs = malloc(sizeof(int) * n * 4);
    int count = 0;
    seen[0] = 1;
    for (int d = 0; d < 4; d++) {
        if (neighbor(0, d) >= 0) { rooms[count] = 0; dirs[count++] = d; }
    }
    while (count > 0) {
        int i = rand() % count;
        int room = rooms[i], d = dirs[i];
        rooms[i] = rooms[count - 1];
        dirs[i] = dirs[--count];
        int other = neighbor(room, d);
        if (other < 0 || seen[other]) continue;
        carve(links, room, other, d);
        seen[other] = 1;
        for (int nd = 0; nd < 4; nd++) {
            int far = neighbor(other, nd);
            if (far >= 0 && !seen[far]) {
                rooms[count] = other;
                dirs[count++] = nd;
            }
        }
    }
    free(seen);
    free(rooms);
    free(dirs);
}

void prim_maze(std::vector<int>& links, int w, int h, std::mt19937& rng) {
    std::vector<char> seen(w * h, 0);
    std::vector<std::pair<int, int>> frontier;
    seen[0] = 1;
    for (int d = 0; d < 4; d++) {
        if (neighbor(0, d) >= 0) frontier.push_back({0, d});
    }
    while (!frontier.empty()) {
        std::uniform_int_distribution<size_t> pick(0, frontier.size() - 1);
        size_t i = pick(rng);
        auto [room, d] = frontier[i];
        frontier[i] = frontier.back();
        frontier.pop_back();
        int other = neighbor(room, d);
        if (other < 0 || seen[other]) continue;
        carve(links, room, other, d);
        seen[other] = 1;
        for (int nd = 0; nd < 4; nd++) {
            int far = neighbor(other, nd);
            if (far >= 0 && !seen[far]) frontier.push_back({other, nd});
        }
    }
}

static int[] PrimMaze(int w, int h, Random rng) {
    int[] links = new int[w * h];
    bool[] seen = new bool[w * h];
    var frontier = new List<(int Room, int Dir)>();
    seen[0] = true;
    for (int d = 0; d < 4; d++) {
        if (Neighbor(0, d) >= 0) frontier.Add((0, d));
    }
    while (frontier.Count > 0) {
        int i = rng.Next(frontier.Count);
        var (room, dir) = frontier[i];
        frontier[i] = frontier[^1];
        frontier.RemoveAt(frontier.Count - 1);
        int next = Neighbor(room, dir);
        if (next < 0 || seen[next]) continue;
        Carve(links, room, next, dir);
        seen[next] = true;
        for (int nd = 0; nd < 4; nd++) {
            int far = Neighbor(next, nd);
            if (far >= 0 && !seen[far]) frontier.Add((next, nd));
        }
    }
    return links;
}

static int[] primMaze(int w, int h, Random rng) {
    int[] links = new int[w * h];
    boolean[] seen = new boolean[w * h];
    List<int[]> frontier = new ArrayList<>();
    seen[0] = true;
    for (int d = 0; d < 4; d++) {
        if (neighbor(0, d) >= 0) frontier.add(new int[] {0, d});
    }
    while (!frontier.isEmpty()) {
        int i = rng.nextInt(frontier.size());
        int[] edge = frontier.get(i);
        frontier.set(i, frontier.get(frontier.size() - 1));
        frontier.remove(frontier.size() - 1);
        int next = neighbor(edge[0], edge[1]);
        if (next < 0 || seen[next]) continue;
        carve(links, edge[0], next, edge[1]);
        seen[next] = true;
        for (int nd = 0; nd < 4; nd++) {
            int far = neighbor(next, nd);
            if (far >= 0 && !seen[far]) frontier.add(new int[] {next, nd});
        }
    }
    return links;
}