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

1 ：名前は開発中のものです。：2007/06/19(火) 12:21:35 ID:oqLsw/ra.net

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

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

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

108 ：名前は開発中のものです。：2007/12/21(金) 23:44:22 ID:dB2xCSTp.net

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

109 ：名前は開発中のものです。：2007/12/22(土) 01:39:31 ID:mYtBb4dP.net

>>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

110 ：名前は開発中のものです。：2007/12/22(土) 14:12:51 ID:TbioTVeu.net

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

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

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

111 ：名前は開発中のものです。：2007/12/23(日) 22:53:27 ID:7Ch2cFyT.net

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

112 ：名前は開発中のものです。：2007/12/23(日) 23:00:04 ID:PQd2o1nK.net

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

113 ：名前は開発中のものです。：2007/12/23(日) 23:45:07 ID:sYYhIO4q.net

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

114 ：名前は開発中のものです。：2007/12/24(月) 00:13:58 ID:iCCURTXI.net

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

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

115 ：名前は開発中のものです。：2007/12/24(月) 17:22:07 ID:cKY7rpLD.net

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

116 ：名前は開発中のものです。：2007/12/24(月) 18:25:05 ID:s6ioOBVT.net

つWikipedia

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

117 ：名前は開発中のものです。：2007/12/25(火) 05:04:41 ID:f266Y5WJ.net

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

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

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

118 ：名前は開発中のものです。：2007/12/25(火) 11:10:25 ID:45JhSWjC.net

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

119 ：名前は開発中のものです。：2007/12/25(火) 11:14:12 ID:6WgQSOPl.net

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

120 ：名前は開発中のものです。：2007/12/26(水) 12:47:24 ID:LPlmC5KA.net

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

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

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

121 ：名前は開発中のものです。：2007/12/27(木) 11:28:11 ID:Ytg+YzMm.net

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

122 ：名前は開発中のものです。：2007/12/30(日) 00:55:54 ID:R2ZefpMo.net

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

123 ：名前は開発中のものです。：2007/12/30(日) 05:57:27 ID:gh2DPire.net

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

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

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

124 ：名前は開発中のものです。：2007/12/30(日) 15:52:49 ID:GdVUAPHc.net

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

125 ：名前は開発中のものです。：2007/12/30(日) 17:12:09 ID:GelyN0Wd.net

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

126 ：名前は開発中のものです。：2008/01/01(火) 00:12:45 ID:fTSX/zU4.net

物語理論か……

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

127 ：名前は開発中のものです。：2008/01/02(水) 16:12:12 ID:SvgGyawT.net

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

128 ：名前は開発中のものです。：2008/01/03(木) 19:42:38 ID:m4afjvCW.net

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

129 ：名前は開発中のものです。：2008/01/03(木) 20:02:55 ID:DnILrl9J.net

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

130 ：名前は開発中のものです。：2008/01/04(金) 01:35:35 ID:0eO4bikW.net

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

131 ：名前は開発中のものです。：2008/01/04(金) 01:58:27 ID:osyt6r0V.net

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

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

132 ：名前は開発中のものです。：2008/01/10(木) 04:35:59 ID:PkUQ+U0a.net

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

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

133 ：名前は開発中のものです。：2008/01/12(土) 23:58:19 ID:Sk9TeTsY.net

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

134 ：名前は開発中のものです。：2008/01/13(日) 03:30:41 ID:X4JKR+6e.net

>>133
おまはや

135 ：名前は開発中のものです。：2008/01/13(日) 05:42:26 ID:t2Ib2ko/.net

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

136 ：名前は開発中のものです。：2008/01/13(日) 09:32:42 ID:WGuhQnKH.net

ここはマップ生成スレ。

137 ：名前は開発中のものです。：2008/01/13(日) 13:43:50 ID:6dlu7jBB.net

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

138 ：名前は開発中のものです。：2008/01/13(日) 15:27:39 ID:qr0K3hAQ.net

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

139 ：名前は開発中のものです。：2008/01/13(日) 23:38:43 ID:V1w7zyd4.net

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

140 ：103：2008/01/14(月) 00:40:52 ID:OMKohYtz.net

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

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

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


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

141 ：名前は開発中のものです。：2008/01/14(月) 01:46:09 ID:2cfS3gf5.net

ＧＪ

142 ：名前は開発中のものです。：2008/01/14(月) 08:58:47 ID:KMhCtH8L.net

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

143 ：名前は開発中のものです。：2008/01/14(月) 11:09:37 ID:X3lp6un1.net

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

144 ：名前は開発中のものです。：2008/01/14(月) 16:34:50 ID:OMKohYtz.net

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

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

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

145 ：名前は開発中のものです。：2008/01/14(月) 16:52:08 ID:OMKohYtz.net

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

146 ：名前は開発中のものです。：2008/01/14(月) 20:39:34 ID:dLp72EAg.net

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

147 ：名前は開発中のものです。：2008/01/19(土) 22:54:02 ID:lZOHlVzA.net

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

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

148 ：名前は開発中のものです。：2008/01/28(月) 00:09:54 ID:icdx03N7.net

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

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

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


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

149 ：名前は開発中のものです。：2008/01/29(火) 16:53:20 ID:ubNaezab.net

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

プロファイラでメモリ使用状況見てみたけど（個＝インスタンス数）
・全体 - 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を実行してやるのが効果的だと思う。

150 ：名前は開発中のものです。：2008/01/29(火) 20:19:35 ID:ubNaezab.net

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

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)して、処理速度が大幅に改善する筈。
これ以上の最適化が必要なら、自分でパフォーマンス計測して頑張ってくださいな。

151 ：名前は開発中のものです。：2008/01/29(火) 23:14:51 ID:T50arNCm.net

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

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

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

152 ：名前は開発中のものです。：2008/01/29(火) 23:49:44 ID:Pi9FjTVd.net

面白そうだな

153 ：名前は開発中のものです。：2008/01/30(水) 14:31:24 ID:JO1v1kVl.net

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

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

154 ：名前は開発中のものです。：2008/01/30(水) 20:06:27 ID:haTlidy2.net

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

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

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

155 ：名前は開発中のものです。：2008/01/31(木) 01:02:39 ID:cyh1Enm0.net

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

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

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

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


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

156 ：名前は開発中のものです。：2008/02/25(月) 11:00:41 ID:ErmfSiFs.net

保守

157 ：名前は開発中のものです。：2008/03/18(火) 12:55:32 ID:h6Yy+dcr.net

ほ

158 ：名前は開発中のものです。：2008/03/18(火) 22:15:21 ID:Ncc283w3.net

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

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

159 ：名前は開発中のものです。：2008/03/18(火) 22:29:25 ID:7C0sKKNU.net

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

160 ：名前は開発中のものです。：2008/03/19(水) 09:41:49 ID:RshlZjYv.net

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

161 ：名前は開発中のものです。：2008/03/19(水) 11:48:06 ID:4ojlhiyF.net

>>160
っ七度文庫

162 ：名前は開発中のものです。：2008/03/19(水) 13:22:30 ID:iyq7/Nu/.net

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

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

163 ：名前は開発中のものです。：2008/03/20(木) 05:27:11 ID:3mOwhcLn.net

>>162
なんとかの賞を取ったシナリオと、シナリオと独立して動作するリーダーがダウンロードできた気がする。
そのシナリオだと18禁シーンもそれなりに描写があったような。