Class: Theseus::Solvers::Backtracker

Inherits:
Base
  • Object
show all
Defined in:
lib/theseus/solvers/backtracker.rb

Overview

An implementation of a recursive backtracker for solving a maze. Although it will work (eventually) for multiply-connected mazes, it will almost certainly not return an optimal solution in that case. Thus, this solver is best suited only for “perfect” mazes (those with no loops).

For mazes that contain loops, see the Theseus::Solvers::Astar class.

Constant Summary collapse

VISIT_MASK = 
{ false => 1, true => 2 }

Instance Attribute Summary

Attributes inherited from Base

#a, #b, #maze

Instance Method Summary collapse

Methods inherited from Base

#each, #solution, #solve, #solved?, #to_path

Constructor Details

#initialize(maze, a = maze.start, b = maze.finish) ⇒ Backtracker

:nodoc:



12
13
14
15
16
 
# File 'lib/theseus/solvers/backtracker.rb', line 12

def initialize(maze, a=maze.start, b=maze.finish) #:nodoc:
  super
  @visits = Array.new(@maze.height) { Array.new(@maze.width, 0) }
  @stack = []
end

Instance Method Details

#current_solution ⇒ Object

:nodoc:



20
21
22
 
# File 'lib/theseus/solvers/backtracker.rb', line 20

def current_solution #:nodoc:
  @stack[1..-1].map { |item| item[0] }
end

#step ⇒ Object

:nodoc:



24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
# File 'lib/theseus/solvers/backtracker.rb', line 24

def step #:nodoc:
  if @stack == [:fail]
    return false
  elsif @stack.empty?
    @stack.push(:fail)
    @stack.push([@a, @maze.potential_exits_at(@a[0], @a[1]).dup])
    return @a.dup
  elsif @stack.last[0] == @b
    @solution = @stack[1..-1].map { |pt, tries| pt }
    return false
  else
    x, y = @stack.last[0]
    cell = @maze[x, y]
    loop do
      try = @stack.last[1].pop

      if try.nil?
        spot = @stack.pop
        x, y = spot[0]
        return :backtrack
      elsif (cell & try) != 0
        # is the current path an "under" path for the current cell (x,y)?
        is_under = (try & Maze::UNDER != 0)

        dir = is_under ? (try >> Maze::UNDER_SHIFT) : try
        opposite = @maze.opposite(dir)

        nx, ny = @maze.move(x, y, dir)

        # is the new path an "under" path for the next cell (nx,ny)?
        going_under = @maze[nx, ny] & (opposite << Maze::UNDER_SHIFT) != 0

        # might be out of bounds, due to the entrance/exit passages
        next if !@maze.valid?(nx, ny) || (@visits[ny][nx] & VISIT_MASK[going_under] != 0)

        @visits[ny][nx] |= VISIT_MASK[going_under]
        ncell = @maze[nx, ny]
        p = [nx, ny]

        if ncell & (opposite << Maze::UNDER_SHIFT) != 0 # underpass
          unders = (ncell & Maze::UNDER) >> Maze::UNDER_SHIFT
          exit_dir = unders & ~opposite
          directions = [exit_dir << Maze::UNDER_SHIFT]
        else
          directions = @maze.potential_exits_at(nx, ny) - [@maze.opposite(dir)]
        end

        @stack.push([p, directions])
        return p.dup
      end
    end
  end
end