Class: AStarFinder

Inherits:
Object
  • Object
show all
Defined in:
lib/pathfinding/finder/astar.rb

Overview

A* path-finder.

Instance Method Summary collapse

Constructor Details

#initialize(heuristic = Heuristic::method(:manhattan), diagonal_movement = DiagonalMovement::NEVER) ⇒ AStarFinder

Initializes the A* path-finder. Params:

  • heuristic: heuristic function (see the Heuristic module)

  • diagonal_movement: set diagonal movements (see the DiagonalMovement module)



21
22
23
24
25
26
27
28
29
30
31
 
# File 'lib/pathfinding/finder/astar.rb', line 21

def initialize(
  heuristic = Heuristic::method(:manhattan),
  diagonal_movement = DiagonalMovement::NEVER
)
  @diagonal_movement = diagonal_movement
  if diagonal_movement == DiagonalMovement::NEVER
    @heuristic = heuristic
  else
    @heuristic = Heuristic::method(:octile)
  end
end

Instance Method Details

#d(n1, n2) ⇒ Object

Returns the distance between two nodes.



79
80
81
 
# File 'lib/pathfinding/finder/astar.rb', line 79

def d(n1, n2)
  (n1.x == n2.x || n1.y == n2.y) ? 1 : Math.sqrt(2)
end

#find_path(start_node, end_node, grid) ⇒ Object

Finds and returns the path as a list of node objects.



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
68
69
70
71
72
73
74
 
# File 'lib/pathfinding/finder/astar.rb', line 36

def find_path(start_node, end_node, grid)
  open_set = [start_node]
  came_from = {}
  g_score = {}
  f_score = {}
  grid.each_node do |node|
    g_score[node] = Float::INFINITY
    f_score[node] = Float::INFINITY
  end
  g_score[start_node] = 0
  f_score[start_node] = @heuristic.call(
    (start_node.x - end_node.x).abs, (start_node.y - end_node.y).abs)

  until open_set.empty?
    current = open_set[0]
    open_set.each do |node|
      current = node if f_score[node] < f_score[current]
    end

    if current == end_node
      return reconstruct_path(came_from, current)
    end

    current = open_set.delete_at(open_set.index(current))

    grid.neighbors(current, @diagonal_movement).each do |neighbor|
      tentative_g_score = g_score[current] + d(current, neighbor)
      next if tentative_g_score >= g_score[neighbor]

      came_from[neighbor] = current
      g_score[neighbor] = tentative_g_score
      f_score[neighbor] = g_score[neighbor] + @heuristic.call(
        (neighbor.x - end_node.x).abs, (neighbor.y - end_node.y).abs)
      unless open_set.include?(neighbor)
        open_set << neighbor
      end
    end
  end
end

#reconstruct_path(came_from, current) ⇒ Object

Reconstructs the path from the current node.



86
87
88
89
90
91
92
93
 
# File 'lib/pathfinding/finder/astar.rb', line 86

def reconstruct_path(came_from, current)
  total_path = [current]
  while came_from.include?(current)
    current = came_from[current]
    total_path << current
  end
  total_path.reverse
end