class AiController::PathCompute

Path finding algorithm

Public Class Methods

new(battle, map, entity) click to toggle source

Creates a path finder @param battle [Natural20::Battle] @param map [Natural20::BattleMap] @param entity [Natural20::Entity]

# File lib/natural_20/ai_controller/path_compute.rb, line 11
def initialize(battle, map, entity)
  @entity = entity
  @map = map
  @battle = battle
  @max_x, @max_y = @map.size
end

Public Instance Methods

backtrace(source_x, source_y, destination_x, destination_y, show_cost: false) click to toggle source
# File lib/natural_20/ai_controller/path_compute.rb, line 33
def backtrace(source_x, source_y, destination_x, destination_y, show_cost: false)
  path = []
  current_node = [destination_x, destination_y]
  return nil if @distances[destination_x][destination_y] == MAX_DISTANCE # no route!

  path << current_node
  cost = @distances[destination_x][destination_y]
  visited_nodes = Set.new
  visited_nodes.add(current_node)
  Kernel.loop do
    adjacent_squares = get_adjacent_from(*current_node)
    adjacent_squares += get_adjacent_from(*current_node, squeeze: true)

    min_node = nil
    min_distance = nil

    adjacent_squares.reject { |n| visited_nodes.include?(n) }.each do |node|
      line_distance = Math.sqrt((destination_x - node[0])**2 + (destination_y - node[1])**2)
      current_distance = @distances[node[0]][node[1]].to_f + line_distance / MAX_DISTANCE.to_f
      if min_node.nil? || current_distance < min_distance
        min_distance = current_distance
        min_node = node
      end
    end

    return nil if min_node.nil?

    path << min_node
    current_node = min_node
    visited_nodes.add(current_node)
    break if current_node == [source_x, source_y]
  end

  show_cost ? [path.reverse, cost] : path.reverse
end
build_structures(source_x, source_y) click to toggle source
# File lib/natural_20/ai_controller/path_compute.rb, line 18
def build_structures(source_x, source_y)
  @pq = PQueue.new([]) { |a, b| a[1] < b[1] }
  @visited_nodes = Set.new

  @distances = @max_x.times.map do
    @max_y.times.map do
      MAX_DISTANCE
    end
  end

  @current_node = [source_x, source_y]
  @distances[source_x][source_y] = 0
  @visited_nodes.add(@current_node)
end
compute_path(source_x, source_y, destination_x, destination_y) click to toggle source

compute path using Djikstras shortest path

# File lib/natural_20/ai_controller/path_compute.rb, line 98
def compute_path(source_x, source_y, destination_x, destination_y)
  build_structures(source_x, source_y)
  path([destination_x, destination_y])
  backtrace(source_x, source_y, destination_x, destination_y)
end
get_adjacent_from(pos_x, pos_y, squeeze: false) click to toggle source
# File lib/natural_20/ai_controller/path_compute.rb, line 122
def get_adjacent_from(pos_x, pos_y, squeeze: false)
  valid_paths = Set.new
  [-1, 0, 1].each do |x_op|
    [-1, 0, 1].each do |y_op|
      cur_x = pos_x + x_op
      cur_y = pos_y + y_op

      next if cur_x < 0 || cur_y < 0 || cur_x >= @max_x || cur_y >= @max_y
      next if x_op.zero? && y_op.zero?
      next unless @map.passable?(@entity, cur_x, cur_y, @battle, squeeze)

      valid_paths.add([cur_x, cur_y])
    end
  end

  valid_paths
end
incremental_path(source_x, source_y, destination_x, destination_y) click to toggle source
# File lib/natural_20/ai_controller/path_compute.rb, line 104
def incremental_path(source_x, source_y, destination_x, destination_y)
  rpath = backtrace(source_x, source_y, destination_x, destination_y, show_cost: true)
  return rpath if rpath && rpath.size > 1

  nil
end
path(destination = nil) click to toggle source
# File lib/natural_20/ai_controller/path_compute.rb, line 69
def path(destination = nil)
  Kernel.loop do
    distance = @distances[@current_node[0]][@current_node[1]]

    adjacent_squares = get_adjacent_from(*@current_node)
    visit_squares(@pq, adjacent_squares, @visited_nodes, @distances, distance)

    # with squeezing into terrain
    squeeze_adjacent_squares = get_adjacent_from(*@current_node, squeeze: true)

    squeeze_adjacent_squares -= adjacent_squares

    unless squeeze_adjacent_squares.empty?
      visit_squares(@pq, squeeze_adjacent_squares, @visited_nodes, @distances, distance,
                    2)
    end

    break if destination && @current_node == destination

    @visited_nodes.add(@current_node)

    @current_node, node_d = @pq.pop
    break if @current_node.nil?

    return nil if node_d == MAX_DISTANCE
  end
end
visit_squares(pq, adjacent_squares, visited_nodes, distances, distance, override_move_cost = nil) click to toggle source

@param pq [PQueue] @param adjacent_squares [Array<Array<Integer,Integer>>]

# File lib/natural_20/ai_controller/path_compute.rb, line 113
def visit_squares(pq, adjacent_squares, visited_nodes, distances, distance, override_move_cost = nil)
  adjacent_squares.reject { |n| visited_nodes.include?(n) }.each do |node|
    move_cost = override_move_cost || @map.difficult_terrain?(@entity, node[0], node[1], @battle) ? 2 : 1
    current_distance = distance + move_cost
    distances[node[0]][node[1]] = current_distance if distances[node[0]][node[1]] > current_distance
    pq << [node, distances[node[0]][node[1]]]
  end
end