From cff0b04e9092613ee24a6a291ba42c086b65c7c8 Mon Sep 17 00:00:00 2001
From: Noah Loomans <noahloomans@gmail.com>
Date: Sun, 22 Apr 2018 14:51:02 +0200
Subject: Create MazeSolver

---
 main.rb        | 13 ++++++++++---
 maze.rb        | 32 +++++++++++++++++++++++++++++---
 maze_solver.rb | 38 ++++++++++++++++++++++++++++++++++++++
 3 files changed, 77 insertions(+), 6 deletions(-)
 create mode 100644 maze_solver.rb

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
-- 
cgit v1.1