A*アルゴリズムで壁を通る場合の計算になってしまう

Question

RubyでA*アルゴリズムを使って最短経路を求めたい

RubyでA*アルゴリズムを書いているのですが、ゴールからの距離を求めるときに壁も通るようになってしまいます。

発生している問題・エラーメッセージ

関数「distance」の定義の仕方のせいで壁（通らない座標）を通る場合の距離になってしまいます...

:kaku_route
[[1, 13], [1, 12], [1, 11], [1, 10], [2, 10], [2, 11], [3, 11], [4, 11], [4, 10]]

**最短経路が求まりません...

該当のソースコード

def distance(point1, point2)
  return (point1[0] - point2[0]).abs + (point1[1] - point2[1]).abs
end
def dijkstra(s,g,e)
	p_all_v = []
	d_hash = {}
	before = []
	best_east = []
	best_west = []
	best_north = []
	best_south = []
	best_point = []
	directions = []
	kaku_route = []
	best_history = []
	test_route = []
	player_east = [s[0]+1,s[1]]
	if !(e.include?(player_east))
		directions.push(player_east)
	end
	player_west = [s[0]-1,s[1]]
	if !(e.include?(player_west))
		directions.push(player_west)
	end
	player_north = [s[0],s[1]-1]
	if !(e.include?(player_north))
		directions.push(player_north)
	end
	player_south = [s[0],s[1]+1]
	if !(e.include?(player_south))
		directions.push(player_south)
	end
	directions.each do |d|
		p_distance = distance(s, d)
		d_distance = distance(g, d)
	    before.push(p_distance + d_distance)
	    #後から最小のコストの座標を求めた時に座標を取り出さなければならないため、ハッシュで代入しておく
	    d_hash[d] = before[-1]
	end
	before.sort!
	best = before[0]
	best_point = d_hash.invert[best]
	best_history.push(best_point)
	kaku_route.push(best_point)
	before = []
	d_hash = {}
	directions = []
	#目的地を見つけるまで繰り返す
	until (best_point == g)
		best_east = [best_point[0]+1, best_point[1]]
		if !(e.include?(best_east)) && !(best_east == s) && !(best_history.include?(best_east))
			directions.push(best_east)
		end
		best_west = [best_point[0]-1, best_point[1]]
		if !(e.include?(best_west)) && !(best_west == s) && !(best_history.include?(best_west))
			directions.push(best_west)
		end
		best_north = [best_point[0], best_point[1]-1]
		if !(e.include?(best_north)) && !(best_north == s) && !(best_history.include?(best_north))
			directions.push(best_north)
		end
		best_south =[best_point[0], best_point[1]+1]
		if !(e.include?(best_south)) && !(best_south == s) && !(best_history.include?(best_south))
			directions.push(best_south)
		end
		directions.each do |d|
			test_route = kaku_route
			test_route.push(d)
			p_distance = test_route.length
			d_distance = distance(g, d)
	    	before.push(p_distance + d_distance)
	        #後から最小のコストの座標を求めた時に座標を取り出さなければならないため、ハッシュで代入しておく
	    	d_hash[d] = before[-1]
	    	test_route.delete(d)
		end
		#昇順にソートする
		before.sort!
		#最小のコストのものを選ぶ
		best = before[0]
		#最小コストの座標
		best_point = d_hash.invert[best]
		best_history.push(best_point)
		#最小のコストの座標を毎回配列に挿入する
		kaku_route.push(best_point)

		before = []
		directions = []
		d_hash = {}
	end
	kaku_route.unshift(s)
	p :kaku_route,kaku_route
end

#通らない座標
except = [[3,10],[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[0,10],[0,11],[0,12],[0,13], [0,14], [1,0],[2,0],[3,0],[4,0],[0,4],[5,0],[6,0],[7,0],[8,0],[9,0],[10,0],[11,0],[12,0],[13,0], [14,0]]
dijkstra([1,13],[4,10],except)

Answer 1

A*で使う推定距離は実際の距離より短ければなんでもいいので
壁を通った場合の距離でも問題ありません。

追記

実装してみた

require 'set'

class PriorityQueue
  def initialize
    @hash = Hash.new{|h,k| h[k] = [] }
  end
  def push(val, priority)
    @hash[priority].push val
  end
  def min_key
    @hash.select{|k,v| !v.empty?}.map(&:first).min
  end
  def pop
    @hash[min_key].pop
  end
  def empty?
    @hash.delete_if{|k,v| v.empty?}
         .empty?
  end
end

def distance(start, goal)
  (start[0]-goal[0]).abs + (start[1]-goal[1]).abs
end

def a_star(start, goal, except)
  directions = [[0,1],[0,-1],[1,0],[-1,0]]
  que = PriorityQueue.new
  que.push([start,[]], distance(start, goal))
  close = Set[]
  until que.empty?
    now, route = que.pop
    next unless close.add?(now)
    next_route = route + [now]
    return next_route if now == goal
    dist = next_route.size
    dirs = directions.map{|dx,dy| [now[0] + dx, now[1] + dy] }
                     .select{|pos| !except.include?(pos) }
    dirs.each do |to|
      que.push([to,next_route], dist + distance(to, goal))
    end
  end
end

except = [
  [3,10], # [4,11],[4,9],[5,10],
  *Array.new(15){|i| [0,i] },
  *Array.new(15){|i| [i,0] },
  # *Array.new(14){|i| [14,i+1]},
  # *Array.new(14){|i| [i+1, 14]},
]
p a_star([1,13],[4,10],except)

Comments

[minokiti]

すみません。
説明の仕方が悪かったみたいです。
壁を通った場合の距離にすると最短経路が求まりません

[asm]

なるほど
d_hashを毎回消してるせいでダイクストラ法としても成立してないのが問題のように思います

[minokiti]

ありがとうございます！
無事動きました！
ご迷惑をお掛けしました。初めての質問だったので不手際もあったかと思いますが、みなさんありがとうございました。

[minokiti]

質問ですが、「require 'set'」って何をしているのですか？

[asm]

既探索箇所を表す集合closeのためです。

[minokiti]

質問続きで申し訳ないですが、同じ座標(アイテム)の種類(複数の座標)をできるだけ通らないようにしたいのですが、どのようにすればよいのでしょうか...

[asm]

「壁の種類」とは、なんでしょうか？
「できるだけ」とは具体的にできますか？

もし、壁だけではなく段差みたいな通れるが固定のコストが掛かる場合は
今回省略していたコスト計算をしてやればどうにかなる場合はあります。
そうではなく扉と複数種類の鍵のような資源的制約がある場合はA*では難しいように思います。

[minokiti]

複数の座標をグループ化して通らない座標として固定はせずに通る回数をなるべく少なくする、みたいな感じです。

[asm]

グループ化とはどういう事でしょうか？複数グループあるのですか？
もし、単一グループと見なしても変わらないのであれば、コストとしてマス数以上を計上してやればいいでしょう。
ただ、通りたく無い座標を通る度に全探索する羽目になるのでA*である必要が微妙ですね
ダイクストラ法でも変わらないかもしれません。

[minokiti]

すみません。「グループ化」という表現が悪かったみたいです。特定の座標だけコストを上げることはできるのでしょうか？

[asm]

それ自体は可能です。
が、提示したコードではその機能は省略していますのでちょっと厄介です。

省略せずにやるには、
> dist = next_route.size
の部分を考え直す必要があります。
ここでは、過去の合計コストを計算しています。
いちいち計算してたら時間が掛かるので、queについでに保存してやる感じになるかと思います。

[minokiti]

最初に water = [[1,1],[3,6],[1,7],[4,7]] みたいな感じで定義しておいて
if water.include(now)
　dist = next_route.size + 1
else
　dist = next_route.size
end
みたいな感じでいけませんか？

[minokiti]

すみません。やっぱり無理でした。queに保存するとは、具体的にどういうことか教えていただけいただけませんか？

Answer 2

まず、葉っぱから
def distance(point1, point2)　冗長すぎて理解に時間がかかりました
(point1[0] - point2[0]).abs + (point1[1] - point2[1]).abs

次に幹
A* ですから ノード間のつながりの情報が必要です。
定義してあるexceptはノードの位置情報ですよね？
どのノードとどのノードがつながっているか、という情報がないです。
プログラム読んでませんが、多分全ノードが繋がり合ってるということになってませんか？