Maze solving: Difference between revisions

Content added Content deleted
Line 2,540: Line 2,540:
# last coordinate being the one that shall be visited next.
# last coordinate being the one that shall be visited next.
def solve
def solve
queue = []
path = nil
# Clean up.
⚫
reset_visiting_state

⚫
# Enqueue start position.
# Enqueue start position.
enqueue_cell queue, [], @start_x, @start_y
@queue = []
enqueue_cell([], @start_x, @start_y)

⚫
# Loop as long as there are cells to visit and no solution has
# Loop as long as there are cells to visit and no solution has
# been found yet.
# been found yet.
⚫
path = nil
while !queue.empty? && !path
path = solve_visit_cell queue
until path || @queue.empty?
path = solve_visit_cell
end
end
⚫

# Clean up.
if path
⚫
# Mark the cells that make up the shortest path.
⚫
reset_visiting_state
⚫
for x, y in path

puts "No solution found?!" unless path
@path[x][y] = true
⚫
end

⚫
else
⚫
# Mark the cells that make up the shortest path.
for x, y in path
puts "No solution found?!"
@path[y][x] = true
end
end
end
end

private
private

# Maze solving visiting method.
# Maze solving visiting method.
def solve_visit_cell(queue)
def solve_visit_cell
# Get the next path.
# Get the next path.
path = queue.shift
path = @queue.shift
# The cell to visit is the last entry in the path.
# The cell to visit is the last entry in the path.
x, y = path.last
x, y = path.last

# Have we reached the end yet?
# Have we reached the end yet?
if x == @end_x && y == @end_y
return path if x == @end_x && y == @end_y
⚫
# Yes, we have!
⚫
return path
⚫
end

# Mark cell as visited.
# Mark cell as visited.
@visited[y][x] = true
@visited[x][y] = true

for dx, dy in DIRECTIONS
# Left
new_x = x - 1
if dx.nonzero?
⚫
# Left / Right
⚫
if move_valid?(new_x, y) && !@vertical_walls[y][new_x]
enqueue_cell queue, path, new_x, y
new_x = x + dx
⚫
if move_valid?(new_x, y) && !@vertical_walls[ [x, new_x].min ][y]
enqueue_cell(path, new_x, y)
⚫
end
⚫
else
⚫
# Top / Bottom
⚫
new_y = y + dy
⚫
if move_valid?(x, new_y) && !@horizontal_walls[x][ [y, new_y].min ]
enqueue_cell(path, x, new_y)
⚫
end
⚫
end
end
end

⚫
nil # No solution yet.
⚫
# Right
⚫
new_x = x + 1
if move_valid?(new_x, y) && !@vertical_walls[y][x]
enqueue_cell queue, path, new_x, y
⚫
end

⚫
# Top
⚫
new_y = y - 1
if move_valid?(x, new_y) && !@horizontal_walls[new_y][x]
enqueue_cell queue, path, x, new_y
⚫
end

⚫
# Bottom
⚫
new_y = y + 1
⚫
if move_valid?(x, new_y) && !@horizontal_walls[y][x]
enqueue_cell queue, path, x, new_y
⚫
end

⚫
# No solution yet.
return nil
end
end

# Enqueue a new coordinate to visit.
# Enqueue a new coordinate to visit.
def enqueue_cell(queue, path, x, y)
def enqueue_cell(path, x, y)
# Copy the current path, add the new coordinates and enqueue
# Add new coordinates to the current path and enqueue the new path.
# the new path.
@queue << path + [[x, y]]
⚫
path = path.dup
path << [x, y]
queue << path
end
end
end
end
Line 2,622: Line 2,609:
maze = Maze.new 20, 10
maze = Maze.new 20, 10
maze.solve
maze.solve
maze.print
maze.print</lang>

</lang>
Example output:
Example output:
<pre>
<pre>
+---+---+---+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+
+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| | | o o o o o | | o o | o o o | |
| * * | * | | * * | | | |
+ +---+ +---+ + + +---+---+---+ + + +---+ + +---+ +---+ +
+ + +---+---+---+ + + +---+---+ + + + +---+ + +---+ +---+
| | | | | o | | o o | | | o o | | o | |
| * | * * * * * | | * | * | | | |
+ + + +---+---+ + + +---+ +---+ +---+ +---+---+ + + +---+
+ +---+---+---+---+---+---+---+---+---+ + +---+---+ +---+---+---+---+ +
| | | | | o o | o o | | | | o o | |
| * | * * | * * * | * * | | | |
+ + +---+---+ +---+---+ + +---+---+ + +---+ + + +---+---+ +
+ + +---+---+---+---+ + + +---+---+---+ + + + +---+---+---+ +
| | | | o | o o o | | | | o o o o |
| * | | * * | * * | * * * * | | | |
+ +---+---+ +---+---+ + +---+---+ +---+---+ +---+ +---+---+---+ +
+ +---+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+---+ + +
| | | | o o | | o | | o o | o |
| * * * * | * * | | * | | | | |
+---+---+ +---+ + + +---+ + + +---+---+---+---+ +---+ + + +
+---+---+---+ + +---+---+ +---+ + +---+---+---+ +---+---+ + + +
| | | | | o o | o o o | | o o | o o |
| | * * | | * * | | | | | | |
+ + +---+ +---+---+---+---+---+ +---+---+ + +---+---+ +---+---+---+
+ + +---+---+---+ +---+---+ +---+ + +---+ + +---+---+---+ +---+
| | | | o | | o | | | o | |
| | | * * | * * * | * * | | | | | |
+ +---+ +---+---+---+---+---+ + +---+ + +---+ + + +---+---+ +
+---+ + + + +---+ + +---+ +---+---+ +---+ + +---+ +---+ +
| | | | | o o o | o o | | o | |
| | * | * * | * * | * * | | | | | | | |
+ + +---+---+ + + +---+---+---+---+ +---+ +---+---+ + +---+---+
+ + + +---+---+ +---+---+ +---+ + +---+---+ + + + + + +
| | | | | | o o o o | o o | o o o | |
| | | * | | * | * * * | | | | | | | |
+ + +---+ +---+ +---+ + +---+---+---+ +---+ +---+---+---+---+ +
+ +---+ +---+ + + +---+---+ +---+---+---+ +---+ + +---+---+ +
| | | o o o | o o o |
| * * | * * | | |
+---+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+
+---+ +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
</pre>
</pre>



=={{header|Tcl}}==
=={{header|Tcl}}==
Retrieved from "https://rosettacode.org/wiki/Maze_solving"