Go言語で作るローグライクダンジョン生成プログラム
目次
最近2Dゲーム制作エンジンである Ebitengine を使用して、ローグライクゲームの作成を行っています。
ローグライクゲームの代名詞であるランダムダンジョン生成。今回は、Ebitengine で使用されている Go 言語でRogueスタイルのダンジョンを生成するプログラムを詳しく解説します。
このプログラムは Ebitengine に依存しない、Go 製のコマンドラインアプリです。ダンジョン生成のコードは、そのまま Ebitengine のプロジェクトにも流用できます。
初心者にも分かりやすく、プログラム全体の仕組みから各関数の役割まで、順を追って説明していきます。
プログラムの全体は以下のリポジトリで公開しています。
https://github.com/Kenshu-Miura/RandomDungeon
以下のコマンドでコードを実行することで、ランダムなダンジョンが生成されます。
go run dungeon.go
Table of Contents
プログラム概要
このプログラムは、3×3のグリッドシステムを基盤として、次の手順でダンジョンを生成します：
- 設計図作成: マップを9つの区画（セクション）に分割
- 部屋配置: 各セクション内にランダムに部屋を生成
- 通路接続: 部屋同士を通路で繋いで歩行可能にする
- マップ描画: 文字によるASCIIアートでダンジョンを表示
生成されるマップは、壁（-, |）、床（.）、通路（#）、扉（+）で構成される、古典的なローグライクスタイルのダンジョンです。
設計図作成
セクションシステム
ダンジョン全体は3×3の9つのセクションに分割されます：
type SectionDefinition struct {
id int // セクションID
area Rect // セクションの範囲
weight int // 部屋生成の重み（確率）
required bool // 必須部屋かどうか
}
type Section struct {
def SectionDefinition // セクション定義
room *Room // 生成された部屋（nil可能）
relay Point // リレー点（部屋がない場合の接続点）
hasRelay bool // リレー点を持つかどうか
}
weightが高いセクションほど部屋が生成されやすく、requiredがtrueのセクションには必ず部屋が作られます。部屋が生成できなかった場合は、relay（リレー点）が接続のために使用されます。
初期化処理（NewDungeon関数）
func NewDungeon() *Dungeon {
// 乱数シードを設定し空のマップを初期化
seed := time.Now().UnixNano()
if s := os.Getenv("DUNGEON_SEED"); s != "" {
if parsed, err := strconv.ParseInt(s, 10, 64); err == nil {
seed = parsed
}
}
rand.Seed(seed)
d := &Dungeon{}
// マップを空白で初期化
for y := 0; y < MAP_HEIGHT; y++ {
for x := 0; x < MAP_WIDTH; x++ {
d.level[y][x] = SPACE
}
}
// 設計図に従ってセクションを登録
for _, def := range createBlueprint() {
section := &Section{def: def}
d.sections = append(d.sections, section)
}
return d
}
初期化では以下の処理を行います：
- 乱数シード設定: 現在時刻をシードとして使用（環境変数DUNGEON_SEEDで固定値も指定可能）
- マップ初期化: 全体を空白（SPACE）で埋める
- セクション作成: 3×3グリッドの各セクションに設定を適用
設計図の作成（createBlueprint関数）
func createBlueprint() []SectionDefinition {
weights := [GRID_HEIGHT][GRID_WIDTH]int{
{3, 2, 3}, // 上段：角が重要度高、中央やや低
{2, 5, 2}, // 中段：中央が最重要
{3, 2, 3}, // 下段：上段と同じ
}
required := map[[2]int]bool{
{1, 1}: true, // 中央は必須
{0, 2}: true, // 右上も必須
}
var defs []SectionDefinition
id := 0
for gy := 0; gy < GRID_HEIGHT; gy++ {
for gx := 0; gx < GRID_WIDTH; gx++ {
// グリッド座標から実際の座標範囲を計算
rect := Rect{
x: gx * CELL_WIDTH, // 25マス間隔
y: gy * CELL_HEIGHT, // 7マス間隔
width: CELL_WIDTH,
height: CELL_HEIGHT,
}
defs = append(defs, SectionDefinition{
id: id,
area: rect,
weight: weights[gy][gx],
required: required[[2]int{gx, gy}],
})
id++
}
}
return defs
}
この関数では、3×3の各セクションに以下を設定します：
- 重み配分: 中央セクション（重み5）が最も部屋が作られやすい
- 必須部屋: 中央と右上の2箇所は必ず部屋を配置
- 座標計算: グリッド位置を実際のマップ座標に変換
部屋配置
基本データ構造
座標とサイズを扱う構造体
プログラムの根幹となる基本的な構造体を見ていきましょう。
// 座標を表す構造体
type Point struct {
x int // X座標
y int // Y座標
}
// 矩形を表す構造体
type Rect struct {
x int // 左上角のX座標
y int // 左上角のY座標
width int // 幅
height int // 高さ
}
Pointは単純にX、Y座標を持つ構造体です。Rectは矩形（長方形）を表現し、部屋やセクションの範囲を定義するのに使います。
Rectには便利なメソッドがいくつか用意されています：
func (r Rect) center() Point {
// 長方形の中央の座標を計算して返す
return Point{r.x + r.width/2, r.y + r.height/2}
}
func (r Rect) right() int {
// 右端の座標を算出する（左端 + 幅）
return r.x + r.width
}
func (r Rect) bottom() int {
// 下端の座標を算出する（上端 + 高さ）
return r.y + r.height
}
これらのメソッドにより、矩形の中心点や端の座標を簡単に取得できます。
部屋の情報を管理する構造体
type Room struct {
area Rect // 部屋の範囲
doorsByDir map[string][]Point // 方向別の扉候補一覧
}
Room構造体は、部屋の位置とサイズ（area）に加えて、扉の候補位置を方向別（”N”、”S”、”E”、”W”）に管理しています。これにより、隣接する部屋との接続時に適切な位置に扉を設置できます。
部屋生成（generateRooms関数）
func (d *Dungeon) generateRooms() {
roomCount := 0
// 必須セクションに部屋を優先配置
for _, section := range d.sections {
if section.def.required {
if d.createRoomInSection(section) {
roomCount++
}
}
}
// 未配置セクションから候補リストを作成
var candidates []*Section
for _, section := range d.sections {
if section.room == nil {
candidates = append(candidates, section)
}
}
// 重み付きランダムで追加部屋を生成（最大6部屋）
maxRooms := 6
for roomCount < maxRooms && len(candidates) > 0 {
idx := pickWeightedIndex(candidates) // 重み付き選択
section := candidates[idx]
if d.createRoomInSection(section) {
roomCount++
}
// 選択されたセクションを候補から除去
candidates = append(candidates[:idx], candidates[idx+1:]...)
}
// 部屋が作れなかったセクションにはリレー点を設定
for _, section := range d.sections {
if section.room == nil {
section.relay = chooseRelayPoint(section.def.area)
section.hasRelay = true
}
}
}
部屋生成は段階的に進みます：
- 必須部屋: 最初に確実に配置
- 追加部屋: 重み付き確率で最大6部屋まで生成
- リレー点: 部屋が作れなかったセクションの接続点を設定
個別部屋の作成（createRoomInSection関数）
func (d *Dungeon) createRoomInSection(section *Section) bool {
area := section.def.area
maxWidth := area.width - 2 // 外壁分を除く
maxHeight := area.height - 2
if maxWidth < 4 || maxHeight < 4 {
return false // 最小サイズに満たない
}
// ランダムなサイズを決定（最小4マス）
roomWidth := randInRange(4, maxWidth)
roomHeight := randInRange(4, maxHeight)
// セクション内での配置位置を計算
xMin, xMax := area.x+1, area.right()-roomWidth-1
yMin, yMax := area.y+1, area.bottom()-roomHeight-1
if xMax < xMin || yMax < yMin {
return false // 配置不可能
}
roomX := randInRange(xMin, xMax)
roomY := randInRange(yMin, yMax)
// 部屋情報を作成
roomArea := Rect{x: roomX, y: roomY, width: roomWidth, height: roomHeight}
room := &Room{
area: roomArea,
doorsByDir: generateDoorCandidates(roomArea),
}
section.room = room
section.hasRelay = false
return true
}
各部屋は以下の制約で作成されます：
- 最小サイズ: 4×4マス
- 配置位置: セクション内で1マスの余裕を持つ
- 扉候補: 生成時に各方向の扉候補も計算
通路接続
隣接関係の構築（buildAdjacency関数）
func (d *Dungeon) buildAdjacency() map[int][]int {
adj := make(map[int][]int)
for i := 0; i < len(d.sections); i++ {
for j := i + 1; j < len(d.sections); j++ {
if sectionsAdjacent(d.sections[i].def.area, d.sections[j].def.area) {
adj[i] = append(adj[i], j)
adj[j] = append(adj[j], i)
}
}
}
return adj
}
func sectionsAdjacent(a, b Rect) bool {
// 左右で接触
if a.right() == b.x || b.right() == a.x {
_, _, ok := overlapRange(a.y, a.bottom(), b.y, b.bottom())
return ok
}
// 上下で接触
if a.bottom() == b.y || b.bottom() == a.y {
_, _, ok := overlapRange(a.x, a.right(), b.x, b.right())
return ok
}
return false
}
この関数では、各セクションが上下左右で隣接しているかを調べ、隣接リストを作成します。隣接判定は矩形同士の境界が一致し、なおかつY軸（または X軸）で重複があることを確認します。
接続関係の決定（generateConnections関数）
func (d *Dungeon) generateConnections(adjacency map[int][]int) [][2]int {
sectionCount := len(d.sections)
if sectionCount == 0 {
return nil
}
connections := make([][2]int, 0)
visited := make(map[int]bool)
start := rand.Intn(sectionCount) // ランダムな開始点
visited[start] = true
pending := []int{start}
// 全セクションが接続されるまで繰り返し
for len(visited) < sectionCount {
var current int
if len(pending) > 0 {
current = pending[rand.Intn(len(pending))]
} else {
// フォールバック処理
for idx := range visited {
current = idx
break
}
}
// 未訪問の隣接セクションを探す
neighbors := adjacency[current]
var nextCandidates []int
for _, nb := range neighbors {
if !visited[nb] {
nextCandidates = append(nextCandidates, nb)
}
}
if len(nextCandidates) > 0 {
// 未訪問セクションと接続
next := nextCandidates[rand.Intn(len(nextCandidates))]
connections = append(connections, [2]int{current, next})
visited[next] = true
pending = append(pending, next)
} else {
// 接続先がない場合は保留リストから削除
for i, v := range pending {
if v == current {
pending = append(pending[:i], pending[i+1:]...)
break
}
}
}
}
// 追加のランダム接続でループを作成
extraEdges := rand.Intn(3)
for e := 0; e < extraEdges; e++ {
a := rand.Intn(sectionCount)
neighbors := adjacency[a]
if len(neighbors) > 0 {
b := neighbors[rand.Intn(len(neighbors))]
if !connectionExists(connections, a, b) {
connections = append(connections, [2]int{a, b})
}
}
}
return connections
}
この関数は最小スパニングツリーの考え方で、全セクションが確実に繋がるように接続を作ります：
- ランダムな開始点から開始
- 未接続の隣接セクションを選んで接続
- 全セクションが接続されるまで継続
- 追加でランダムな接続を作成してバリエーション増加
実際の通路掘削（connectPair関数）
func (d *Dungeon) connectPair(aIdx, bIdx int) {
sectionA := d.sections[aIdx]
sectionB := d.sections[bIdx]
// 共有境界情報を取得
boundary, hasBoundary := sharedBoundaryInfo(sectionA.def.area, sectionB.def.area)
// 各セクションのアクセス点を決定
startDoor, hasStartDoor, startPos := d.accessPoint(sectionA, sectionB, boundary, hasBoundary)
endDoor, hasEndDoor, endPos := d.accessPoint(sectionB, sectionA, boundary, hasBoundary)
// 扉を設置
if hasStartDoor {
d.placeDoorAtPosition(startDoor.x, startDoor.y)
}
if hasEndDoor {
d.placeDoorAtPosition(endDoor.x, endDoor.y)
}
// 境界に沿った整列接続または直接接続
if hasBoundary {
// 境界情報を使って効率的な接続
// （詳細なアライメント処理）
} else {
// 直接的な通路掘削
d.carveCorridorPath(startPos.x, startPos.y, endPos.x, endPos.y)
}
}
2つのセクションを繋ぐ際は：
- 境界分析: セクション同士が共有する境界を分析
- アクセス点決定: 各セクションの適切な接続点を選択
- 扉設置: 部屋の壁にドアを配置
- 通路掘削: 最適な経路で通路を作成
通路生成アルゴリズム
パス探索（findTilePath関数）
func (d *Dungeon) findTilePath(startX, startY, endX, endY int) [][2]int {
type node struct {
x, y int
}
startKey := [2]int{startX, startY}
endKey := [2]int{endX, endY}
front := []node{{startX, startY}} // 優先キュー（コスト0）
back := make([]node, 0) // 通常キュー（コスト1）
dist := map[[2]int]int{startKey: 0}
parent := make(map[[2]int][2]int)
directions := [][2]int{{0, -1}, {1, 0}, {0, 1}, {-1, 0}} // 上右下左
for len(front) > 0 || len(back) > 0 {
var current node
if len(front) > 0 {
// コスト0のマスを優先処理（スタック）
current = front[len(front)-1]
front = front[:len(front)-1]
} else {
// 通常コストのマス（キュー）
current = back[0]
back = back[1:]
}
if current.x == endX && current.y == endY {
break // 目標到達
}
currentKey := [2]int{current.x, current.y}
currentDist := dist[currentKey]
// 4方向を探索
for _, dir := range directions {
nx, ny := current.x+dir[0], current.y+dir[1]
if !d.isInBounds(nx, ny) {
continue
}
cost, ok := d.corridorStepCost(nx, ny)
if !ok {
continue // 通行不可
}
neighborKey := [2]int{nx, ny}
newDist := currentDist + cost
if existing, exists := dist[neighborKey]; exists && existing <= newDist {
continue // より良いパスが既存
}
dist[neighborKey] = newDist
parent[neighborKey] = currentKey
nextNode := node{nx, ny}
if cost == 0 {
front = append(front, nextNode) // 優先処理
} else {
back = append(back, nextNode) // 通常処理
}
}
}
// パスの復元
if _, found := dist[endKey]; !found {
return nil // パスなし
}
var reversed [][2]int
current := endKey
for {
reversed = append(reversed, current)
if current == startKey {
break
}
current = parent[current]
}
// 逆順を修正
path := make([][2]int, 0, len(reversed))
for i := len(reversed) - 1; i >= 0; i-- {
path = append(path, reversed[i])
}
return path
}
この関数は0-1 BFS（幅優先探索）という高効率なアルゴリズムを使用します：
- コスト0: 既存の通路や扉は通行コスト0
- コスト1: 空白地帯は掘削コスト1
- デュアルキュー: コスト0のマスを優先的に処理
これにより、既存の通路を活用しつつ最短経路で新しい通路を生成します。
L字型通路の試行（carveSingleLCorridor関数）
func (d *Dungeon) carveSingleLCorridor(start, end Point) bool {
// 直線で繋がる場合
if d.canCarveStraightSegment(start, end) {
d.carveStraightSegment(start, end)
return true
}
// L字の2つのコーナーを試す
corners := []Point{
{x: end.x, y: start.y}, // 水平→垂直
{x: start.x, y: end.y}, // 垂直→水平
}
for _, corner := range corners {
if !d.isInBounds(corner.x, corner.y) {
continue
}
if !d.canCarveStraightSegment(start, corner) {
continue
}
if !d.canCarveStraightSegment(corner, end) {
continue
}
// L字型通路を作成
d.carveStraightSegment(start, corner)
d.carveStraightSegment(corner, end)
return true
}
return false
}
複雑な経路探索の前に、シンプルなL字型接続を試します。これは処理が軽く、自然な見た目の通路になります。
マップ描画
実行とデバッグ
メイン実行部分
func main() {
dungeon := NewDungeon() // ダンジョン初期化
dungeon.Generate() // 生成実行
dungeon.Display() // 表示
}
func (d *Dungeon) Generate() {
d.generateRooms() // 部屋生成
// 部屋をマップに描画
for _, section := range d.sections {
if section.room != nil {
d.drawRoom(section.room)
}
}
// リレー点を通路として設定
for _, section := range d.sections {
if section.hasRelay {
d.setCorridorTile(section.relay.x, section.relay.y)
}
}
d.connectSections() // セクション間接続
}
実行は以下の順序で進みます：
- 初期化: 空のダンジョンを作成
- 部屋生成: セクション内に部屋を配置
- 部屋描画: マップ上に壁と床を描く
- リレー設定: 部屋のないセクションに接続点を設置
- 接続処理: 全セクションを通路で繋ぐ
- 表示: 完成したダンジョンを出力
デバッグ機能
const debugLogging = false
func debugf(format string, args ...interface{}) {
if !debugLogging {
return
}
fmt.Printf("[DEBUG] "+format+"\n", args...)
}
debugLoggingをtrueに変更すると、詳細な処理ログが出力されます。通路生成やセクション接続の内部処理を追跡できるため、アルゴリズムの理解や問題解決に役立ちます。
環境変数での制御
seed := time.Now().UnixNano()
if s := os.Getenv("DUNGEON_SEED"); s != "" {
if parsed, err := strconv.ParseInt(s, 10, 64); err == nil {
seed = parsed
}
}
rand.Seed(seed)
環境変数DUNGEON_SEEDを設定すると、同じレイアウトのダンジョンを再現できます：
DUNGEON_SEED=12345 go run dungeon.go重要なユーティリティ関数
重み付きランダム選択（pickWeightedIndex関数）
func pickWeightedIndex(sections []*Section) int {
// 全体の重み合計を計算
weight := 0
for _, section := range sections {
weight += max(1, section.def.weight)
}
// 重み範囲内でランダム選択
choice := rand.Intn(weight)
for idx, section := range sections {
choice -= max(1, section.def.weight)
if choice < 0 {
return idx
}
}
return len(sections) - 1
}
この関数により、重みの高いセクションほど選ばれやすくなります。例えば重み5のセクションは重み1のセクションより5倍選ばれやすくなります。
範囲制限関数（clamp関数）
func clamp(v, lo, hi int) int {
if v < lo {
return lo
}
if v > hi {
return hi
}
return v
}
値を指定範囲内に収める関数で、座標計算でマップ境界を超えないようにするのに使用されます。
Bresenhamライン描画
func bresenhamLine(x0, y0, x1, y1 int) []Point {
var points []Point
dx := abs(x1 - x0)
dy := -abs(y1 - y0)
sx := 1
if x0 > x1 {
sx = -1
}
sy := 1
if y0 > y1 {
sy = -1
}
err := dx + dy
for {
points = append(points, Point{x: x0, y: y0})
if x0 == x1 && y0 == y1 {
break
}
e2 := 2 * err
if e2 >= dy {
if x0 != x1 {
err += dy
x0 += sx
}
}
if e2 <= dx {
if y0 != y1 {
err += dx
y0 += sy
}
}
}
return points
}
Bresenhamアルゴリズムは、コンピュータグラフィックスで直線を描画する古典的な手法です。2点間の格子点上の最短パスを効率的に計算し、通路の直線部分を生成するのに使用されます。
まとめ
このプログラムは、Rogueライクゲームの核心である「ランダムでありながら必ず歩行可能なダンジョン」を生成する洗練されたアルゴリズムの実装です。
ポイント：
- 構造化設計: データ構造を明確に分離して管理
- 段階的処理: 複雑な問題を小さな手順に分割
- グラフ理論: 接続性を保証するスパニングツリーの活用
- 効率的探索: 0-1 BFSによる最適化された経路探索
- 確率的生成: 重み付きランダムによる自然なバリエーション
ローグライクゲーム開発やプロシージャル生成に興味がある方は、ぜひこのコードを基盤として、より複雑なダンジョン生成や、モンスター配置、アイテム生成などの機能拡張にチャレンジしてみてください。
コメントを残す