Class: Theseus::Solvers::Astar

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

Overview

An implementation of the A* search algorithm. Although this can be used to search “perfect” mazes (those without loops), the recursive backtracker is more efficient in that case.

The A* algorithm really shines, though, with multiply-connected mazes (those with non-zero braid values, or some symmetrical mazes). In this case, it is guaranteed to return the shortest path through the maze between the two points.

Defined Under Namespace

Classes: Node

Instance Attribute Summary collapse

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) ⇒ Astar

:nodoc:



63
64
65
66
67
 
# File 'lib/theseus/solvers/astar.rb', line 63

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

Instance Attribute Details

#open ⇒ Object (readonly)

The open set. This is a linked list of Node instances, used by the A* algorithm to determine which nodes remain to be considered. It is always in sorted order, with the most likely candidate at the head of the list.



61
62
63
 
# File 'lib/theseus/solvers/astar.rb', line 61

def open
  @open
end

Instance Method Details

#current_solution ⇒ Object

:nodoc:



69
70
71
 
# File 'lib/theseus/solvers/astar.rb', line 69

def current_solution #:nodoc:
  @open.history + [@open.point]
end

#step ⇒ Object

:nodoc:



73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
# File 'lib/theseus/solvers/astar.rb', line 73

def step #:nodoc:
  return false unless @open

  current = @open

  if current.point == @b
    @open = nil
    @solution = current.history + [@b]
  else
    @open = @open.next

    @visits[current.point[1]][current.point[0]] |= current.under ? 2 : 1

    cell = @maze[current.point[0], current.point[1]]

    directions = @maze.potential_exits_at(current.point[0], current.point[1])
    directions.each do |dir|
      try = current.under ? (dir << Theseus::Maze::UNDER_SHIFT) : dir
      if cell & try != 0
        point = move(current.point, dir)
        next unless @maze.valid?(point[0], point[1])
        under = ((@maze[point[0], point[1]] >> Theseus::Maze::UNDER_SHIFT) & @maze.opposite(dir) != 0)
        add_node(point, under, current.path_cost+1, current.history + [current.point])
      end
    end
  end

  return current
end