2017年2月22日水曜日

【Ruby】 迷路自己解決器

自動で迷路を生成し自動で迷路を解いてくれる迷路自己解決器をつくりました。人間のすることはなにもありません。迷路を解く方は以前の記事（【Ruby】 A*(A-star)アルゴリズムを可視化してみた）にて紹介したものに入力しているだけなので今回は迷路生成部について書きます。




ソースコード

「穴掘り法」で検索すれば図解を混じえたすばらしい解説がたくさん見つかると思うので、そこは良記事に譲るとしてここでは実装にあたっての工夫をば。

穴掘り法は再帰でかなりきれいに簡単に書けるので私はすきなんですが、生成された迷路が単調になりやすいという問題があります。特にこれ以上掘れないってなったとき掘れる地点まで戻るという方法は、きれいに再帰が書ける反面かなり単調なものになります。そこで、できるだけいろいろな地点で枝分かれしてもらうために穴掘りを開始できる地点を記憶しておき、行き止まりになったらそこからランダムに選ばれるようにしました。これは終了判定にも流用できるので一石二鳥です。

長くなりましたがちょいちょいコメントを書いたのであとはソースコードを確認してください。

?
main.rb
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 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)