summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--main.rb13
-rw-r--r--maze.rb32
-rw-r--r--maze_solver.rb38
3 files changed, 77 insertions, 6 deletions
diff --git a/main.rb b/main.rb
index a56a2c5..800cb89 100644
--- a/main.rb
+++ b/main.rb
@@ -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)
diff --git a/maze.rb b/maze.rb
index f3cbe1f..7e26735 100644
--- a/maze.rb
+++ b/maze.rb
@@ -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