ダンジョン自動生成

**名前は開発中のものです。** · 02/07/19 22:06

「風来のシレン」みたいにランダムでダンジョンを作るのって
どうやるんですか

**名前は開発中のものです。** · 03/10/13 11:31

>>132
boidみたいに、できるといいね

**132** · 03/10/13 13:20

自分でプログラミングするまでの気力が生じないので、似たようなモノを探してみた。

アリの巣作り（画像紹介のみ）
ttp://acolyte.t.u-tokyo.ac.jp/~kaityo/ant2.html

巡回セールスマン問題を「アリのフェロモン」をシミュして解くアプレットらしい。
ttp://uk.geocities.com/markcsinclair/aco.html

ズバリのものは見つけられんかった。自分で作るしかないか…

**名前は開発中のものです。** · 03/10/14 11:56

1.部屋生成
2.通路は((奇数ブロック*i)進んだら曲がる)*n
3.1に戻る
を任意数繰り返したら終了、ってのでやってみた。最初と最後の部屋には階段もつけてみた。
たしかに>>82みたいにきっちりやろうとすると大変だけど、「ダンジョンらしきもの」を自動生成させるのはそれほど難しくはないね。
初めてやってみたけどこれ面白いわ。もちっとがんばってみる。

82 · 03/10/24 23:55

135に期待して保守

**名前は開発中のものです。** · 03/12/03 22:01

http://www.infoseek.livedoor.net/~koushi_okada/links/hsptips/hsptips5_2.html

**名前は開発中のものです。** · 03/12/04 00:54

俺が昔つくったやつは
１　X*Yの外壁をつくる。中は全部床。これをダンジョンと呼ぶ。
２　ダンジョンの中にX個の壁を置く。位置はランダム。
３　ダンジョンの中にX*Yの部屋をZ個作る。部屋は外周が全て壁で中が全て床。
４　入り口をランダムで一つ作る。
５　入り口から深さ優先の探索で床に深度を付ける。
６　深度の最大値がXより小さかったら、一番深い床に接してる壁を一つ床に変えて４に戻る

パラメータをうまく与えてやればそれらしいものが出来たよ。
ゲーム作成には挫折したが。

**名前は開発中のものです。** · 03/12/04 00:56

×　４に戻る
○　５に戻る

**名前は開発中のものです。** · 03/12/04 22:39

>138

すまんが何がどうなのかさっぱりわからん。
なんで全部床なところにさらに床と壁を作るのか？
１～３と６にあるＸはどこまで同じものなのか？
深度がなにを意味しているのか？

**名前は開発中のものです。** · 03/12/05 00:12

>>138
まず、ｘとかｙとか同じものを違う意味で使うのは止めたほうがよいと思った。

**名前は開発中のものです。** · 03/12/05 01:35

わかりにくくてスマン。
しかも深さ優先じゃなくて幅優先の探索だった。

深度は入り口からその床までの最短歩数。
Xは全部別物。

スゲー単純に言うとある程度の深さになるまで壁→床、床→壁を適当に繰り返してるだけ。
部屋を作って通路で繋ぐという考え方ではないので
ここで議論してるのとは全然違うものでした。

**名前は開発中のものです。** · 03/12/06 17:18

だからさ。５，６が全然分からない。

・幅優先・・なんのこと？
・最短歩数・・なんのこと？直線じゃなくてもいい？

あと、結局どんなダンジョンになるかわからん。

**名前は開発中のものです。** · 03/12/06 20:27

ソースをＵＰだ。それで全て解決する。

**名前は開発中のものです。** · 03/12/06 22:34

（´Д｀）　えーと。

１．部屋数を一定数＋乱数に決定
２．壁で埋め尽くされたマップに部屋を重ならないように配置
３．開始地点・終点をどこかの部屋の中に指定
４．開始地点から終点までの通路を１＋乱数個作成

とまぁ、言うのは簡単なんだが
アルゴリズムにしろってーと難しいな・・・（´Д｀）ハァ。

**名前は開発中のものです。** · 03/12/06 23:51

部屋
部屋　９８７
部屋　　　６
部屋　３４５
部屋１２

深度ってこんな感じか？でも廊下が巻いたらどうするんだ？
９から下に行って右に行ったら？
同じ部屋についた場合とか廊下が交差したりすぐ隣を通って広くなったりで
これだけだとあまり廊下っぽくならない気がするぞ。

**138** · 03/12/07 04:08

探索のアルゴリズムは一般的なものだと思ってた

>>144
ソースはPC98を物置から引っ張り出さないとならないから面倒
でも面白そうだから、暇なときにでもサルベージします。

>>146の例の空白が壁を現しているなら
０がダンジョンの入り口だったとして下のようになる。

５４
４３　９８７
３２　　　６
２１　３４５
１０１２

続き · 03/12/07 04:08

深さ９では狭いと判断してランダムで床/壁を微調整時したとき、
９の下、９の左下が壁から床になると

５４
４３　５６７
３２３４　６
２１　３４５
１０１２

になる。

書いてて思い出したが、６の「一番深い床に接してる壁を一つ床に変えて」は記憶違い。
ランダムで床を５個置く、壁を５個置く、とかやってたような気がする。

俺の作ってたやつは部屋の概念が無かったので、
床がたまたま四角く残ってたら部屋って感じ。
イベントの位置は深度で決定してた。

全然ローグ系じゃなくてｺﾞﾒﾝﾈ

**名前は開発中のものです。** · 03/12/07 10:16

確かにローグ系というより、アリの巣っぽいものができそうだ。
でも、参考になったよ。おかげで下の方法を思いついた。
138と比較するとローグ系の廊下は一マスごとに方向をランダムに決めているんじゃなくて
他の部屋を目指した直線的なランダムってことだろうな。

A：掘り始めの部屋と行き先の部屋をランダムに決める。
B：XとY、どちらかを先にあわせるか決めて廊下を延ばす。
C：一方が合えばもう一方を合わせる方向へ。
D：数十回に一回、進行方向をランダムに変える。
E：別の廊下と繋がったらそこで終了。

まだ欠点はあるだろうけどたぶんこんな感じか？

**名前は開発中のものです。** · 03/12/17 19:26

大昔こんな感じで作った気がする
作りたいタイプによってアルゴリズムを変えてた

迷路風
　アルゴリズム辞典に出ているようなやり方で
　所々壁を消したりしてアクセントを付けてみたり
ローグ風？
　部屋を適当に配置し、適当に通路でつなぐ
　行き止まり通路を作ってみたり
洞窟風？
　適当に掘り進んで、適当に太らせる

**名前は開発中のものです。** · 03/12/23 16:22

>>150
その適当って個所のアルゴリズムを書けよアホ

**名前は開発中のものです。** · 03/12/23 17:22

「大昔」に作ったやつだから忘れちゃったんだよ。きっと

**名前は開発中のものです。** · 04/01/13 23:46

150が思い出すのを期待して保守

**名前は開発中のものです。** · 04/03/18 05:26

なんとなくage

**名前は開発中のものです。** · 04/05/03 20:45

>>17 >>93
Nethack ではダンジョンの深い所では古典的な迷路が(いっぱい)出現します。
ミノタウルスも(いっぱい)いるよ。
とってもつらいけど、神様がくれた試練なので頑張ろうと思いました。

**名前は開発中のものです。** · 04/05/30 09:02

テス

◆wvM6C8VLoU · 04/06/09 23:07

>>151
超亀レスで別人だが自分が昔考えたアルゴリズムは

１．適当な部屋を選択
２．その部屋から一番近く部屋を探す。
３．それぞれの部屋から縦横に直線状に通路掘る
をすべての部屋に通路が繋がるまで繰り返す。
　　　□

□
つまり上の場合（□は部屋）
　　　□
　　　↓
□→Ｘ
矢印方向に通路を掘っていけばＸ地点で通路が繋がる。
例外的な場合として、下みたいな場合があるが、書くまでもないので省略
□

□

◆wvM6C8VLoU · 04/06/09 23:09

あと掘る方向は」

◆wvM6C8VLoU · 04/06/09 23:11

　　←□
↑　
□
でもかまわない。
その他細々したものがあったと思うが思い出したらまた書く。

**名前は開発中のものです。** · 04/06/10 16:16

nethackのランダムマップは
マップが重要じゃなくてランダムイベントを#でつないでるんだよな

だから面白いんだと思った

**名前は開発中のものです。** · 04/06/13 12:09

>>157
それだけだとこのように孤立したエリアができる可能性がある。

　　□　□
　　┃　┃
□━┛　┗━□

すべての部屋に通路は繋がっているが、部屋同士が繋がっていることにはならない。
厳密にやるなら、すべての部屋が繋がったかどうかのチェックが必要

あと「部屋から部屋へ通路を伸ばす」のではなく「部屋Aからの通路と部屋Bからの通路を繋げる」というアルゴリズムならば、その合流点Ｘをどう求めるのか気になる

◆Mn5mzn8hAQ · 04/06/13 19:51

俺はあんましシレンとか好きでないので
内容がよくわからんというか
思いっきり忘れたんだが
こういう感じのマップを自動生成できたら
結構イケテルか？
教えてくれろ。

□□□□□□□□□□□□□□□□□□□
□■■■■■□□□□□□□□□□□□□
□■■■■■■■■■■■■□□□□□□
□■■■■■□□□□□□■□□□□□□
□■■■■■□□□□□□■□□■■■□
□□□■□□□□□□□□■□□■■■□
□□■■■■■■■■■■■■■■■■□
□□■□□□□□□□□□■□□■■■□
□■■■■□□□□□□□■□□□□□□
□■■■■□□□□■■■■■□□□□□
□■■■■■■■■■■■■■□□□□□
□■■■■□□□□■■■■■□□□□□
□□□□□□□□□■■■■■□□□□□
□□□□□□□□□□□□□□□□□□□
場所とってしまってすまんね～

**名前は開発中のものです。** · 04/06/13 21:03

意外と出来ないんだよな
トルネコタイプ

**名前は開発中のものです。** · 04/06/13 21:10

いや、トルネコはRogue起源な訳で、NetHack起源な訳で、、

つまりNetHackのソースでも見ればいいだろ(´д`)

**名前は開発中のものです。** · 04/06/13 21:18

いきなりNethack読むと軽く死ねると思う

◆Mn5mzn8hAQ · 04/06/13 21:28

とりあえずローグのソース読んでたが寝れる。
死ねるというか寝れる。
で>>162はどうかいな？

**名前は開発中のものです。** · 04/06/13 21:34

そうなのかー、かー。読んだ事無かったから、ｽﾏｿ
162は悪くないけど全ての部屋にほぼ直通で行ける状態はどうかと。
ある程度の回り道を要求する方がいいと思いますた。

◆Mn5mzn8hAQ · 04/06/13 21:43

>>167
さようか一筋縄ではいかんな。
ソース読んだ方が早いかな。

ちなみにローグの生成部分のソースファイルは1000行未満で
ほんとに関係あるのは
そのうち一部分だけなので実はたいしたことがない。
でもコメントついてねぇし。。orz..ぐぅ

**名前は開発中のものです。** · 04/06/13 23:22

じゃあ、みんなでソースを読み進める勉強会なんてしませんか？

◆Mn5mzn8hAQ · 04/06/13 23:34

>>169
いいこと言うなぁ。
仕切ってくださいくださいください

**名前は開発中のものです。** · 04/06/14 03:47

迷路生成の部分だけ抜き出して
貼ってちょうだい

◆Mn5mzn8hAQ · 04/06/14 04:32

>>171
貼り付けられるほどは短くないジョ。。。

ソース付ウィンドウズ版ローグクローン２
ttp://www.freak.ne.jp/HEPOPO/
のRogue Clone II

部屋生成の理屈はわかったが
通路つなぎの部分で苦戦中。

◆Mn5mzn8hAQ · 04/06/14 05:09

んでもってローグに関する
（厳密にはローグクローン２系）の
我輩が読んでみた限りの情報提供しようとおもふ。
参考になるかわからんが（読み間違えてるかもしんないし）

AppMain.cがエントリポイントを含むソース
（Win版でない人は多分Main.c）
135行目のfor(;;)ループの部分の
make_level();が生成の関数。
level.cで定義されている。
これ以外で生成にからんでくるファイルは
room.cとrogue.h位だがちょっと参照する程度。
＜つづく＞

◆Mn5mzn8hAQ · 04/06/14 05:13

生成は非常に大雑把に言うと
①３ｘ３に分けたエリアのうち８箇所に部屋を設置する
②一定の法則で対となる部屋を決める
③3回方向転換しながら通路を結ぶ
という段取り。
＜つづく＞

◆Mn5mzn8hAQ · 04/06/14 05:24

①と③はそれとなくなんとなくわかったような気分。
しかし②の部分がまだ理解不能。
>>157 で指摘している繋がりチェックを省いて
華麗かつスマートなアルゴリズムで選定するんだろう。
寝ぼけた脳みそでは理解できんねぃ。朝になっちゃったねぃ。
ぐぅ。
他いろいろ気づいたことあるんですが長くなったのでさやうなら。
＜つづかない＞

◆Mn5mzn8hAQ · 04/06/14 05:53

ごめん上の>>157ての>>161の間違いです脳はすでに睡眠しています

**名前は開発中のものです。** · 04/06/14 08:05

>>108の穴掘り法は、３次元の迷路も作れそうだな。
というかこのページ、迷路ゲームの面白さへの考察まで書いてある。
なかなかいい大学だな。

**名前は開発中のものです。** · 04/06/14 09:28

>>161の問題は最初の部屋から最短経路探索、領域拡張法でいいで解決しない？

**名前は開発中のものです。** · 04/06/14 09:47

で、もまいら具体的なソースはできたのかい？

**名前は開発中のものです。** · 04/06/14 11:25

思っていたより厄介なソースだなぁ、コメント少ないし。

get_rand(x, y);
xからyまでの範囲の乱数値を得る

例）
get_rand(5, 2);
5から7までの間の乱数値

**名前は開発中のものです。** · 04/06/14 11:26

coin_toss();
0か1の値をランダムに返す

◆Mn5mzn8hAQ · 04/06/14 12:04

>>180
なるほど、ここで判明した関数かきだして
リファレンスみたいにすれば
みんなで読めるね

と、get_randの説明がおかしいある・・

get_rand(5, 2)なら２～５の乱数を返す
get_rand(5, 7)なら５～７の乱数を返す　だわいね

乱数に関する関数はrandom.cに入っております。

>>178
最短経路探索、お、と思ったけどローグのソースはなんか違う気がしる

>>179
他のしとは知らんけど俺はまだ読むばかりなり。アンタも読むなり。

**２時間しか寝てませんよ？** ◆Mn5mzn8hAQ · 04/06/14 12:19

画面ORマップまわりの重要な定数（Rogue.h）

#define ROW1 7
#define ROW2 15
#define DROWS 24/*縦の最大*/

#define COL1 26
#define COL2 52
#define DCOLS 80/*横の最大*/

※～1、～2は
マップを３ｘ３の領域にきりわける際に利用している

**２時間しか寝てませんよ？** ◆Mn5mzn8hAQ · 04/06/14 12:54

●rm = room・・・部屋を表現する構造体。
Y2、X2、Y1、X1、door[4], is_room で構成される
is_roomはR_NOTHIN、R_ROOM、R_MAZE、R_CROSSなどの定数が入り、
部屋の種類をあらわす。

●door = dr・・・ドアに関する情報をつめこむ構造体
ペアになる部屋番号、ペアのドアのY、ペアのドアのX、X、Yで構成される

一つの部屋は最大４つのドアをもっていて
しかもペアになる部屋のドアの座標ももっており
かつ部屋ではなく通路になったりもする、と。

**名前は開発中のものです。** · 04/06/14 13:08

>>183
まだ読みかけだから間違っているかもしれないけど補足すると・・・

部屋の最大数は9で、80x24の空間をを9個に分割して
部屋を配置しているっぽい。

例外はBIG_ROOM。空間内に一部屋だけという状態。部屋のサイズは画面内でランダム。
これはゲーム中、いずれかの階に一度だけかつ 1/100の確率で出現する。

**名前は開発中のものです。** · 04/06/14 13:09

>>185
あ、0lapHs9H氏の書き込みみると、9個じゃなくて8個なのかな。

**２時間しか寝てませんよ？** ◆Mn5mzn8hAQ · 04/06/14 13:17

>>185
あ、ほんとだ部屋の数９だね
for WonderWitchのソースはなぜか８ですた

#define MAXROOMS 9（rogue.h)

100分の１の確率なのか、なーる

**２時間しか寝てませんよ？** ◆Mn5mzn8hAQ · 04/06/14 13:24

ぶっちゃけてしまうが
風来のシレン月影村の怪物インターネット版の体験版
を画面キャプチャしながら4階層遊んでみたが
今わかっている時点だけであきらかにRogueと
生成方法が違いますケドｗ

**名前は開発中のものです。** · 04/06/14 14:21

rogueのソース読むのもいいけど自分で書いちゃった方が早いし面白いんじゃないかなあ

**名前は開発中のものです。** · 04/06/14 16:11

そうして、他人のソースを読まずに突き進んできた奴があｗｑせｄｒｆｔｇｙふじこｌｐ；

**名前は開発中のものです。** · 04/06/14 17:06

せっかくだから斬新な自動生成段ジョンを開発しようぜ

**名前は開発中のものです。** · 04/06/14 19:04

ダラダラと別のことしながらローグIIのソース読んでる。
部屋生成について補足。make_level()から呼び出される、make_room()は以下の通り。

画面を3x3に分割して、その分割された領域内に矩形を作ることで部屋にしている。
サイズはランダムで、領域内の左上からの位置もランダム。この時、他の領域には
踏み入らないように計算しているので、部屋の重なりをチェックする必要はない。

必ず9個の部屋があるわけでない。条件によって部屋のあるなしが決められる。
条件は単なるランダムではなく、ある程度の法則性がある。
これはゲームバランス的なものだと思うので詳しい説明は省略。
1/2の確率で縦に3部屋並ぶ構成になる・1/2の確率で3種類の部屋の並びになる、
一つのフロアには、少なくとも3つの部屋が生成される、とか。

部屋のあるなしを決定したら、フロアマップに部屋の構成を記録すると同時に、
部屋の位置やサイズを別に記憶しておく。

**名前は開発中のものです。** · 04/06/14 19:18

おっと、一部読み間違えた。

>部屋の位置やサイズを別に記憶しておく。
サイズではなく、左上の座標と右下の座標っぽい。

あと、条件チェックで部屋がないと判断されても、先に計算した部屋の位置・・・
つまり、小領域内での左上と右下の座標値を保存している。どうやら通路？を
生成する時に利用しているっぽい。

ぐぅ ◆Mn5mzn8hAQ · 04/06/14 19:40

だいたいわかったんだが、
わからないのが
ペアの部屋を選定するコード。

add_maze/make_maze。
add_mazeは>>193の「部屋ではなく通路にする」場合の処理で
座標を保存して範囲を限定することで
どこまでも無駄に通路を延ばしてしまうことを避け
るためと読んだ。
月曜日は面白いテレビ番組がなくて退屈である。

**名前は開発中のものです。** · 04/06/14 19:42

部屋を作ったら、次は迷路の作成らしい。通路ではない。

9個の小領域内に、ある条件を満たしたら、迷路を作る。
基点は先の部屋を作成した時に保存した左上の位置から、掘り進む。
1回（1文字）掘るごとに1/3の確率で進行方向を変える。
掘り進む方向+1と、その左右方向（画面の左右ではなく進行方向に対して）、
それから、掘り進む方向+2を調べて、すでに掘った通路があったら迷路作成終了。
掘る範囲は先にランダムに決定した部屋サイズ内なので、小領域を出ることはない。

迷路が生成される条件はゲームバランス的なので詳しい説明は略。
最初の階では絶対に迷路がない。１６階以降は階を増やすごとに迷路が作られる確率が高まる。
迷路は１つの階につき１つっぽい。

**名前は開発中のものです。** · 04/06/14 19:45

>>195は、make_maze()の処理内容です。

**名前は開発中のものです。** · 04/06/14 19:49

>>195
また読み違えた。

> 掘る範囲は先にランダムに決定した部屋サイズ内なので、小領域を出ることはない。

掘る範囲は少領域内。
基点が、部屋サイズ内。

ぐぅ ◆Mn5mzn8hAQ · 04/06/14 19:52

ははぁなるほど。
するってぇと通路への変更は別のコードか。

**名前は開発中のものです。** · 04/06/14 19:57

>>198
関数名だけみると、通路&ドア作成は、connect_rooms()内っぽいですよ。

**名前は開発中のものです。** · 04/06/14 20:12

迷路を作ったら、hide_boxed_passage()を実行してる。

処理内容は、作った迷路をところどころHIDDEN属性にする。
つまり、先に迷路を掘ってから迷路の一部をHIDDEN化してる。
このルーチンは、迷路だけでなく、通路作成時にも呼び出されてる。

隠し処理は3階以降にしか発生しない。あとはゲームバランス的な条件で。

**名前は開発中のものです。** · 04/06/14 20:14

というわけで、add_mazes()もおしまい。

>>197は間違いで、やっぱり掘る領域は部屋サイズだったけど、まぁいいや。

ぐぅ ◆Mn5mzn8hAQ · 04/06/14 20:16

>>199
ああ、通常の部屋同士の通路掘りはそれなんだけど、
229行で部屋でも迷路でもないものははじかれるから
それ以外に部屋を通路にするロジックがあるのではないかと
おもて。

R_CROSSという定数がアヤシイ・・
fill_out_level()とfill_it()がアヤシイ・・
とかおもてました。
最後に調整してるんかな、とか。
でもなんか違う気もするし・・
まぁ割と瑣末な部分なので
この時点で突っ込まないでもいいのかもしれんが。

**ぐぅ＞腹ペコ** ◆Mn5mzn8hAQ · 04/06/14 20:29

>>200
ほほぅ。そうなんだ。ソース読むの早いなぁ。

部屋同士を接続するアバウトなしくみの見当ついた。
０１２
３４５
６７８
とわかれているエリアで
ランダムに部屋を選んで、（ここでは仮に０とすると）
１，２，３，６のエリアの部屋に接続に行く。
選んだ部屋が４だったとすると５と７に接続にいく。
実は６にも接続に行ってしまうが、
connect_roomsで実際に接続する際、行か列のいずれかがあっていないと
処理を終了するので結局６には接続しない。
これをランダムな順番で０～７について行う（８はイラン）
つまり、
右、さらに右、下、さらに下の4箇所に接続に行く。
非常にアバウトだが、
これが接続先選定のアルゴリズムであった。タブンネｗ
夕飯買ってきてそれからそれからもうちっと読んでみます。

**名前は開発中のものです。** · 04/06/14 21:06

連続投稿制限に引っかかって、ふてくされてた。

3x3の領域内に部屋と迷路を作ってから、迷路の部分隠しをしたあとは、
mix_random_rooms()で3x3の小領域の情報を10回ほどシャッフルしてるっぽい。
領域単位での入れ替え。

・・・すでに部屋とか迷路をdungeon[][]内に書き込んでるけど、
そんなことしていいのか？どこか読み違えてるかも。

というわけで、そろそろ通路の処理に入りそうなんだけど、ここからが面倒っすね。
とりあえずアミュレットは26階以降にでるっつーことで。

**ぐぅ＞腹ペコ** ◆Mn5mzn8hAQ · 04/06/14 21:29

>>204
そうそう、mix_random_rooms()でしっちゃかめっちゃかと俺も悩んだw
でも冷静によむと、
mix_random_rooms()はrandom_roomsをシャッフルするだけで
肝心のroomsはいじられないので大丈夫だったりしる。
random_roomsはランダムに部屋選ぶのに参照しるだけの配列にゃり。

部屋同士の接続はこれまたアバウトにいうと
部屋の出入り口を向かい合わせにつくって（dirとrevに向きを設定)
通路を延ばして途中で向きかえて座標をあわせて再度通路をのばして
ドッキングしてるだけ

というか、細かい話抜きにしると
これでほぼ全容はわかったことになるんだなぁ。

**名前は開発中のものです。** · 04/06/14 21:53

ソースに日本語コメントつけてうぷ汁

**ぐぅ＠満腹** ◆Mn5mzn8hAQ · 04/06/14 21:59

>>206
なんかくれるか？

**名前は開発中のものです。** · 04/06/14 22:10

>>205
なるほど、そっちだったか～。
深読み＆変数名勘違いのトラップひっかかってました。

**ぐぅ＠凍結** ◆Mn5mzn8hAQ · 04/06/14 22:35

隣り合っていても部屋と部屋を繋ぐ通路がなかったりしるのは
どのような理屈であろうか。

**名前は開発中のものです。** · 04/06/14 23:18

>>200の続き。
部屋と部屋をつなぐ処理・・・は>>203ですが、ちょっと補足。

１つの小領域につき1度、右とその右、下とその下の4箇所の
小領域（にある部屋）に対して通路を作成する。

connect_rooms();
まず、向かい合わせになっているそれぞれの部屋の壁に対して、
ランダムな位置に扉を作成する。そこから通路を延ばす。

draw_simple_passage();
通路は2回曲がるように作成される。スタート地点の扉から
ランダムな長さまで直線をひいて、進行方向を変えて、そこからゴールの扉の
縦座標（or横座標）まで直線をひいて、進行方向を扉の方にして、
そこからゴールの扉まで直線をひくだけ。進行方向を変えるとかいうのは90度向きを...
とかではなく、部屋の位置関係が上下であれば、下にひいて、右か左にひいて、また下ひく
という、ただの条件分岐と線をひくためのfor()ループ三回。

**名前は開発中のものです。** · 04/06/14 23:28

通路を作成したら、12%の確率で通路の一部を隠す。
迷路作成時に呼び出した、hide_boxed_passage()と同じ。
そうそう、小領域をまたぐ場合...つまり、>>200の図でいうと、0から2とか、
0から6へ通路を作成した場合には、その中間の小領域(1 or 3)には、
R_CROSSという部屋扱いになるけど・・・これが何を意味するのか、今はわからない。
もちろん、1と3に部屋があったら、通路は作成されない。
あとは、is_all_connected()とfill_out_level()を読んだらオシマイ。

ナゾというか、勘違いかもしれないけど、隠し扉ってなかったっけ？
あれっていつ作ってるんだろう？

**ぐぅ＠凍結** ◆Mn5mzn8hAQ · 04/06/14 23:42

R_CROSSは
R_ROOMでもR_MAZEでもR_NOTHINGでもないエリア（というか部屋）
connect_rooms()の最初の条件文ではじかれるエリア、
はやい話、通路を延ばせない場所でいいんでないかと。
十字路ってみかけないものな。

put_door()の最後の方の
if ((cur_level > 2) && rand_percent(HIDE_PERCENT)) {
dungeon[*row][*col] |= HIDDEN;
は隠しドアとは違うの？ちゃんと読んでないからわからんけど。

**名前は開発中のものです。** · 04/06/14 23:46

通路を一本作成したら、全ての部屋がつながっているかを調べる。

is_all_connected();
9つの小領域分用意された、部屋訪問フラグをクリアする。同時に、部屋が
あるかどうかを調べて、あれば、その部屋の番号を覚えておく。(starting_room)
その部屋から訪問調査する。

visit_rooms(roomnum);
roomnum部屋の訪問フラグをオンにする。
roomnum部屋にある4つの扉に対して・・・
扉から接続されている別の部屋の扉を調べて、
その部屋に対してvisit_rooms()する。再帰呼び出しですよ。
※先に書き忘れたけど、部屋に扉と通路を作成する時に、どこの部屋の
扉につながっているのかを記録してあるので、それを参照している。
また、一つの部屋には最大で4つの扉が設置される。上下左右の壁に一つずつ。

全部屋訪問フラグがONになっていれば、全部屋が接続されているとみなされる。
なぜか、
if ((rooms[i].is_room & (R_ROOM | R_MAZE)) && (!rooms_visited[i])) {
部屋だけでなく、迷路も部屋と同じ扱いになってる。

**ぐぅ＠氷解** ◆Mn5mzn8hAQ · 04/06/14 23:51

おおお、謎がほぼすべて解けた
ヽ(｀Д´)ノうぉ～

あれ、部屋が通路になってしまう仕掛けはいったい・・

**名前は開発中のものです。** · 04/06/14 23:51

>>212
隠し扉それです、ThanX！

>>209
その１ ... 隠し扉
その２ ... is_all_connected();が真の場合、通路作成のfor()ループをbreakしてます。
つまり、ぐるっとまわって別の部屋へつながっている場合、直通路は作成されないのだと思います。

**名前は開発中のものです。** · 04/06/14 23:59

fill_out_level()ながーい！休憩。

**ぐぅ＠氷解** ◆Mn5mzn8hAQ · 04/06/15 00:02

make_room()内の
if ((rn != r1) && (rn != r2) && (rn != r3) && rand_percent(40)) {
goto END;
}
の処理、必須の3部屋でなければ４０％の確率で
通路に変貌すると見た。つぅか既出だったっけかな・・

**ID変わっちゃった** · 04/06/15 01:58

fill_out_level()はよくわからない。
部屋に扉がない場合（どこにもつながってない壁がある）、
行き止まりの通路を作成してる？
まぁ、ローグの部屋と通路の作成方法はこれでわかった、ということでいっかな。

このアルゴリズムのキモは“空間を3x3に分割する”ということに尽きますね。
これで部屋の重なりを防げるし、ある程度のばらつきを保証できるわけです。

**ぐぅ＠氷解** ◆Mn5mzn8hAQ · 04/06/15 02:25

>>218
ｳﾝｳﾝ
おれっちも3X3が肝とおもふさ～
あと、再帰して繋がりチェックしるやつ
あれないと全部の部屋がつながってしまうわけだけど
ランダムな部屋から通路つくるから絶妙に無駄な通路ができたりする。
必ずしも最低限の通路ではないちうとこもよくできてる。

まとめでもアップしようと思ったけど（カッタルイからｗ）やめて
このアルゴリズムの簡易版でも作ってアップしようかな。

ID変わっちゃったさんありがとう
おかげでかなりスムーズに解析できた。
というわけで、とりあえずどもおつかれさました～

**名前は開発中のものです。** · 04/06/15 16:40

ローグのソース解析お疲れさんです
労をねぎらう意味で、
Delphianで人気の「Delphiゲームプログラミングのエッセンス」
からロジックを転載します。

フロアを3×5のブロックに分ける
1ブロックは、10×10のマス
　　　　　　　　　部屋番号
　□□□□□　0～4
　□□■□□　5～9
　□□□□□　10～14

部屋の数は、5～10として、最低3個は偶数の部屋番号に配置する
1ブロックには、最大9×9マスの部屋が作られる。
（1マス分は通路に充てる。）
1ブロックには、必ず部屋か通路が存在する。ただし■は何も無し。
2と12（■の上下にあるブロック）はどちらかを必ず両隣とつなぐ。
2と12を隔てて左右のフロアで各6ブロック毎に部屋や通路を作成する。
そのとき通路を繋ぐロジックは、絶対に繋がっていない部屋を作らないこと。

これが基本。
3×3のブロックに分けるロジックよりは、ダンジョンっぽい造りになると思う
後は、部屋を迷路状にしてしまうとか、ブロックをまたいだ中部屋をつくるとか、
隣り合わせのブロックに向かう通路を必ず作るとか（円形のフロアになる）、
適当に部屋や通路を加工していけば面白くなるかもね。

**ぐぅ＠夜更かし** ◆Mn5mzn8hAQ · 04/06/16 03:10

このようなものを生成できるようになりました。
らしくなってるじゃろうか？

http://namihei.zone.ne.jp/upup/up/12992.jpg
http://namihei.zone.ne.jp/upup/up/12991.jpg

**名前は開発中のものです。** · 04/06/16 06:49

>>221
おおっ、トルネコっぽい。グッド。

**名前は開発中のものです。** · 04/06/16 17:06

>>221
いい感じだね。
しかも、ローグのソースをもとにちょこっと拡張しました？

せっかく結果も出てきたことですし、
ここらで、ダンジョン自動生成のルールを決めたらどうでしょうか？
とりあえず、たたき台
1.「風来のシレン」を習い、1フロアの面積を50x30とする
2.1フロアの情報は、部屋・通路・壁の3種類として、出力を区別する
3.サンプル出力は、画像とし、2パターン以上提出する

意見等あればどうぞ。

**名前は開発中のものです。** · 04/06/16 18:17

いや、技術的な話は、もう特にないんだよ。
ここまでくるとあとはゲームバランスになってしまう。
１フロアに部屋をいくつ配置するのかっていうのは、
腹の減り具合とか、敵の強さとかに依存するし。

**ぐぅ＠腹ペコ** ◆Mn5mzn8hAQ · 04/06/16 18:30

>>222
さんくすこ
究極的ダンジョン生成エンジンを開発して
それはもう愉快なローグ系携帯アプリを作るのが夢ですの。
もちろん主人公はｶｼﾜﾓｰﾁですわ。

>>223
現状１フロアは６４ｘ４８。
４ｘ３のエリアにわけて生成。
部屋を配置して通路でつないでるだけ。

ここまできて気づいたのだが
俺っちには今のところ
「どんなマップを生成したいのか」という具体的なビジョンがない。
究極的てなんやねん、て話。
夕飯買いに逝ってきます。

**名前は開発中のものです。** · 04/06/16 19:21

ローグ系アルゴリズムが落ち着いたところでこんなものを放り出してみるテスト
ttp://www.aarg.net/%7Eminam/dungeon.cgi

**ぐぅ＠アイスクリーム** ◆Mn5mzn8hAQ · 04/06/16 19:31

>>226
むぅ
それすごいね。
それで生成したマップで内容がシレンだったら面白いのだろうか。

**名前は開発中のものです。** · 04/06/16 19:37

もともとＤ＆Ｄ用だからシレンよりＷｉｚとか３Ｄ系の方が相性がいいだろう。
シレンとかはフィールドを巡るって感じだけどＷｉｚは部屋を漁るって感じだから。

**名前は開発中のものです。** · 04/06/16 19:52

うむ、それみると、自動生成でWiz作れそうだね
よさげだ

**名前は開発中のものです。** · 04/06/16 20:07

ttp://www.vector.co.jp/soft/win95/game/se261865.html

**ぐぅ＠満腹** ◆Mn5mzn8hAQ · 04/06/16 20:24

そうか自動生成でウィザードリ～。
なるほど・・・

**名前は開発中のものです。** · 04/06/16 21:20

自動生成でWizといったらヘルドアか
RPGツクールだけど