2020/09/18学び

ウツボ先生の【作ってみよう!プログラム(3)】出口はどこだ!?自動で迷路を探索!

【作ってみようと考えたきっかけ】

 1980年代に巨大迷路ブームが起こり各地に100個以上の娯楽施設に迷路が作成された。現在では20個ほどの迷路が残っているが、幅広い年齢層が遊べる施設として活用されている[1]。この巨大迷路だが、いったん中に入ると方向感覚がわかりにくくなり、出てくるまでに非常に時間がかかる場合がある。特に小さいこどもたちが一人でゴールすることは難しい。

 この迷路の探索を自動で行うプログラムを作成することで、迷路の攻略方法をシミュレーション!!迷路の達人を目指そう!!

【アプリの特徴】

  • アプリはExcelで作成
  • 起動時にはマクロを有効にしてシートを開く必要あり
  • 迷路はsampleシートに作成されており、黒いセルが壁を表す
  • 黒いセルで外枠を囲み、その中に白いセルを道とみなして、黒いセルで迷路を作成
  • スタート地点にはセルにSの文字を、ゴール地点にはセルにFの文字を入力
  • 迷路は黒い枠で囲まれた、行27×列27のセル内に記述
  • 探索の実行はシートの実行ボタンを押すことで、スタート地点からセル内のOの文字が自動で探索をはじめ、ゴール地点まで進む
  • リセットボタンを押すことで、探索前の状態に戻すことができる
  • 基本的なアルゴリズムの一つである、バックトラック法による自動迷路探索を実装
  • バックトラック法とは「進めるところまで進んだのちに、進めなくなった時には、ひとつ前に戻って違う方向に進み、ゴールにたどり着くまで繰り返す」という方法であり、迷路の探索に用いることができる。
  • Excelの黒いセルを壁、壁に囲まれた白いセルを道とみなして、Sと表示されたスタート地点から、Fが表示されたゴール地点までを進む。一度通った道はグレーの色が塗られ、複数回通るとグレーが濃くなるようにしている。
  • プログラムは、ExcelのVBAで記述されており、マクロSolveで迷路の探索を実行し、マクロResetで探索の終わった迷路をもとの状態に戻すために、探索の際にグレーに塗られたセルを白くするようになっている。

【アプリはこちらからダウンロード可能です】

https://github.com/QuantsResearch-Inc/zsjk/tree/master/excel_maze

参考文献
[1] Wikipedia,迷路,https://ja.wikipedia.org/wiki/%E8%BF%B7%E8%B7%AF

 

靱勝彦 靱勝彦(うつぼ かつひこ)

 クォンツ・リサーチ株式会社 フェロー2001年からクォンツ・リサーチ株式会社で、金融工学×プログラミングを軸としたサービス開発に従事。日本技術士会修習技術者支援委員会の委員や、慶應技術士会で子供向け理科教室の指導員を務めるなど、ITを軸とした技術の普及に尽力。最近では社会人大学院にて修士(知識科学)を取得し、自然言語処理を用いた「知識」を研究。技術士(情報工学部門・経営工学部門)。

戻る