Class: AStar::Node

Inherits:
Object show all
Defined in:
lib/ext/astar/node.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(x, y, move_cost = 0) ⇒ Node

Returns a new instance of Node.



14
15
16
17
18
 
# File 'lib/ext/astar/node.rb', line 14

def initialize(x,y,move_cost=0)
  @x,@y,@m=x,y,move_cost
  @g=@m
  @h=0
end

Instance Attribute Details

#g ⇒ Object (readonly)

Returns the value of attribute g.



12
13
14
 
# File 'lib/ext/astar/node.rb', line 12

def g
  @g
end

#h ⇒ Object (readonly)

Returns the value of attribute h.



12
13
14
 
# File 'lib/ext/astar/node.rb', line 12

def h
  @h
end

#m ⇒ Object (readonly)

Returns the value of attribute m.



12
13
14
 
# File 'lib/ext/astar/node.rb', line 12

def m
  @m
end

#parent ⇒ Object

class Node provides a node on a map which can be used for pathfinding. For Node to work with PriorityQueue and AMap it needs to implement the following <= used for comparing g values

used for finding the same node - using the x,y co-ordinates



11
12
13
 
# File 'lib/ext/astar/node.rb', line 11

def parent
  @parent
end

#x ⇒ Object (readonly)

Returns the value of attribute x.



12
13
14
 
# File 'lib/ext/astar/node.rb', line 12

def x
  @x
end

#y ⇒ Object (readonly)

Returns the value of attribute y.



12
13
14
 
# File 'lib/ext/astar/node.rb', line 12

def y
  @y
end

Instance Method Details

#<=(other) ⇒ Object 



31
32
33
34
 
# File 'lib/ext/astar/node.rb', line 31

def <=(other)
  #used for comparing cost so far
  @g<=other.g
end

#<=>(other) ⇒ Object 



25
26
27
28
29
 
# File 'lib/ext/astar/node.rb', line 25

def <=>(other)
  #can be used for ordering the priority list
  #puts "using <=>" #currently unused - can delete this line if required
  self.f<=>other.f
end

#==(other) ⇒ Object 



36
37
38
39
40
 
# File 'lib/ext/astar/node.rb', line 36

def ==(other)
  # nodes are == if x and y are the same - used for finding and removing same node
  return false if other==nil
  return (@x==other.x)&(@y==other.y)
end

#better?(other, tbmul = 1.01) ⇒ Boolean

Returns:

  • (Boolean) 


54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
 
# File 'lib/ext/astar/node.rb', line 54

def better?(other,tbmul=1.01)
  #which is better, self or other
  #can pass a tie-breaker multiplier (tbmul) if required
  if other==nil then return false end
  if self==other then return false end
  if f<other.f then 
    return true
  #here's the tie-breaker
  elsif f==other.f then
    nf=@g+tbmul*@h
    bf=other.g+tbmul*other.h
    if nf<bf then return true end
  end
  false
end

#calc_g(previous) ⇒ Object 



42
43
44
45
 
# File 'lib/ext/astar/node.rb', line 42

def calc_g(previous)
  #cost so far is total cost of previous step plus the movement cost of this one
  @g=previous.g+@m
end

#calc_h(goal) ⇒ Object 



47
48
49
50
 
# File 'lib/ext/astar/node.rb', line 47

def calc_h(goal)
  #using manhattan distance to generate a heuristic value
  @h=(@x-goal.x).abs+(@y-goal.y).abs
end

#f ⇒ Object 



51
52
53
 
# File 'lib/ext/astar/node.rb', line 51

def f
  @g+@h
end

#to_s ⇒ Object 



20
21
22
23
 
# File 'lib/ext/astar/node.rb', line 20

def to_s
  #prints the node in the following format [x,y] f:g:h
  "[#{@x},#{@y}] #{@g+@h}:#{@g}:#{@h}"
end