No Programming, No Life

プログラミング関連の話題や雑記

Re:今流行のお題を出してみた(一方通行を許可した迷路を作成)

はじめに

元ネタはこちら。前から取り組んでいたのですが、仕様が複雑なのとアルゴリズムを考えてたら頭がこんがらがってきてしまっていたのと、新年度が始まったので色々と忙しかったので、なかなか取り組めてなかったのですが、力技で作ったやつを公開してみます。
ただし、ちょこちょこ手直ししていく気マンマンです!

お題内容

問題

一方通行を許可した迷路を作成する。

10×10=100マスに合同な正方形のセルを並べて、そのセルの間をドアで繋いで経路を作成する。

ドアには鍵が掛かっていることがあり、一方通行とすることができる。

ドアは両側から開くドアとすることもできる。

スタート地点となるセルとゴール地点となるセルは任意に設定できる(=どのセルをスタート地点にしても全ての経路を辿れること)。

以下に、上記説明と重複する部分があるが、条件と実装の仕様をまとめる。
条件

セルは正方形であり、全てのセルの面積は同じである。
セルは 10 × 10の行列をなす100マスで構成されている。
セルは、隣り合うセルに移動するためのルートをひとつ以上持っている。(ひとつのセルから出られなくなることはない)
あるセルから別のセルへの移動は、隣り合う関係のセル同士でのみ可能である。(セルを飛ばして移動したりしない)
隣り合う関係のセルAとセルBで、セルAからセルBへの移動するルートがあるとき、セルBからセルAに移動できることは保証しない。(一方からのみ移動できる場合がある)
セルから、隣り合うひとつのセルへ移動できる確率は、全てのセル間の移動できる確率を平均して60%以内である。
全てのセルは、そのセルを出発点として全てのセルへ移動できる。(どこから出発してもどこへでも行ける)
経路はランダムで決定する。ランダム性については実装者にて判断してよい。

実装の仕様

条件を満たす迷路を生成する機能を作成する。
生成した迷路のひとつのセルは、次のXML要素で表現する。

cell:固定
doors:コロン区切りのタプルで移動可能方向をtrueとするカンマ区切りのマップ表現(falseとなる場合のキーは必須ではない)
position:1,1-10,10でカラムの座標を表現する。左右上下の値増加の方向は特に問わない。
迷路全体は、上記の要素が100個並んだ形式で表現する。
XML表現の迷路が、条件に合致しているかを判定する機能を作成する。

今流行のお題を出してみた - 糸電話式のアレ

とりあえずやっつけバージョン

解説

モデリング

これはセルとかドアとかをどうやってモデリングするかが勝負となるような気がしています。
上記で私が取った方法ですと、セル(Cell)っていうクラスが一つのセルを表し、セルにはドア(Door)が東西南北方向に一つずつ付く*1ようにしています。ドアには鍵がかかっているかの状態とどのセルからどのセルへ通じるものなのかというセルの参照を持たせています。
といった構造にしてみました。

最低限のルートを確保する

このアルゴリズムは要するに、「最低でも一つのセルはどこかから入ってこれて、どこかへ出れなければならない」という定義でよいと思われるので、そのようになるように実装してみています。
が、どうやら私の実装した方法だとバグっているのか、

セルから、隣り合うひとつのセルへ移動できる確率は、全てのセル間の移動できる確率を平均して60%以内である。

がどうしても満たせていない感じになっています。

課題
  • 最低限のルートを確保するアルゴリズムが汚いので改善する
  • できあがった迷路が仕様を満たしているか証明できていない

*1:はじっこは除く