🐭

# 迷路探索アルゴリズムまとめ

2023/08/13に公開

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

## 処理速度

A* 9230 0 2223
ダイクストラ法 9415 0 2277

サイズ: 201 x 201

## 右手法

``````class RightWallFollower < Base
self.logic_name = "右手法"

def walk(limit: rect.w * rect.h)
current = node_create(start)
dir = rand(V.around.size)
limit.times do
if current.v == goal
break
end
dir = turn_right(dir)
V.around.size.times do
v1 = current.v + vector_by(dir)
if field[v1] == :route
current = node_create(v1, parent: current)
break
end
dir = turn_left(dir)
end
end
end

private

def turn_right(dir, one = 1)
dir + one * direction_to_turn
end

def turn_left(dir)
turn_right(dir, -1)
end

def vector_by(dir)
V.around[dir.modulo(V.around.size)]
end

def direction_to_turn
1
end

def node_create(v, parent: nil)
Node.new(v: v, parent: parent).tap do |node|
walked_at(v, node)
end
end
end
``````

``````## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
##  0 XX 22 23 24 25 26 27 28 29 30 XX                                        ##
##  1 XX 21 XX XX XX XX XX XX XX 31 XX    XX XX XX XX XX XX XX    XX XX XX    ##
##  2 XX 20 19 18 17 16 XX 38 XX 32 XX    XX 56 57 58 59 60 XX          XX    ##
##  3 XX    XX XX XX 15 XX 39 XX 33 XX    XX 55 XX XX XX 61 XX    XX    XX XX ##
##  4 XX    XX 12 13 14 XX 40 35 34 XX    XX 54 XX 64 63 62 XX    XX          ##
##  5 XX XX XX 11 XX XX XX 41 XX XX XX XX XX 53 XX 65 XX XX XX XX XX XX XX    ##
##  6  7  8  9 10 XX 44 45 46 47 48 49 50 51 52 XX 66 67 68 69 70 71 72 73 74 ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
``````

``````## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
##  o XX  o  o  o  o  o  o  o  o  o XX                                        ##
##  o XX  o XX XX XX XX XX XX XX  o XX    XX XX XX XX XX XX XX    XX XX XX    ##
##  o XX  o  o  o  o  o XX  o XX  o XX    XX  o  o  o  o  o XX          XX    ##
##  o XX    XX XX XX  o XX  o XX  o XX    XX  o XX XX XX  o XX    XX    XX XX ##
##  o XX    XX  o  o  o XX  o  o  o XX    XX  o XX  o  o  o XX    XX          ##
##  o XX XX XX  o XX XX XX  o XX XX XX XX XX  o XX  o XX XX XX XX XX XX XX    ##
##  o  o  o  o  o XX  o  o  o  o  o  o  o  o  o XX  o  o  o  o  o  o  o  o  o ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
``````

## 左手法

``````class LeftWallFollower < RightWallFollower
self.logic_name = "左手法"

private

def direction_to_turn
-1
end
end
``````

``````## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
##  0 XX 26 27 28 29 30 31 32 33 34 XX                                        ##
##  1 XX 25 XX XX XX XX XX XX XX 35 XX    XX XX XX XX XX XX XX    XX XX XX    ##
##  2 XX 24 19 18 17 16 XX    XX 36 XX    XX 52 53 54 55 56 XX          XX    ##
##  3 XX 23 XX XX XX 15 XX    XX 37 XX    XX 51 XX XX XX 57 XX    XX    XX XX ##
##  4 XX 22 XX 12 13 14 XX 40 39 38 XX    XX 50 XX 60 59 58 XX    XX          ##
##  5 XX XX XX 11 XX XX XX 41 XX XX XX XX XX 49 XX 61 XX XX XX XX XX XX XX    ##
##  6  7  8  9 10 XX       42 43 44 45 46 47 48 XX 62 63 64 65 66 67 68 69 70 ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
``````

``````## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
##  o XX  o  o  o  o  o  o  o  o  o XX                                        ##
##  o XX  o XX XX XX XX XX XX XX  o XX    XX XX XX XX XX XX XX    XX XX XX    ##
##  o XX  o  o  o  o  o XX    XX  o XX    XX  o  o  o  o  o XX          XX    ##
##  o XX  o XX XX XX  o XX    XX  o XX    XX  o XX XX XX  o XX    XX    XX XX ##
##  o XX  o XX  o  o  o XX  o  o  o XX    XX  o XX  o  o  o XX    XX          ##
##  o XX XX XX  o XX XX XX  o XX XX XX XX XX  o XX  o XX XX XX XX XX XX XX    ##
##  o  o  o  o  o XX        o  o  o  o  o  o  o XX  o  o  o  o  o  o  o  o  o ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
``````

## 幅優先探索

``````class BfsWalker < Base
self.logic_name = "幅優先探索"

def walk(limit: rect.w * rect.h)
@queue = []
node_create(start)
limit.times do
current = node_next
if current.v == goal
break
end
V.around.each do |v|
node_create(current.v + v, parent: current)
end
end
end

private

def node_next
@queue.shift
end

def node_create(v, parent: nil)
if @field[v] == :route && !@nodes_hash[v]
node = Node.new(v: v, parent: parent)
@queue << node
walked_at(v, node)
end
end
end
``````

``````## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
##  0 XX 22 23 24 25 26 27 28 29 30 XX                                        ##
##  1 XX 21 XX XX XX XX XX XX XX 31 XX    XX XX XX XX XX XX XX    XX XX XX    ##
##  2 XX 20 19 18 17 16 XX 38 XX 32 XX    XX 48 49 50 51 52 XX          XX    ##
##  3 XX 21 XX XX XX 15 XX 37 XX 33 XX    XX 47 XX XX XX 53 XX    XX    XX XX ##
##  4 XX 22 XX 12 13 14 XX 36 35 34 XX    XX 46 XX 56 55 54 XX    XX          ##
##  5 XX XX XX 11 XX XX XX 37 XX XX XX XX XX 45 XX 57 XX XX XX XX XX XX XX    ##
##  6  7  8  9 10 XX 40 39 38 39 40 41 42 43 44 XX 58 59 60 61 62 63 64 65 66 ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
``````

``````## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
##  o XX  o  o  o  o  o  o  o  o  o XX                                        ##
##  o XX  o XX XX XX XX XX XX XX  o XX    XX XX XX XX XX XX XX    XX XX XX    ##
##  o XX  o  o  o  o  o XX 38 XX  o XX    XX  o  o  o  o  o XX          XX    ##
##  o XX 21 XX XX XX  o XX 37 XX  o XX    XX  o XX XX XX  o XX    XX    XX XX ##
##  o XX 22 XX  o  o  o XX  o  o  o XX    XX  o XX  o  o  o XX    XX          ##
##  o XX XX XX  o XX XX XX  o XX XX XX XX XX  o XX  o XX XX XX XX XX XX XX    ##
##  o  o  o  o  o XX 40 39  o  o  o  o  o  o  o XX  o  o  o  o  o  o  o  o  o ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
``````

## 深さ優先探索

``````class DfsWalker < BfsWalker
self.logic_name = "深さ優先探索"

private

def node_next
@queue.pop
end
end
``````

``````## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
##  0 XX 22 23 24 25 26 27 28 29 30 XX                                        ##
##  1 XX 21 XX XX XX XX XX XX XX 31 XX    XX XX XX XX XX XX XX    XX XX XX    ##
##  2 XX 20 19 18 17 16 XX    XX 32 XX    XX 48 49 50 51 52 XX          XX    ##
##  3 XX 21 XX XX XX 15 XX 37 XX 33 XX    XX 47 XX XX XX 53 XX    XX    XX XX ##
##  4 XX 22 XX 12 13 14 XX 36 35 34 XX    XX 46 XX 56 55 54 XX    XX          ##
##  5 XX XX XX 11 XX XX XX 37 XX XX XX XX XX 45 XX 57 XX XX XX XX XX XX XX    ##
##  6  7  8  9 10 XX 40 39 38 39 40 41 42 43 44 XX 58 59 60 61 62 63 64 65 66 ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
``````

``````## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
##  o XX  o  o  o  o  o  o  o  o  o XX                                        ##
##  o XX  o XX XX XX XX XX XX XX  o XX    XX XX XX XX XX XX XX    XX XX XX    ##
##  o XX  o  o  o  o  o XX    XX  o XX    XX  o  o  o  o  o XX          XX    ##
##  o XX 21 XX XX XX  o XX 37 XX  o XX    XX  o XX XX XX  o XX    XX    XX XX ##
##  o XX 22 XX  o  o  o XX  o  o  o XX    XX  o XX  o  o  o XX    XX          ##
##  o XX XX XX  o XX XX XX  o XX XX XX XX XX  o XX  o XX XX XX XX XX XX XX    ##
##  o  o  o  o  o XX 40 39  o  o  o  o  o  o  o XX  o  o  o  o  o  o  o  o  o ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
``````

## A*

ゴールに近い方に進む

``````class Aster < Base
self.logic_name = "A*"

def walk(limit: rect.w * rect.h)
node_create(start)
limit.times do
current = open_nodes.min_by(&:total_cost)
if current.v == goal
break
end
V.around.each do |v|
node_create(current.v + v, parent: current)
end
current.state = :close
end
end

def to_s_with_h_cost
to_s do |v|
if @field[v] == :route
h_cost(v)
end
end
end

private

def nodes
@nodes_hash.values
end

def open_nodes
nodes.find_all { |e| e.state == :open }
end

def node_create(v, parent: nil)
if field[v] == :route && !@nodes_hash[v]
node = Node2.new(v: v, parent: parent, h_cost: h_cost(v))
walked_at(v, node)
end
end

# ヒューリスティックコスト
# 地点 v がゴールに近いほど小さい値を返す
def h_cost(v)
v.distance_to(goal).round
end
end

class Node2 < Node
attr_accessor :state

def initialize(v:, parent: nil, h_cost: nil)
super(v: v, parent: parent)
@h_cost = h_cost
@state = :open
end

def total_cost
super + @h_cost
end
end
``````

``````## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
## 25 XX 23 22 21 20 19 18 17 16 15 XX 13 13 12 11 10  9  8  8  7  7  6  6  6 ##
## 25 XX 23 XX XX XX XX XX XX XX 15 XX 13 XX XX XX XX XX XX XX  6 XX XX XX  5 ##
## 24 XX 22 21 20 19 18 XX 16 XX 15 XX 13 XX 11 10  9  8  7 XX  6  5  4 XX  4 ##
## 24 XX 22 XX XX XX 18 XX 16 XX 14 XX 12 XX 10 XX XX XX  7 XX  5 XX  4 XX XX ##
## 24 XX 22 XX 20 19 18 XX 16 15 14 XX 12 XX 10 XX  8  7  6 XX  4 XX  3  2  2 ##
## 24 XX XX XX 20 XX XX XX 16 XX XX XX XX XX 10 XX  8 XX XX XX XX XX XX XX  1 ##
## 24 23 22 21 20 XX 18 17 16 15 14 13 12 11 10 XX  8  7  6  5  4  3  2  1  0 ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
``````

わかりやすいようにコストを距離としたが実際は距離が知りたいのではなく近いかどうかが知りたいだけなので平方根まで求める必要はない。

また通ってほしいセルの距離を手動で下げるなどの調整をしてもよい。が、下手するとゴールに辿りつけないケースがでてくる。辿りつけない場合 current が nil になる。

``````## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
## 25 XX 45 45 45 45 45 45 45 45 45 XX                                        ##
## 26 XX 44 XX XX XX XX XX XX XX 46 XX    XX XX XX XX XX XX XX    XX XX XX    ##
## 26 XX 42 40 38 36 34 XX 54 XX 47 XX    XX 59 59 59 59 59 XX          XX    ##
## 27 XX 43 XX XX XX 33 XX 53 XX 47 XX    XX 57 XX XX XX 60 XX    XX    XX XX ##
## 28 XX 44 XX 32 32 32 XX 52 50 48 XX    XX 56 XX 64 62 60 XX    XX          ##
## 29 XX XX XX 31 XX XX XX 53 XX XX XX XX XX 55 XX 65 XX XX XX XX XX XX XX    ##
## 30 30 30 30 30 XX 58 56 54 54 54 54 54 54 54 XX 66 66 66 66 66 66 66 66 66 ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
``````

``````## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
##  o XX  o  o  o  o  o  o  o  o  o XX                                        ##
##  o XX  o XX XX XX XX XX XX XX  o XX    XX XX XX XX XX XX XX    XX XX XX    ##
##  o XX  o  o  o  o  o XX 54 XX  o XX    XX  o  o  o  o  o XX          XX    ##
##  o XX 43 XX XX XX  o XX 53 XX  o XX    XX  o XX XX XX  o XX    XX    XX XX ##
##  o XX 44 XX  o  o  o XX  o  o  o XX    XX  o XX  o  o  o XX    XX          ##
##  o XX XX XX  o XX XX XX  o XX XX XX XX XX  o XX  o XX XX XX XX XX XX XX    ##
##  o  o  o  o  o XX 58 56  o  o  o  o  o  o  o XX  o  o  o  o  o  o  o  o  o ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
``````

## ダイクストラ法

ゴールまでの歩数が少ない方に進む

``````class Dijkstra < Aster
self.logic_name = "ダイクストラ法"

private

def h_cost(v)
0
end
end
``````
ゴールまでの距離は分からない
``````## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
##  0 XX  0  0  0  0  0  0  0  0  0 XX  0  0  0  0  0  0  0  0  0  0  0  0  0 ##
##  0 XX  0 XX XX XX XX XX XX XX  0 XX  0 XX XX XX XX XX XX XX  0 XX XX XX  0 ##
##  0 XX  0  0  0  0  0 XX  0 XX  0 XX  0 XX  0  0  0  0  0 XX  0  0  0 XX  0 ##
##  0 XX  0 XX XX XX  0 XX  0 XX  0 XX  0 XX  0 XX XX XX  0 XX  0 XX  0 XX XX ##
##  0 XX  0 XX  0  0  0 XX  0  0  0 XX  0 XX  0 XX  0  0  0 XX  0 XX  0  0  0 ##
##  0 XX XX XX  0 XX XX XX  0 XX XX XX XX XX  0 XX  0 XX XX XX XX XX XX XX  0 ##
##  0  0  0  0  0 XX  0  0  0  0  0  0  0  0  0 XX  0  0  0  0  0  0  0  0  0 ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
``````

``````## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
##  0 XX 22 23 24 25 26 27 28 29 30 XX                                        ##
##  1 XX 21 XX XX XX XX XX XX XX 31 XX    XX XX XX XX XX XX XX    XX XX XX    ##
##  2 XX 20 19 18 17 16 XX 38 XX 32 XX    XX 48 49 50 51 52 XX          XX    ##
##  3 XX 21 XX XX XX 15 XX 37 XX 33 XX    XX 47 XX XX XX 53 XX    XX    XX XX ##
##  4 XX 22 XX 12 13 14 XX 36 35 34 XX    XX 46 XX 56 55 54 XX    XX          ##
##  5 XX XX XX 11 XX XX XX 37 XX XX XX XX XX 45 XX 57 XX XX XX XX XX XX XX    ##
##  6  7  8  9 10 XX 40 39 38 39 40 41 42 43 44 XX 58 59 60 61 62 63 64 65 66 ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
``````

``````## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
##  o XX  o  o  o  o  o  o  o  o  o XX                                        ##
##  o XX  o XX XX XX XX XX XX XX  o XX    XX XX XX XX XX XX XX    XX XX XX    ##
##  o XX  o  o  o  o  o XX 38 XX  o XX    XX  o  o  o  o  o XX          XX    ##
##  o XX 21 XX XX XX  o XX 37 XX  o XX    XX  o XX XX XX  o XX    XX    XX XX ##
##  o XX 22 XX  o  o  o XX  o  o  o XX    XX  o XX  o  o  o XX    XX          ##
##  o XX XX XX  o XX XX XX  o XX XX XX XX XX  o XX  o XX XX XX XX XX XX XX    ##
##  o  o  o  o  o XX 40 39  o  o  o  o  o  o  o XX  o  o  o  o  o  o  o  o  o ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
``````