secret
Created — forked from voxdei/guillaumepetit.rb

  • Download Gist
guillaumepetit.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124
class Maze
# Constants used for the search and setup
NOTHING = 0
WALL = 1
A = 2
B = 3
WALK = 4
def initialize(maze)
@maze = Array.new
# a little bit of parsing !
splitted_maze = maze.split("\n")
splitted_maze.each_index do |y|
array_line = Array.new
x = 0
splitted_maze[y].each_char do |char|
case char
when "#"
array_line << WALL
when "A"
array_line << A
@start = { :x => x, :y => y }
when "B"
array_line << B
else
array_line << NOTHING
end
x += 1
end
@maze << array_line
end
# let's start the engine !!!
# first, we change the starting point, from A to Nothing
# for simplification purpose
@maze[@start[:y]][@start[:x]] = NOTHING
# starting (and shortest) depth
@depth = 0
# will try every possible path, and remember the shortest one
find_path(@start[:x], @start[:y], @depth)
# fixing our starting point modification thing back
# for printing purpose only
@maze[@start[:y]][@start[:x]] = A
end
def steps
@depth
end
def solvable?
@depth > 0
end
# print the initial maze setup
def print_maze
pm @maze
end
# print the maze with the solution path in dot
def print_solution
if solvable?
p "This maze can be solved in #{steps} steps"
pm @shortest_path
else
p "No path found for this maze"
end
end
private
# print a maze
def pm(maze)
maze.each do |array_line|
line = array_line.join
line.gsub!(/0/, " ")
line.gsub!(/1/, "#")
line.gsub!(/2/, "A")
line.gsub!(/3/, "B")
line.gsub!(/4/, ".")
p line
end
end
def find_path(x, y, depth)
if @maze[y][x] == B # found the B
# did we find a shorter path ? (or the first one)
if depth < @depth || @depth == 0
# yep ! so let's save the steps
@depth = depth
# then we make a snapshot of the current path
@shortest_path = Marshal.load( Marshal.dump(@maze) )
# fixing our starting point modification thing back
# for printing purpose only
@shortest_path[@start[:y]][@start[:x]] = A
end
# we stop the process for this node search
# but it will continu to find another path, hopefully shorter !
return
end
return if @maze[y][x] > 0 # this place is not "walkable"
# let's mark this case
@maze[y][x] = WALK
# let's try the 4 direction in recursion
find_path(x, y-1, depth+1) if y > 0 # up first, only if possible
find_path(x+1, y, depth+1) if x+1 < @maze[y].size # right now, only if possible
find_path(x, y+1, depth+1) if y+1 < @maze.size # then down, only if possible
find_path(x-1, y, depth+1) if x > 0 # and left to finish, only if possible
# we clean our path, since we are going back
@maze[y][x] = NOTHING
end
end

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.