shigureni.dev

BSPで部屋を割る

四角い部屋がきっちり並ぶダンジョンは、空間そのものを再帰的に二分割して作る。BSP（Binary Space Partitioning）。大きな矩形を縦か横にざっくり割って、できた2つをまた割って、を木構造でくり返す。十分小さくなった葉の矩形の中に、一回り小さい部屋を置く。

BSPは空間を二分木に畳む。根が領域全体、内部ノードが「一本の直線で割った境界」、葉が分割しきった小区画。各葉に部屋を彫れば、兄弟の区画は元の親矩形を縦か横に分けたものなので領域が交わらず、部屋同士の不重複が木構造から保証される。割る向き・位置に乱数を入れると規則的すぎない部屋割りになり、サブディビジョンで矩形を分けていくのは再帰的な構図生成と同じ骨格。

まず割る部分だけを作る。split は矩形を受け取り、横か縦をランダムに選んで分割位置 cut を決め、左右（上下）の2枚に切ってそれぞれを再び split に渡す。矩形が minSize より小さくなったら割るのをやめ、その矩形を葉として残す。盤面いっぱいの一枚から始めて、depth を時間で増やしながら分割の深さを段々深くする。

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const minSize = 70
  let t = 0

const split = (rect, leaves, depthLeft) => {
    if (depthLeft <= 0 || (rect.w < minSize * 2 && rect.h < minSize * 2)) {
      leaves.push(rect)
      return
    }
    const horiz = rect.w > rect.h
    const span = horiz ? rect.w : rect.h
    const cut = Math.floor(span * (0.35 + Math.sin(rect.x + rect.y) * 0.1 + 0.15))
    if (horiz) {
      split({ x: rect.x, y: rect.y, w: cut, h: rect.h }, leaves, depthLeft - 1)
      split({ x: rect.x + cut, y: rect.y, w: rect.w - cut, h: rect.h }, leaves, depthLeft - 1)
    } else {
      split({ x: rect.x, y: rect.y, w: rect.w, h: cut }, leaves, depthLeft - 1)
      split({ x: rect.x, y: rect.y + cut, w: rect.w, h: rect.h - cut }, leaves, depthLeft - 1)
    }
  }

return () => {
    t += 0.012
    const depth = 1 + Math.floor((1 - Math.cos(t)) * 3)
    const leaves = []
    split({ x: 0, y: 0, w: w, h: h }, leaves, depth)

c.fillStyle = colors.paper
    c.fillRect(0, 0, w, h)
    c.fillStyle = colors.tint(40)
    for (const r of leaves) {
      c.fillRect(r.x + 2, r.y + 2, r.w - 4, r.h - 4)
    }
  }
}

割る向きを長い辺に合わせているので、横長の区画は縦に、縦長の区画は横に切れて、どの葉もおよそ正方形に近づく。depth が増えるたびに各区画がさらに二つに割れ、盤面が細かいタイルへ分かれていく。cut を span * 0.5 の固定にすると等分されて格子状に、乱数を強くすると区画の大小が散らばる。minSize を上げると割りが早く止まって大きな区画が残る。

葉の矩形が決まったら、その中に一回り小さい部屋を彫る。区画の縁から pad だけ内側に余白を取り、残りの幅・高さの中でさらにランダムに縮めて置く。区画より小さい部屋にするので、隣り合う部屋のあいだに壁が残る。

const split = (rect, leaves, depthLeft, minSize) => {
  if (depthLeft <= 0 || (rect.w < minSize * 2 && rect.h < minSize * 2)) {
    leaves.push(rect)
    return
  }
  const horiz = rect.w > rect.h
  const span = horiz ? rect.w : rect.h
  const cut = Math.floor(span * (0.35 + Math.random() * 0.3))
  if (horiz) {
    split({ x: rect.x, y: rect.y, w: cut, h: rect.h }, leaves, depthLeft - 1, minSize)
    split(
      { x: rect.x + cut, y: rect.y, w: rect.w - cut, h: rect.h },
      leaves,
      depthLeft - 1,
      minSize,
    )
  } else {
    split({ x: rect.x, y: rect.y, w: rect.w, h: cut }, leaves, depthLeft - 1, minSize)
    split(
      { x: rect.x, y: rect.y + cut, w: rect.w, h: rect.h - cut },
      leaves,
      depthLeft - 1,
      minSize,
    )
  }
}

const carveRoom = (rect, pad) => {
  const rw = Math.max(8, rect.w - pad * 2 - Math.floor(Math.random() * rect.w * 0.2))
  const rh = Math.max(8, rect.h - pad * 2 - Math.floor(Math.random() * rect.h * 0.2))
  const rx = rect.x + pad + Math.floor(Math.random() * Math.max(1, rect.w - pad * 2 - rw))
  const ry = rect.y + pad + Math.floor(Math.random() * Math.max(1, rect.h - pad * 2 - rh))
  return { x: rx, y: ry, w: rw, h: rh, cx: rx + rw / 2, cy: ry + rh / 2 }
}

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const minSize = 80
  const pad = 10
  let leaves = []
  let rooms = []
  let timer = 0

const build = () => {
    leaves = []
    split({ x: 0, y: 0, w: w, h: h }, leaves, 5, minSize)
    rooms = leaves.map((r) => carveRoom(r, pad))
  }

build()

return () => {
    timer += 1
    if (timer > 90) {
      timer = 0
      build()
    }

c.fillStyle = colors.paper
    c.fillRect(0, 0, w, h)

c.strokeStyle = colors.tintAlpha(0, 0.18)
    c.lineWidth = 1
    for (const r of leaves) {
      c.strokeRect(r.x + 0.5, r.y + 0.5, r.w - 1, r.h - 1)
    }

c.fillStyle = colors.tint(40)
    for (const r of rooms) {
      c.fillRect(r.x, r.y, r.w, r.h)
    }
  }
}

薄い線が分割の境界、塗りつぶしが各葉に彫った部屋。区画は盤面を隙間なく覆い、部屋はその内側に浮く。pad を増やすと部屋が痩せて区画とのあいだの壁が太り、0 にすると部屋が区画いっぱいに膨らんで隣と接する。部屋が重ならないのは、各部屋が自分の葉の矩形の内側に収まっていて、葉同士が交わらないため。

部屋を置いただけでは行き来できない。兄弟の部屋の中心どうしをL字の廊下で結ぶと、木の枝に沿って全部屋が一本に繋がる。split が左右の子のインデックスを覚えるノード木に変え、葉から根へ戻りながら、左の子の部屋と右の子の部屋の中心を横線と縦線で縫う。

const carve = (nodes, idx, corridors, pad) => {
  const node = nodes[idx]
  if (node.left < 0 && node.right < 0) {
    const r = node.rect
    const rw = Math.max(8, r.w - pad * 2 - Math.floor(Math.random() * r.w * 0.2))
    const rh = Math.max(8, r.h - pad * 2 - Math.floor(Math.random() * r.h * 0.2))
    const rx = r.x + pad + Math.floor(Math.random() * Math.max(1, r.w - pad * 2 - rw))
    const ry = r.y + pad + Math.floor(Math.random() * Math.max(1, r.h - pad * 2 - rh))
    node.room = { x: rx, y: ry, w: rw, h: rh, cx: rx + rw / 2, cy: ry + rh / 2 }
    return node.room
  }
  const lr = node.left >= 0 ? carve(nodes, node.left, corridors, pad) : null
  const rr = node.right >= 0 ? carve(nodes, node.right, corridors, pad) : null
  if (lr && rr) {
    const ax = lr.cx
    const ay = lr.cy
    const bx = rr.cx
    const by = rr.cy
    corridors.push({ x: Math.min(ax, bx), y: ay - 3, w: Math.abs(ax - bx) + 6, h: 6 })
    corridors.push({ x: bx - 3, y: Math.min(ay, by), w: 6, h: Math.abs(ay - by) + 6 })
  }
  node.room = lr || rr
  return node.room
}

const split = (nodes, rect, depthLeft, minSize) => {
  const idx = nodes.length
  nodes.push({ rect: rect, left: -1, right: -1, room: null })
  if (depthLeft <= 0 || (rect.w < minSize * 2 && rect.h < minSize * 2)) return idx
  const horiz = rect.w > rect.h
  const span = horiz ? rect.w : rect.h
  const cut = Math.floor(span * (0.35 + Math.random() * 0.3))
  const l = horiz
    ? { x: rect.x, y: rect.y, w: cut, h: rect.h }
    : { x: rect.x, y: rect.y, w: rect.w, h: cut }
  const r = horiz
    ? { x: rect.x + cut, y: rect.y, w: rect.w - cut, h: rect.h }
    : { x: rect.x, y: rect.y + cut, w: rect.w, h: rect.h - cut }
  nodes[idx].left = split(nodes, l, depthLeft - 1, minSize)
  nodes[idx].right = split(nodes, r, depthLeft - 1, minSize)
  return idx
}

export default (c) => {
  const w = c.canvas.width
  const h = c.canvas.height
  const minSize = 80
  const pad = 8
  let nodes = []
  let corridors = []
  let timer = 0

const build = () => {
    nodes = []
    corridors = []
    split(nodes, { x: 0, y: 0, w: w, h: h }, 5, minSize)
    carve(nodes, 0, corridors, pad)
  }

build()

return () => {
    timer += 1
    if (timer > 110) {
      timer = 0
      build()
    }

c.fillStyle = colors.paper
    c.fillRect(0, 0, w, h)

c.fillStyle = colors.tint(40)
    for (const node of nodes) {
      if (node.left < 0 && node.right < 0 && node.room) {
        const r = node.room
        c.fillRect(r.x, r.y, r.w, r.h)
      }
    }

c.fillStyle = colors.ink
    for (const r of corridors) {
      c.fillRect(r.x, r.y, r.w, r.h)
    }
  }
}

各部屋から伸びる細い線が廊下で、兄弟の中心を横へ引いてから縦へ下りるL字になっている。木を葉から戻りながら、ひとつ上のノードで左右の部屋を結ぶので、深い階層の近い部屋から順に繋がり、最後に根で大きく二分された両側が一本で繋がる。Math.min(ax, bx) と Math.abs(ax - bx) で挟んでいるため、左右どちらが上でも同じ向きに彫れる。割る向きと位置の乱数が変わるたびに、部屋の配置と廊下の縫い目が組み変わる。

廊下まで引いても、乱数次第でどこかの部屋が孤立する可能性は残る。全部の部屋に行き着けるかは、別途BFSで到達範囲を塗って確かめる。