Recursive Division

pick a language to open the code

def divide(links, w, x, y, rw, rh, rng):
    if rh <= 1:
        for i in range(rw - 1):
            room = y * w + x + i
            carve(links, room, neighbor(room, 1), 1)
        return
    if rw <= 1:
        for i in range(rh - 1):
            room = (y + i) * w + x
            carve(links, room, neighbor(room, 2), 2)
        return
    if rw > rh or (rw == rh and rng.below(2) == 0):
        cut = rng.below(rw - 1)
        room = (y + rng.below(rh)) * w + x + cut
        carve(links, room, neighbor(room, 1), 1)
        divide(links, w, x, y, cut + 1, rh, rng)
        divide(links, w, x + cut + 1, y, rw - cut - 1, rh, rng)
        return
    cut = rng.below(rh - 1)
    room = (y + cut) * w + x + rng.below(rw)
    carve(links, room, neighbor(room, 2), 2)
    divide(links, w, x, y, rw, cut + 1, rng)
    divide(links, w, x, y + cut + 1, rw, rh - cut - 1, rng)


def recursive_division(w, h, rng):
    links = [0] * (w * h)
    divide(links, w, 0, 0, w, h, rng)
    return links

function divide(links, w, x, y, rw, rh, rng) {
  if (rh <= 1) {
    for (let i = 0; i + 1 < rw; i++) {
      const room = y * w + x + i;
      carve(links, room, neighbor(room, 1), 1);
    }
    return;
  }
  if (rw <= 1) {
    for (let i = 0; i + 1 < rh; i++) {
      const room = (y + i) * w + x;
      carve(links, room, neighbor(room, 2), 2);
    }
    return;
  }
  const vertical = rw > rh || (rw === rh && rng.below(2) === 0);
  const cut = rng.below((vertical ? rw : rh) - 1);
  if (vertical) {
    const room = (y + rng.below(rh)) * w + x + cut;
    carve(links, room, neighbor(room, 1), 1);
    divide(links, w, x, y, cut + 1, rh, rng);
    divide(links, w, x + cut + 1, y, rw - cut - 1, rh, rng);
    return;
  }
  const room = (y + cut) * w + x + rng.below(rw);
  carve(links, room, neighbor(room, 2), 2);
  divide(links, w, x, y, rw, cut + 1, rng);
  divide(links, w, x, y + cut + 1, rw, rh - cut - 1, rng);
}

function recursiveDivision(w, h, rng) {
  const links = new Array(w * h).fill(0);
  divide(links, w, 0, 0, w, h, rng);
  return links;
}

static void divide(int links[], int w, int x, int y, int rw, int rh) {
    if (rh <= 1) {
        for (int i = 0; i + 1 < rw; i++) {
            int room = y * w + x + i;
            carve(links, room, neighbor(room, 1), 1);
        }
        return;
    }
    if (rw <= 1) {
        for (int i = 0; i + 1 < rh; i++) {
            int room = (y + i) * w + x;
            carve(links, room, neighbor(room, 2), 2);
        }
        return;
    }
    if (rw > rh || (rw == rh && rand() % 2 == 0)) {
        int cut = rand() % (rw - 1);
        int room = (y + rand() % rh) * w + x + cut;
        carve(links, room, neighbor(room, 1), 1);
        divide(links, w, x, y, cut + 1, rh);
        divide(links, w, x + cut + 1, y, rw - cut - 1, rh);
        return;
    }
    int cut = rand() % (rh - 1);
    int room = (y + cut) * w + x + rand() % rw;
    carve(links, room, neighbor(room, 2), 2);
    divide(links, w, x, y, rw, cut + 1);
    divide(links, w, x, y + cut + 1, rw, rh - cut - 1);
}

void recursive_division(int links[], int w, int h) {
    divide(links, w, 0, 0, w, h);
}

static void divide(std::vector<int>& links, int w, int x, int y, int rw,
                   int rh, std::mt19937& rng) {
    auto pick = [&rng](int top) {
        return std::uniform_int_distribution<int>(0, top - 1)(rng);
    };
    if (rh <= 1) {
        for (int i = 0; i + 1 < rw; i++) {
            int room = y * w + x + i;
            carve(links, room, neighbor(room, 1), 1);
        }
        return;
    }
    if (rw <= 1) {
        for (int i = 0; i + 1 < rh; i++) {
            int room = (y + i) * w + x;
            carve(links, room, neighbor(room, 2), 2);
        }
        return;
    }
    if (rw > rh || (rw == rh && pick(2) == 0)) {
        int cut = pick(rw - 1);
        int room = (y + pick(rh)) * w + x + cut;
        carve(links, room, neighbor(room, 1), 1);
        divide(links, w, x, y, cut + 1, rh, rng);
        divide(links, w, x + cut + 1, y, rw - cut - 1, rh, rng);
        return;
    }
    int cut = pick(rh - 1);
    int room = (y + cut) * w + x + pick(rw);
    carve(links, room, neighbor(room, 2), 2);
    divide(links, w, x, y, rw, cut + 1, rng);
    divide(links, w, x, y + cut + 1, rw, rh - cut - 1, rng);
}

void recursive_division(std::vector<int>& links, int w, int h,
                        std::mt19937& rng) {
    divide(links, w, 0, 0, w, h, rng);
}

static void Divide(int[] links, int w, int x, int y, int rw, int rh,
                   Random rng) {
    if (rh <= 1) {
        for (int i = 0; i + 1 < rw; i++) {
            int room = y * w + x + i;
            Carve(links, room, Neighbor(room, 1), 1);
        }
        return;
    }
    if (rw <= 1) {
        for (int i = 0; i + 1 < rh; i++) {
            int room = (y + i) * w + x;
            Carve(links, room, Neighbor(room, 2), 2);
        }
        return;
    }
    if (rw > rh || (rw == rh && rng.Next(2) == 0)) {
        int cut = rng.Next(rw - 1);
        int room = (y + rng.Next(rh)) * w + x + cut;
        Carve(links, room, Neighbor(room, 1), 1);
        Divide(links, w, x, y, cut + 1, rh, rng);
        Divide(links, w, x + cut + 1, y, rw - cut - 1, rh, rng);
        return;
    }
    int wall = rng.Next(rh - 1);
    int gap = (y + wall) * w + x + rng.Next(rw);
    Carve(links, gap, Neighbor(gap, 2), 2);
    Divide(links, w, x, y, rw, wall + 1, rng);
    Divide(links, w, x, y + wall + 1, rw, rh - wall - 1, rng);
}

static int[] RecursiveDivision(int w, int h, Random rng) {
    int[] links = new int[w * h];
    Divide(links, w, 0, 0, w, h, rng);
    return links;
}

static void divide(int[] links, int w, int x, int y, int rw, int rh,
                   Random rng) {
    if (rh <= 1) {
        for (int i = 0; i + 1 < rw; i++) {
            int room = y * w + x + i;
            carve(links, room, neighbor(room, 1), 1);
        }
        return;
    }
    if (rw <= 1) {
        for (int i = 0; i + 1 < rh; i++) {
            int room = (y + i) * w + x;
            carve(links, room, neighbor(room, 2), 2);
        }
        return;
    }
    if (rw > rh || (rw == rh && rng.nextInt(2) == 0)) {
        int cut = rng.nextInt(rw - 1);
        int room = (y + rng.nextInt(rh)) * w + x + cut;
        carve(links, room, neighbor(room, 1), 1);
        divide(links, w, x, y, cut + 1, rh, rng);
        divide(links, w, x + cut + 1, y, rw - cut - 1, rh, rng);
        return;
    }
    int wall = rng.nextInt(rh - 1);
    int gap = (y + wall) * w + x + rng.nextInt(rw);
    carve(links, gap, neighbor(gap, 2), 2);
    divide(links, w, x, y, rw, wall + 1, rng);
    divide(links, w, x, y + wall + 1, rw, rh - wall - 1, rng);
}

static int[] recursiveDivision(int w, int h, Random rng) {
    int[] links = new int[w * h];
    divide(links, w, 0, 0, w, h, rng);
    return links;
}