古くて新しい自動迷路生成アルゴリズム - やねうらおブログ(移転しました)

最近、ゲーム界隈ではプロシージャルテクスチャー生成だとか、プロシージャルマップ生成だとか、手続き的にゲーム上で必要なデータを生成してしまおうというのが流行りであるが、その起源はどこにあるのだろうか。 メガデモでは初期のころから少ないデータでなるべくど派手な演出をするためにプロシージャルな生成は活用されてきたが、ゲームの世界でプロシージャル生成が初めて導入されたのは、もしかするとドルアーガの塔(1984年/ナムコ)の迷路の自動生成かも知れない。 なぜ私が迷路のことを突然思い出したのかと言うと、最近、Twitterで「30年前、父が7年と数ヶ月の歳月をかけて描いたA1サイズの迷路を、誰かゴールさせませんか。」というツイートが話題になっていたからである。 この迷路を見て「ああ、俺様も迷路のことを書かねば！俺様しか知らない(?)自動迷路生成のことを後世に書き残さねば！」と誰も求めちゃいない使命感が

[yaneurao]

ドルアーガの塔の迷路の自動生成アルゴリズムと、それにより開ループ・閉ループが出来ないことを証明しました。

[romgame]

データ圧縮目的で自動生成を活用するのは同年のEliteも、8つの銀河の各256の惑星の位置や物資の値段、それらの名前や詳細に対してやってるらしい。それ以前だとローグ。これらの後継ゲームがFaster Than Light

[qnighy]

全域木を求めればいいんだから最小全域木のアルゴリズムを流用できて、前者がPrim、後者がKruskalに対応しますね。おわり

[sucrose]

Wikipedia の記事に色々載ってる http://en.wikipedia.org/wiki/Maze_generation_algorithm

[technerd]

もうこれ、ロストテクノロジーの段階にきてるような気がするので良い資料。

[iww]

迷路の作り方はペンゴで学んだ

[kimurasatoru]

すばらしい！（ところで84年では？）

[itamae]

本文中に出てくるDEAD ENDがドルアーガの続編のリターンオブイシターのフロア名に見えてきて、気になって本文か頭に入らなくなってもうたw

[bynn_chapu]

ついに#例の迷路 がやねうらおさんのブログで取り上げられるとは…

[Kureduki_Maari]

古くて新しい自動迷路生成アルゴリズム - やねうらお－ノーゲーム・ノーライフ (id:yaneurao)

[natroun]

ドルアーガの塔、その他の迷路生成の話。雑駁だけど面白い。

[firestorm]

ドルアーガ

[hayakawa_j]

255をseedにして乱数を発生させ、下位2ビットを取り出すと3ばかりが出てきたのだろう

[mooz]

「解くと絵が浮かび上がる迷路」をつくることもできる．グラフの最小全域木を求める問題らしい．プリム法とクラスカル法．

[eiji8pou]

帰ったら実装してみる。

[shidho]

穴掘るのと壁はやすのは昔使った。柱から倒すのはどうだったかなあ。

[qaz76]

ゲーム買ってもらえなくて、ひたすらタイプしてたの思い出した(´；ω；｀)ﾌﾞﾜｯ

[kitaj]

すげー面白い．クラスタリングアルゴリズムとか昔読んだ気がするがすっかり忘れてたな…

[kokemono]

TKGHatebuReaderより

[tanakaBox]

nethckもクラスタリングしてた気がした。

[amatuka]

古くて新しい自動迷路生成アルゴリズム - やねうらお−俺のブログがこんなによっちゃんイカなわけがない 最近、ゲーム界隈ではプロシージャルテクスチャー生成だとか、プロシージャルマップ生成だとか、手続き的にゲ

[tyru]

穴堀り法、クラスタリングアルゴリズム

[tak4hir0]

古くて新しい自動迷路生成アルゴリズム - やねうらお−俺のブログがこんなによっちゃんイカなわけがない 最近、ゲーム界隈ではプロシージャルテクスチャー生成だとか、プロシージャルマップ生成だとか、手続き的にゲ

[Nyoho]

楽しそうなのでメモメモ

[timetrain]

トルネコも似たようなことやってるのかな。

[adsty]

「ドルアーガの塔」の自動迷路生成アルゴリズム。

[sionsou]

専門の時にこのアルゴリズムとゲーム作ったなぁ。ビットで管理懐かしいｗ

[inulab]

お題はドルアーガの塔

[khtokage]

昔こういうの考えたりしたなぁ、懐かしい。帰ったらゆっくり読もう。

[liquidfunc]

こういうのすごいなーと

[vid]

当時の2223Byteは結構な容量ではないかと。機械語での迷路作成コードが全部乗っておつりが出るんじゃないかな。

[hotch_botch]

おもしろい

[mohno]

そういえば、迷路を作る方は自分でプログラムを考えたことがなかったな。

[naochin]

ドルアーガの塔が迷路をプログラム生成と言うので、あれ？60階は？っておもったけど、60階もプログラムの出力結果なのか。驚き。

[gin0606]

"古くて新しい自動迷路生成アルゴリズム - やねうらお−俺のブログがこんなによっちゃんイカなわけがない"

[sirocco]

凄い。

[tamtam3]

柱から壁を生やしていくのか！今でもＭＭＯの自動形成ダンジョンとかで応用が利くような気もする