[QUIZ] A* (#98)

[Ruby Quiz]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Steven Davidovitz

The A* (A-Star) search algorithm is a path-finding algorithm with many uses,
including Artificial Intelligence for games. The search builds the route from
tile to tile until it reaches the goal. To help choose the best possible tile
the algorithm will use an equation that takes into account the distance from the
tile to the goal and the cost of moving to that tile.

Let's work through an example, so you can see how this comes together.

Movement Cost for Terrain:
Non-walkable:
N/A = Water (~)
Walkable:
1 = Flatlands (. or @ or X)
2 = Forest (*)
3 = Mountain (^)

Test Map:
@*^^^ @ = User start
~~*~. X = The goal tile
**...
^..*~
~~*~X

Step 1: Search the surrounding tiles for walkable choices.

The only possible tile for the fist step is to the right: a forest (*) tile.

Step 2: Go through that list finding the cost of movement for each of those
choice tiles. The cost of movement is the path cost so far, plus the cost to
move to the tile being considered.

Our cost so far is 0, since we just started. The cost of a forest is 2 so the
total cost of this move is 2 (0 + 2).

Step 3: Determine the distance from the choice tiles to the goal and add that
to the cost from Step 2 to find the score for each tile.

You can calculate the distance from the tile to the goal using Manhattan
distance formula |x1 - x2| + |y1 - y2|. For our example that is:

|1 - 4| + |0 - 4| = |-3| + |-4| = 7

Knowing that we can produce the final score for this move:

score = cost (2) + distance to goal (7) = 9

Step 4: Choose the best tile to move to by comparing the score of the
surrounding tiles and choosing the lowest.

Step 6: Repeat Steps 1-4 until you reach the goal tile. Be careful to prevent
checking tiles twice and/or circling back.

Test Map Solution:
##^^^ # = Best path
~~#~.
**.#.
^..#~
~~*~#

When you have a working solution, try it out on this move involved map:

http://www.rubyquiz.com/large_map.txt

 

[Jacob Fugal]

Isn't he just explaining a greedy search without backtracking?
Also, this algorithm seems to go wrong even on the small map:

Pretty much, yes. Hoping it's not a spoiler, here's how you really do A*:

1) use a priority queue (prioritized by estimated cost)
2) initialize the queue with the start state(s)
3) while the queue is not empty
a) shift the head off the queue (cheapest state found so far)
b) return the path to the current state if the state is a goal state
b) expand that state by finding neighbors and calculating their costs
c) push each neighbor onto the queue
4) if the queue emptied without finding a solution, there is no solution

For the sake of both brevity and challenge, I've left some details out, such as:

* How do you prevent cycles and backtracking?
* How do you calculate costs for a new state?
* How do you manage your priority queue?
* How do you keep track of the path so you can return it when you hit a goal?

Happy hacking!

 

[James Edward Gray II]

Hoping it's not a spoiler, here's how you really do A*:

1) use a priority queue (prioritized by estimated cost)
2) initialize the queue with the start state(s)
3) while the queue is not empty
a) shift the head off the queue (cheapest state found so far)
b) return the path to the current state if the state is a goal state
b) expand that state by finding neighbors and calculating their
costs
c) push each neighbor onto the queue
4) if the queue emptied without finding a solution, there is no
solution

The priority queue is the major aspect not really touched on by the
quiz, yes. If you need help with this, a past Ruby Quiz about heaps
had code you could borrow:

http://www.rubyquiz.com/quiz40.html

Just be sure to read the summary where I fix a couple of bugs in the
code.

James Edward Gray II

 

[Timothy Goddard]

The priority queue is the major aspect not really touched on by the
quiz, yes. If you need help with this, a past Ruby Quiz about heaps
had code you could borrow:

http://www.rubyquiz.com/quiz40.html

Just be sure to read the summary where I fix a couple of bugs in the
code.

James Edward Gray II

My solution for last week's quiz used an A* search with a priority
queue if anybody wants to see some live code. The queue was, however,
designed for adding large numbers of new states in batches and would
need to be adapted.

By complete coincidence I've actually attempted something almost
identical to this before, attempting top move from any cell on the left
side to any cell on the right. I found that for larger grids an A*
search cell-by-cell becomes unacceptably slow.

I think the real challenge in this quiz will be forming intelligent
methods of reducing the number of states that must be searched. I never
actually did this for the left-to-right problem but have several ideas
for this quiz. Don't worry, they haven't given us the answers to the
real problems

 

[Roland Swingler]

Hi,

Here is my solution - I haven't done much more than implement what was
asked for in the quiz. It produces this path on the large map:

0,0 1,1 2,2 3,3 4,4 5,5 6,6 7,7 8,8 9,9 10,9 11,10 12,11
12,12 13,13 14,14 15,15 15,16 15,17 16,18 17,18 18,19 19,20
20,21 21,22 22,22 23,23 22,24 22,25 23,26 24,27 25,28 26,29
27,29 28,29 29,30 30,31 30,32 31,33 30,34 30,35 31,36 32,37
33,38 34,39 34,40 35,41 36,42 37,43 38,43 39,44 40,44 41,45
42,46 43,46 44,47 45,48 46,48 47,48 48,49 49,49

I've used Brian Schröder's PriorityQueue implementation, so to run
this you'll need to do gem install priorityqueue first.

In response to Martin about the quiz being "spoiled" - I don't come
from a Computer Science background and finding out about algorithms /
data structures which might be obvious to someone with a more technical
bent is one of the things I like getting out of ruby quiz. I think
there is room for a mix of quizes, some with more vague goals than
others.

Cheers,
Roland Swingler

My solution:

require 'rubygems'
require 'priority_queue'

class String
# Convenience method so we can iterate over characters easily

def to_chars
a = []
each_byte do |b|
a << b.chr
end
a
end
end

module TileMap
# Although start is a plains, its cost is 0

START = 0
PLAINS = 1
FOREST = 2
MOUNTAIN = 3
WATER = nil

class TilePath < Array
def initialize(map)
@map = map
super([@map.start])
end

def cost
inject(0) {|sum, c| sum + @map.tile(*c) }
end
end

class Map
attr_reader :start, :goal

# parse a string contining a tile map into a nested array

def initialize(map_str)
@tiles = []
map_str.each do |line|
@tiles << []
line.chomp.to_chars.each do |c|
@tiles.last << case c
when "@"
START
when ".", "X"
PLAINS
when "*"
FOREST
when "^"
MOUNTAIN
when "~"
WATER
else
raise "Invalid tile type"
end
if '@' == c
@start = [@tiles.last.length - 1, @tiles.length - 1]
elsif 'X' == c
@goal = [@tiles.last.length - 1, @tiles.length - 1]
end
end
end
unless @start && @goal
raise "Either position or goal tile are not set"
end
end

def tile(x, y)
@tiles[y][x]
end

def move_choices(x, y)
if tile(x, y) == WATER
raise "Illegal tile"
end
choices = []
(-1..1).each do |i|
ypos = y + i
if ypos >= 0 && ypos < @tiles.length
(-1..1).each do |j|
xpos = x + j
if xpos >= 0 && xpos < @tiles.length
new_position = [xpos, ypos]
if new_position != [x, y] && tile(*new_position) != WATER
choices << new_position
end
end
end
end
end
choices
end

def self.manhattan(point1, point2)
((point2[0] - point1[0]) + (point2[1] - point1[1])).abs
end
end

def self.a_star_search(map)
# To store points we have already visited, so we don't repeat
ourselves
closed = []
open = PriorityQueue.new
# Start off the queue with one path, which will contain the start
position
open.push TilePath.new(map), 0
while ! open.empty?
# Get the path with the best cost to expand

current_path = open.delete_min_return_key
pos = current_path.last
unless closed.include?(pos)
if pos == map.goal
return current_path
end
closed << pos
# Create new paths and add them to the priority queue

map.move_choices(*pos).each do |p|
heuristic = Map.manhattan(p, map.goal)
new_path = current_path.clone << p
open.push(new_path, new_path.cost + heuristic)
end
end
end
raise "Cannot be solved"
end
end

@m = TileMap::Map.new(File.read('large_map.txt'))
results = TileMap.a_star_search(@m)
puts results.map! {|pos| pos.join(",") }.join(" ")

 

[Paolo Negri]

Here's my solution, first submission to ruby quiz, I hope is not 100%
rubbish. I use a * 2 calculating the distance to avoid some noisy
movements when approaching the ending point (so when the simple cost
of terrain is about the same dimension of the distance).
You can try the small map of the quiz without the *2 to see this
behaviour. When the distance from the end point is >> than the terrain
costs the *1 and *2 version act more or less the same way
whell, here's the code.

http://pastie.caboo.se/17815

Thanks

Paolo

 

[Boris Prinz]

Hi,

I finally unterstood the algorithm when I read this page:
http://www.policyalmanac.org/games/aStarTutorial.htm

Best regards,
Boris


# A node represents a tile in the game
class Node
include Comparable # by total_cost

class << self
# each node class is defined by a "map letter" and a cost (1, 2, 3)
attr_accessor :letter, :cost
end

attr_accessor osition, arent, :cost, :cost_estimated

def initialize(position)
@position = position
@cost = 0
@cost_estimated = 0
@on_path = false
@parent = nil
end

def mark_path
@on_path = true
@parent.mark_path if @parent
end

def walkable?
true # except Water
end

def total_cost
cost + cost_estimated
end

def <=> other
total_cost <=> other.total_cost
end

def == other
position == other.position
end

def to_s
@on_path ? '#' : self.class.letter
end
end

class Flatland < Node
self.letter = '.'
self.cost = 1
end

class Start < Flatland
self.letter = '@'
end

class Goal < Flatland
self.letter = 'X'
end

class Water < Node
self.letter = '~'
def walkable?
false
end
end

class Forest < Node
self.letter = '*'
self.cost = 2
end

class Mountain < Node
self.letter = '^'
self.cost = 3
end

NodeClassByLetter = {}
[Flatland, Start, Goal, Water, Forest, Mountain].each do |klass|
NodeClassByLetter[klass.letter] = klass
end

# An (x, y) position on the map
class Position
attr_accessor :x, :y

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

def ==(other)
return false unless Position===other
@x == other.x and @y == other.y
end

# Manhattan
def distance(other)
(@x - other.x).abs + (@y - other.y).abs
end

# Get a position relative to this
def relative(xr, yr)
Position.new(x + xr, y + yr)
end
end

# A map contains a two-dimensional array of nodes
class Map
include Enumerable # for find

def initialize(io)
@nodes = []
y = 0
io.each_line do |line|
x = 0
@nodes[y] = []
line.chomp.split(//).each do |letter|
@nodes[y] << NodeClassByLetter[letter].new(Position.new(x, y))
x += 1
end
y += 1
@width = x
end
@height = y
end

# Returns true if the given position is on the map
def contains?(pos)
pos.x >= 0 and pos.x < @width and pos.y >= 0 and pos.y < @height
end

# Return node at position
def at(pos)
@nodes[pos.y][pos.x]
end

# Iterate all nodes
def each
@nodes.each do |row|
row.each do |node|
yield(node)
end
end
end

# Iterates through all adjacent nodes
def each_neighbour(node)
pos = node.position
yield_it = lambda{|p| yield(at(p)) if contains? p} # just a
shortcut
yield_it.call(pos.relative(-1, -1))
yield_it.call(pos.relative( 0, -1))
yield_it.call(pos.relative( 1, -1))
yield_it.call(pos.relative(-1, 0))
yield_it.call(pos.relative( 1, 0))
yield_it.call(pos.relative(-1, 1))
yield_it.call(pos.relative( 0, 1))
yield_it.call(pos.relative( 1, 1))
end

def to_s
@nodes.collect{|row|
row.collect{|node| node.to_s}.join('')
}.join("\n")
end
end

# see http://www.policyalmanac.org/games/aStarTutorial.htm
class PathFinder
def find_path(map)
start = map.find{|node| Start === node}
goal = map.find{|node| Goal === node}
open_set = [start] # all nodes that are still worth examining
closed_set = [] # nodes we have already visited

loop do
current = open_set.min # find node with minimum cost
raise "There is no path from #{start} to #{goal}" unless current
map.each_neighbour(current) do |node|
if node == goal # we made it!
node.parent = current
node.mark_path
return
end
next unless node.walkable?
next if closed_set.include? node
cost = current.cost + node.class.cost
if open_set.include? node
if cost < node.cost # but it's cheaper from current node!
node.parent = current
node.cost = cost
end
else # we haven't seen this node
open_set << node
node.parent = current
node.cost = cost
node.cost_estimated = node.position.distance(goal.position)
end
end
# move "current" from open to closed set:
closed_set << open_set.delete(current)
end
end
end


abort "usage: #$0 <mapfile>" unless ARGV.size == 1
map = Map.new(File.open(ARGV[0]))
finder = PathFinder.new
finder.find_path(map)
puts map

 

[Tristram Gräbener]

Hi,

Here is my first submission to a ruby quiz
I tried to make the A* algorithm as re-usable as possible (class
A_star).

As a parameter it gets an instance of the class Problem that need to
implement :
- neighbors(node) that returns a list of the neighbor nodes and their
distance to that node
- heuristic(node) that give to heuristical distance to the goal
- end_node?(node) that returns true if node is the goal

Thus the A_star class doesn't need to know anything about the problem
(it doesn't even care about what are nodes)

To run it just call the script with the map in stdio; it will print the
solution.

The implementation is rather simple and not optimized (the heuristic
and A_star#add_to_open are critical), and not very nice.

However, here is the code :

class Problem
attr_reader :start, :goal

def initialize
@data = []
STDIN.readlines.each do |line|
@data << line.chomp
start = line =~ /@/
@start = [start, @data.length-1] if start != nil
goal = line =~ /X/
@goal = [goal, @data.length-1] if goal != nil
end
end

def cost(x,y)
if x < 0 || x >= @data.length || y < 0 || y >= @data[0].length
nil
elsif @data[x][y..y].match(/[@\.X]/)
1
elsif @data[x][y..y] == '*'
2
elsif @data[x][y..y] == '^'
3
else
nil
end
end

# Returns the list of all the neighbors
def neighbors node
neighbors_list = []
x,y = node
for i in -1..1 do
for j in -1..1 do
if i != 0 || j != 0
cost = cost(x+i, y+j)
neighbors_list << [[x+i, y+j],cost] unless cost == nil
end
end
end
neighbors_list
end

def heuristic node
x, y = node
gx, gy = @goal
(gx-x)**2 + (gy-y)**2
end

def end_node? node; node == @goal; end

def print_solution path
data = @data
path.each{|x,y| data[x][y] = '#'}
data.each{|line| puts line}
end
end

class A_star
attr_reader :closed

def initialize problem
@problem = problem
@open = [problem.start]
@closed = []
@f = {problem.start => 0} # Estimated cost
@g = {problem.start => 0} # Cost so far
end

def run
while @open != []
node = @open.pop
@closed << node
return @closed if @problem.end_node? node

@problem.neighbors(node).each do |n|
neighbor, cost = n
add_to_open(neighbor, @g[node] + cost)
end
end
return nil
end

def add_to_open(node, cost)
unless @closed.include? node
if @open.include? node
@g[node] = cost if cost < @g[node]
else
@open << node
@g[node] = cost
end
@f[node] = @g[node] + @problem.heuristic(node)
@open.sort! {|a,b| @f <=> @f[a]}
end
end
end

pb = Problem.new
test = A_star.new pb
pb.print_solution test.run

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Steven Davidovitz

The A* (A-Star) search algorithm is a path-finding algorithm with many uses,
including Artificial Intelligence for games. The search builds the route from
tile to tile until it reaches the goal. To help choose the best possible tile
the algorithm will use an equation that takes into account the distance from the
tile to the goal and the cost of moving to that tile.

Let's work through an example, so you can see how this comes together.

Movement Cost for Terrain:
Non-walkable:
N/A = Water (~)
Walkable:
1 = Flatlands (. or @ or X)
2 = Forest (*)
3 = Mountain (^)

Test Map:
@*^^^ @ = User start
~~*~. X = The goal tile
**...
^..*~
~~*~X

Step 1: Search the surrounding tiles for walkable choices.

The only possible tile for the fist step is to the right: a forest (*) tile.

Step 2: Go through that list finding the cost of movement for each of those
choice tiles. The cost of movement is the path cost so far, plus the cost to
move to the tile being considered.

Our cost so far is 0, since we just started. The cost of a forest is 2 so the
total cost of this move is 2 (0 + 2).

Step 3: Determine the distance from the choice tiles to the goal and add that
to the cost from Step 2 to find the score for each tile.

You can calculate the distance from the tile to the goal using Manhattan
distance formula |x1 - x2| + |y1 - y2|. For our example that is:

|1 - 4| + |0 - 4| = |-3| + |-4| = 7

Knowing that we can produce the final score for this move:

score = cost (2) + distance to goal (7) = 9

Step 4: Choose the best tile to move to by comparing the score of the
surrounding tiles and choosing the lowest.

Step 6: Repeat Steps 1-4 until you reach the goal tile. Be careful to prevent
checking tiles twice and/or circling back.

Test Map Solution:
##^^^ # = Best path
~~#~.
**.#.
^..#~
~~*~#

When you have a working solution, try it out on this move involved map:

http://www.rubyquiz.com/large_map.txt

 

[Daniel Martin]

Here's my solution, first submission to ruby quiz, I hope is not 100%
rubbish. I use a * 2 calculating the distance to avoid some noisy
movements when approaching the ending point (so when the simple cost
of terrain is about the same dimension of the distance).
You can try the small map of the quiz without the *2 to see this
behaviour. When the distance from the end point is >> than the terrain
costs the *1 and *2 version act more or less the same way
whell, here's the code.

http://pastie.caboo.se/17815

Unfortunately, the A* algorithm depends on the fact that the estimate
of cost being added to each point (in this case, distance to goal) is
always less than or equal to the actual cost of getting to the goal
from that point.

By doubling the distance you violate this constraint, and so your
solution computes the wrong path given this map:

@..*...
...~...
...~~~*
.....^X

Your solution with the *2 in it does this:

####...
...~##.
...~~~#
.....^X

For a total cost of 10 (counting both the start and goal, and going
over two forests)

Your solution with the *2 bit removed gets closer to the correct path,
but there's still something off:

###*...
..#~...
..#~~~*
...###X

Looking over your solution, I think you've fallen victim to the fact
that the quiz author failed to explain A* clearly. The excellent
online tutorials and wikipedia article already cited here on the list
are a better introduction.

On the plus side, yours is the only solution besides mine posted so
far that manages to get this path right:

@.*..
..~..
..^.X

That's because you wisely didn't use the manhattan distance quoted in
the puzzle statement.

 

[Paolo Negri]

Unfortunately, the A* algorithm depends on the fact that the estimate
of cost being added to each point (in this case, distance to goal) is
always less than or equal to the actual cost of getting to the goal
from that point.

By doubling the distance you violate this constraint, and so your
solution computes the wrong path given this map:

@..*...
...~...
...~~~*
.....^X

Your solution with the *2 in it does this:

####...
...~##.
...~~~#
.....^X

For a total cost of 10 (counting both the start and goal, and going
over two forests)

Your solution with the *2 bit removed gets closer to the correct path,
but there's still something off:

###*...
..#~...
..#~~~*
...###X

Looking over your solution, I think you've fallen victim to the fact
that the quiz author failed to explain A* clearly. The excellent
online tutorials and wikipedia article already cited here on the list
are a better introduction.

On the plus side, yours is the only solution besides mine posted so
far that manages to get this path right:

@.*..
..~..
..^.X

That's because you wisely didn't use the manhattan distance quoted in
the puzzle statement.

The problem of my *1 version is how the choice among tiles with the
same price is done. The *2 is really rubbish and was just based on a
specific map, sorry.

to have a better view of what happens is interesting to print out all
the costs of the points on the map, here's a diff to avoid the *2 and
print the final result with cost.

59c59
< (point1.zip(point2).map {|c| (c[0] - c[1]).abs}).max
---

(point1.zip(point2).map {|c| (c[0] - c[1]).abs}).max*2

103d102
< (0..(line.size - 1)).each {|n| out << cost([n, line_n]).to_s}

If I'll have the time to work on it I'll submit some improvements.

Thanks

Paolo

 

[Daniel Martin]

Hi,

Here is my solution - I haven't done much more than implement what was
asked for in the quiz. It produces this path on the large map:

0,0 1,1 2,2 3,3 4,4 5,5 6,6 7,7 8,8 9,9 10,9 11,10 12,11
12,12 13,13 14,14 15,15 15,16 15,17 16,18 17,18 18,19 19,20
20,21 21,22 22,22 23,23 22,24 22,25 23,26 24,27 25,28 26,29
27,29 28,29 29,30 30,31 30,32 31,33 30,34 30,35 31,36 32,37
33,38 34,39 34,40 35,41 36,42 37,43 38,43 39,44 40,44 41,45
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.

 

[Daniel Martin]

Hi,

Here is my first submission to a ruby quiz

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.

--=20
s=3D%q( Daniel Martin -- (e-mail address removed)
puts "s=3D%q(#{s})",s.map{|i|i}[1] )
puts "s=3D%q(#{s})",s.map{|i|i}[1]

 

[Louis J Scoras]

#!/usr/bin/env ruby
#
# Louis J. Scoras <[email protected]>
# Monday, October 16, 2006
# Solution for Ruby Quiz 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| }
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 [](x,y)
@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 = @data, @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] >= 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