🐭

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

2023/08/08に公開
コード
``````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,
: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
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(*[
])
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

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

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
``````

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

さらに半分にする。

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

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

まとめると

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

となる。

となる。