class AStar::AMap

Attributes

nodes[R]

Public Class Methods

load(filename) click to toggle source
# File lib/ext/astar/AMap.rb, line 32
def self.load(filename)
  #loads a map from a text file - see map.txt for example, reproduced here
  #~ 1,1,1,1,1,1
  #~ 1,2,2,2,2,1
  #~ 1,3,3,3,3,1
  #~ 1,3,3,3,3,1
  #~ 1,2,2,2,2,1
  #~ 1,1,1,1,1,1
  mmap=[]
  File.open(filename) do |f|
    f.each_line do |line|
      linearr=[]
      line.chomp.split(',').each do |e|
        linearr.push(e.to_i)
      end
      mmap.push(linearr)
    end
  end
  return AMap.new(mmap)
end
new(costmap) click to toggle source
# File lib/ext/astar/AMap.rb, line 11
def initialize(costmap)
  #cost map is a 2D array - eg a 2x2 map is AMap.new([[3,5],[3,2]])
  # the values are the movement cost for the node at those co-ordinates
  #should do some error checking for size of the map, but anyway
  # note that the costmap array is indexed @costmap[y][x],
  # which is the opposite way to Node(x,y)
  ##note that it's probably easier to use AMap.load(file)
  @costmap=costmap
  @height=costmap.size
  @width=costmap.first.size
  @nodes=[]
  @output="\n"
  costmap.each_index do |row|
    costmap[row].each_index do |col|
      @nodes.push(Node.new(col,row,costmap[row][col]))
      @output<<"|#{costmap[row][col]}"
    end
    @output<<"|\n"
  end
end

Public Instance Methods

astar(node_start,node_goal) click to toggle source
# File lib/ext/astar/AMap.rb, line 80
def astar(node_start,node_goal)
  iterations=0
  open=PriorityQueue.new()
  closed=PriorityQueue.new()
  node_start.calc_h(node_goal)
  open.push(node_start)
  while !open.empty? do
    iterations+=1 #keep track of how many times this itersates
    node_current=open.find_best
    if node_current==node_goal then #found the solution
      puts "Iterations: #{iterations}"
      return node_current 
    end       
    generate_successor_nodes(node_current) do |node_successor|
      #now doing for each successor node of node_current
      node_successor.calc_g(node_current)
      #skip to next node_successor if better one already on open or closed list
      if open_successor=open.find(node_successor) then 
        if open_successor<=node_successor then next end  #need to account for nil result
      end
      if closed_successor=closed.find(node_successor) then
        if closed_successor<=node_successor then next end 
      end
      #still here, then there's no better node yet, so remove any copies of this node on open/closed lists
      open.remove(node_successor)
      closed.remove(node_successor)
      # set the parent node of node_successor to node_current
      node_successor.parent=node_current
      # set h to be the estimated distance to node_goal using the heuristic
      node_successor.calc_h(node_goal)
      # so now we know this is the best copy of the node so far, so put it onto the open list
      open.push(node_successor)
    end
    #now we've gone through all the successors, so the current node can be closed
    closed.push(node_current)
  end
end
co_ord(x,y) click to toggle source
# File lib/ext/astar/AMap.rb, line 118
def co_ord(x,y)
  a=Node.new(x,y)
  @nodes.find {|n| n==a}
end
generate_successor_nodes(anode) { |newnode| ... } click to toggle source
# File lib/ext/astar/AMap.rb, line 53
def generate_successor_nodes(anode)
  # determine nodes bordering this one - only North,S,E,W for now
  # no boundary condition check, eg if anode.x==-4
  # considers a wall to be a 0 so therefore not allow that to be a neighbour
  north=@costmap[anode.y-1][(anode.x)] unless (anode.y-1)<0 #boundary check for -1
  south=@costmap[anode.y+1][(anode.x)] unless (anode.y+1)>(@height-1)
  east=@costmap[anode.y][(anode.x+1)] unless (anode.x+1)>(@width-1)
  west=@costmap[anode.y][(anode.x-1)] unless (anode.x-1)<0 #boundary check for -1
  
  if (west && west>0) then # not on left edge, so provide a left-bordering node
    newnode=Node.new((anode.x-1),anode.y,@costmap[anode.y][(anode.x-1)])
    yield newnode
  end
  if (east && east>0) then # not on right edge, so provide a right-bordering node
    newnode=Node.new((anode.x+1),anode.y,@costmap[anode.y][(anode.x+1)])
    yield newnode
  end
  if (north && north>0) then # not on left edge, so provide a left-bordering node
    newnode=Node.new(anode.x,(anode.y-1),@costmap[(anode.y-1)][anode.x])
    yield newnode
  end
  if (south && south>0) then # not on right edge, so provide a right-bordering node
    newnode=Node.new(anode.x,(anode.y+1),@costmap[(anode.y+1)][anode.x])
    yield newnode
  end    
end
show_path(anode) click to toggle source
# File lib/ext/astar/AMap.rb, line 127
def show_path(anode)
  #shows the path back from node 'anode' by following the parent pointer
  curr=anode
  pathmap=@costmap.clone
  while curr.parent do
    pathmap[curr.y][curr.x]='*'
    curr=curr.parent
  end
  pathmap[curr.y][curr.x]='*'
  pathstr="\n"
  pathmap.each_index do |row|
    pathmap[row].each_index do |col|
      pathstr<<"|#{pathmap[row][col]}"
    end
    pathstr<<"|\n"
  end
  pathstr
end
to_s() click to toggle source
# File lib/ext/astar/AMap.rb, line 123
def to_s
  @output
end