【ダンジョン】　自動生成　2　【地形】

**名前は開発中のものです。** · 2007/06/19(火) 12:21:35

ランダムでダンジョンを自動作成する手法についてのスレです。
ローグタイプやシレンタイプのダンジョンや、街並みや地形など。

※過去スレ
ダンジョン自動生成
http://pc11.2ch.net/test/read.cgi/gamedev/1027084016/

関連サイトは>>2 >>3

**名前は開発中のものです。** · 2007/08/01(水) 12:48:14

しかし、ぱっと見だけのもんしか作ってないというのは同意かな。
なんか料理の模型が並んでるショーケースみたいなサイトだね。

**名前は開発中のものです。** · 2007/08/01(水) 12:51:12

と、１行もコードを書いたことのない者が申しております。

**名前は開発中のものです。** · 2007/08/01(水) 12:56:54

お、必死だな本人ｗ

**名前は開発中のものです。** · 2007/08/01(水) 20:06:44

RANDRANDLAND
http://www.interq.or.jp/moonstone/person/RRL/index.html

**名前は開発中のものです。** · 2007/08/01(水) 20:09:03

>>53
って、これすげえなｗ
ドラクエってだけで、wktkするｗ

**名前は開発中のものです。** · 2007/08/02(木) 01:40:04

ホイール必須のインターフェースはどうかと思うけどな

**名前は開発中のものです。** · 2007/08/02(木) 06:52:48

それしか思わんのか

**名前は開発中のものです。** · 2007/08/02(木) 07:05:33

なんで本人そんな必死なのｗ

**名前は開発中のものです。** · 2007/08/02(木) 07:42:21

？

**名前は開発中のものです。** · 2007/08/02(木) 07:58:56

！

**名前は開発中のものです。** · 2007/08/02(木) 09:41:42

夏ですね

**名前は開発中のものです。** · 2007/08/02(木) 10:01:03

Flash厨はいつも元気ですよ（苦笑）

**名前は開発中のものです。** · 2007/08/02(木) 20:55:14

>>60
見栄えがずっと良くなってGood!
これで生成したマップを何かに使えないかなーとか刺激されﾏｽﾀ

**名前は開発中のものです。** · 2007/08/02(木) 21:30:13

プゲラッチョ

**名前は開発中のものです。** · 2007/08/03(金) 01:06:26

単発IDに煽られても自演にしか見えないって知っててやってるんだろうか？

**名前は開発中のものです。** · 2007/08/03(金) 04:50:18

単発IDの擁護は作者自演にしか見えないって知っててやってるんだろうか？

**名前は開発中のものです。** · 2007/08/03(金) 07:57:24

無能で何やっても駄目な奴が、嫉妬してる様子に笑った。

**名前は開発中のものです。** · 2007/08/03(金) 08:00:37

Flash厨の分際で有能だとか勘違いしてる様子に笑った。

**名前は開発中のものです。** · 2007/08/03(金) 08:39:45

おいおいこのスレすっげー盛り上がってるじゃねーかよ！！

**名前は開発中のものです。** · 2007/08/03(金) 08:49:13

どこも夏だなあ

**名前は開発中のものです。** · 2007/08/03(金) 08:59:24

>>82
どのスレを開いても夏な展開になってるから困る

**名前は開発中のものです。** · 2007/08/03(金) 09:02:48

夏が寄り付かないようにもっと寒い流れにしておけば
夏厨も裸足で逃げ出すんじゃないか

**名前は開発中のものです。** · 2007/08/03(金) 09:15:47

Flash（苦笑）

**名前は開発中のものです。** · 2007/08/03(金) 13:17:35

板名考えたらそりゃそうだよなぁ

**名前は開発中のものです。** · 2007/08/03(金) 16:11:10

>>82-83
夏は露骨ですげえ
単発IDがどうとか言い出すからな・・・

**名前は開発中のものです。** · 2007/08/03(金) 16:54:26

夏が過ぎればまた過疎気味の濃いスレに戻ってくれることでせう

進可 ◆Sinka1my5k · 2007/08/09(木) 00:13:33

>66
GJ！

**名前は開発中のものです。** · 2007/08/09(木) 12:09:31

丘とか山のような地形データって、座標と標高で表すものでしょうか？
その上の建物とかはまた別に普通のモデルとして表しているのでしょうか？
何か参考になる本がありましたら教えてください。

**名前は開発中のものです。** · 2007/08/09(木) 18:39:09

地形はグレースケールとか？

**名前は開発中のものです。** · 2007/08/10(金) 02:04:49

>>90
3DのHeightMap的な考えならそうだろうと思う。

**名前は開発中のものです。** · 2007/09/13(木) 00:01:35

保守

**名前は開発中のものです。** · 2007/09/21(金) 22:12:54

今、自動生成のアルゴリズムを作ってた。
ちなみに最初はRacanhack コード解説を参考にしてみてたんだけどうまくいかなかったから自己流にしてみたんさ。
作り方は、ランダムに生成する部屋の数を決める。
部屋のサイズを決定し、各部屋が重ならないようにランダムに配置。

二つ目の部屋からは部屋の中に通路の基点を用意。
一つ前の段階で作った部屋にも通路の基点を設定して二つの起点を直線的に結ぶ。
これを最後の部屋まで繰り返す。

したがって、一つ目の部屋と最後の部屋には通常一本しか通路がつかない。
また、通路の交差および関係ない部屋と通路の接触は判定しないので、十字路や通路と混じっていびつな形になった部屋も生成される可能性がある。

けっこういびつなんだけど、これはこれでいいかなーとか思う。

**SDL厨** ◆SDL/2aFg42 · 2007/10/22(月) 22:48:43

http://www.chukkysoft.com/m-bara/My3D/main.html
JavaApplet製

・テクスチャ貼ってみました。重い。't'を押したらテクスチャ解除。
・画面下の数値は飾りです。

**名前は開発中のものです。** · 2007/10/23(火) 17:34:42

久しぶりに書き込みが！

>>95
重いよ。
テクスチャ解除すると普通に動くのに・・・・・

**名前は開発中のものです。** · 2007/10/23(火) 18:22:05

すまん。あげてもーた。

**名前は開発中のものです。** · 2007/10/23(火) 22:00:43

奥行きに従って暗くしてくれ

**SDL厨** ◆SDL/2aFg42 · 2007/10/24(水) 01:07:23

>>96氏
すまんこってす。
もっと軽くする工夫が必要ですね。

>>98氏
了解。
http://www.chukkysoft.com/m-bara/My3D/main.html
暗い・暗くないの二値ですが出来ました。
さらに重くなったのでとりあえずテクスチャ解像度落としました。

**名前は開発中のものです。** · 2007/10/24(水) 01:43:43

立ち位置の真横が通路があるかないかわかりにくいのは
テクスチャのふちで段差ができるせいじゃないかな

**SDL厨** ◆SDL/2aFg42 · 2007/10/24(水) 23:11:16

>>100氏
通路が分かりやすいように壁と床のテクスチャをてきとーに代えてみた。
テクスチャの横線がガクガクしてる事に気付いた。

もっと軽くする工夫を思いついたけどあんまり時間が無い。
まとまった時間欲しい･･･

**名前は開発中のものです。** · 2007/11/14(水) 15:43:19

初めて遊んでみたけどz(扉を開ける)で前進するのがいいね。
WizでK(Kick)で進んでたの思い出した。

敵と宝箱、そしてレベルアップがあればブラウザのタブを切り替えて、ちょこちょこっと遊んでしまいそうだ。
ただそれはすれ違いになってしまうけど。ともかく頑張ってください。

**名前は開発中のものです。** · 2007/12/19(水) 00:19:15

http://gamdev.org/up/img/10737.png

保守ついでに投下
アルゴリズムは掘削式にちょっと手を加えた感じ

**名前は開発中のものです。** · 2007/12/19(水) 06:32:25

>>103
これは地上マップ生成かな？
実行ファイルもあげてほしい

**名前は開発中のものです。** · 2007/12/19(水) 08:23:53

>>104
ダンジョン自動生成
まだ未完成なので、出来上がったら再度来ます

**名前は開発中のものです。** · 2007/12/19(水) 08:30:48

がんばれだぜ

**名前は開発中のものです。** · 2007/12/19(水) 23:30:02

このスレっぽい話題だったので

ttp://www.inside-games.jp/news/258/25833.html

**名前は開発中のものです。** · 2007/12/21(金) 23:44:22

>107
シナリオを自動生成ってどうやるんだろうね？
誰が何をどうしたのランダムぐらいしか思いつかない。
ダンスで、アフロを、でかくしろ！とか。

**名前は開発中のものです。** · 2007/12/22(土) 01:39:31

>>108
物語の流れにはいくつか基本的な組み合わせがあるので、
その流れの組み合わせをランダムに繋げる方法があるよ。

その組み合わせ方について書かれている本としては、
ウラジミール・プロップの『昔話の形態学』が有名だね。
詳しくは↓のサイトでも読んでくれ。
ttp://www.trpg.net/user/el./fct/labo/u_p.htm
ttp://gumina.sakura.ne.jp/CREATION/OLD/STORY/OLDTALE.htm
ttp://gumina.sakura.ne.jp/CREATION/OLD/STORY/OLDTALE2.htm

**名前は開発中のものです。** · 2007/12/22(土) 14:12:51

俺好みの話題になってきた
前スレでもシナリオの話題は出てたね
でも、あれはドラクエタイプのシナリオだったけど
（金の鍵を設置→金の扉の向こうに次の世界への入り口を設置、とか）

TRPGには前からノウハウがあって、俺もサイコロを振ってシナリオ作ったりしてたよ
こことか詳しい
http://www.trpg-labo.com/modules/article/index.php?articleid=38

>>109の方法論と組み合わせれば、結構実用的なものができるかも？

**名前は開発中のものです。** · 2007/12/23(日) 22:53:27

そこまで凝ると、小説のあらすじメーカーができそうだな。

**名前は開発中のものです。** · 2007/12/23(日) 23:00:04

>>111
七度文庫を思い出した。

**名前は開発中のものです。** · 2007/12/23(日) 23:45:07

央華封神ってTRPGがあったんだけど、それをもとにしたTCGも作られてたんですよ。
そのTCGが「物語を作って得点を競う」っていうものだったそうなんで、ちょっと関係あるかもしれませんね。

**名前は開発中のものです。** · 2007/12/24(月) 00:13:58

なんでこの話題で、ティルナノーグが出てこないんだ。

つーか、PC９８の頃の話なんてしてもだれもわからんか・・・・。orz.

**名前は開発中のものです。** · 2007/12/24(月) 17:22:07

ティルナノーグはドラクエタイプのシナリオ生成だよね。
物語主体のシナリオ生成ではなかったような・・・？

**名前は開発中のものです。** · 2007/12/24(月) 18:25:05

つWikipedia

これを読む限りでは>109なのかな。

**名前は開発中のものです。** · 2007/12/25(火) 05:04:41

Elonaというゲームが、自動生成っぽい感じ・・・

Elona
http://homepage3.nifty.com/rfish/elona_top.html

シナリオといっても、基本、おつかいだけど

**名前は開発中のものです。** · 2007/12/25(火) 11:10:25

そういう自動小説の物語の確信に関わる部分で
○○は××だと思っていたが、実は真相は△△だった！
みたいなどんでん返しが欲しいところだけど
まさかそこまで実装できてるものはないよなぁ。

**名前は開発中のものです。** · 2007/12/25(火) 11:14:12

自動小説だとまた違うだろ
どちらにしろテンプレートを考えれば実装は難しくもない
需要が無いだけ

**名前は開発中のものです。** · 2007/12/26(水) 12:47:24

ストーリーの自動生成という話に関して
水声社から出ている

「可能世界・人工知能・物語理論」
マリー＝ロール・ライアン著
岩松正洋約
ISBN4-89176-550

…を先日入手したが、まだ読む時間がとれない｡･ﾟ･(ﾉД｀)･ﾟ･｡

**名前は開発中のものです。** · 2007/12/27(木) 11:28:11

ランダムで４コマというのがあってだな。なかなかカオスだぞ。

**名前は開発中のものです。** · 2007/12/30(日) 00:55:54

この話題は、実装は簡単だけど手間はかかるから現物が出てこないのが難だね

**名前は開発中のものです。** · 2007/12/30(日) 05:57:27

そういや、思いだした。
昔出てた、天国から来た男というゲーム？が、
シナリオ自動生成だった気がする

しかし、当時、クソ高くて手が出なかった orz

天国から来た男
http://www.electricsheep.co.jp/amfh.shtml

**名前は開発中のものです。** · 2007/12/30(日) 15:52:49

思ったんだが、RPGのシナリオとノベルゲームのシナリオの話題がごっちゃになってるなｗ

**名前は開発中のものです。** · 2007/12/30(日) 17:12:09

共有できるからいいんでね？

**名前は開発中のものです。** · 2008/01/01(火) 00:12:45

物語理論か……

俺のところの教授の分野じゃないか……

**名前は開発中のものです。** · 2008/01/02(水) 16:12:12

ジャンルどこよ？文学かな？それともコンピューター系かな？

**名前は開発中のものです。** · 2008/01/03(木) 19:42:38

俺も学生のころウラジーミルプロップにはまりかけたよ

**名前は開発中のものです。** · 2008/01/03(木) 20:02:55

>>127
コンピュータ系なんだぜ？
AI系

**名前は開発中のものです。** · 2008/01/04(金) 01:35:35

だとしたら文系の膨大な資料が必要になってくるだろうけど
たぶん文系教授はものごっつ嫌がりそうだ。

**名前は開発中のものです。** · 2008/01/04(金) 01:58:27

文系教授がネット上に公開している↓のような資料はあった。

物語要素事典
ttp://www.agu.ac.jp/~kamiyama/index.html

**名前は開発中のものです。** · 2008/01/10(木) 04:35:59

SCIgen - An Automatic CS Paper Generator
http://pdos.csail.mit.edu/scigen/

論文自動生成機らしい
英語なので、評価できんけど

**名前は開発中のものです。** · 2008/01/12(土) 23:58:19

ってかスレ違いはいい加減にしろ

**名前は開発中のものです。** · 2008/01/13(日) 03:30:41

>>133
おまはや

**名前は開発中のものです。** · 2008/01/13(日) 05:42:26

いいんじゃない？
前スレもダンジョン以外をやって今回スレタイ変わったんだし

**名前は開発中のものです。** · 2008/01/13(日) 09:32:42

ここはマップ生成スレ。

**名前は開発中のものです。** · 2008/01/13(日) 13:43:50

でも、新スレ立てようとしたとたん、こちらに誘導されるだろうなｗ

**名前は開発中のものです。** · 2008/01/13(日) 15:27:39

マップだけに限定したい理由がわからん

**名前は開発中のものです。** · 2008/01/13(日) 23:38:43

言いたいことはわかるが、別スレ立てたって見るメンバー同じだろ

**103** · 2008/01/14(月) 00:40:52

■ダンジョン自動生成アプリ
ttp://gamdev.org/up/img/10938.zip
ttp://gamdev.org/up/img/10939.png

■動作環境
・.NetFrameWork 2.0　が動くこと

■操作方法
ReadMe読んでください

自然窟っぽいダンジョン生成を目標に作りました。

**名前は開発中のものです。** · 2008/01/14(月) 01:46:09

ＧＪ

**名前は開発中のものです。** · 2008/01/14(月) 08:58:47

>>140
いいね！
部屋だけの生成だったのか
繋がってない部屋にはうねうねした通路を
渡してやると完璧かも

**名前は開発中のものです。** · 2008/01/14(月) 11:09:37

ヘルプにあるのは矩形のことだよね。
小さい四角を重なり合うように配置している？
大きくすると時間かかるのはコリジョンチェックのため？
どういうアルゴリズムでやっているのか興味がある。

**名前は開発中のものです。** · 2008/01/14(月) 16:34:50

>>143
あー恥ずかしい、ずっと　たんけい　って読んでた　そりゃ変換できないわな

■アルゴリズム
1）フィールド（200x200のマップの描画先）からランダムで一点選び、基点とする
2）左右、上下をそれぞれランダムでどちらかに絞り、矩形サイズ定数内の値をランダムに取得して矩形のX,Yを得る
3）基点から 2) で求めた値を使って矩形を生成。このとき、矩形がフィールドからはみ出すことがあれば、 2) からやり直す
4) 3) で生成した矩形内からランダムで一点選び、基点とする。矩形数が設定値に達していなかったら 2) へもどる

Mキーを１回押すと、これが実行される。
矩形が大きいと時間がかかるのは、 3) で処理戻りが発生しやすいからだと思うけど、とてもトレースできないので定かではない。
矩形サイズ下限を100とかにすると、基点によっては無限ループが発生する

**名前は開発中のものです。** · 2008/01/14(月) 16:52:08

■ダンジョン自動生成アプリ（誤字修正版）
ttp://gamdev.org/up/img/10940.zip

**名前は開発中のものです。** · 2008/01/14(月) 20:39:34

どうせ1も2もランダムなら、2を先にしたらどうかな
そうすれば戻りはなくせる
もちろん結果は変わってしまうけど

**名前は開発中のものです。** · 2008/01/19(土) 22:54:02

>>140
GJ
Shash&Hack系のダンジョンに合いそう

つながらねーと思って繰り返すと、それっぽくなるんだよなー。
面白い

**名前は開発中のものです。** · 2008/01/28(月) 00:09:54

■ダンジョン自動生成アプリ
ttp://gamdev.org/up/img/10989.zip

■動作環境
・.NetFrameWork 2.0　が動くこと

■操作方法
ReadMe読んでください

部屋の連結などを実装
処理時間が猛烈にかかるのは、私が言語仕様をしっかり理解していないから、な気がする

**名前は開発中のものです。** · 2008/01/29(火) 16:53:20

異常にページフォルトが頻発してるね（暴走してるのかと思って一瞬焦ったお･･）

プロファイラでメモリ使用状況見てみたけど（個＝インスタンス数）
・全体 - 5.670.000個 - 約117M
・Dictionary<T,U>.Entry - 270,000個 - 41M(34.2%)
・DungeonAutoCreate.Data.arrow - 3,300,000個 - 38M(32.2%)
・Int32 - 1,600,000個 - 18M(15.5%)
・Int32[] - 270,000個 - 13M(10.5%)
・Dictionary<T,U> - 90,000個 - 4.5M(3.8%)
これで全体の96.2%を占めている。
・DungeonAutoCreate.Block - 90,000個 - 1.7M(1.5%)
・DungeonAutoCreate.Block[] - 10,000個 - 1.7M(1.4%)
ここまで入れると99.1%

330万インスタンスあるData.arrowってのも気にはなるけど、何で辞書がこんなに大量に使われてるの？

GCも何度か発生して殆どのインスタンスがGEN2になっている辺りも改善の余地がある（＝無駄なGCが発生している）
処理速度に関しては明らかにボトルネックは別なので見ていない。

あと、ReadMeに書いてあるサイズ変更した場合に大量のメモリが消費される問題だけど
「古いフィールドを破棄→新しいフィールドを作成」の間で手動でGCを実行してやるのが効果的だと思う。

**名前は開発中のものです。** · 2008/01/29(火) 20:19:35

既存のコードを極力変更せずに対処してみた

Dictionary<Data.arrow, Block> 互換の辞書クラスを作成
・IDictionary<Data.arrow, Block>を実装

> ArrowDict.cs
・Dictionaryとして使えるが、実態は配列として実装されている
internal class ArrowDict : IDictionary<Data.arrow, Block>
ttp://gamdev.org/up/img/10994.zip
↑実際のコード例（ちょっと手抜き）

> Block.cs
・ArrowDictを使うように修正
// public Dictionary<Data.arrow, Block> arw = new Dictionary<Data.arrow, Block>();
public ArrowDict arw = new ArrowDict();

これでメモリ使用量が激減(117M→10M)して、処理速度が大幅に改善する筈。
これ以上の最適化が必要なら、自分でパフォーマンス計測して頑張ってくださいな。

**名前は開発中のものです。** · 2008/01/29(火) 23:14:51

疑似生命体に掘らせるアイデア。

最初は部屋一つとそこの主である親が一つ。親は通路を掘る子供を作る。
子供はある程度通路を掘ると、エネルギーが貯まって親になり
そこに新しく部屋を作り、動かなくなる。そして通路を掘る子供を作る。

別な部屋に突き当たった子は、その部屋の主に吸収されて消滅。
吸収した親は増えたエネルギーのぶん部屋を大きくする。

**名前は開発中のものです。** · 2008/01/29(火) 23:49:44

面白そうだな

**名前は開発中のものです。** · 2008/01/30(水) 14:31:24

全部壁の状態から　掘り進めるってアルゴリズムはあったけど

＞吸収した親は増えたエネルギーのぶん部屋を大きくする。
ってのはいいな

**名前は開発中のものです。** · 2008/01/30(水) 20:06:27

>>149-150
占有メモリがかなーり減りました。サンクス。
Dictionaryのパフォーマンスがよろしくない、というよりenumの使い方がまずかったんだろうか。

＞330万インスタンスあるData.arrowってのも気にはなるけど、何で辞書がこんなに大量に使われてるの？

もうお察しかもわかりませんが、Data.Arrowは方向を示すenumです。（ナナメ有り上下左右の8つ）
マップチップ(Block)のインスタンスに　Dictionary<Data.Arrow,Block>　を持たせて、マップチップの隣接を表現しよう、という考えです。

**名前は開発中のものです。** · 2008/01/31(木) 01:02:39

>>154
お役に立てたようで嬉しいです。
# 解決の為にコードを覗き見したのはすまなかった。

enumの使い方は特に間違ってないと思いますよ。

今回のケースでは"大量の辞書を使用した"のが直接の問題ですかねぇ
・辞書自体がインデックスを管理したりするためにメモリを消費する
・後から追加するために余分な領域を確保する（コレクション全般）
　（ただし、最初に大きさを指定してやれば必要以上に確保してしまう事はない）

この辺が影響してるのかな？とは思うけどあまり詳しくは分からない。
（実際に>>149で使用状況見た時に「こんなに使うのか？！」と衝撃を受けました）

最後に何かの時に役に立つかも知れないので、>>149で使ったツールを貼っておきま
CLR Profiler 2.0
ttp://www.microsoft.com/downloads/details.aspx?familyid=A362781C-3870-43BE-8926-862B40AA0CD0&displaylang=en

**名前は開発中のものです。** · 2008/02/25(月) 11:00:41

保守

**名前は開発中のものです。** · 2008/03/18(火) 12:55:32

ほ

**名前は開発中のものです。** · 2008/03/18(火) 22:15:21

シナリオ生成で思い出したが、少女漫画の恋愛ものの話が
どれもこれも似たり寄ったりすぎるので、恋愛ストーリーを
自動で作成できないかと考えてた時期があったな。

しかも物理的なシミュレーションを使用www
線で結んだ距離で縁を、好き嫌いを引力斥力に設定。
さすがに他のパラメーターが多すぎて諦めたが。

**名前は開発中のものです。** · 2008/03/18(火) 22:29:25

>>158
韓流ドラマもいけそうだなｗ

**名前は開発中のものです。** · 2008/03/19(水) 09:41:49

恋愛ストーリー自動生成だったら
18禁ノベルの濡れ場シーン自動生成のほうがまだ簡単そうだな。

**名前は開発中のものです。** · 2008/03/19(水) 11:48:06

>>160
っ七度文庫

**名前は開発中のものです。** · 2008/03/19(水) 13:22:30

あれって制限版以外入手できるの？

どっかで必ず打ち砕かれるのには笑った。

【ダンジョン】 自動生成 2 【地形】

【ダンジョン】　自動生成　2　【地形】