Instantly share code, notes, and snippets.

# tjtuom/grid.rbSecret Created Jan 1, 2010

 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