rustedの日記

■ [ruby][quiz]Amazing Mazes (#31) 08:16

今度は迷路の自動生成(とその解き方)(http://www.rubyquiz.com/quiz31.html)。

All nodes of the maze must be reachable from any point.

まず全てのノードに到達できるようにすること。これは生成後に移動可能な場所をチェックして、いっていないところがあったら穴をあけることで解決した。

Furthermore, let us enforce that only 1 viable solution for the maze exists for any given start/stop (you cannot reach the same destination from 2 different routes).

もう1つ注意点。ただ1つの解になるようにすること、ということなので環ができていたら埋めてみました。

生成した迷路を解くほうは再帰でサクっと書いてみた。

ソース。start/stopはランダムで決定されるよ。

#!/usr/bin/ruby
# Amazing Mazes (#31)

class Maze
  LEFT = 1
  TOP = 2
  RIGHT = 4
  BOTTOM = 8
  def initialize(w, h)
    if h <= 0 || w <= 0
      raise 'error : invalid size'
    end
    @width = w
    @height = h
    @start = rand(@width * @height)
    @stop = rand(@width * @height)
    while @start == @stop
      @stop = rand(@width * @height)
    end
    @data = Array.new(@width * @height) { |i| 0 }
    @solve = Array.new(@width * @height) { |i| 0 }
  end
  
  def dig(i, d)
    if d == 0
      if i % @width != 0
        @data[i] |= LEFT
        @data[i - 1] |= RIGHT
      end
    elsif d == 1
      if i >= @width
        @data[i] |= TOP
        @data[i - @width] |= BOTTOM
      end
    elsif d == 2
      if i % @width != @width - 1
        @data[i] |= RIGHT
        @data[i + 1] |= LEFT
      end
    elsif d == 3
      if i < @width * @height - @width
        @data[i] |= BOTTOM
        @data[i + @width] |= TOP
      end
    end
  end
  
  def fill(i, d)
    if d == 0
      if i % @width != 0
        @data[i] &= ~LEFT
        @data[i - 1] &= ~RIGHT
      end
    elsif d == 1
      if i >= @width
        @data[i] &= ~TOP
        @data[i - @width] &= ~BOTTOM
      end
    elsif d == 2
      if i % @width != @width - 1
        @data[i] &= ~RIGHT
        @data[i + 1] &= ~LEFT
      end
    elsif d == 3
      if i < @width * @height - @width
        @data[i] &= ~BOTTOM
        @data[i + @width] &= ~TOP
      end
    end
  end
  
  def generate
    n = @width * @height
    list = Array.new(n) { |i| i }
    
    cnt = 0
    while cnt < 10000
      i = rand(n)
      j = rand(n)
      tmp = list[i]
      list[i] = list[j]
      list[j] = tmp
      cnt += 1
    end
    
    list.each_index { |i| 
      while !dig(i, rand(4))
      end
    }
  end
  
  def search(list, x, y, d)
    if(list[x + y * @width] == 1)
      fill(x + y * @width, d)
      return
    end
    list[x + y * @width] = 1
    
    if (d != 0) && (x > 0) && (@data[x + y * @width] & LEFT != 0)
      search(list, x - 1, y, 2)
    end
    if  (d != 1) && (y > 0) && (@data[x + y * @width] & TOP != 0)
      search(list, x, y - 1, 3)
    end
    if  (d != 2) && (x < @width - 1) && (@data[x + y * @width] & RIGHT != 0)
      search(list, x + 1, y, 0)
    end
    if  (d != 3) && (y < @height - 1) && (@data[x + y * @width] & BOTTOM != 0)
      search(list, x, y + 1, 1)
    end
  end
  
  def check
    list = Array.new(@width * @height) { |i| 0 }
    search(list, rand(@width), rand(@height), -1)
    
    dig_list = Array.new
    list.each_index { |i|
      if list[i] == 0
        dig_list.push(i)
      end
    }
    
    if dig_list.size > 0
      while !dig(dig_list[rand(dig_list.size)], rand(4))
      end
      return false
    end
    return true
  end
  
  def solve(x, y, d)
    if @stop == x + y * @width
      return true
    end
    
    if (d != 0) && (x > 0) && (@data[x + y * @width] & LEFT != 0) && (solve(x - 1, y, 2))
      @solve[x + y * @width] = 1
      return true
    end
    if  (d != 1) && (y > 0) && (@data[x + y * @width] & TOP != 0) && (solve(x, y - 1, 3))
      @solve[x + y * @width] = 1
      return true
    end
    if  (d != 2) && (x < @width - 1) && (@data[x + y * @width] & RIGHT != 0) && (solve(x + 1, y, 0))
      @solve[x + y * @width] = 1
      return true
    end
    if  (d != 3) && (y < @height - 1) && (@data[x + y * @width] & BOTTOM != 0) && (solve(x, y + 1, 1))
      @solve[x + y * @width] = 1
      return true
    end
    return false
  end
  
  def solving_maze
    solve(@start % @width, @start / @width, -1)
  end
  
  def print_maze
    y = 0
    while y < @height
      if y == 0
        x = 0
        while x < @width
          if x == 0
            print "+"
          end
          if @data[x + y * @width] & TOP != 0
            print " "
          else
            print "+"
          end
          print "+"
          x += 1
        end
        print "\n"
      end
      x = 0
      while x < @width
        if x == 0
          if @data[x + y * @width] & LEFT != 0
            print " "
          else
            print "+"
          end
        end
        if @start == x + y * @width
          print "S"
        elsif @stop == x + y * @width
          print "P"
        elsif @solve[x + y * @width] == 1
          print "."
        else
          print " "
        end
        if @data[x + y * @width] & RIGHT != 0
          print " "
        else
          print "+"
        end
        x += 1
      end
      print "\n"
      x = 0
      while x < @width
        if x == 0
          print "+"
        end
        if @data[x + y * @width] & BOTTOM != 0
          print " "
        else
          print "+"
        end
        print "+"
        x += 1
      end
      print "\n"
      y += 1
    end
  end
end

m = Maze.new((ARGV[0] || 8).to_i, (ARGV[1] || 8).to_i)
m.generate
while !m.check
end
m.print_maze
m.solving_maze
m.print_maze

実行!

$ ruby maze.rb
+++++++++++++++++
+ +P  + +       +
+ +++ + +++ +++ +
+     +  S    + +
+ +++++++++++++ +
+ +   + +   +   +
+ + +++ +++ + + +
+     +       + +
+ +++ +++ + +++++
+ +     + +     +
+ +++ + +++ + +++
+   + +     + + +
+++ + +++++++++ +
+   +   +     + +
+++ + +++ +++ + +
+   +     +     +
+++++++++++++++++
+++++++++++++++++
+ +P .+ +  . . .+
+ +++ + +++ +++ +
+. . .+  S .  +.+
+ +++++++++++++ +
+.+   + +   +. .+
+ + +++ +++ + + +
+. . .+    . .+ +
+ +++ +++ + +++++
+ +  . .+ +.    +
+ +++ + +++ + +++
+   + +. . .+ + +
+++ + +++++++++ +
+   +   +     + +
+++ + +++ +++ + +
+   +     +     +
+++++++++++++++++

できた！