A*探索アルゴリズムにチャレンジ

最近なんだかtwitterとかでよく見るので、そういえば作ったことないしひとつチャレンジしてみようかと。
A*探索アルゴリズムはたとえばシミュレーションゲームの敵の移動なんかで使われている（らしい）移動経路探索のアルゴリズム。
ヒトマスずつ調べて、元からの距離とゴールまでの距離でスコアをつけ、低いマスを優先的に辿っていくことで最短距離を求める。

# A*アルゴリズムの実装にチャレンジ

G = S = 0
map = [
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,0,G,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,1],
[1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1],
[1,0,S,0,0,1,0,0,0,0,0,0,0,0,0,1],
[1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1],
[1,0,0,0,0,1,0,0,0,0,1,1,1,1,1,1],
[1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1],
[1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1],
[1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1],
[1,0,0,0,0,1,1,1,1,0,0,1,0,0,0,1],
[1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,1],
[1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
]

# タイルクラス
class Tile
  attr_accessor :h, :c, :s # hは目的地までの距離、cはそのタイルまでの距離、sはhとcの合計
  attr_accessor :flag      # :openでオープン(調査中)状態、:closeでクローズ(調査済)状態
  attr_reader :x, :y       # タイルの位置
  attr_accessor :prev_tile # 一つ前のタイル

  def initialize(x, y)
    @h = 0
    @s = 0
    @c = 0
    @flag = nil
    @x = x
    @y = y
    @prev_tile = nil
  end
end

# 全部のタイル
tile_list = Array.new(16) { |y| Array.new(16) { |x| Tile.new(x, y) }}

# スタートとゴール
start_x = 2
start_y = 6
goal_x = 2
goal_y = 2

# オープンタイルリストにはスタートのタイルを入れておく
open_list = [tile_list[start_y][start_x]]
tile_list[start_y][start_x].flag = :open

# クローズタイルリストはからっぽ
close_list = []

# 進行方向一覧
ary = [[-1,0], [-1,-1], [0,-1], [1,-1], [1,0], [1,1], [0,1], [-1,1]]

# 2重ループを抜けるための終了フラグ
flag = false
while (flag == false) do
  i = 0
  # オープンタイルをs、hでソート。安定である必要は無いがなんとなく。
  open_list.sort_by {|v| [v.s, v.h, i += 1] }
  # 最も優先順位の高いタイルを取り出す
  base_tile = open_list.shift

  # 全進行方向のタイルを調べる。ほんとはsの低いタイルが出たら打ち切るのがよい。
  ary.each do |v|
    check_tile = tile_list[base_tile.y + v[1]][base_tile.x + v[0]]
    # 未調査のタイルのみ調査。壁は無視。
    if check_tile.flag == nil and map[base_tile.y + v[1]][base_tile.x + v[0]] != 1
      # c,h,sを算出、格納
      check_tile.c = [(check_tile.x - start_x).abs, (check_tile.y - start_y).abs].max
      check_tile.h = [(check_tile.x - goal_x).abs, (check_tile.y - goal_y).abs].max
      check_tile.s = check_tile.c + check_tile.h
      # 経路の保存
      check_tile.prev_tile = base_tile
      # オープンタイルにする
      check_tile.flag = :open
      open_list.push(check_tile)
      # ゴール
      if check_tile.x == goal_x and check_tile.y == goal_y
        flag = true
        break
      end
    end
  end
  base_tile.flag = :close
  close_list.push(base_tile)
end

# ゴールから辿る
x = goal_x
y = goal_y
loop do
  map[y][x] = "*"
  break if x == start_x and y == start_y
  x, y = tile_list[y][x].prev_tile.x, tile_list[y][x].prev_tile.y
end

# 結果表示
map.each do |m|
  m.each do |i|
    print i
    print ","
  end
  print "\n"
end

結果。

1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,0,*,0,0,0,0,0,0,0,0,0,0,0,0,1,
1,0,0,*,*,*,*,*,*,*,*,*,0,0,0,1,
1,1,1,1,1,1,1,1,1,1,1,1,*,0,0,1,
1,0,0,0,0,1,0,0,0,0,0,*,0,0,0,1,
1,0,*,0,0,1,0,0,0,0,*,0,0,0,0,1,
1,0,0,*,0,1,0,0,0,*,0,0,0,0,0,1,
1,0,0,0,*,1,0,0,*,0,1,1,1,1,1,1,
1,0,0,0,*,1,0,*,0,0,0,0,0,0,0,1,
1,0,0,0,*,1,0,*,0,0,0,0,0,0,0,1,
1,0,0,0,*,1,0,0,*,0,0,1,0,0,0,1,
1,0,0,0,*,1,1,1,1,*,0,1,0,0,0,1,
1,0,0,0,0,*,*,*,1,*,0,1,0,0,0,1,
1,0,0,0,0,0,0,0,*,0,0,1,0,0,0,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,

ちなみに所要時間は1時間ほど。
動作の正しさは検証していないので参考にする人がいたら注意。