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

共通処理

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

処理速度

名前	歩数	重複	消費時間(ms)
右手法	26673	10654	401
左手法	14117	4376	194
幅優先探索	9415	0	98
深さ優先探索	15318	0	168
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 ##
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##