A*アルゴリズムで特定の座標のコストを上げたい

Question

RubyでA*アルゴリズムを作りたいと思っています。
（下はasmさんの書いたコードにちょっと付け足しました。asmさんすみません...）

@water = [[2,4], [2,5]]
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.size != 0}.map(&:first).min
	end
	def pop
	  @hash[min_key].pop
	end
	def empty?
	  @hash.values.all?(&: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.new(start)
	until que.empty?
		now, route = que.pop
		next_route = route + [now]
        #付け足した部分
		if @water.include?(now)
		  dist = next_route.size + 1
		else
		  dist = next_route.size
		end
		return next_route if now == goal
		dirs = directions.map{|dx,dy| [now[0] + dx, now[1] + dy] }
		.select{|pos| !except.include?(pos) && close.add?(pos) }
		dirs.each do |to|
		  que.push([to,next_route], dist + distance(to, goal))
		end
	end
end
except = [[3,4], [1,2], [3,6]]
p a_star([1,1], [3,5], except)

自分は初心者ですが自分なりに　if @water.include?(now)　のところを考えてみたんですがどのように書けばいいのか分かりません。

Answer 1

修正前にコストがdist = next_route.sizeで求まっていたのは、
すべての場所に移動するコストが1だったからです。

今回の修正で、その前提が崩れたわけですから、
ルート上の場所をすべて確認して、それぞれのコストを求めて足し合わせなければなりません。

@waterに含まれていればコスト2、それ以外ならコスト1なので、素直に作れば以下のようになります。

dist = next_route.sum{|pos| @water.include?(pos) ? 2 : 1}

ただ、これだと毎回計算して遅くなるので、asmさんもおっしゃっていた通り、
now,routeに加えてdistもqueueに保存するのが良いでしょう。

そちらの方法については、自分で考えてみてください。

Comments

[minokiti]

ありがとうございました????
なんとなくわかったような気がするので、もう一度自分で考えてみます。