class Astrid::Finders::AStar

Attributes

allow_diagonal[RW]
current_grid[RW]
current_path[RW]

Public Class Methods

new(opts={}) click to toggle source
# File lib/astrid/finders/a_star.rb, line 9
      def initialize(opts={})
        @allow_diagonal = opts[:allow_diagonal] || false
        @heuristic = opts[:heuristic] || Heuristics::Manhattan
#        @diagonal_movement = opts[:diagonal_movement]
        @weight = opts[:weight] || 1;
      end

Public Instance Methods

final_path(_end_node) click to toggle source
# File lib/astrid/finders/a_star.rb, line 110
def final_path(_end_node)
  path = [_end_node]
  _current_node = _end_node

  while _current_node[:parent] do
    parent_position = _current_node[:parent]
    parent_node = @current_grid[parent_position]

    path << parent_node
    _current_node = parent_node
  end

  @current_path = path.reverse
end
find_path(start_node, end_node, grid) click to toggle source

A* requires x & y node = g, f, h, x, y, opened, walkable, closed, parent

extract a grid class clearly not optomized at all!

# File lib/astrid/finders/a_star.rb, line 26
def find_path(start_node, end_node, grid)
  start_node = sanitize(start_node)
  end_node = sanitize(end_node)
  if grid.nil?
    [start_node]
  else
    @current_grid = grid.clone
    _max_x = grid[:max_x]
    _max_y = grid[:max_y]

    raise 'max_x & max_y required' unless _max_x && _max_y

    _start_node = start_node.clone
    _end_node = end_node.clone

    heuristic = @heuristic.new(_end_node, @weight)

    _start_node[:f] = 0   # sum of g and h
    _start_node[:g] = 0   # steps to start node
    _start_node[:h] = nil # steps to end node
    _start_node[:opened] = true

    # use heap or tree for better perf
    open = []
    open.push _start_node

    while !open.empty? do
      _current_node = open.pop

      _current_node[:closed] = true
      @current_grid[node_to_a(_current_node)] = _current_node

      if node_to_a(_current_node) == node_to_a(_end_node)
        return final_path(_current_node)
      end

      new_g = _current_node[:g] + 1

      x = _current_node[:x]
      y = _current_node[:y]

      neighbors = []

      neighbors << [x-1, y] if x > 0
      neighbors << [x, y-1] if y > 0
      neighbors << [x+1, y] if x < _max_x-1
      neighbors << [x, y+1] if y < _max_y-1

      _neighbors = neighbors.map do |position|
        node = @current_grid[position]
        if node.nil? || node[:walkable]
          node ||= {}
          @current_grid[position] = node.merge({
            x: position.first,
            y: position[1],
            closed: false,
            opened: false
          })
        end
      end.compact

      _neighbors.each do |neighbor|
        if (!neighbor[:opened] || new_g < neighbor[:g])
          neighbor[:g] = new_g
          neighbor[:h] ||= heuristic.h(neighbor)
          neighbor[:f] = neighbor[:g] + neighbor[:h]
          neighbor[:parent] = node_to_a(_current_node)

          if (!neighbor[:opened])
            open.push neighbor
            neighbor[:opened] = true
          else
            # ???
            puts "got here some how!!!"
          end
        end
      end

      open.sort_by! {|i| [-i[:f], -i[:h]]}
      # grid_p
    end
  end
end
find_path_a(start_node, end_node, grid) click to toggle source
# File lib/astrid/finders/a_star.rb, line 125
def find_path_a(start_node, end_node, grid)
  p = find_path(start_node, end_node, grid)
  if p
    p.map do |node|
      node_to_a(node)
    end
  end
end
find_path_a_with_time(start_node, end_node, grid) click to toggle source
# File lib/astrid/finders/a_star.rb, line 134
def find_path_a_with_time(start_node, end_node, grid)
  result, time = find_path_a(start_node, end_node, grid)
end
grid_from_s_map(str) click to toggle source
# File lib/astrid/finders/a_star.rb, line 138
def grid_from_s_map(str)
  normalize = str.lines.reverse

  max_x = normalize.map(&:length).max
  max_y = normalize.length

  y_idx = 0
  normalize.inject({max_x: max_x, max_y: max_y}) do |grid, line|
    line.each_char.each_with_index do |c, x_idx|
      if c == '|' || c == '_'
        grid.merge!(
          [x_idx,y_idx] => { walkable: false}
        )
      end
    end
    y_idx += 1
    grid
  end
end
grid_p() click to toggle source
# File lib/astrid/finders/a_star.rb, line 164
def grid_p
  puts ""
  puts "#"*80
  s = ""
  n = @current_grid[:max_y].to_s.size + 2
  (-@current_grid[:max_y]..0).each do |y|
    (0..@current_grid[:max_x]).each do |x|
      node = @current_grid[[x,-y]]
      if node
        if node[:walkable].nil? || node[:walkable]
          s << node[:f].to_s.rjust(n, " ")
        else
          s << "|".rjust(n, " ")
        end
      else
        s << ''.rjust(n, '.')
      end
    end
    s << "\n"
  end
  puts s
end
node_to_a(node) click to toggle source
# File lib/astrid/finders/a_star.rb, line 187
def node_to_a(node)
  [node[:x], node[:y]]
end
sanitize(node) click to toggle source
# File lib/astrid/finders/a_star.rb, line 16
def sanitize(node)
  node
end
visited_positions() click to toggle source
# File lib/astrid/finders/a_star.rb, line 158
def visited_positions
  @current_grid.select do |k,v|
    k.is_a?(Array) && (v[:opened] || v[:closed])
  end.map {|a| a[1]}
end