Skip to content

Instantly share code, notes, and snippets.

@RLGGHC

RLGGHC/grid.rb Secret

Forked from tjtuom/grid.rb
Created January 5, 2010 02:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save RLGGHC/b868e9633eb6b608e324 to your computer and use it in GitHub Desktop.
Save RLGGHC/b868e9633eb6b608e324 to your computer and use it in GitHub Desktop.
require 'node'
class Grid
def initialize(grid)
@grid = parse(grid)
end
def node(x, y)
@grid[y][x]
end
def nodes
@nodes ||= @grid.flatten
end
def walkable_nodes
@walkable_nodes ||= nodes.select { |node| node.walkable? }
end
def width
@grid[0].length
end
def height
@grid.length
end
def start_node
@start_node ||= walkable_nodes.find { |node| node.start? }
end
def end_node
@end_node ||= walkable_nodes.find { |node| node.end? }
end
def adjecents(center)
nodes.select do |node|
((center.x == node.x + 1 || center.x == node.x - 1) && center.y == node.y) ||
((center.y == node.y + 1 || center.y == node.y - 1) && center.x == node.x)
end
end
def to_s
@grid.map { |row| row.join("") }.join("\n")
end
private
def parse(grid)
rows = grid.split("\n")
matrix = Array.new(rows.length) { Array.new(rows.first.length) }
rows.each_with_index do |row, y|
row.split("").each_with_index do |char, x|
matrix[y][x] = Node.new(char, x, y)
end
end
matrix
end
end
require 'grid'
class Maze
def initialize(maze)
@maze = Grid.new(maze)
end
def solvable?
steps > 0
end
def steps
[path.length - 1, 0].max # remove start node or end node, the specs don't make this clear
end
def path
@path ||= get_path
end
def solved
clone = Marshal.load( Marshal.dump( @maze ) )
path.each do |node|
clone.node(node.x, node.y).content = "*" unless node.start? || node.end?
end
clone.to_s
end
private
def get_path
@open_list = []
@closed_list = []
@maze.start_node.g = 0
@open_list << @maze.start_node
until @open_list.empty? || @closed_list.include?(@maze.end_node)
@current_node = get_lowest_f(@open_list)
@closed_list << @open_list.delete(@current_node)
@nodes_to_test = @maze.adjecents(@current_node).select { |node| node.walkable? } - @closed_list
@nodes_to_test.each do |node|
if @open_list.include? node
old_g = node.g
new_g = @current_node.g + 1
if new_g < old_g
node.parent = @current_node
node.g = new_g
end
else
@open_list << node
node.parent = @current_node
node.g = node.parent.g + 1
#node.h = (@current_node.x - @maze.end_node.x).abs + (@current_node.y - @maze.end_node.y).abs
node.h = node.distance_from(@maze.end_node)
end
end
end
path = []
if @closed_list.include?(@maze.end_node)
node = @maze.end_node
until node.nil?
path << node
node = node.parent
end
end
path.reverse
end
def get_lowest_f(list)
list.sort.first
end
end
class Node
attr_reader :x, :y
attr_accessor :parent, :g, :h, :content
def initialize(content, x, y)
@x = x
@y = y
@content = content
end
def walkable?
content != "#"
end
def start?
content == "A"
end
def end?
content == "B"
end
def f
g + h
end
def <=>(other)
self.f <=> other.f
end
def distance_from(other)
Math.sqrt((self.x - other.x) ** 2 + (self.y - other.y) ** 2)
end
def to_s
content
end
end
require 'test/unit'
require 'grid'
GRID = %{
####
#AB#
####
}.strip
class GridTest < Test::Unit::TestCase
def setup
@grid = Grid.new(GRID)
end
def test_width
assert_equal 4, @grid.width
end
def test_height
assert_equal 3, @grid.height
end
def test_get_node
assert_equal 1, @grid.node(1, 0).x
assert_equal 2, @grid.node(0, 2).y
end
def test_get_walkable_nodes
assert_equal 1, @grid.walkable_nodes.first.x
assert_equal 1, @grid.walkable_nodes.first.y
assert_equal 2, @grid.walkable_nodes.last.x
assert_equal 1, @grid.walkable_nodes.last.y
end
def test_get_start_node
assert_equal 1, @grid.start_node.x
assert_equal 1, @grid.start_node.y
end
def test_get_end_node
assert_equal 2, @grid.end_node.x
assert_equal 1, @grid.end_node.y
end
def test_get_adjecents
node = @grid.node(0, 1)
assert_equal 3, @grid.adjecents(node).length
node = @grid.node(1, 1)
assert_equal 4, @grid.adjecents(node).length
end
def test_to_str
assert_equal @grid.to_s, GRID
end
end
require 'test/unit'
require 'node'
class NodeTest < Test::Unit::TestCase
def test_walkable
assert_equal true, Node.new(" ", 0, 0).walkable?
assert_equal false, Node.new("#", 0, 0).walkable?
assert_equal true, Node.new("A", 0, 0).walkable?
assert_equal true, Node.new("B", 0, 0).walkable?
end
def test_start
assert_equal true, Node.new("A", 0, 0).start?
assert_equal false, Node.new(" ", 0, 0).start?
end
def test_end
assert_equal true, Node.new("B", 0, 0).end?
assert_equal false, Node.new(" ", 0, 0).end?
end
def test_f
node = Node.new(" ", 0, 0)
node.g = 2
node.h = 3
assert_equal 5, node.f
end
def test_distance_from
a = Node.new(" ", 1, 1)
b = Node.new(" ", 5, 4)
assert_equal 5, a.distance_from(b)
end
def test_to_s
assert_equal "#", Node.new("#", 0, 0).to_s
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment