はじめに

以下の記事を参考に、A*アルゴリズムをRubyで実装してみました。スタートからゴールまでの最短経路の探索と、探索した経路の可視化を実装しました。
よくわかるA*(A-star)アルゴリズム (Unity2Dのサンプルコードつき)

A*アルゴリズムとは

参考記事より引用いたします。

A*アルゴリズムとは、探索アルゴリズムの一種です。経路をノードで表現して、スタートノード（開始地点）からゴールノード（目標地点）までの経路を計算し、この経路が最短であることを保証するアルゴリズムとなります。そしてスタートからゴールまでの間に障害物があってもちゃんと迂回してくれます。

製作したRubyコード

今回の実装では、以下の2つのクラスを作成しました。

A_star_fieldクラス：経路を探索するフィールドを表すクラスです。
A_star_nodeクラス：フィールドを構成するノードを表すクラスです。

以下、それぞれのクラスについて、コードを紹介します。

A_star_fieldクラス

コード

require './a_star_node.rb'
require 'cairo'

class A_star_field
  def initialize(x_length,y_length)
    @field = Array.new(x_length).map{Array.new(y_length).map{A_star_node.new}}
    @field.each_with_index do |x_line,x|
      x_line.each_with_index do |node,y|
        node.set_xy_coordinate x,y
      end
    end
    @start_node
    @goal_node
  end

  def set_impassable_nodes(node_places)
    node_places.each do |x,y|
      @field[x][y].impassable
    end
  end

  def set_start_node(x,y)
    @start_node = @field[x][y]
  end

  def set_goal_node(x,y)
    @goal_node = @field[x][y]
  end

  def get_surrounding_node(x,y)
    node_array = []
    (x-1..x+1).each do |i|
      (y-1..y+1).each do |j|
        next if i == x and j == y
        next if i < 0 or 5 <= i # フィールドの範囲内のノードだけ取り出す
        next if j < 0 or 5 <= j # フィールドの範囲内のノードだけ取り出す
        node_array << @field[i][j]
      end
    end
    node_array
  end

  def get_minimum_score_node(opened_nodes)
    minimum_score_node = opened_nodes[1]
    opened_nodes.each do |node|
      next unless node.passable
      minimum_score_node = node if node.score < minimum_score_node.score
    end
    minimum_score_node
  end

  def find_route
    @start_node.open
    @start_node.calc_estimated_cost(@goal_node.x,@goal_node.y)
    @start_node.calc_score

    reference_node = @start_node # スタートノードの設定
    opened_nodes = [] # オープンされているノード

    until reference_node == @goal_node
      # p reference_node
      surrounding_nodes = get_surrounding_node reference_node.x,reference_node.y
      surrounding_nodes.each do |node|
        next unless node.open # オープンに失敗したら、次のノードを評価する
        node.calc_actual_cost reference_node.actual_cost
        node.calc_estimated_cost(@goal_node.x,@goal_node.y)
        node.calc_score
        node.set_parent_node reference_node
        opened_nodes << node # オープンされているノードに追加
      end
      reference_node.close
      reference_node = get_minimum_score_node(opened_nodes)
      opened_nodes.delete(reference_node)
    end
  end

  def show_route_to_goal_node
    node = @goal_node
    until node.nil?
      puts "(#{node.x},#{node.y})"
      node = node.parent_node
    end
  end

  def output_picture
    format = Cairo::FORMAT_ARGB32
    width = @field.length * 50 + 50 # 両端に25の余白。四角は50四方
    height = @field[0].length * 50 + 50 # 両端に25の余白。四角は50四方

    surface = Cairo::ImageSurface.new(format, width, height)
    context = Cairo::Context.new(surface)

    # 背景
    context.set_source_rgb(1, 1, 1) # 白
    context.rectangle(0, 0, width, height)
    context.fill

    # ノードのマス目を作成
    rect_width = 50
    context.set_source_rgb(0,0,0) # 黒
    @field.each_with_index do |x_line,x|
      x_line.each_with_index do |node,y|
        x_start = 25+x*rect_width
        y_start = 25+y*rect_width
        context.rectangle(x_start, y_start, rect_width, rect_width)
        if node.passable
          context.stroke
        else
          context.fill
        end
      end
    end

    # ゴールノードが設定されていない場合、または
    # 経路が作成されていない場合（スタートノードが設定されていない場合含む）、return
    return if @goal_node.nil?
    return if @goal_node.parent_node.nil?

    # 経路の線を引く
    context.set_source_rgb(1,0,0)
    first_node = @goal_node
    second_node = @goal_node.parent_node
    until second_node.nil?
      context.move_to(50*(first_node.x+1), 50*(first_node.y+1))
      context.line_to(50*(second_node.x+1), 50*(second_node.y+1))
      context.stroke
      # draw_line(50*(first_node.x+1), 50*(first_node.y+1), 50*(second_node.x+1), 50*(second_node.y+1))
      first_node = second_node
      second_node = second_node.parent_node
    end

    context.set_source_rgb(0,0,0)
    context.font_size = 20
    # スタートノードに"S"を表示
    context.move_to(50*(@start_node.x+1), 50*(@start_node.y+1))
    context.show_text("S")

    # ゴールノードに"G"を表示
    context.move_to(50+@goal_node.x*50, 50*(@goal_node.y+1))
    context.show_text("G")

    surface.write_to_png("field.png")
  end
end

インスタンス変数

インスタンス変数名	内容
@field	A_star_nodeクラスの二次元配列。二次元のフィールドを表している。
@start_node	スタートノード。@fieldの中のノードの１つが代入される。
@goal_node	ゴールノード。@fieldの中のノードの１つが代入される。

メソッド

メソッド名	内容
initialize	初期化メソッド。引数として、フィールドのx方向及びy方向の大きさを渡す。引数の値に従って、@fieldに格納する配列を作成する。
set_impassable_nodes	フィールドのノードの中で、通過できないノードを設定する。引数には、座標の配列を渡す。
set_start_node	スタートノードを設定する。
set_goal_node	ゴールノードを設定する。
get_surrounding_node	引数で指定した座標の周囲にあるノードを返す。
get_minimum_score_node	引数で渡されたノードの中で、スコアが最小であるノードを返す。
find_route	経路の探索を行うメソッド。
show_route_to_goal_node	ゴールノードまでの経路をテキストベースで出力する。
output_picture	可視化メソッド。フィールド及び探索経路を、画像として出力する。詳細は後述。

可視化処理

参考記事の内容に加えて、フィールドと探索経路を可視化する処理を実装しました。今回は、cairoを用いて、画像として出力を行います。可視化処理を担うoutput_pictureメソッドにて、以下の処理を行っています。

cairoのsurfaceに、フィールドを描画する。各ノードを、四角で描画する。
- 通行可能なノードは白抜きの四角（□）
- 通行可能でないノードは黒塗りの四角（■）
cairoのsurfaceに、探索経路を描画する。ゴールノードから親ノードを辿っていき、直線を描画する。
画像として出力する。

A_star_nodeクラス

コード

class A_star_node
  def initialize
    @passable = true # trueなら、ノードを通行可能
    @moving_cost = 1
    @status = "none"
    @x
    @y
    @actual_cost = 0 # 実コスト
    @estimated_cost = 0# 推定コスト
    @score = 0 # スコア
    @parent_node = nil
  end

  attr_reader :x, :y, :actual_cost, :score, :passable, :parent_node

  def open
    if(@passable and @status == "none")
      @status = "open"
      true
    else false
    end
  end

  def close
    @status = "close"
  end

  def impassable
    @passable = false
  end

  def set_xy_coordinate(x,y)
    @x = x
    @y = y
  end

  def calc_actual_cost(cost)
    @actual_cost = cost + @moving_cost
  end

  def calc_estimated_cost(goal_x,goal_y)
    dx = goal_x - @x
    dx *= -1 if dx < 0
    dy = goal_y - @y
    dy *= -1 if dy < 0
    @estimated_cost = (dx > dy ? dx : dy)
  end

  def calc_score
    @score = @actual_cost + @estimated_cost
  end

  def set_parent_node(node)
    @parent_node = node
  end
end

インスタンス変数

インスタンス変数名	内容
passable	ノードが通過可能かを示すフラグ。trueなら通過可能
moving_cost	ノードの移動コスト
status	ノードの状態。none,open,closeの3状態のいずれか
x	ノードのx座標
y	ノードのy座標
actual_cost	スタートノードからの移動の実コスト
estimated_cost	ゴールノードまでの移動の推定コスト
score	実コストと推定コストの和
parent_node	親ノード（このノードに移動する前のノード）へのポインタ

実行結果

参考記事にて登場しているフィールドを対象に、経路探索を行いました。可視化結果を以下に示します。
通行可能でないノードを迂回し、スタートノードからゴールノードまでの経路が探索できていることが分かります。