🐭

迷路作成アルゴリズムまとめ

2023/07/30に公開

Ruby

処理速度

アルゴリズム	N=100	N=200	N=400	N=800	N=1600
棒倒し法	32	140	552	2396	12292
穴掘り法	48	-	-	-	-
穴掘り法 (非再帰)	205	468	1824	6547	21709
壁埋め法	42	-	-	-	-
壁伸ばし法	122	244	971	4092	17972
壁伸ばし法 (非再帰)	83	214	871	4617	22319
壁伸ばし法 (アレンジ)	16	66	189	956	5067

迷路サイズ: N x N
単位: ms
-: Stack Overflow

特徴

棒倒し法
- 良い
  - シンプル
  - 巨大な迷路が安全に作れる
- ダメ
  - 到達不能な場所ができる
    - 対処するには変な補正が必要になり迷路が破綻する
穴掘り法
- 良い
  - シンプル
  - 完璧な迷路が作れる
- ダメ
  - 大きな迷路が作れない
    - 180x180 程度でスタックが死ぬ
穴掘り法 (非再帰)
- 良い
  - 巨大な迷路が安全に作れる
  - 完璧な迷路が作れる
- ダメ
  - ひと目でコードを理解するのが難しい
壁伸ばし法
- 良い
  - 再帰なのに想定していたより大きな迷路が作れる
    - 4096x4096 まで確認済み
  - 完璧な迷路が作れる
  - 複雑な迷路が作れる(と言われている)
    - 感覚的なものもあってはっきり認識できてはいない
- ダメ
  - どこかでサイズの限界がくる心配がある
壁伸ばし法 (非再帰)
- 良い
  - スタックオーバーフローの心配がない
壁伸ばし法 (アレンジ)
- 更地をあえて残すようにしたもの

棒倒し法

小細工しなかったら美しい

StickKnockdown クラス

class StickKnockdown < Base
  self.seed = 1

  def self.build(...)
    new.tap do |e|
      e.build(...)
    end
  end

  def build(...)
    fill(:route)
    odd_cells.each do |v|
      instance_exec(v, ...)
    end
  end
end

1. 何も壁を置いていない状態

builder = StickKnockdown.build do |v|
end

## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
##  S                                                                         ##
##                                                                            ##
##                                                                            ##
##                                                                            ##
##                                                                            ##
##                                                                            ##
##                                                                          G ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##

2. 等間隔に壁を配置する

左上が (0, 0) なので x と y が奇数のときだけ壁を配置する。build ブロックは x と y が奇数のときだけ呼ぶようにしている。v は x, y が入ったベクトルを表す。ここで配置した壁は絶対に壊れない。

builder = StickKnockdown.build do |v|
  wall_set(v)
end

## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
##  S                                                                         ##
##    XX    XX    XX    XX    XX    XX    XX    XX    XX    XX    XX    XX    ##
##                                                                            ##
##    XX    XX    XX    XX    XX    XX    XX    XX    XX    XX    XX    XX    ##
##                                                                            ##
##    XX    XX    XX    XX    XX    XX    XX    XX    XX    XX    XX    XX    ##
##                                                                          G ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##

ここで壁の個数を調べる。外周は無視する。

builder.field.values.count { |e| e == :wall }  # => 36

3. 壁から4方向の一方に壁を生やす

builder = StickKnockdown.build do |v|
  wall_set(v)
  set(v + V.around.sample, :wall)
end

## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
##  S             XX    XX                                  XX    XX          ##
##    XX XX XX    XX    XX XX XX    XX XX XX    XX XX XX    XX    XX    XX XX ##
##    XX                XX                      XX                      XX    ##
##    XX XX XX    XX XX XX    XX    XX XX XX    XX    XX    XX XX XX    XX    ##
##          XX          XX    XX          XX    XX    XX          XX          ##
## XX XX    XX    XX    XX    XX XX XX    XX    XX XX XX XX XX    XX XX XX XX ##
##                XX                XX    XX                                G ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##

迷路らしくなってきた。ここでもまた壁の個数を調べると数がおかしい。

builder.field.values.count { |e| e == :wall }  # => 69

これは対面する壁がお互いに対面に向かって壁を生やしたので重なってしまっている。

4. 重ならないように生やして完成

builder = StickKnockdown.build do |v|
  wall_set(v)
  found = V.around.shuffle.find { |e| field[v + e] == :route }
  wall_set(v + found)
end

## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
##  S       XX                                                    XX          ##
## XX XX    XX XX XX    XX XX XX XX XX XX XX    XX XX XX XX XX    XX    XX XX ##
##    XX                XX          XX          XX    XX                      ##
##    XX    XX    XX    XX XX XX    XX XX XX    XX    XX    XX    XX XX XX    ##
##          XX    XX    XX          XX          XX    XX    XX    XX    XX    ##
##    XX    XX XX XX    XX XX XX XX XX    XX    XX    XX XX XX XX XX    XX XX ##
##    XX          XX                      XX                                G ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##

壁の個数も合っている。

builder.field.values.count { |e| e == :wall }  # => 72

棒倒し法はここまでなら非常にシンプルで美しいアルゴリズムなのでこれ以上余計なことはしてはいけない。

インチキ補正

上の迷路を見ると中央に壁に囲まれた領域ができている。これを囲まれないようにするには

上下左右ではなく「下左右」だけに生やすようにする。
ただし Y = 1 の行の壁たちが上に生やさなかったら Y = 0 の行が通路になってしまうため Y = 1 の行の壁たちはいままで通り上に生やす。

とすればいいのだけどこの小手先の補正が本当に美しくない。

builder = StickKnockdown.build do |v|
  wall_set(v)
  dirs = V.around
  if v.y >= 3
    dirs -= [V[0, -1]]          # 上を除外する
  end
  found = dirs.shuffle.find { |e| field[v + e] == :route }
  wall_set(v + found)
end

## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
##  S       XX                                                    XX          ##
## XX XX    XX XX XX    XX XX XX XX XX XX XX    XX XX XX XX XX    XX    XX XX ##
##                      XX                            XX                      ##
##    XX XX XX XX XX XX XX XX XX XX XX XX XX    XX XX XX    XX XX XX XX XX    ##
##                            XX                      XX                XX    ##
##    XX XX XX    XX    XX XX XX XX XX    XX XX XX XX XX XX XX    XX XX XX XX ##
##          XX    XX                XX                      XX              G ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##

美しくないだけではない。上3行の通路が不自然にスカスカになるため、上3行だけを通ればスタート地点から右端まで移動できてしまうという迷路としては致命的な欠陥ができる。したがって囲まれた領域を許容できないならインチキ補正をするのではなく次の穴掘り法や壁伸ばし法を使う。

穴掘り法

シンプルで美しいが再帰を使うと巨大な迷路が作れない。

class DiggingOut < Base
  self.logic_name = "穴掘り法"

  def build
    fill(:wall)
    dig(start)
  end

  def dig(v0)
    route_set(v0)                 # 今いる居る場所を掘る
    V.around.shuffle.each do |e|  # ランダムな順番で四方を向く
      v1 = v0 + e                 # 1歩先
      v2 = v1 + e                 # 2歩先
      if field[v2] == :wall       # 2歩先が壁なら
        route_set(v1)             # 1歩先を掘って
        dig(v2)                   # 2歩先から同様に繰り返す
      end
    end
  end
end

## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
##  S XX                            XX                      XX                ##
##    XX    XX XX XX XX XX XX XX    XX    XX    XX XX XX    XX    XX XX XX    ##
##    XX                XX    XX    XX    XX    XX          XX          XX    ##
##    XX    XX XX XX    XX    XX    XX    XX    XX XX XX    XX    XX    XX XX ##
##    XX    XX          XX          XX    XX          XX    XX    XX          ##
##    XX XX XX    XX XX XX    XX XX XX XX XX XX XX    XX    XX XX XX XX XX    ##
##                XX                                  XX                    G ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##

インチキしない棒倒し法とは異なり、絶対に囲まれた部分ができない特徴がある。そしてなによりアルゴリズムが美しい。しかし、

begin
  DiggingOut.new(rect: Rect.from_w_h(180, 180)).build
rescue SystemStackError => error
  error  # => #<SystemStackError: stack level too deep>
end

180 x 180 程度で死んだ。

穴掘り法 (非再帰)

巨大な迷路に対応する。

class DiggingOut2 < DiggingOut
  self.logic_name = "穴掘り法 (非再帰)"

  def dig(v0)
    stack = [v0]
    until stack.empty?
      v0 = stack.last
      if @field[v0] == :wall    # 壁のときだけ
        route_set(v0)           # 掘る
      end
      v = V.around.shuffle.find { |v| @field[v0 + v + v] == :wall }
      unless v
        stack.pop
        next
      end
      route_set(v0 + v)
      stack.push(v0 + v + v)
    end
  end
end

再帰だとすっきりするコードが、非再帰だと動いているのが不思議なほどややこしくなる。ループの中で再帰呼び出ししている場合は単にスタックに置き換えればいいわけではない。とくに route_set(v0) が何度も呼ばれないように、再帰では必要なかった「壁のときだけ」の条件が必要な点や、last と pop を使い分ける部分の理解が難しい。

## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
##  S XX                            XX                                        ##
##    XX    XX XX XX XX XX XX XX    XX    XX XX XX XX XX XX XX    XX XX XX    ##
##    XX                XX    XX    XX    XX                XX          XX    ##
##    XX    XX XX XX    XX    XX    XX    XX    XX XX XX    XX    XX    XX XX ##
##    XX    XX          XX          XX    XX    XX          XX    XX          ##
##    XX XX XX    XX XX XX    XX XX XX XX XX    XX    XX XX XX XX XX XX XX    ##
##                XX                            XX                          G ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##

とりあえずこれで巨大な迷路の作成も可能になった。

begin
  DiggingOut2.new(rect: Rect.from_w_h(180, 180)).build
rescue SystemStackError => error
  error  # =>
end

壁埋め法 (勝手に命名)

穴掘り法の壁と通路を逆にしたもの。外周に通路ができる。

class PutUpWall < Base
  self.logic_name = "壁埋め法"

  def build
    fill(:route)                  # 全体を空にしておく
    dig(V[1, 1])                  # 左上から1つ離して開始する
  end

  def dig(v0)
    wall_set(v0)                  # 今いる居る場所を掘る
    V.around.shuffle.each do |e|  # ランダムな順番で四方を向く
      v1 = v0 + e                 # 1歩先
      v2 = v1 + e                 # 2歩先
      if field[v2] == :route      # 2歩先が空なら
        wall_set(v1)              # 1歩先を壁にする
        dig(v2)                   # 2歩先から同様に繰り返す
      end
    end
  end
end

## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
##  S                                                                         ##
##    XX    XX XX XX XX XX XX XX XX XX XX XX    XX XX XX XX XX XX XX XX XX    ##
##    XX    XX                XX          XX                XX    XX    XX    ##
##    XX    XX XX XX    XX XX XX    XX    XX    XX XX XX    XX    XX    XX    ##
##    XX                XX          XX    XX    XX    XX          XX    XX    ##
##    XX XX XX XX XX XX XX    XX XX XX XX XX XX XX    XX XX XX XX XX    XX    ##
##                                                                          G ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##

壁伸ばし法

壁を伸ばすうちに自分の胴体に刺さると輪ができてしまうのでそれを回避するのがやや難しい。

class GrowingTree < Base
  self.logic_name = "壁伸ばし法"

  def build
    # 全体を通路にする
    fill(:route)

    # 奇数の位置がまだ通路ならそこから生やしていく
    odd_cells.shuffle.each do |v0|
      if field[v0] == :route
        @walls = Set.new
        dig(v0)
      end
    end
  end

  def dig(v0)
    wall_set(v0)
    V.around.shuffle.each do |e|
      v1 = v0 + e               # 1歩目
      v2 = v1 + e               # 2歩目

      # 自分に刺さって輪ができるのを防ぐ
      # 輪ができていいなら取ってもいい
      if @walls.include?(v2)
        next
      end

      if field[v1] == :route
        wall_set(v1)            # 2歩先を見る前に1歩先を壁にする
        if field[v2] == :route
          dig(v2)
        end
        break
      end
    end
  end

  def wall_set(v)
    super
    @walls << v
  end
end

## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
##  S                                                       XX          XX    ##
##    XX XX XX XX XX    XX XX XX XX XX    XX XX XX    XX    XX XX XX    XX    ##
##    XX    XX          XX          XX    XX          XX          XX    XX    ##
##    XX    XX    XX XX XX    XX XX XX    XX XX XX    XX XX XX    XX    XX    ##
##    XX    XX                XX    XX    XX    XX    XX    XX    XX          ##
##    XX    XX XX XX XX XX XX XX    XX XX XX    XX    XX    XX    XX    XX    ##
##                            XX                      XX                XX  G ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##

この方法は再帰を使っていてもスタックがそれほど深くならないため大きな迷路を作成することができる。

rect = Rect.from_w_h(4096, 4096)
builder = GrowingTree.new(rect: rect)
builder.build
builder.to_s.size # => 52252672

それでも不安な場合は次の非再帰を使う。

壁伸ばし法 (非再帰)

再帰をやめて安全に巨大な迷路を安全に作れるようにしたもの。

class GrowingTree2 < GrowingTree
  self.logic_name = "壁伸ばし法 (非再帰)"

  def dig(v0)
    stack = [v0]
    until stack.empty?
      v0 = stack.pop
      wall_set(v0)
      v = V.around.shuffle.find do |v|
        v1 = v0 + v             # 1歩目
        v2 = v1 + v             # 2歩目
        field[v1] == :route && !@walls.include?(v2)
      end
      if v
        v1 = v0 + v             # 1歩目
        v2 = v1 + v             # 2歩目
        wall_set(v1)            # 2歩先を見る前に1歩先を壁にする
        if field[v2] == :route
          stack.push(v2)
        end
      end
    end
  end
end

## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
##  S                                                       XX          XX    ##
##    XX XX XX XX XX    XX XX XX XX XX    XX XX XX    XX    XX XX XX    XX    ##
##    XX    XX          XX          XX    XX          XX          XX    XX    ##
##    XX    XX    XX XX XX    XX XX XX    XX XX XX    XX XX XX    XX    XX    ##
##    XX    XX                XX    XX    XX    XX    XX    XX    XX          ##
##    XX    XX XX XX XX XX XX XX    XX XX XX    XX    XX    XX    XX    XX    ##
##                            XX                      XX                XX  G ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##

rect = Rect.from_w_h(4096, 4096)
builder = GrowingTree2.new(rect: rect)
builder.build
builder.to_s.size # => 52252672

壁伸ばし法 (アレンジ)

「壁伸ばし開始回数」と「伸ばす最大の長さ」を指定できるようにすると迷路風のステージができる。

class StageBuilder < Base
  self.logic_name = "壁伸ばし法 (アレンジ)"

  def build(birth_max: 3, dig_max: 8)
    @dig_max = dig_max

    fill(:route)

    birth = 0
    odd_cells.shuffle.each do |v0|
      if field[v0] == :route
        if birth >= birth_max
          break # もう壁伸ばしを開始しない
        end
        @walls = Set.new
        dig(v0)
        birth += 1
      end
    end
  end

  def dig(v0, depth = 0)
    if depth >= @dig_max
      return # 伸ばすのを止める
    end

    wall_set(v0)
    V.around.shuffle.each do |e|
      v1 = v0 + e
      v2 = v1 + e
      if @walls.include?(v2)
        next
      end
      if field[v1] == :route
        wall_set(v1)
        if field[v2] == :route
          dig(v2, depth.next)
        end
        break
      end
    end
  end

  def wall_set(v)
    super
    @walls << v
  end
end

builder = StageBuilder.new
builder.build(birth_max: 20, dig_max: 1)

## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
##  S                                                                         ##
##                XX             XX XX                XX XX       XX XX XX    ##
##                XX                                              XX    XX    ##
##          XX    XX    XX XX XX    XX XX          XX XX          XX          ##
##          XX    XX    XX    XX                XX          XX                ##
##                      XX    XX XX XX XX XX    XX    XX XX XX       XX XX    ##
##                                  XX                                      G ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##

builder = StageBuilder.new
builder.build(birth_max: 10, dig_max: 5)

## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
##  S             XX                                                          ##
##                XX                                  XX XX XX XX XX XX XX XX ##
##                XX                                                          ##
##                XX XX XX    XX          XX XX XX    XX XX XX XX XX          ##
##                            XX    XX    XX    XX                XX          ##
##                      XX    XX XX XX XX XX    XX    XX    XX XX XX XX XX    ##
##                      XX                            XX          XX        G ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##

共通処理

コード

require "matrix"
require "pathname"
require "active_support/core_ext/class/attribute"
require "active_support/core_ext/module/delegation"

class V < Vector
  class << self
    def l
      self[-1,  0]
    end

    def r
      self[1,  0]
    end

    def u
      self[0,  -1]
    end

    def d
      self[0, 1]
    end

    def around
      [
        u,
        r,
        d,
        l,
      ]
    end
  end

  def initialize(...)
    super
    freeze
  end

  def x
    self[0]
  end

  def y
    self[1]
  end

  def length_squared
    x**2 + y**2
  end

  def distance_squared_to(other)
    (other - self).length_squared
  end

  def distance_to(other)
    Math.sqrt(distance_squared_to(other))
  end

  def to_s
    "(#{x},#{y})"
  end

  def inspect
    to_s
  end
end

Rect = Data.define(:w, :h) do
  def self.from_w_h(...)
    new(...)
  end

  def cover?(v)
    (0...w).cover?(v.x) && (0...h).cover?(v.y)
  end

  def w_h
    [w, h]
  end
end

class Base
  class_attribute :logic_name, default: "?"
  class_attribute :seed, default: 0

  attr_accessor :rect
  attr_accessor :field

  class << self
    def build(...)
      new(...).tap do |e|
        e.build
      end
    end
  end

  def initialize(rect: Rect.from_w_h(25, 7), seed: self.class.seed, **options)
    @rect = rect
    @options = options

    @field = {}
    @nodes_hash = {}
    @counts = Hash.new(0)

    if seed
      srand(seed)
    end
  end

  def build
    fill(:wall)
    non_recursive_dig(start)
  end

  def to_s(...)
    border_type = " ##"
    border_line = ([border_type] * (@rect.w + 2)).join
    s = [
      border_line,
      @rect.h.times.collect { |y|
        [
          border_type,
          @rect.w.times.collect { |x| "%3s" % cell_as_string(V[x, y], ...) },
          border_type,
        ].join
      },
      border_line,
    ] * "\n"
    s.gsub(/^\s+/, "")
  end

  def to_s_start_to_goal
    to_s do |v|
      if start_to_goal
        if start_to_goal.include?(v)
          "o"
        end
      end
    end
  end

  def output(file)
    Pathname(file).write(to_s)
  end

  def walk_info
    {
      "名前" => logic_name,
      "歩数" => @counts[:walk],
      "重複" => @counts[:uturn], # 同じ場所を歩いた歩数
    }
  end

  private

  def recursive_dig(v0)
    route_set(v0)
    V.around.shuffle.each do |e|
      v1 = v0 + e
      v2 = v1 + e
      if @field[v2] == :wall
        route_set(v1)
        dig(v2)
      end
    end
  end

  def non_recursive_dig(v0)
    stack = [v0]
    until stack.empty?
      v0 = stack.last
      if @field[v0] == :wall
        route_set(v0)
      end
      v = V.around.shuffle.find { |v| @field[v0 + v + v] == :wall }
      unless v
        stack.pop
        next
      end
      route_set(v0 + v)
      stack.push(v0 + v + v)
    end
  end

  def fill(value)
    cell_each do |v|
      @field[v] = value
    end
  end

  def cell_each(&block)
    @rect.h.times do |y|
      @rect.w.times do |x|
        yield V[x, y]
      end
    end
  end

  def odd_cells
    @odd_cells ||= [].tap do |av|
      cell_each do |v|
        if v.x.odd? && v.y.odd?
          av << v
        end
      end
    end
  end

  def even_cells
    @even_cells ||= [].tap do |av|
      cell_each do |v|
        if v.x.even? && v.y.even?
          av << v
        end
      end
    end
  end

  def invalid?(v)
    !valid?(v)
  end

  def valid?(v)
    @rect.cover?(v)
  end

  def wall_set(v)
    @field[v] == :route or raise ArgumentError, v.inspect
    set(v, :wall)
  end

  def route_set(v)
    @field[v] == :wall or raise ArgumentError, v.inspect
    set(v, :route)
  end

  def top_left
    V[0, 0]
  end

  def start
    V[0, 0]
  end

  def goal
    V[@rect.w.pred, @rect.h.pred]
  end

  def assert_start_and_goal_is_route
    @field[start] == :route or raise
    @field[goal] == :route or raise
  end

  def assert_inside_field(v)
    valid?(v) or raise ArgumentError, v.inspect
  end

  def set(v, value)
    assert_inside_field(v)
    @field[v] = value
  end

  def walked_at(v, node)
    assert_inside_field(v)
    if @nodes_hash[v]
      @counts[:uturn] += 1
    end
    @nodes_hash[v] = node
    @counts[:walk] += 1
  end

  def cell_as_string(v, **options, &block)
    if block
      if s = block.call(v, options)
        return s
      end
    end

    case
    when @field[v] == :wall
      "XX"
    when f = @nodes_hash[v]
      case
      when f.respond_to?(:to_footprint)
        f.to_footprint(**options)
      when f.respond_to?(:to_i)
        f.to_i % 1000
      else
        "."
      end
    when v == start
      "S"
    when v == goal
      "G"
    when @field[v] == :route
      ""
    else
      raise v.inspect
    end
  end

  def start_to_goal
    @start_to_goal ||= yield_self do
      if node = @nodes_hash[goal]
        node.self_and_ancestors.reverse.collect(&:v)
      end
    end
  end
end

class Node
  attr_accessor :v
  attr_accessor :parent
  attr_accessor :path_cost

  def initialize(v:, parent: nil)
    @v = v
    @parent = parent
    @path_cost = 0

    if @parent
      @path_cost = @parent.path_cost.next
    end
  end

  def total_cost
    @path_cost
  end

  def to_footprint(**options)
    total_cost
  end

  def self_and_ancestors
    [self] + (parent ? parent.self_and_ancestors : [])
  end
end

if true
  require "rmagick"
  include Magick

  class ImageFormatter
    delegate :rect, :field, to: :@base

    def initialize(base, **options)
      @base = base
      @options = {
        :route       => 32,
        :wall        => 32,
        :padding     => nil,
        :route_color => "hsl(0,0%,98%)",
        :wall_color  => "hsl(0,0%,60%)",
        :frame_color => "hsl(0,0%,60%)",
      }.merge(options)
    end

    def write
      canvas.write(@options[:path])
    end

    private

    def canvas
      bg_layer.composite(fg_layer, *padding.w_h, OverCompositeOp)
    end

    def bg_layer
      Image.new(*bg_layer_rect.w_h) do |e|
        e.background_color = @options[:frame_color]
      end
    end

    def fg_layer
      layer = Image.new(*fg_layer_rect.w_h) do |e|
        e.background_color = @options[:route_color]
      end
      wall_draw(layer)
      layer
    end

    def wall_draw(layer)
      cy = 0
      rect.h.times do |y|
        if y.odd?
          h = wall.h
        else
          h = route.h
        end
        cx = 0
        rect.w.times do |x|
          if x.odd?
            w = wall.w
          else
            w = route.w
          end
          v = V[x, y]
          if field[v] == :wall
            g = Draw.new
            g.fill(@options[:wall_color])
            g.rectangle(cx, cy, cx + w - 1, cy + h - 1)
            g.draw(layer)
          end
          cx += w
        end
        cy += h
      end
    end

    def fg_layer_rect
      @fg_layer_rect ||= yield_self do
        Rect.from_w_h(*[
            (rect.w / 2 * wall.w) + ((rect.w / 2 + 1) * route.w),
            (rect.h / 2 * wall.h) + ((rect.h / 2 + 1) * route.h),
          ])
      end
    end

    def bg_layer_rect
      @bg_layer_rect ||= Rect.from_w_h(*[
          fg_layer_rect.w + padding.w * 2,
          fg_layer_rect.h + padding.h * 2,
        ])
    end

    def route
      @route ||= Rect.from_w_h(@options[:route], @options[:route])
    end

    def wall
      @wall ||= Rect.from_w_h(@options[:wall], @options[:wall])
    end

    def padding
      @padding ||= yield_self do
        v = @options[:padding] || @options[:wall]
        Rect.from_w_h(v, v)
      end
    end
  end

  Base.class_eval do
    def write(path, **options)
      options = { path: path }.merge(options)
      ImageFormatter.new(self, **options).write
    end
  end
end

if $0 == __FILE__
  require "test/unit"

  class TestMain < Test::Unit::TestCase
    test "works" do
      object = Base.new(seed: nil)
      object.build
      object.to_s
    end

    test "works" do
      10.times do |w|
        10.times do |h|
          object = Base.new(rect: Rect.from_w_h(w, h), seed: nil)
          object.build
          object.to_s
        end
      end
    end
  end
end

処理速度

特徴

棒倒し法

1. 何も壁を置いていない状態

2. 等間隔に壁を配置する

3. 壁から4方向の一方に壁を生やす

4. 重ならないように生やして完成

インチキ補正

穴掘り法

穴掘り法 (非再帰)

壁埋め法 (勝手に命名)

壁伸ばし法

壁伸ばし法 (非再帰)

壁伸ばし法 (アレンジ)

共通処理

Discussion