-
-
Save RLGGHC/b868e9633eb6b608e324 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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