Class: AStar

Inherits:
Object
  • Object
show all
Defined in:
lib/IFMapper/AStar.rb

Overview

A class used for path finding. This is largely based on C++ code by Justin Heyes-Jones, albeit simplified

Defined Under Namespace

Classes: Node

Constant Summary collapse

SEARCH_STATE_NOT_INITIALIZED = 
0
SEARCH_STATE_SEARCHING = 
1
SEARCH_STATE_SUCCEEDED = 
2
SEARCH_STATE_FAILED = 
3

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ AStar

Returns a new instance of AStar.



165
166
167
168
 
# File 'lib/IFMapper/AStar.rb', line 165

def initialize
  @state = SEARCH_STATE_NOT_INITIALIZED
  @successors = []
end

Instance Attribute Details

#closed_list ⇒ Object 



29
30
31
32
33
34
35
 
# File 'lib/IFMapper/AStar.rb', line 29

def closed_list
  puts "Closed List:"
  @closed_list.each { |n|
    p n
  }
  puts "Closed List # of nodes: #{@closed_list.size}"
end

#open_list ⇒ Object 



21
22
23
24
25
26
27
 
# File 'lib/IFMapper/AStar.rb', line 21

def open_list
  puts "Open List:"
  @open_list.each { |n|
    p n
  }
  puts "Closed List # of nodes: #{@open_list.size}"
end

#start ⇒ Object (readonly)

Returns the value of attribute start.



10
11
12
 
# File 'lib/IFMapper/AStar.rb', line 10

def start
  @start
end

#state ⇒ Object (readonly)

Returns the value of attribute state.



11
12
13
 
# File 'lib/IFMapper/AStar.rb', line 11

def state
  @state
end

#successors ⇒ Object (readonly)

Returns the value of attribute successors.



12
13
14
 
# File 'lib/IFMapper/AStar.rb', line 12

def successors
  @successors
end

Instance Method Details

#add_successor(info) ⇒ Object 



150
151
152
 
# File 'lib/IFMapper/AStar.rb', line 150

def add_successor( info )
  @successors << Node.new(info)
end

#goals(start, goal) ⇒ Object

sets start and end goals and initializes A* search



61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
# File 'lib/IFMapper/AStar.rb', line 61

def goals( start, goal )
  @start = Node.new( start )
  @start.g    = 0.0
  @start.h    = start.distance_estimate( goal )
  @start.f    = @start.h

  @open_list  = []
  @open_list.push( @start )
  @closed_list = []

  @goal  = Node.new( goal )
  
  @state = SEARCH_STATE_SEARCHING
end

#path ⇒ Object

return solution as an path (ie. an array of [x,y] coordinates)



155
156
157
158
159
160
161
162
163
 
# File 'lib/IFMapper/AStar.rb', line 155

def path
  p = []
  curr = @start
  while curr
    p << [curr.info.x, curr.info.y]
    curr = curr.child
  end
  return p
end

#search_step ⇒ Object

Advances one search step



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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
 
# File 'lib/IFMapper/AStar.rb', line 77

def search_step
  if @open_list.empty?
    @state = SEARCH_STATE_FAILED
    return @state
  end

  # Pop the best node (the one with the lowest f)
  n = @open_list.pop

  # Check for the goal.  Once we pop that, we are done
  if n.info.is_goal?( @goal.info )
    # The user is going to use the Goal Node he passed in 
    # so copy the parent pointer of n 
    @goal.parent = n.parent
    # Special case is that the goal was passed in as the start state
    # so handle that here
    if n != @start
	child  = @goal
	parent = @goal.parent

	while child != @start
 parent.child = child
 child = parent
 parent = parent.parent
	end
    end
    @state = SEARCH_STATE_SUCCEEDED
    return @state
  else
    # Not goal, get successors
    n.info.successors( self, n.parent )
    @successors.each do |s|
	newg = n.g + n.info.cost( s.info )

	# Now, we need to find out if this node is on the open or close lists
	# If it is, but the node that is already on them is better (lower g)
	# then we can forget about this successor
	open = @open_list.find { |e| e.info.is_same?( s.info ) }
	# State in open list is cheaper than this successor
	next if open and open.g <= newg

	closed = @closed_list.find { |e| e.info.is_same?( s.info ) }
	# We found a cheaper state in closed list
	next if closed and closed.g <= newg
	
	# This node is the best node so far so let's keep it and set up
	# its A* specific data
	s.parent = n
	s.g = newg
	s.h = s.info.distance_estimate( @goal.info )
	s.f = s.g + s.h

	# Remove succesor from closed list if it was on it
	@closed_list.delete(closed) if closed
	# Change succesor from open list if it was on it
	if open
 open.parent = s.parent
 open.g = s.g
 open.h = s.h
 open.f = s.f
	else
 @open_list.push(s)
	end
    end
    # Make sure open list stays sorted based on f
    @open_list.sort!

    @closed_list.push(n)
    @successors.clear
  end
  return @state
end