Class: AStar

Inherits:
Gosu::Window
  • Object
show all
Defined in:
lib/astar_visualizer/astar.rb

Overview

The AStar class manages the window with the grid and can launch the A* algorithm.

Constant Summary collapse

SIZE_GRID =

Size of the grid in pixels.

700
HEIGHT_INFO_BLOCK =

Height of the informations block in pixels.

40
DEFAULT_SIZE =

Number of squares by lines and columns in the grid.

50

Instance Method Summary collapse

Constructor Details

#initialize(size = DEFAULT_SIZE) ⇒ AStar

Creates the window with its grid.



29
30
31
32
33
34
35
36
37
 
# File 'lib/astar_visualizer/astar.rb', line 29

def initialize(size=DEFAULT_SIZE)
  super(SIZE_GRID, SIZE_GRID + HEIGHT_INFO_BLOCK, false)
  self.caption = 'A* Pathfinding Visualizer'
  @font = Gosu::Font.new(28)
  @message = 'Choose the start node.'
  @grid = Grid.new(self, size, size, SIZE_GRID)
  @start = @end = nil
  @needs_reset = false
end

Instance Method Details

#a_star ⇒ Object

Launchs the A* algorithm.



180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
 
# File 'lib/astar_visualizer/astar.rb', line 180

def a_star
  open_set = [@start]
  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] = 0
  f_score[@start] = h(@start)

  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
      reconstruct_path(came_from, current)
      @message = 'Path found! Press SUPPR to clear the window.'
      return true
    end

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

    current.neighbors.each do |neighbor|
      tentative_g_score = g_score[current] + 1
      next if tentative_g_score >= g_score[neighbor]

      came_from[neighbor] = current
      g_score[neighbor] = tentative_g_score
      f_score[neighbor] = g_score[neighbor] + h(neighbor)
      unless open_set.include?(neighbor)
        open_set << neighbor
        neighbor.open!
      end
    end

    current.closed! if current != @start
  end
  @message = 'No path found! Press SUPPR to clear the window.'
  false
end

#button_down(id) ⇒ Object

Gets the button down. Two different actions:

  • ENTER: launch A* algorithm

  • SUPPR: clear window



83
84
85
86
87
88
89
90
91
92
93
 
# File 'lib/astar_visualizer/astar.rb', line 83

def button_down(id)
  # ENTER: launch A* algorithm
  if id == Gosu::KbReturn && ready?
    @grid.update_neighbors
    a_star
    @needs_reset = true
  end

  # SUPPR: clear window
  reset! if id == Gosu::KbDelete
end

#draw ⇒ Object

Draws the grid and the informations block.



153
154
155
156
 
# File 'lib/astar_visualizer/astar.rb', line 153

def draw
  @grid.draw
  show_info
end

#find_node ⇒ Object

Finds the node in the grid corresponding to the mouse position.



98
99
100
 
# File 'lib/astar_visualizer/astar.rb', line 98

def find_node
  @grid.find_node(self.mouse_x, self.mouse_y)
end

#h(node) ⇒ Object

Heuristic function used : Manhattan distance.



228
229
230
 
# File 'lib/astar_visualizer/astar.rb', line 228

def h(node)
  (node.x - @end.x).abs + (node.y - @end.y).abs
end

#needs_cursor? ⇒ Boolean

To show the mouse cursor on the window.

Returns:

  • (Boolean) 


42
43
44
 
# File 'lib/astar_visualizer/astar.rb', line 42

def needs_cursor?
  true
end

#ready? ⇒ Boolean

Returns if the A* algorithm can be launched.

Returns:

  • (Boolean) 


49
50
51
 
# File 'lib/astar_visualizer/astar.rb', line 49

def ready?
  !@needs_reset && @start && @end
end

#reconstruct_path(came_from, current) ⇒ Object

Reconstructs the path found by coloring the nodes.



168
169
170
171
172
173
174
175
 
# File 'lib/astar_visualizer/astar.rb', line 168

def reconstruct_path(came_from, current)
  while came_from.include?(current)
    current = came_from[current]
    current.path!
  end
  @start.start!
  @end.end!
end

#reset! ⇒ Object

Resets the window.



70
71
72
73
74
75
 
# File 'lib/astar_visualizer/astar.rb', line 70

def reset!
  reset_start!
  reset_end!
  @grid.reset!
  @needs_reset = false
end

#reset_end! ⇒ Object

Resets the end node.



63
64
65
 
# File 'lib/astar_visualizer/astar.rb', line 63

def reset_end!
  @end = nil
end

#reset_start! ⇒ Object

Resets the start node.



56
57
58
 
# File 'lib/astar_visualizer/astar.rb', line 56

def reset_start!
  @start = nil
end

#show_info ⇒ Object

Shows the informations block.



161
162
163
 
# File 'lib/astar_visualizer/astar.rb', line 161

def show_info
  @font.draw_text(@message, 10, SIZE_GRID + 8, 5)
end

#update ⇒ Object

Updates the window. If the mouse buttons are used, it updates nodes and the message in the informations block.



106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
 
# File 'lib/astar_visualizer/astar.rb', line 106

def update
  return if @needs_reset

  # Message
  if !@start
    @message = 'Choose the start node.'
  elsif !@end
    @message = 'Choose the end node.'
  else
    @message = 'Add obstacles and press ENTER.'
  end

  if Gosu.button_down? Gosu::MsLeft
    node = find_node
    if node
      # Make start node
      if !@start && node != @end
        node.start!
        @start = node
      # Make end node
      elsif !@end && node != @start
        node.end!
        @end = node
      # Make obstacle
      elsif node != @start && node != @end
        node.obstacle!
      end
    end
  end

  # Clear a node
  if Gosu.button_down? Gosu::MsRight
    node = find_node
    if node
      node.reset!
      if node == @start
        reset_start!
      elsif node == @end
        reset_end!
      end
    end
  end
end