diff options
| -rw-r--r-- | main.rb | 13 | ||||
| -rw-r--r-- | maze.rb | 32 | ||||
| -rw-r--r-- | maze_solver.rb | 38 |
3 files changed, 77 insertions, 6 deletions
@@ -1,8 +1,15 @@ require_relative 'maze_generator' +require_relative 'maze_solver' +require_relative 'pos' width = ARGV[0].to_i height = ARGV[1].to_i -mazeGenerator = MazeGenerator.new(width, height, 40) -mazeGenerator.generate! -puts mazeGenerator.maze +maze_generator = MazeGenerator.new(width, height, 10000000) +maze_generator.generate! + +maze = maze_generator.maze + +maze_solver = MazeSolver.new(maze, Pos.new(0, 0), Pos.new(width - 1, height - 1)) +maze_solver.solve! +puts maze.to_s('', maze_solver.stack) @@ -3,6 +3,8 @@ Tile = Struct.new(:pos, :up, :right, :down, :left) class Maze attr_reader :width attr_reader :height + attr_accessor :start_pos + attr_accessor :end_pos def initialize(width, height) @width = width @@ -37,6 +39,18 @@ class Maze neighbors end + def open_neighbors(pos) + neighbors = [] + + tile = get(pos) + + [:up, :right, :down, :left].each do |dir| + neighbors.push(pos.move(dir)) if tile[dir] == false + end + + neighbors + end + def set(pos, dir, state) raise IndexError if pos.x >= @width raise IndexError if pos.y >= @height @@ -53,8 +67,8 @@ class Maze end end - def to_s(prefix='') - drawingField = Array.new(@height * 2 + 1) { " " * (@width * 2 + 1) } + def to_s(prefix='', path=[]) + drawingField = Array.new(@height * 2 + 1) { Array.new(@width * 2 + 1) { " " } } @v_walls.each_index do |x| @v_walls[x].each_index do |y| @@ -76,6 +90,18 @@ class Maze end end - drawingField.map { |line| prefix + line }.join("\n") + bright_red_block = "\e[0;31;1m█\e[0m" + + path.each_index do |i| + drawingField[path[i].y * 2 + 1][path[i].x * 2 + 1] = bright_red_block + if i > 0 + wall_pos = Pos.new(path[i - 1].x * 2 + 1, path[i - 1].y * 2 + 1) + .move(path[i].dir_from(path[i - 1])) + + drawingField[wall_pos.y][wall_pos.x] = bright_red_block + end + end + + drawingField.map { |line| prefix + line.join("") }.join("\n") end end diff --git a/maze_solver.rb b/maze_solver.rb new file mode 100644 index 0000000..d529495 --- /dev/null +++ b/maze_solver.rb @@ -0,0 +1,38 @@ +require_relative 'pos' +require_relative 'maze' + +class MazeSolver + attr_reader :maze + attr_reader :stack + + def initialize(maze, start_pos, end_pos) + @maze = maze + @start_pos = start_pos + @end_pos = end_pos + @stack = [start_pos] + @visitedTiles = Array.new(@maze.width) { Array.new(@maze.height) { false } } + end + + def solve!() + while @stack.last != @end_pos + step() + end + end + + def step() + current_tile = @stack.last + + neighbors = @maze.open_neighbors(current_tile) + neighbors.select! do |neighbor| + @visitedTiles[neighbor.x][neighbor.y] == false + end + + if neighbors.empty? + @stack.pop() + else + randomNeighbor = neighbors.sample + @stack.push(randomNeighbor) + @visitedTiles[randomNeighbor.x][randomNeighbor.y] = true + end + end +end |