Synced with 2.3.

1 files changed, 844 insertions, 0 deletions

diff --git a/samples/13_path_finding_algorithms/05_dijkstra/app/main.rb b/samples/13_path_finding_algorithms/05_dijkstra/app/main.rb
new file mode 100644
index 0000000..b335447
--- /dev/null
+++ b/samples/13_path_finding_algorithms/05_dijkstra/app/main.rb
@@ -0,0 +1,844 @@
+# Demonstrates how Dijkstra's Algorithm allows movement costs to be considered
+
+# Inspired by https://www.redblobgames.com/pathfinding/a-star/introduction.html
+
+# The first grid is a breadth first search with an early exit.
+# It shows a heat map of all the cells that were visited by the search and their relative distance.
+
+# The second grid is an implementation of Dijkstra's algorithm.
+# Light green cells have 5 times the movement cost of regular cells.
+# The heat map will darken based on movement cost.
+
+# Dark green cells are walls, and the search cannot go through them.
+class Movement_Costs
+  attr_gtk
+
+  # This method is called every frame/tick
+  # Every tick, the current state of the search is rendered on the screen,
+  # User input is processed, and
+  # The next step in the search is calculated
+  def tick
+    defaults
+    render 
+    input  
+    calc
+  end
+
+  def defaults
+    # Variables to edit the size and appearance of the grid
+    # Freely customizable to user's liking
+    grid.width     ||= 10
+    grid.height    ||= 10
+    grid.cell_size ||= 60
+    grid.rect      ||= [0, 0, grid.width, grid.height]
+
+    # The location of the star and walls of the grid
+    # They can be modified to have a different initial grid
+    # Walls are stored in a hash for quick look up when doing the search
+    state.star   ||= [1, 5]
+    state.target ||= [8, 4]
+    state.walls  ||= {[1, 1] => true, [2, 1] => true, [3, 1] => true, [1, 2] => true, [2, 2] => true, [3, 2] => true}    
+    state.hills  ||= {
+      [4, 1] => true,
+      [5, 1] => true,
+      [4, 2] => true,
+      [5, 2] => true,
+      [6, 2] => true,
+      [4, 3] => true,
+      [5, 3] => true,
+      [6, 3] => true,
+      [3, 4] => true,
+      [4, 4] => true,
+      [5, 4] => true,
+      [6, 4] => true,
+      [7, 4] => true,
+      [3, 5] => true,
+      [4, 5] => true,
+      [5, 5] => true,
+      [6, 5] => true,
+      [7, 5] => true,
+      [4, 6] => true,
+      [5, 6] => true,
+      [6, 6] => true,
+      [7, 6] => true,
+      [4, 7] => true,
+      [5, 7] => true,
+      [6, 7] => true,
+      [4, 8] => true,
+      [5, 8] => true,
+    }
+
+    # What the user is currently editing on the grid
+    # We store this value, because we want to remember the value even when
+    # the user's cursor is no longer over what they're interacting with, but
+    # they are still clicking down on the mouse.
+    state.user_input ||= :none 
+
+    # Values that are used for the breadth first search
+    # Keeping track of what cells were visited prevents counting cells multiple times
+    breadth_first_search.visited    ||= {}
+    # The cells from which the breadth first search will expand
+    breadth_first_search.frontier   ||= []
+    # Keeps track of which cell all cells were searched from
+    # Used to recreate the path from the target to the star
+    breadth_first_search.came_from  ||= {}
+
+    # Keeps track of the movement cost so far to be at a cell
+    # Allows the costs of new cells to be quickly calculated
+    # Also doubles as a way to check if cells have already been visited
+    dijkstra_search.cost_so_far ||= {}
+    # The cells from which the Dijkstra search will expand
+    dijkstra_search.frontier    ||= []
+    # Keeps track of which cell all cells were searched from
+    # Used to recreate the path from the target to the star
+    dijkstra_search.came_from   ||= {}
+  end
+
+  # Draws everything onto the screen
+  def render
+    render_background       
+
+    render_heat_maps
+
+    render_star
+    render_target
+    render_hills
+    render_walls
+
+    render_paths
+  end
+  # The methods below subdivide the task of drawing everything to the screen
+
+  # Draws what the grid looks like with nothing on it
+  def render_background
+    render_unvisited  
+    render_grid_lines 
+    render_labels
+  end
+
+  # Draws two rectangles the size of the grid in the default cell color
+  # Used as part of the background
+  def render_unvisited
+    outputs.solids << [scale_up(grid.rect), unvisited_color]
+    outputs.solids << [move_and_scale_up(grid.rect), unvisited_color]
+  end
+
+  # Draws grid lines to show the division of the grid into cells
+  def render_grid_lines
+    for x in 0..grid.width
+      outputs.lines << vertical_line(x)
+      outputs.lines << shifted_vertical_line(x)
+    end
+
+    for y in 0..grid.height
+      outputs.lines << horizontal_line(y) 
+      outputs.lines << shifted_horizontal_line(y)
+    end
+  end
+
+  # Easy way to draw vertical lines given an index for the first grid
+  def vertical_line column
+    scale_up([column, 0, column, grid.height])
+  end
+
+  # Easy way to draw horizontal lines given an index for the second grid
+  def horizontal_line row
+    scale_up([0, row, grid.width, row])
+  end
+
+  # Easy way to draw vertical lines given an index for the first grid
+  def shifted_vertical_line column
+    scale_up([column + grid.width + 1, 0, column + grid.width + 1, grid.height])
+  end
+
+  # Easy way to draw horizontal lines given an index for the second grid
+  def shifted_horizontal_line row
+    scale_up([grid.width + 1, row, grid.width + grid.width + 1, row])
+  end
+
+  # Labels the grids
+  def render_labels
+    outputs.labels << [175, 650, "Number of steps", 3]
+    outputs.labels << [925, 650, "Distance", 3]
+  end
+
+  def render_paths
+    render_breadth_first_search_path
+    render_dijkstra_path
+  end
+
+  def render_heat_maps
+    render_breadth_first_search_heat_map
+    render_dijkstra_heat_map
+  end
+
+  # Renders the breadth first search on the first grid
+  def render_breadth_first_search
+  end
+
+  # This heat map shows the cells explored by the breadth first search and how far they are from the star.
+  def render_breadth_first_search_heat_map
+    # For each cell explored
+    breadth_first_search.visited.each_key do | visited_cell |
+      # Find its distance from the star
+      distance = (state.star.x - visited_cell.x).abs + (state.star.y - visited_cell.y).abs
+      max_distance = grid.width + grid.height
+      # Get it as a percent of the maximum distance and scale to 255 for use as an alpha value
+      alpha = 255.to_i * distance.to_i / max_distance.to_i
+      outputs.solids << [scale_up(visited_cell), red, alpha]
+    end
+  end
+
+  def render_breadth_first_search_path
+    # If the search found the target
+    if breadth_first_search.visited.has_key?(state.target)
+      # Start from the target
+      endpoint = state.target
+      # And the cell it came from
+      next_endpoint = breadth_first_search.came_from[endpoint]
+      while endpoint and next_endpoint
+        # Draw a path between these two cells
+        path = get_path_between(endpoint, next_endpoint)
+        outputs.solids << [scale_up(path), path_color]
+        # And get the next pair of cells
+        endpoint = next_endpoint
+        next_endpoint = breadth_first_search.came_from[endpoint]
+        # Continue till there are no more cells
+      end
+    end
+  end
+
+  # Renders the Dijkstra search on the second grid
+  def render_dijkstra
+  end
+
+  def render_dijkstra_heat_map
+    dijkstra_search.cost_so_far.each do |visited_cell, cost|
+      max_cost = (grid.width + grid.height) #* 5
+      alpha = 255.to_i * cost.to_i / max_cost.to_i
+      outputs.solids << [move_and_scale_up(visited_cell), red, alpha]
+    end
+  end
+
+  def render_dijkstra_path
+    # If the search found the target
+    if dijkstra_search.came_from.has_key?(state.target)
+      # Get the target and the cell it came from
+      endpoint = state.target
+      next_endpoint = dijkstra_search.came_from[endpoint]
+      while endpoint and next_endpoint
+        # Draw a path between them
+        path = get_path_between(endpoint, next_endpoint)
+        outputs.solids << [move_and_scale_up(path), path_color]
+
+        # Shift one cell down the path
+        endpoint = next_endpoint
+        next_endpoint = dijkstra_search.came_from[endpoint]
+
+        # Repeat till the end of the path
+      end
+    end
+  end
+
+  # Renders the star on both grids
+  def render_star
+    outputs.sprites << [scale_up(state.star), 'star.png']
+    outputs.sprites << [move_and_scale_up(state.star), 'star.png']
+  end 
+
+  # Renders the target on both grids
+  def render_target
+    outputs.sprites << [scale_up(state.target), 'target.png']
+    outputs.sprites << [move_and_scale_up(state.target), 'target.png']
+  end 
+
+  def render_hills
+    state.hills.each_key do |hill| 
+      outputs.solids << [scale_up(hill), hill_color]
+      outputs.solids << [move_and_scale_up(hill), hill_color]
+    end
+  end
+
+  # Draws the walls on both grids
+  def render_walls
+    state.walls.each_key do |wall| 
+      outputs.solids << [scale_up(wall), wall_color]
+      outputs.solids << [move_and_scale_up(wall), wall_color]
+    end
+  end
+
+  def get_path_between(cell_one, cell_two)
+    path = nil
+    if cell_one.x == cell_two.x
+      if cell_one.y < cell_two.y
+        path = [cell_one.x + 0.3, cell_one.y + 0.3, 0.4, 1.4]
+      else
+        path = [cell_two.x + 0.3, cell_two.y + 0.3, 0.4, 1.4]
+      end
+    else
+      if cell_one.x < cell_two.x
+        path = [cell_one.x + 0.3, cell_one.y + 0.3, 1.4, 0.4]
+      else
+        path = [cell_two.x + 0.3, cell_two.y + 0.3, 1.4, 0.4]
+      end
+    end
+    path
+  end
+
+  # Representation of how far away visited cells are from the star
+  # Replaces the render_visited method
+  # Visually demonstrates the effectiveness of early exit for pathfinding
+  def render_breadth_first_search_heat_map
+    breadth_first_search.visited.each_key do | visited_cell |
+      distance = (state.star.x - visited_cell.x).abs + (state.star.y - visited_cell.y).abs
+      max_distance = grid.width + grid.height
+      alpha = 255.to_i * distance.to_i / max_distance.to_i
+      outputs.solids << [scale_up(visited_cell), red, alpha]
+    end
+  end
+
+  # Translates the given cell grid.width + 1 to the right and then scales up
+  # Used to draw cells for the second grid
+  # This method does not work for lines,
+  # so separate methods exist for the grid lines
+  def move_and_scale_up(cell)
+    cell_clone = cell.clone
+    cell_clone.x += grid.width + 1
+    scale_up(cell_clone)
+  end
+
+  # In code, the cells are represented as 1x1 rectangles
+  # When drawn, the cells are larger than 1x1 rectangles
+  # This method is used to scale up cells, and lines
+  # Objects are scaled up according to the grid.cell_size variable
+  # This allows for easy customization of the visual scale of the grid
+  def scale_up(cell)
+    # Prevents the original value of cell from being edited
+    cell = cell.clone
+
+    # If cell is just an x and y coordinate
+    if cell.size == 2
+      # Add a width and height of 1
+      cell << 1
+      cell << 1
+    end
+
+    # Scale all the values up
+    cell.map! { |value| value * grid.cell_size }
+
+    # Returns the scaled up cell
+    cell
+  end
+
+  # Handles user input every tick so the grid can be edited
+  # Separate input detection and processing is needed
+  # For example: Adding walls is started by clicking down on a hill,
+  # but the mouse doesn't need to remain over hills to add walls
+  def input
+    # If the mouse was lifted this tick
+    if inputs.mouse.up
+      # Set current input to none
+      state.user_input = :none
+    end
+
+    # If the mouse was clicked this tick
+    if inputs.mouse.down
+      # Determine what the user is editing and edit the state.user_input variable
+      determine_input          
+    end
+
+    # Process user input based on user_input variable and current mouse position
+    process_input
+  end
+
+  # Determines what the user is editing and stores the value
+  # This method is called the tick the mouse is clicked
+  # Storing the value allows the user to continue the same edit as long as the
+  # mouse left click is held
+  def determine_input
+    # If the mouse is over the star in the first grid
+    if mouse_over_star?                 
+      # The user is editing the star from the first grid
+      state.user_input = :star          
+    # If the mouse is over the star in the second grid
+    elsif mouse_over_star2?                 
+      # The user is editing the star from the second grid
+      state.user_input = :star2          
+    # If the mouse is over the target in the first grid
+    elsif mouse_over_target?                 
+      # The user is editing the target from the first grid
+      state.user_input = :target          
+    # If the mouse is over the target in the second grid
+    elsif mouse_over_target2?                 
+      # The user is editing the target from the second grid
+      state.user_input = :target2 
+    # If the mouse is over a wall in the first grid
+    elsif mouse_over_wall?                 
+      # The user is removing a wall from the first grid
+      state.user_input = :remove_wall   
+    # If the mouse is over a wall in the second grid
+    elsif mouse_over_wall2?                 
+      # The user is removing a wall from the second grid
+      state.user_input = :remove_wall2
+    # If the mouse is over a hill in the first grid
+    elsif mouse_over_hill?                 
+      # The user is adding a wall from the first grid
+      state.user_input = :add_wall   
+    # If the mouse is over a hill in the second grid
+    elsif mouse_over_hill2?                 
+      # The user is adding a wall from the second grid
+      state.user_input = :add_wall2
+    # If the mouse is over the first grid
+    elsif mouse_over_grid?                 
+      # The user is adding a hill from the first grid
+      state.user_input = :add_hill
+    # If the mouse is over the second grid
+    elsif mouse_over_grid2?                 
+      # The user is adding a hill from the second grid
+      state.user_input = :add_hill2
+    end
+  end
+
+  # Processes click and drag based on what the user is currently dragging
+  def process_input
+    if state.user_input == :star         
+      input_star                            
+    elsif state.user_input == :star2
+      input_star2                            
+    elsif state.user_input == :target         
+      input_target                            
+    elsif state.user_input == :target2         
+      input_target2                            
+    elsif state.user_input == :remove_wall  
+      input_remove_wall                     
+    elsif state.user_input == :remove_wall2
+      input_remove_wall2                     
+    elsif state.user_input == :add_hill     
+      input_add_hill                        
+    elsif state.user_input == :add_hill2     
+      input_add_hill2                        
+    elsif state.user_input == :add_wall     
+      input_add_wall                        
+    elsif state.user_input == :add_wall2     
+      input_add_wall2                        
+    end
+  end
+
+  # Calculates the two searches
+  def calc
+    # If the searches have not started
+    if breadth_first_search.visited.empty?
+      # Calculate the two searches
+      calc_breadth_first
+      calc_dijkstra
+    end
+  end
+  
+
+  def calc_breadth_first
+    # Sets up the Breadth First Search
+    breadth_first_search.visited[state.star]   = true              
+    breadth_first_search.frontier              << state.star                   
+    breadth_first_search.came_from[state.star] = nil
+
+    until breadth_first_search.frontier.empty?
+      return if breadth_first_search.visited.has_key?(state.target)
+      # A step in the search
+      # Takes the next frontier cell
+      new_frontier = breadth_first_search.frontier.shift 
+      # For each of its neighbors
+      adjacent_neighbors(new_frontier).each do | neighbor | 
+        # That have not been visited and are not walls
+        unless breadth_first_search.visited.has_key?(neighbor) || state.walls.has_key?(neighbor) 
+          # Add them to the frontier and mark them as visited in the first grid
+          breadth_first_search.visited[neighbor] = true 
+          breadth_first_search.frontier << neighbor 
+          # Remember which cell the neighbor came from
+          breadth_first_search.came_from[neighbor] = new_frontier
+        end
+      end
+    end
+  end
+
+  # Calculates the Dijkstra Search from the beginning to the end
+
+  def calc_dijkstra
+    # The initial values for the Dijkstra search
+    dijkstra_search.frontier                << [state.star, 0]
+    dijkstra_search.came_from[state.star]   = nil
+    dijkstra_search.cost_so_far[state.star] = 0
+
+    # Until their are no more cells to be explored
+    until dijkstra_search.frontier.empty?
+      # Get the next cell to be explored from
+      # We get the first element of the array which is the cell. The second element is the priority.
+      current = dijkstra_search.frontier.shift[0]
+
+      # Stop the search if we found the target
+      return if current == state.target
+
+      # For each of the neighbors
+      adjacent_neighbors(current).each do | neighbor |
+        # Unless this cell is a wall or has already been explored.
+        unless dijkstra_search.came_from.has_key?(neighbor) or state.walls.has_key?(neighbor)
+          # Calculate the movement cost of getting to this cell and memo
+          new_cost = dijkstra_search.cost_so_far[current] + cost(neighbor)
+          dijkstra_search.cost_so_far[neighbor] = new_cost
+
+          # Add this neighbor to the cells too be explored
+          dijkstra_search.frontier << [neighbor, new_cost]
+          dijkstra_search.came_from[neighbor] = current
+        end
+      end
+
+      # Sort the frontier so exploration occurs that have a low cost so far.
+      # My implementation of a priority queue
+      dijkstra_search.frontier = dijkstra_search.frontier.sort_by {|cell, priority| priority}
+    end
+  end
+
+  def cost(cell)
+    if state.hills.has_key?(cell)
+      return 5
+    else
+      return 1
+    end
+  end
+
+
+
+
+  # Moves the star to the cell closest to the mouse in the first grid
+  # Only resets the search if the star changes position
+  # Called whenever the user is editing the star (puts mouse down on star)
+  def input_star
+    old_star = state.star.clone 
+    unless cell_closest_to_mouse == state.target
+      state.star = cell_closest_to_mouse 
+    end
+    unless old_star == state.star 
+      reset_search 
+    end
+  end
+
+  # Moves the star to the cell closest to the mouse in the second grid
+  # Only resets the search if the star changes position
+  # Called whenever the user is editing the star (puts mouse down on star)
+  def input_star2
+    old_star = state.star.clone 
+    unless cell_closest_to_mouse2 == state.target
+      state.star = cell_closest_to_mouse2
+    end
+    unless old_star == state.star 
+      reset_search 
+    end
+  end
+
+  # Moves the target to the grid closest to the mouse in the first grid
+  # Only reset_searchs the search if the target changes position
+  # Called whenever the user is editing the target (puts mouse down on target)
+  def input_target
+    old_target = state.target.clone 
+    unless cell_closest_to_mouse == state.star
+      state.target = cell_closest_to_mouse
+    end
+    unless old_target == state.target 
+      reset_search 
+    end
+  end
+
+  # Moves the target to the cell closest to the mouse in the second grid
+  # Only reset_searchs the search if the target changes position
+  # Called whenever the user is editing the target (puts mouse down on target)
+  def input_target2
+    old_target = state.target.clone 
+    unless cell_closest_to_mouse2 == state.star
+      state.target = cell_closest_to_mouse2
+    end
+    unless old_target == state.target 
+      reset_search 
+    end
+  end
+
+  # Removes walls in the first grid that are under the cursor
+  def input_remove_wall
+    # The mouse needs to be inside the grid, because we only want to remove walls
+    # the cursor is directly over
+    # Recalculations should only occur when a wall is actually deleted
+    if mouse_over_grid? 
+      if state.walls.has_key?(cell_closest_to_mouse) or state.hills.has_key?(cell_closest_to_mouse)
+        state.walls.delete(cell_closest_to_mouse) 
+        state.hills.delete(cell_closest_to_mouse) 
+        reset_search 
+      end
+    end
+  end
+
+  # Removes walls in the second grid that are under the cursor
+  def input_remove_wall2
+    # The mouse needs to be inside the grid, because we only want to remove walls
+    # the cursor is directly over
+    # Recalculations should only occur when a wall is actually deleted
+    if mouse_over_grid2? 
+      if state.walls.has_key?(cell_closest_to_mouse2) or state.hills.has_key?(cell_closest_to_mouse2)
+        state.walls.delete(cell_closest_to_mouse2) 
+        state.hills.delete(cell_closest_to_mouse2) 
+        reset_search 
+      end
+    end
+  end
+
+  # Adds a hill in the first grid in the cell the mouse is over
+  def input_add_hill
+    if mouse_over_grid? 
+      unless state.hills.has_key?(cell_closest_to_mouse)
+        state.hills[cell_closest_to_mouse] = true 
+        reset_search 
+      end
+    end
+  end
+
+
+  # Adds a hill in the second grid in the cell the mouse is over
+  def input_add_hill2
+    if mouse_over_grid2? 
+      unless state.hills.has_key?(cell_closest_to_mouse2)
+        state.hills[cell_closest_to_mouse2] = true 
+        reset_search 
+      end
+    end
+  end
+
+  # Adds a wall in the first grid in the cell the mouse is over
+  def input_add_wall
+    if mouse_over_grid? 
+      unless state.walls.has_key?(cell_closest_to_mouse)
+        state.hills.delete(cell_closest_to_mouse) 
+        state.walls[cell_closest_to_mouse] = true 
+        reset_search 
+      end
+    end
+  end
+
+  # Adds a wall in the second grid in the cell the mouse is over
+  def input_add_wall2
+    if mouse_over_grid2? 
+      unless state.walls.has_key?(cell_closest_to_mouse2)
+        state.hills.delete(cell_closest_to_mouse2) 
+        state.walls[cell_closest_to_mouse2] = true 
+        reset_search 
+      end
+    end
+  end
+
+  # Whenever the user edits the grid,
+  # The search has to be reset_searchd upto the current step
+  # with the current grid as the initial state of the grid
+  def reset_search
+    breadth_first_search.visited    = {}
+    breadth_first_search.frontier   = []
+    breadth_first_search.came_from  = {}
+
+    dijkstra_search.frontier    = []
+    dijkstra_search.came_from   = {}
+    dijkstra_search.cost_so_far = {}
+  end
+
+
+
+  # Returns a list of adjacent cells
+  # Used to determine what the next cells to be added to the frontier are
+  def adjacent_neighbors(cell)
+    neighbors = [] 
+
+    # Gets all the valid neighbors into the array
+    # From southern neighbor, clockwise
+    neighbors << [cell.x    , cell.y - 1] unless cell.y == 0 
+    neighbors << [cell.x - 1, cell.y    ] unless cell.x == 0 
+    neighbors << [cell.x    , cell.y + 1] unless cell.y == grid.height - 1 
+    neighbors << [cell.x + 1, cell.y    ] unless cell.x == grid.width - 1 
+
+    # Sorts the neighbors so the rendered path is a zigzag path
+    # Cells in a diagonal direction are given priority
+    # Comment this line to see the difference
+    neighbors = neighbors.sort_by { |neighbor_x, neighbor_y|  proximity_to_star(neighbor_x, neighbor_y) }
+
+    neighbors 
+  end
+
+  # Finds the vertical and horizontal distance of a cell from the star
+  # and returns the larger value
+  # This method is used to have a zigzag pattern in the rendered path
+  # A cell that is [5, 5] from the star,
+  # is explored before over a cell that is [0, 7] away.
+  # So, if possible, the search tries to go diagonal (zigzag) first
+  def proximity_to_star(x, y)
+    distance_x = (state.star.x - x).abs
+    distance_y = (state.star.y - y).abs
+
+    if distance_x > distance_y
+      return distance_x
+    else
+      return distance_y
+    end
+  end
+
+  # When the user grabs the star and puts their cursor to the far right
+  # and moves up and down, the star is supposed to move along the grid as well
+  # Finding the cell closest to the mouse helps with this
+  def cell_closest_to_mouse
+    # Closest cell to the mouse in the first grid
+    x = (inputs.mouse.point.x / grid.cell_size).to_i 
+    y = (inputs.mouse.point.y / grid.cell_size).to_i 
+    # Bound x and y to the grid
+    x = grid.width - 1 if x > grid.width - 1 
+    y = grid.height - 1 if y > grid.height - 1 
+    # Return closest cell
+    [x, y] 
+  end
+
+  # When the user grabs the star and puts their cursor to the far right
+  # and moves up and down, the star is supposed to move along the grid as well
+  # Finding the cell closest to the mouse in the second grid helps with this
+  def cell_closest_to_mouse2
+    # Closest cell grid to the mouse in the second
+    x = (inputs.mouse.point.x / grid.cell_size).to_i 
+    y = (inputs.mouse.point.y / grid.cell_size).to_i 
+    # Translate the cell to the first grid
+    x -= grid.width + 1
+    # Bound x and y to the first grid
+    x = 0 if x < 0
+    y = 0 if y < 0
+    x = grid.width - 1 if x > grid.width - 1 
+    y = grid.height - 1 if y > grid.height - 1 
+    # Return closest cell
+    [x, y] 
+  end
+
+  # Signal that the user is going to be moving the star from the first grid
+  def mouse_over_star?
+    inputs.mouse.point.inside_rect?(scale_up(state.star))
+  end
+
+  # Signal that the user is going to be moving the star from the second grid
+  def mouse_over_star2?
+    inputs.mouse.point.inside_rect?(move_and_scale_up(state.star))
+  end
+
+  # Signal that the user is going to be moving the target from the first grid
+  def mouse_over_target?
+    inputs.mouse.point.inside_rect?(scale_up(state.target))
+  end
+
+  # Signal that the user is going to be moving the target from the second grid
+  def mouse_over_target2?
+    inputs.mouse.point.inside_rect?(move_and_scale_up(state.target))
+  end
+
+  # Signal that the user is going to be removing walls from the first grid
+  def mouse_over_wall?
+    state.walls.each_key do | wall |
+      return true if inputs.mouse.point.inside_rect?(scale_up(wall))
+    end
+
+    false
+  end
+
+  # Signal that the user is going to be removing walls from the second grid
+  def mouse_over_wall2?
+    state.walls.each_key do | wall |
+      return true if inputs.mouse.point.inside_rect?(move_and_scale_up(wall))
+    end
+
+    false
+  end
+
+  # Signal that the user is going to be removing hills from the first grid
+  def mouse_over_hill?
+    state.hills.each_key do | hill |
+      return true if inputs.mouse.point.inside_rect?(scale_up(hill))
+    end
+
+    false
+  end
+
+  # Signal that the user is going to be removing hills from the second grid
+  def mouse_over_hill2?
+    state.hills.each_key do | hill |
+      return true if inputs.mouse.point.inside_rect?(move_and_scale_up(hill))
+    end
+
+    false
+  end
+
+  # Signal that the user is going to be adding walls from the first grid
+  def mouse_over_grid?
+    inputs.mouse.point.inside_rect?(scale_up(grid.rect))
+  end
+
+  # Signal that the user is going to be adding walls from the second grid
+  def mouse_over_grid2?
+    inputs.mouse.point.inside_rect?(move_and_scale_up(grid.rect))
+  end
+
+  # These methods provide handy aliases to colors
+
+  # Light brown
+  def unvisited_color
+    [221, 212, 213] 
+  end
+
+  # Camo Green
+  def wall_color
+    [134, 134, 120] 
+  end
+
+  # Pastel White
+  def path_color
+    [231, 230, 228]
+  end
+
+  def red
+    [255, 0, 0]
+  end
+
+  # A Green
+  def hill_color
+    [139, 173, 132]
+  end
+
+  # Makes code more concise
+  def grid
+    state.grid
+  end
+
+  def breadth_first_search
+    state.breadth_first_search
+  end
+
+  def dijkstra_search
+    state.dijkstra_search
+  end
+end
+
+# Method that is called by DragonRuby periodically
+# Used for updating animations and calculations
+def tick args
+
+  # Pressing r will reset the application
+  if args.inputs.keyboard.key_down.r
+    args.gtk.reset
+    reset
+    return
+  end
+
+  # Every tick, new args are passed, and the Dijkstra tick method is called
+  $movement_costs ||= Movement_Costs.new(args)
+  $movement_costs.args = args
+  $movement_costs.tick
+end
+
+
+def reset
+  $movement_costs = nil
+end