class AStar

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

Constants

DEFAULT_SIZE: Number of squares by lines and columns in the grid.
HEIGHT_INFO_BLOCK: Height of the informations block in pixels.
SIZE_GRID: Size of the grid in pixels.

Public Class Methods

new(size=DEFAULT_SIZE) click to toggle source

Creates the window with its grid.

Calls superclass method

# 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

Public Instance Methods

a_star() click to toggle source

Launchs the A* algorithm.

# 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) click to toggle source

Gets the button down. Two different actions:

ENTER: launch A* algorithm
SUPPR: clear window

# 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() click to toggle source

Draws the grid and the informations block.

# File lib/astar_visualizer/astar.rb, line 153
def draw
  @grid.draw
  show_info
end

find_node() click to toggle source

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

# File lib/astar_visualizer/astar.rb, line 98
def find_node
  @grid.find_node(self.mouse_x, self.mouse_y)
end

h(node) click to toggle source

Heuristic function used : Manhattan distance.

# File lib/astar_visualizer/astar.rb, line 228
def h(node)
  (node.x - @end.x).abs + (node.y - @end.y).abs
end

needs_cursor?() click to toggle source

To show the mouse cursor on the window.

# File lib/astar_visualizer/astar.rb, line 42
def needs_cursor?
  true
end

ready?() click to toggle source

Returns if the A* algorithm can be launched.

# File lib/astar_visualizer/astar.rb, line 49
def ready?
  !@needs_reset && @start && @end
end

reconstruct_path(came_from, current) click to toggle source

Reconstructs the path found by coloring the nodes.

# 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!() click to toggle source

Resets the window.

# File lib/astar_visualizer/astar.rb, line 70
def reset!
  reset_start!
  reset_end!
  @grid.reset!
  @needs_reset = false
end

reset_end!() click to toggle source

Resets the end node.

# File lib/astar_visualizer/astar.rb, line 63
def reset_end!
  @end = nil
end

reset_start!() click to toggle source

Resets the start node.

# File lib/astar_visualizer/astar.rb, line 56
def reset_start!
  @start = nil
end

show_info() click to toggle source

Shows the informations block.

# File lib/astar_visualizer/astar.rb, line 161
def show_info
  @font.draw_text(@message, 10, SIZE_GRID + 8, 5)
end

update() click to toggle source

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

# 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