自動で迷路を生成し自動で迷路を解いてくれる迷路自己解決器をつくりました。人間のすることはなにもありません。迷路を解く方は以前の記事(【Ruby】 A*(A-star)アルゴリズムを可視化してみた)にて紹介したものに入力しているだけなので今回は迷路生成部について書きます。
ソースコード
「穴掘り法」で検索すれば図解を混じえたすばらしい解説がたくさん見つかると思うので、そこは良記事に譲るとしてここでは実装にあたっての工夫をば。
穴掘り法は再帰でかなりきれいに簡単に書けるので私はすきなんですが、生成された迷路が単調になりやすいという問題があります。特にこれ以上掘れないってなったとき掘れる地点まで戻るという方法は、きれいに再帰が書ける反面かなり単調なものになります。そこで、できるだけいろいろな地点で枝分かれしてもらうために穴掘りを開始できる地点を記憶しておき、行き止まりになったらそこからランダムに選ばれるようにしました。これは終了判定にも流用できるので一石二鳥です。
長くなりましたがちょいちょいコメントを書いたのであとはソースコードを確認してください。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 | module Maze PATH = 0 BLOCK = 1 class Generator attr_reader :nodes , :row , :column def initialize(row = 13 , column = 13 ) raise if row.even? || column.even? @row , @column = row, column end # 掘った穴をリセットする def reset @nodes = Array . new ( @row ) do |i| Array . new ( @column ) do |j| wall = (i == 0 || i == @row - 1 || j == 0 || j == @column - 1 ) wall ? PATH : BLOCK end end # 候補点の配列 # ここから穴を掘り始められる @paths = @nodes .each_with_index.map do |row, i| row.each_with_index.map do |node, j| [i, j] if (i.even? && j.even?) && node == BLOCK end end .flatten( 1 ).compact # はじめにひとつ空ける穴 # ここを @paths.last にすると右下から掘り始める i, j = @paths .sample @nodes [i][j] = PATH end # 迷路を生成して返す def generate print "\e[?25l" reset loop do i, j = @paths .sample next if @nodes [i][j] == BLOCK dig(i, j) break if @paths .empty? end self rescue Interrupt exit ensure print "\e[?25h" end # 穴掘り法 def dig(i, j) puts self print "\e[#{@row}A" ; STDOUT .flush; sleep 0 . 01 # 2マス先がブロックであるなら # 掘り進めることが可能な方向となる dir = [[ 1 , 0 ], [ 0 , 1 ], [- 1 , 0 ], [ 0 ,- 1 ]].map do |di, dj| [di, dj] if @nodes [i+ 2 *di][j+ 2 *dj] == BLOCK end .compact # 掘り進めることが可能な方向の数で場合分け case dir.size # 行き止まりなので # 現在点を候補点から削除し再帰しない when 0 @paths .delete [i, j] # 一方向しか掘り進められないので # 現在点を候補点から削除するが再帰はする when 1 di, dj = dir.first @nodes [i+di][j+dj] = PATH @nodes [i+ 2 *di][j+ 2 *dj] = PATH @paths .delete [i, j] dig(i+ 2 *di, j+ 2 *dj) # 二方向以上掘り進められるので # 現在点を候補点から削除せず再帰する else di, dj = dir.sample @nodes [i+di][j+dj] = PATH @nodes [i+ 2 *di][j+ 2 *dj] = PATH dig(i+ 2 *di, j+ 2 *dj) end end def to_s @nodes .map do |row| row.map do |node| case node when BLOCK then "\e[47m \e[0m" when PATH then " " end end .join end .join( "\n" ) end end end row = 21 column = 31 generator = Maze::Generator. new (row, column) begin maze = generator.generate puts maze print "\e[#{row}A" ; STDOUT .flush; sleep 1 rescue Interrupt exit end while true |
実行すると迷路を生成し続けます。
あとがき
去年から年明けにかけてとても忙しかったため半年ほどブログを更新できずにいましたが、ようやくいろいろ一段落したのでとりあえず落書きスクリプトを投稿しました。その間も一応Qiitaにはちょっと投稿していたのですが。
今後もどれ程のペースで投稿が続けられるかわかりませんが、なにかつくったらできるだけ紹介していきたいと思うのでどうぞ今年もよろしくお願いします。
0 件のコメント:
コメントを投稿