ダンジョン生成プログラムを作ってPyPiに登録した話
https://pypi.python.org/pypi/dungeon-generator
しました。
https://github.com/arvelt/dungeon-generator
リポジトリはここで。Demoみたら雰囲気はわかると思います。
目次
- 背景
- エンジニアリング
- アルゴリズム
背景
Unityでローグライクのゲームを作ろうとしているのですが、ダンジョン生成というのがよくわからないのでとりあえず手元で試そうと思ってPythonで作りました。
せっかく作ったのでpipyに登録しました。
SphinxでPythonのdocstringを生成させたり、それをgithub-pageに登録させたり、テスト書いてみたりといった、エンジニアリング的に試してみたかったこともついでに試しました。
その辺のことを書きます。
エンジニアリング
１．Sphinxでdocstringを生成する
Sphinxを使ってみたかったので使ってみました。まず試したところはここに書きました。http://qiita.com/Arvelt/items/45428c5f9661cec3f513
その後実際にこのリポジトリに適用しドキュメントの生成をするようにしました。
２．Sphinxで生成したドキュメントをGithub-pageにする
それもできれば自動で。これうまくいってるかちょっと怪しいんですが、なんとかできたように思います。
masterのあるディレクトリにgithub-pageブランチのsubmoduleを作るということをしています。
このへんが参考になりました。ありがとうございます。
github のプロジェクトにSphinxドキュメントを良さげな感じにおきたい 其の一 - Study08.net 対シンバシ殲滅用人型機動兵器
github のプロジェクトにSphinxドキュメントを良さげな感じにおきたい 其の二 - Study08.net 対シンバシ殲滅用人型機動兵器
３．PyPiに登録
こういうのは決まりきった手順だと思いますが、知らないとなにからやったらいいのかわからないという系の話です。しかもPythonはパッケージ管理周りが非常にややこしいです。
このへんが参考になりました。ありがとうございます。
今どきのPythonのライブラリ自作からPyPIへの登録 - Qiita
アルゴリズム
せっかくなのでどのように作っているかを書きます。
ダンジョン生成のアルゴリズムは調べると色々とでてきます。
いちばんわかりやすかったのはここです。最初はこれのクローンみたいなものを作ろうとしていました。しかし、二次配列を作ってそこにいろいろやっていく、というアプローチがどうしてもうまく実装できずに失敗してしまいました。
なので全部自分で考えることにしました。アプローチも変えて、ダンジョンのマス目を区切って色々やっていくのではなく、先に部屋クラスや道クラスがマス目をそれぞれ保持して、最後にマスの順に束ねていく、というやり方にしました。
もしかしたら遅いかもと思っていたのですが、実際動かしてみたところそれほど遅さを感じることはなかったので、Unity上でのこの実装を使おうと考えています。 せっかく独自の実装をしたので紹介しようと思います。
おおまかには以下の流れです。
１．部屋を作る。
２．部屋の場所を探す。
３．道を通す。
４．調整する。
例を挙げながら詳しく見ていきます。
１．部屋を作る
２．部屋にドアを決める
３．部屋の場所を探す
ある部屋を基準にした場合、他の部屋が東西南北のどの方向にあるかを調べます。
この例だと、基準にしている部屋の西に部屋が２つあるということがわかります。
４．最短距離の部屋を探す
同じ方向に複数の部屋がある場合は１つに絞ります。最短距離の部屋を選ぶという仕様にしました。
この例だと実線で示した部屋の方が近いのでそちらが選ばれます。
５．ドアのペアを作る
６．３と４と５をすべての部屋に対して行う
これで全ての部屋がどの方向に対して道を作っていくかがわかります。
またこの際に同じドアを逆から見た組み合わせができてしまうのでそれは省いておきます。
７．道を伸ばす
５の時点で道が縦に伸びるか横に伸びるかは決められるので、部屋の方向に向かってお互いに道を伸ばします。
８．道をつなぐ
縦に伸ばしている場合は横、横に伸ばしている場合は縦、がそろったらそちらの方向にも道を伸ばします。これで道がつながります。
９．８を全てのドアの組み合わせに対して行う
これで全ての部屋がつながります。
またこの時に、部屋を横切ってしまうような道、部屋に隣接してしまう道、は作らないようにしています。
１０．調整する
９で道を作らないパターンもあるので、孤立する部屋が発生します。
そのような部屋は削除してしまいます。
１１．完成形
この例だとこのような完成形になります。
以上です。
これをUnityに移してからが私のゲーム作りのスタートなのでがんばりたいと思います。
