Maze solving: Difference between revisions
Content deleted Content added
Line 2,540:
# last coordinate being the one that shall be visited next.
def solve
reset_visiting_state▼
# Enqueue start position.
enqueue_cell([], @start_x, @start_y)
# Loop as long as there are cells to visit and no solution has
# been found yet.
path = solve_visit_cell
end
# Mark the cells that make up the shortest path.▼
▲ reset_visiting_state
end▼
▲ # Mark the cells that make up the shortest path.
end
end
private
# Maze solving visiting method.
def solve_visit_cell
# Get the next path.
path = @queue.shift
# The cell to visit is the last entry in the path.
x, y = path.last
# Have we reached the end yet?
return path if x == @end_x && y == @end_y
# Yes, we have!▼
▲ return path
▲ end
# Mark cell as visited.
@visited[
for dx, dy in DIRECTIONS
if move_valid?(new_x, y) && !@vertical_walls[y][new_x]▼
enqueue_cell(path, new_x, y)
# Top / Bottom▼
enqueue_cell(path, x, new_y)
end
nil # No solution yet.▼
▲ # Right
▲ new_x = x + 1
▲ end
▲ # Top
▲ new_y = y - 1
▲ end
▲ # Bottom
▲ new_y = y + 1
▲ if move_valid?(x, new_y) && !@horizontal_walls[y][x]
▲ end
▲ # No solution yet.
end
# Enqueue a new coordinate to visit.
def enqueue_cell(
#
▲ path = path.dup
end
end
Line 2,622 ⟶ 2,609:
maze = Maze.new 20, 10
maze.solve
maze.print</lang>
Example output:
<pre>
+---+---+---+---+---+ +---+---+---+---+---+---+---+---
| * * | * | |
+ + +---+
|
+ +
|
+ + +---+---
|
+ +---+---
| * * * * | * * |
+---+---
|
+ + +---
| | | * * | * * * | * * |
| | * | * * | * * | * * |
+ + + +---+---
| | |
+ +---+ +---+ +
|
+---+ +---+---+---+---+---+---+---+---+---
</pre>
=={{header|Tcl}}==
| |||