Class: Theseus::Solvers::Base

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

Overview

The abstract superclass for solver implementations. It simply provides some helper methods that implementations would otherwise have to duplicate.

Direct Known Subclasses

Astar, Backtracker

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

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

Create a new solver instance for the given maze, using the given start (a) and finish (b) points. The solution will not be immediately generated; to do so, use the #step or #solve methods.



20
21
22
23
24
25
 
# File 'lib/theseus/solvers/base.rb', line 20

def initialize(maze, a=maze.start, b=maze.finish)
  @maze = maze
  @a = a
  @b = b
  @solution = nil
end

Instance Attribute Details

#a ⇒ Object (readonly)

The point (2-tuple array) at which the solution path should begin.



12
13
14
 
# File 'lib/theseus/solvers/base.rb', line 12

def a
  @a
end

#b ⇒ Object (readonly)

The point (2-tuple array) at which the solution path should end.



15
16
17
 
# File 'lib/theseus/solvers/base.rb', line 15

def b
  @b
end

#maze ⇒ Object (readonly)

The maze object that this solver will provide a solution for.



9
10
11
 
# File 'lib/theseus/solvers/base.rb', line 9

def maze
  @maze
end

Instance Method Details

#current_solution ⇒ Object

Returns the current (potentially partial) solution to the maze. This is for use while the algorithm is running, so that the current best-solution may be inspected (or displayed).

Raises:

  • (NotImplementedError) 


83
84
85
 
# File 'lib/theseus/solvers/base.rb', line 83

def current_solution
  raise NotImplementedError, "solver subclasses must implement #current_solution"
end

#each ⇒ Object

If the maze is solved, this yields each point in the solution, in order.

If the maze has not yet been solved, this yields the result of calling #step, until the maze has been solved.



54
55
56
57
58
59
60
 
# File 'lib/theseus/solvers/base.rb', line 54

def each
  if solved?
    solution.each { |s| yield s }
  else
    yield s while s = step
  end
end

#solution ⇒ Object

Returns the solution path as an array of 2-tuples, beginning with #a and ending with #b. If the solution has not yet been generated, this will generate the solution first, and then return it.



35
36
37
38
 
# File 'lib/theseus/solvers/base.rb', line 35

def solution
  solve unless solved?
  @solution
end

#solve ⇒ Object

Generates the solution to the maze, and returns self. If the solution has already been generated, this does nothing.



42
43
44
45
46
47
48
 
# File 'lib/theseus/solvers/base.rb', line 42

def solve
  while !solved?
    step
  end

  self
end

#solved? ⇒ Boolean

Returns true if the solution has been generated.

Returns:

  • (Boolean) 


28
29
30
 
# File 'lib/theseus/solvers/base.rb', line 28

def solved?
  @solution != nil
end

#step ⇒ Object

Runs a single iteration of the solution algorithm. Returns false if the algorithm has completed, and non-nil otherwise. The return value is algorithm-dependent.

Raises:

  • (NotImplementedError) 


90
91
92
 
# File 'lib/theseus/solvers/base.rb', line 90

def step
  raise NotImplementedError, "solver subclasses must implement #step"
end

#to_path(options = {}) ⇒ Object

Returns the solution (or, if the solution is not yet fully generated, the current_solution) as a Theseus::Path object.



64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
 
# File 'lib/theseus/solvers/base.rb', line 64

def to_path(options={})
  path = @maze.new_path(options)
  prev = @maze.entrance

  (@solution || current_solution).each do |pt|
    how = path.link(prev, pt)
    path.set(pt, how)
    prev = pt
  end

  how = path.link(prev, @maze.exit)
  path.set(@maze.exit, how)

  path
end