A* (#98)

Ruby
21

“Roland S.” [email protected] writes:

42,46 43,46 44,47 45,48 46,48 47,48 48,49 49,49
Your solution appears to produce the wrong path on the map:

@.*…
…~…
…^.X

It wants to go over the mountain, instead of the forest. I think that
this is because of your distance function, which should not be the
manhattan distance function given in the quiz statement, but rather
the distance function I posted.

22

“Tristram Gräbener” [email protected] writes:

Hi,

Here is my first submission to a ruby quiz :slight_smile:

Welcome to the game!

I tried to run your solution, but couldn’t get it to work even on a
very simple map:

esau:~/ruby/quiz98$ echo ‘@…X’ | ruby grabener.rb
grabener.rb:54:in print_solution': undefined method each’ for
nil:NilClass (NoMethodError)
from grabener.rb:100

For some reason, test.run is always returning nil.

23

#!/usr/bin/env ruby

Louis J. Scoras [email protected]

Monday, October 16, 2006

Solution for Ruby Q. number 98

##############################################################################

astar.rb - quiz solution to RubyQuiz # 98

the interesting bits are in this file and see the map.rb part

for the use of Array.cartesian_product

require ‘set’
require ‘enumerator’
require ‘pqueue’ # included below
require ‘map’ # " "
require ‘summary’ # " "

Here we are, a nicely generalized A* method =) We could have easily

just

required that a node has a neigbors method (duck typing), but I wanted

to

make this as general as possible. So astar can have an additional proc

passed in, which when called on a node returns an enumerator to its

successors. Note the default value is what we would have had before.

def astar(start,finish,succ=nil,&h)
closed = Set.new
queue = PQueue.new(&h) << [start]
succ ||= lambda {|n| n.neighbors}

until queue.empty?
path = queue.dequeue
node = path.last
next if closed.include? node
return path if node == finish
closed << node
successors = succ[node]
successors.each do |location|
queue << (path.dup << location)
end
end
end

Nested loops for iterating over a multi-dimentional array hurt the

head;

this abstracts it away. This also leads to a cool little method–well

at

least I think so–for computing neighboring nodes.

cartesian_product([-1,0,1],[-1,0,1])

# => [ [-1,-1], [0, -1], [1, -1],

[-1, 0], [0, 0], [1, 0],

[-1, 1], [0, 1], [1, 1]]

def cartesian_product(*sets)
case sets.size
when 0
nil
when 1
sets[0].collect {|i| [i]}
else
current = sets.pop
tupples = []
current.each do |element|
cartesian_product(*sets).each do |partials|
partials.each do |n|
tupples << [n, element]
end
end
end
tupples
end
end

map = Map.new(File.read(ARGV[0]))

path = astar(map.start,map.goal) do |path_a, path_b|
score_a, score_b =
[path_a, path_b].collect {|path|
current = path.last
traveled = path.inject(0) {|t, node| t + node.cost}
traveled + current.distance(map.goal)
}
score_b <=> score_a # Ordered for min_heap
end

summary path

##############################################################################

map.rb - Contains the code for the mapping part of the program

class Node
attr_reader :x, :y, :cost

def initialize(x,y,cost,map)
@x, @y, @cost, @map = x, y, cost, map
end

Look ma! No nested loops. cartesian_product lets you generate the

offsets then we can just hack away at it with maps/filters until we

get

the right nodes.

def neighbors
h, w = @map.height, @map.width
offsets = [-1,0,1].freeze
cartesian_product(offsets,offsets).
reject {|i| i == [0,0] }.
collect {|dx, dy| [x + dx, y + dy] }.
reject {|j,k| j < 0 || k < 0 || j >= h || k >= w }.
collect {|j,k| @map[j,k] }.
select {|n| n.cost }.
to_enum
end

def distance(node)
[(x-node.x).abs,(y-node.y).abs].max
end

def to_s
“(#{x},#{y}){#{cost}}”
end
end

class Map
TERRAIN_COST = {
‘@’ => :start, ‘X’ => :goal,
‘.’ => 1, ‘*’ => 2, ‘^’ => 3
}.freeze

attr_reader :width, :height

def initialize(map_string)
parse_from_string map_string
end

def
@map[x+y*width]
end

def start
self[*@start]
end

def goal
self[*@goal]
end

private

def parse_from_string(s)
map = s.split(/\s+/).collect{ |l|
l.scan(/./).collect {|t|
TERRAIN_COST[t]
}
}

@height = map.size
@width  = map[0].size
@points = cartesian_product((0..width-1),(0..height-1))
@map    = []

find_ends(map)

@points.each do |x,y|
  @map << Node.new(x,y,map[y][x],self)
end

end

def find_ends(map)
@points.each do |x,y|
case map[y][x]
when :start
@start = [x,y]
map[y][x] = 0
when :goal
@goal = [x,y]
map[y][x] = 0
end
end
end
end

##############################################################################

pqueue.rb - a max/min heap implementation of a priority queue

By having the constructor take the comparison function, this makes

using it for A* extremely easy

class PQueue
def initialize(&sorter)
@data = []
@sorter = sorter ||
lambda do |a,b|
a <=> b
end
end

def inspect
@data.sort(&@sorter).reverse.inspect
end

def <<(element)
@data << element
bubble_up
self
end

def size
@data.size
end

alias_method :enqueue, :<<

def dequeue
if size == 1
@data.pop
else
highest, @data[0] = @data[0], @data.pop
bubble_down
highest
end
end

def empty?
size == 0
end

private

def bubble_up
current_element = size - 1

until root?(current_element)
  parent = parent_index(current_element)
  if @sorter[@data[parent], @data[current_element]] <= 0
    swap_nodes(parent, current_element)
  end
  current_element = parent_index(current_element)
end

end

def bubble_down
current_element = 0

until leaf?(current_element)
  fc, sc = first_child(current_element),

second_child(current_element)
better = choose(fc,sc)

  if @sorter[@data[current_element], @data[better]] > 0
    break
  else
    swap_nodes(current_element, better)
    current_element = better
  end
end

end

def parent_index(index)
(index - 1) / 2
end

def root?(element)
element == 0
end

def swap_nodes(a,b)
@data[a], @data[b] = @data[b], @data[a]
end

def first_child(index)
bounds_check(index * 2 + 1)
end

def second_child(index)
fc = first_child(index)
fc ? bounds_check(fc + 1) : nil
end

def bounds_check(index)
index < size ? index : nil
end

def leaf?(index)
! first_child(index)
end

def choose(a,b)
if b
@sorter[@data[a], @data[b]] >= 0 ? a : b
else
a
end
end
end

##############################################################################

summary.rb - Just prints the results

This didn’t need it’s own file, but it’s not interesting and I’m

trying to keep the interesting bits near the top of the email =)

def summary(path)
cost = 0
back = [nil, ‘across the plains’, ‘through the woods’, ‘over the
moutain’]

path.each_with_index do |n,i|
cost += n.cost
puts case i
when 0
“Starting at #{n}”
when path.size - 1
“and to Grandmothers house #{n} we go!”
else
“#{back[n.cost]} to #{n}”
end
end
puts “Found path. Total cost: #{cost}”
end