Christopher Dicely
2/3/2009 2:25:00 AM
Here's my solution. The request for the unobstructed distance and then
the obstructed distance immediately suggested the A* algorithm (since
the unobstructed distance is clearly an admissible heuristic.) Though
I knew an algorithm to use, I had to look up the algorithm itself.
---[main.rb]
require 'hex_board'
# board = HexBoard.new(9, 9)
# board = HexBoard.new(9, 9) { |row,col| ((4-row).abs <= 1) && (col == 5) }
# board = HexBoard.new(9, 9) { |row,col| [row,col]==[4,4] ? true : rand(6)==0 }
board = HexBoard.new(9, 9) { |row,col| [row,col]==[4,4] ? false : rand(6)==0 }
board.draw
board.draw_map
board.draw_obstructed
---[hex_board.rb]
require 'set'
require 'hex'
class HexBoard
def initialize(rows=9, cols=9)
@rows, @cols = rows, cols
@board = Array.new(@rows) do |row|
Array.new(@cols) do |col|
Hex.new(:obstructed => (block_given? && yield(row,col)))
end
end
end
def distance(start, goal)
if ((start[0]-goal[0]) < 0) == ((start[1]-goal[1]) < 0)
[(start[0]-goal[0]).abs, (start[1]-goal[1]).abs].max
else
(start[0]-goal[0]).abs+(start[1]-goal[1]).abs
end
end
def neighbors(position)
[
[position[0], position[1]-1],
[position[0]-1, position[1]-1],
[position[0]-1, position[1]],
[position[0], position[1]+1],
[position[0]+1, position[1]+1],
[position[0]+1, position[1]]
].delete_if {|x,y| x<0 || y <0 || x>@rows || y>@cols}
end
# Distance between two hexes on the board having to navigate obstructions
# Obstructions are detected by passing the hex in question into the block
# block will return true if the yielded hex should be counted as obstructed
# EX: dist = obstructed_distance(a, b) { |hex| hex.obstructed? }
def obstructed_distance(start, goal)
return nil if (yield(@board[goal[0]][goal[1]]) ||
yield(@board[start[0]][start[1]]))
closed_set = Set.new
@board.size.times {|row|
row.size.times {|col|
if yield @board[row][col]
closed_set << [row,col]
end
}
}
open_set = [start]
actual_distance_to = {start=>0}
estimated_distance_from = {start=>distance(start,goal)}
estimated_distance_through = {start=>estimated_distance_from[start]}
while !(open_set.empty?)
node = open_set.first
return actual_distance_to[node] if node == goal
open_set.delete node
closed_set << node
neighbors(node).each { |neighbor|
next if closed_set.include? neighbor
distance_this_route = actual_distance_to[node] + 1
this_route_good = false
if !open_set.include?(neighbor)
open_set << neighbor
estimated_distance_from[neighbor] = distance(neighbor,goal)
this_route_good = true
elsif distance_this_route < actual_distance_to[neighbor]
this_route_good = true
end
if this_route_good
actual_distance_to[neighbor] = distance_this_route
estimated_distance_through[neighbor] = distance_this_route +
estimated_distance_from[neighbor]
open_set.sort! {|x,y|
estimated_distance_through[x]<=>estimated_distance_through[y]}
end
}
end
return nil
end
# This will print the board out to the console to let you
# know if you're on the right track
def draw
@rows.times do |row|
line = ''
line << "#{row}:"
(@cols - row).times {line << ' '}
@cols.times do |col|
line << (distance([4,4], [row,col]) || 'X').to_s
line << ' '
end
puts line
end
end
def draw_map
@rows.times do |row|
line = ''
line << "#{row}:"
(@cols - row).times {line << ' '}
@cols.times do |col|
line << (@board[row][col].obstructed? ? 'X' : 'O')
line << ' '
end
puts line
end
end
def draw_obstructed
@rows.times do |row|
line = ''
line << "#{row}:"
(@cols - row).times {line << ' '}
@cols.times do |col|
line << (obstructed_distance([4,4], [row,col]) {|hex|
hex.obstructed?} || 'X').to_s
line << ' '
end
puts line
end
end
def [](row)
@board[row]
end
end
---[hex.rb]
class Hex
def initialize(opts={})
@obstructed = !!opts[:obstructed]
end
def obstructed?
@obstructed
end
end