🐭

迷路の壁を薄く表示する方法

2023/08/08に公開

アルゴリズム

迷路

tech

コード

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

迷路が暑苦しい問題

迷路の通路と壁は内部では印の違いでしかないため単純に表示すると次のようになる。

これはこれでいいのだけどなんとも暑苦しい。そこでまず考えるのが壁の四角形だけ小さく表示してみるということだが、そうすれば壁と壁が接触しなくなり、迷路ではなくなってしまう。どうすればいいだろうか。

奇数番目だけ細くする

行と列でそれぞれ奇数のときに細くするだけで整合性のとれた細い壁ができる。なお、見かけではわからないが通路も奇数番目は細くなっている。擬似コードで書けば次のようになる。

cy = 0
行数.times do |y|
  if y.odd?
    h = 壁の縦幅
  else
    h = 通路の縦幅
  end
  cx = 0
  列数.times do |x|
    if x.odd?
      w = 壁の横幅
    else
      w = 通路の横幅
    end
    if field[x, y] == 壁
      # (cx, cy) から (cx + w - 1, cy + h - 1) の四角形(壁)を描画する
    end
    cx += w
  end
  cy += h
end

そうして壁を通路の半分にしたものがこれ。

さらに半分にする。

最終的に 2px にして外周にも 2px の壁を入れてすっきりしたものを完成とする。

画像の縦横幅を事前に求めるには？

上の画像は RMagick で出力したのだけど、コンソールに垂れ流すのとは異なり、レイヤーを事前に用意しないといけない。このときのレイヤーの縦横幅を求める部分が少し難しかった。が、次のように考えれば答えが出た。

仮に列数を 5 とした場合、通路は 0, 2, 4 の 3 列分あり、壁は 1 と 3 の 2 列分ある。つまり、

横の壁数 = 5列 / 2 = 2列分
横の通路数 = 5列 / 2 + 1 = 3列分

となる。これに壁と通路のピクセル数を掛けて足せばレイヤーの横幅が出る。仮に壁が 1px で通路が 10px とすれば次のようになる。

壁 = 2列分 * 1px = 2px
通路 = 3列分 * 10px = 30px
合計 = 2px + 30px = 32px

高さも同様にすれば求まる。

まとめると

レイヤー横幅 = (列数 / 2 * 壁の横幅) + ((列数 / 2 + 1) * 通路の横幅)
レイヤー縦幅 = (行数 / 2 * 壁の高さ) + ((行数 / 2 + 1) * 通路の高さ)

となる。

枠も必要なら

最終的に外周の壁に見えるフレーム(背景レイヤーと呼ぶことにする)も用意するなら

横幅 = 迷路レイヤー横幅 + padding * 2
縦幅 = 迷路レイヤー縦幅 + padding * 2