Class: Theseus::Solvers::Astar::Node

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

Overview

This is the data structure used by the Astar solver to keep track of the current cost of each examined cell and its associated history (path back to the start).

Although you will rarely need to use this class, it is documented because applications that wish to visualize the A* algorithm can use the open set of Node instances to draw paths through the maze as the algorithm runs.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(point, under, path_cost, estimate, history) ⇒ Node

:nodoc:



47
48
49
50
51
 
# File 'lib/theseus/solvers/astar.rb', line 47

def initialize(point, under, path_cost, estimate, history) #:nodoc:
  @point, @under, @path_cost, @estimate = point, under, path_cost, estimate
  @history = history
  @cost = path_cost + estimate
end

Instance Attribute Details

#cost ⇒ Object

The total cost associated with this node (path_cost + estimate)



39
40
41
 
# File 'lib/theseus/solvers/astar.rb', line 39

def cost
  @cost
end

#estimate ⇒ Object

The (optimistic) estimate for how much further the exit is from this node.



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

def estimate
  @estimate
end

#history ⇒ Object (readonly)

The array of points leading from the starting point, to this node.



45
46
47
 
# File 'lib/theseus/solvers/astar.rb', line 45

def history
  @history
end

#next ⇒ Object

The next node in the linked list for the set that this node belongs to.



42
43
44
 
# File 'lib/theseus/solvers/astar.rb', line 42

def next
  @next
end

#path_cost ⇒ Object

The path cost of this node (the distance from the start to this cell, through the maze)



33
34
35
 
# File 'lib/theseus/solvers/astar.rb', line 33

def path_cost
  @path_cost
end

#point ⇒ Object

The point in the maze associated with this node.



26
27
28
 
# File 'lib/theseus/solvers/astar.rb', line 26

def point
  @point
end

#under ⇒ Object

Whether the node is on the primary plane (false) or the under plane (true)



29
30
31
 
# File 'lib/theseus/solvers/astar.rb', line 29

def under
  @under
end

Instance Method Details

#<=>(node) ⇒ Object

:nodoc:



53
54
55
 
# File 'lib/theseus/solvers/astar.rb', line 53

def <=>(node) #:nodoc:
  cost <=> node.cost
end