1 mazeDef1 = <<MAZE_STRING
2 #########################
3 #s--###----#####-#####-##
4 ###-#---##-##--#-##-----#
5 ###-#-#-#--##-##-##-###-#
6 #---#-#-#-###-##-##-##--#
7 #-#---#-#---#-##----##-##
8 #-#-#-#-#-#-#-##-########
9 #-#-#-#-#-#---##--------#
10 #####-###---###########-#
11 #####-#####-###########-#
12 #####------------------e#
13 #########################
14 MAZE_STRING
15
16 mazeDef2 = <<MAZE_STRING
17 #########################
18 #e--###----#####-#####-##
19 ###-#---##-##--#-##-----#
20 ###-#-#-#--##-##-##-###-#
21 #---#-#-#-###-##-##-##--#
22 #-#---#-#---#-##s---##-##
23 #-#-#-#-#-#-#-##-########
24 #-#-#-#-#-#---##--------#
25 #####-###---###########-#
26 #####-#####-###########-#
27 #####-------------------#
28 #########################
29 MAZE_STRING
30
31 mazeDef3= <<MAZE_STRING
32 #########################
33 #e--###----#####-#####-##
34 ###-#---##-##--#-##-----#
35 ###-#-#-#--##-##-##-###-#
36 #---#-#-#-###-#####-##--#
37 #-#---#-#---#-##s#--##-##
38 #-#-#-#-#---#-##-########
39 #-#-#-#-#####-##--------#
40 #####-###---###########-#
41 #####-#####-###########-#
42 #####-------------------#
43 #########################
44 MAZE_STRING
45
46 class MazeSolver
47
48 attr_writer :maze
49
50 def initialize (maze)
51 @maze = maze
52 # initialize array of potential nodes and visited nodes
53 @potential = Array.new
54 @visited = Array.new
55 prepare_maze
56 end
57
58 def prepare_maze
59 find_row_length
60 find_start
61 find_end
62 find_valid_nodes
63 end
64
65 def find_row_length
66 @length = (@maze.split)[0].length + 1 # includes the new line
67 end
68
69 def find_valid_nodes
70 # find the spaces from the maze
71 count = 0
72 @maze.each_byte do |c|
73 if c == 45 # 45 = '-'
74 @potential << count
75 end
76 count += 1
77 end
78
79 #include end as a potential node
80 @potential << @finish
81 end
82
83 # find the start
84 def find_start
85 @start = @maze.index("s")
86 end
87
88 # find the end
89 def find_end
90 @finish = @maze.index("e")
91 end
92
93 # simple traversal methods through the maze
94 def up (currentNode)
95 currentNode - @length
96 end
97
98 def right (currentNode)
99 currentNode + 1
100 end
101
102 def down (currentNode)
103 currentNode + @length
104 end
105
106 def left (currentNode)
107 currentNode - 1
108 end
109
110 # creates the new set of nodes that will be passed on the stack for this iteration
111 def prepare_traversal_for_current_node(currentNode, potentialNodes, visitedNodes)
112 @temp = Array.new(potentialNodes)
113 @temp.delete(currentNode)
114 @visit = Array.new(visitedNodes)
115 @visit << currentNode
116 end
117
118 # the recursive function that does a depth first search for the path
119 def traverse (currentNode, potentialNodes, visitedNodes)
120 # terminating case
121 if (currentNode == @finish)
122 p "Terminated"
123 return true
124 end
125
126 # we need to traverse some more
127 # up
128 if potentialNodes.include?(up(currentNode))
129 # p "up"
130 prepare_traversal_for_current_node(currentNode, potentialNodes, visitedNodes)
131 if traverse(up(currentNode), @temp, @visit)
132 @maze[currentNode] = "x"
133 return true
134 end
135 end
136 # right
137 if potentialNodes.include?(right(currentNode))
138 # p "right"
139 prepare_traversal_for_current_node(currentNode, potentialNodes, visitedNodes)
140 if traverse(right(currentNode), @temp, @visit)
141 @maze[currentNode] = "x"
142 return true
143 end
144 end
145 # down
146 if potentialNodes.include?(down(currentNode))
147 # p "down"
148 prepare_traversal_for_current_node(currentNode, potentialNodes, visitedNodes)
149 if traverse(down(currentNode), @temp, @visit)
150 @maze[currentNode] = "x"
151 return true
152 end
153 end
154 # left
155 if potentialNodes.include?(left(currentNode))
156 # p "left"
157 prepare_traversal_for_current_node(currentNode, potentialNodes, visitedNodes)
158 if traverse(left(currentNode), @temp, @visit)
159 @maze[currentNode] = "x"
160 return true
161 end
162 end
163 # p "done one call"
164 end
165
166 def solve_maze
167 traverse(@start, @potential, @visited)
168 print @maze
169 end
170 end
171
172 # Run
173 mazeSolver = MazeSolver.new(mazeDef1)
174 mazeSolver.solve_maze
175 mazeSolver.maze = mazeDef2
176 mazeSolver.solve_maze
177 mazeSolver.maze = mazeDef3
178 mazeSolver.solve_maze