성장 트리

언어를 고르면 코드가 열린다

def growing_tree_maze(w, h, rng, pick_last):
    links = [0] * (w * h)
    seen = [False] * (w * h)
    start = rng.below(w * h)
    seen[start] = True
    active = [start]
    while active:
        i = len(active) - 1 if pick_last else rng.below(len(active))
        room = active[i]
        open_dirs = [d for d in range(4)
                     if neighbor(room, d) >= 0 and not seen[neighbor(room, d)]]
        if not open_dirs:
            active.pop(i)
            continue
        d = rng.choice(open_dirs)
        other = neighbor(room, d)
        carve(links, room, other, d)
        seen[other] = True
        active.append(other)
    return links

function growingTreeMaze(w, h, rng, pickLast) {
  const links = new Array(w * h).fill(0);
  const seen = new Array(w * h).fill(false);
  const start = rng.below(w * h);
  const active = [start];
  seen[start] = true;
  while (active.length > 0) {
    const i = pickLast ? active.length - 1 : rng.below(active.length);
    const room = active[i];
    const openDirs = [];
    for (let d = 0; d < 4; d++) {
      const other = neighbor(room, d);
      if (other >= 0 && !seen[other]) openDirs.push(d);
    }
    if (openDirs.length === 0) {
      active.splice(i, 1);
      continue;
    }
    const d = openDirs[rng.below(openDirs.length)];
    const other = neighbor(room, d);
    carve(links, room, other, d);
    seen[other] = true;
    active.push(other);
  }
  return links;
}

void growing_tree_maze(int links[], int w, int h, int pick_last) {
    int n = w * h;
    char* seen = calloc(n, 1);
    int* active = malloc(sizeof(int) * n);
    int count = 0;
    int start = rand() % n;
    seen[start] = 1;
    active[count++] = start;
    while (count > 0) {
        int i = pick_last ? count - 1 : rand() % count;
        int room = active[i];
        int open_dirs[4];
        int found = 0;
        for (int d = 0; d < 4; d++) {
            int other = neighbor(room, d);
            if (other >= 0 && !seen[other]) open_dirs[found++] = d;
        }
        if (found == 0) {
            active[i] = active[--count];
            continue;
        }
        int d = open_dirs[rand() % found];
        int other = neighbor(room, d);
        carve(links, room, other, d);
        seen[other] = 1;
        active[count++] = other;
    }
    free(seen);
    free(active);
}

void growing_tree_maze(std::vector<int>& links, int w, int h, bool pick_last,
                       std::mt19937& rng) {
    int n = w * h;
    std::vector<char> seen(n, 0);
    std::uniform_int_distribution<int> any_room(0, n - 1);
    int start = any_room(rng);
    std::vector<int> active{start};
    seen[start] = 1;
    while (!active.empty()) {
        std::uniform_int_distribution<size_t> spot(0, active.size() - 1);
        size_t i = pick_last ? active.size() - 1 : spot(rng);
        int room = active[i];
        std::vector<int> open_dirs;
        for (int d = 0; d < 4; d++) {
            int other = neighbor(room, d);
            if (other >= 0 && !seen[other]) open_dirs.push_back(d);
        }
        if (open_dirs.empty()) {
            active[i] = active.back();
            active.pop_back();
            continue;
        }
        std::uniform_int_distribution<size_t> pick(0, open_dirs.size() - 1);
        int d = open_dirs[pick(rng)];
        int other = neighbor(room, d);
        carve(links, room, other, d);
        seen[other] = 1;
        active.push_back(other);
    }
}

static int[] GrowingTreeMaze(int w, int h, Random rng, bool pickLast) {
    int n = w * h;
    int[] links = new int[n];
    bool[] seen = new bool[n];
    int start = rng.Next(n);
    var active = new List<int> { start };
    seen[start] = true;
    while (active.Count > 0) {
        int i = pickLast ? active.Count - 1 : rng.Next(active.Count);
        int room = active[i];
        var openDirs = new List<int>();
        for (int d = 0; d < 4; d++) {
            int other = Neighbor(room, d);
            if (other >= 0 && !seen[other]) openDirs.Add(d);
        }
        if (openDirs.Count == 0) {
            active[i] = active[^1];
            active.RemoveAt(active.Count - 1);
            continue;
        }
        int dir = openDirs[rng.Next(openDirs.Count)];
        int next = Neighbor(room, dir);
        Carve(links, room, next, dir);
        seen[next] = true;
        active.Add(next);
    }
    return links;
}

static int[] growingTreeMaze(int w, int h, Random rng, boolean pickLast) {
    int n = w * h;
    int[] links = new int[n];
    boolean[] seen = new boolean[n];
    int start = rng.nextInt(n);
    List<Integer> active = new ArrayList<>();
    active.add(start);
    seen[start] = true;
    while (!active.isEmpty()) {
        int i = pickLast ? active.size() - 1 : rng.nextInt(active.size());
        int room = active.get(i);
        List<Integer> openDirs = new ArrayList<>();
        for (int d = 0; d < 4; d++) {
            int other = neighbor(room, d);
            if (other >= 0 && !seen[other]) openDirs.add(d);
        }
        if (openDirs.isEmpty()) {
            active.set(i, active.get(active.size() - 1));
            active.remove(active.size() - 1);
            continue;
        }
        int dir = openDirs.get(rng.nextInt(openDirs.size()));
        int next = neighbor(room, dir);
        carve(links, room, next, dir);
        seen[next] = true;
        active.add(next);
    }
    return links;
}