Class: AiController::PathCompute

Inherits:
Object
  • Object
show all
Defined in:
lib/natural_20/ai_controller/path_compute.rb

Overview

Path finding algorithm

Instance Method Summary collapse

Constructor Details

#initialize(battle, map, entity) ⇒ PathCompute

Creates a path finder

Parameters:



11
12
13
14
15
16
 
# 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

Instance Method Details

#backtrace(source_x, source_y, destination_x, destination_y, show_cost: false) ⇒ Object 



33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
# 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) ⇒ Object 



18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
# 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) ⇒ Object

compute path using Djikstras shortest path



98
99
100
101
102
 
# 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) ⇒ Object 



122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
 
# 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) ⇒ Object 



104
105
106
107
108
109
 
# 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) ⇒ Object 



69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
 
# 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) ⇒ Object

Parameters:

  • pq (PQueue)
  • adjacent_squares (Array<Array<Integer,Integer>>) 


113
114
115
116
117
118
119
120
 
# 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