Mazeen

迷路を自動で解決するプログラム

https://mazeen.herokuapp.com/

メイジンの遊び方

ポチポチとクリックすることで､迷路を作成して､探索ボタンを押すだけです｡

最適解は2通りのルールで探索します｡

1. 移動距離最小: スタートからゴールまでを最短距離で解く

2. ターン数最小: 方向転換がなるべく少ない経路で解く

見つからない場合は画面が赤くフラッシュします｡

探索法

迷路を解くアルゴリズムには色々とありますが､今回はA*(A-star)法を使ってrubyで迷路を解くコードを実装してみました｡

(参考にしたサイト) http://qiita.com/2dgames_jp/items/f29e915357c1decbc4b7

迷路の解決はサーバー側で処理し､迷路の状態はクライアント側でjsを使って管理しています｡ 迷路の状態やアルゴリズムの指定をajaxでサーバ側に送信し､解決した結果をjsonで返すという処理をしています｡

悩んだところ

1) アルゴリズム

最初はまともに全探索しようとして行き詰まりました｡

最初は､途中の枝切り(コスト計算)をせずに､あらゆる可能な｢経路｣の探索をしていました｡ 途中で気づきましたが､これだとざっくり言って３方向**(総セル数=縦×横幅)のオーダーで計算量が増大する｡ とくに全部が空白のように､左右どこでも行けるような状況で計算量が増える｡64×64くらいのサイズでトライしたところ､破綻が見えてきた｡

対処方法

A-starによるコスト計算を知り､rubyで実装してみました｡ 局所的なアルゴリズムを変えるだけで､距離最小やターン数最小など様々な経路探索に使えることがわかったので､複数通りの探索法を切り替えられるようにしました｡

2) railsと実現したい処理との折り合い

MVCにならない

フロントエンド側が状態を保持する(迷路の形状を保持する)ため､いわゆるrailsの標準的なMVCパターンに落とし込めないところで少し悩みました｡ railsアプリが標準的な動作をするのはページの初期描画だけで､後はJSON APIのような動きしかしておらず､色々な面でレールから逸脱しているやり方に思いました｡ フロントエンド側の状態管理をDOM操作を使って間違いなく行う､ということに案外神経を使い､あらためてフレームワークの恩恵を実感しました｡

今後の課題

現在の規模だとDOMの状態管理をマニュアル的に行っても可読性･拡張性ともに､なんとかなる範囲でしたが､処理が複雑なアプリを想像すると､このやり方でやっていくのは難しいだろうなと思いました｡ AngularやReactといった､フロントエンド側でのMVCをハンドリングできるフレームーワークの必要性を今回はじめて肌で痛感しました｡ 次は､こういったJSのフレームワークの勉強を兼ね､実験的な実装をしてみたいと考えています｡