# Contributors outside of DragonRuby who also hold Copyright:
# - Sujay Vadlakonda: https://github.com/sujayvadlakonda

# This program is inspired by https://www.redblobgames.com/pathfinding/a-star/introduction.html

class Breadcrumbs
  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
    # If the grid has not been searched
    if search.came_from.empty?
      calc
      # Calc Path
    end
    render
    input
  end

  def defaults
    # Variables to edit the size and appearance of the grid
    # Freely customizable to user's liking
    grid.width     ||= 30
    grid.height    ||= 15
    grid.cell_size ||= 40
    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
    grid.star   ||= [2, 8]
    grid.target ||= [10, 5]
    grid.walls  ||= {
      [3, 3] => true,
      [3, 4] => true,
      [3, 5] => true,
      [3, 6] => true,
      [3, 7] => true,
      [3, 8] => true,
      [3, 9] => true,
      [3, 10] => true,
      [3, 11] => true,
      [4, 3] => true,
      [4, 4] => true,
      [4, 5] => true,
      [4, 6] => true,
      [4, 7] => true,
      [4, 8] => true,
      [4, 9] => true,
      [4, 10] => true,
      [4, 11] => true,
      [13, 0] => true,
      [13, 1] => true,
      [13, 2] => true,
      [13, 3] => true,
      [13, 4] => true,
      [13, 5] => true,
      [13, 6] => true,
      [13, 7] => true,
      [13, 8] => true,
      [13, 9] => true,
      [13, 10] => true,
      [14, 0] => true,
      [14, 1] => true,
      [14, 2] => true,
      [14, 3] => true,
      [14, 4] => true,
      [14, 5] => true,
      [14, 6] => true,
      [14, 7] => true,
      [14, 8] => true,
      [14, 9] => true,
      [14, 10] => true,
      [21, 8] => true,
      [21, 9] => true,
      [21, 10] => true,
      [21, 11] => true,
      [21, 12] => true,
      [21, 13] => true,
      [21, 14] => true,
      [22, 8] => true,
      [22, 9] => true,
      [22, 10] => true,
      [22, 11] => true,
      [22, 12] => true,
      [22, 13] => true,
      [22, 14] => true,
      [23, 8] => true,
      [23, 9] => true,
      [24, 8] => true,
      [24, 9] => true,
      [25, 8] => true,
      [25, 9] => true,
    }

    # Variables that are used by the breadth first search
    # Storing cells that the search has visited, prevents unnecessary steps
    # Expanding the frontier of the search in order makes the search expand
    # from the center outward

    # The cells from which the search is to expand
    search.frontier              ||= []
    # A hash of where each cell was expanded from
    # The key is a cell, and the value is the cell it came from
    search.came_from             ||= {}
    # Cells that are part of the path from the target to the star
    search.path                  ||= {}

    # 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.current_input ||= :none
  end

  def calc
    # Setup the search to start from the star
    search.frontier << grid.star
    search.came_from[grid.star] = nil

    # Until there are no more cells to expand from
    until search.frontier.empty?
      # Takes the next frontier cell
      new_frontier = 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 search.came_from.has_key?(neighbor) || grid.walls.has_key?(neighbor)
          # Add them to the frontier and mark them as visited in the first grid
          # Unless the target has been visited
          # Add the neighbor to the frontier and remember which cell it came from
          search.frontier << neighbor
          search.came_from[neighbor] = new_frontier
        end
      end
    end
  end


  # Draws everything onto the screen
  def render
    render_background
    # render_heat_map
    render_walls
    # render_path
    # render_labels
    render_arrows
    render_star
    render_target
    unless grid.walls.has_key?(grid.target)
      render_trail
    end
  end

  def render_trail(current_cell=grid.target)
    return if current_cell == grid.star
    parent_cell = search.came_from[current_cell]
    if current_cell && parent_cell
      outputs.lines << [(current_cell.x + 0.5) * grid.cell_size, (current_cell.y + 0.5) * grid.cell_size,
      (parent_cell.x + 0.5) * grid.cell_size, (parent_cell.y + 0.5) * grid.cell_size, purple]

    end
    render_trail(parent_cell)
  end

  def render_arrows
    search.came_from.each do |child, parent|
      if parent && child
        arrow_cell = [(child.x + parent.x) / 2, (child.y + parent.y) / 2]
        if parent.x > child.x # If the parent cell is to the right of the child cell
          # Point arrow right
          outputs.sprites << scale_up(arrow_cell).merge({ path: 'arrow.png', angle: 0})
        elsif parent.x < child.x # If the parent cell is to the right of the child cell
          outputs.sprites << scale_up(arrow_cell).merge({ path: 'arrow.png', angle: 180})
        elsif parent.y > child.y # If the parent cell is to the right of the child cell
          outputs.sprites << scale_up(arrow_cell).merge({ path: 'arrow.png', angle: 90})
        elsif parent.y < child.y # If the parent cell is to the right of the child cell
          outputs.sprites << scale_up(arrow_cell).merge({ path: 'arrow.png', angle: 270})
        end
      end
    end
  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
  end

  # Draws both grids
  def render_unvisited
    outputs.solids << scale_up(grid.rect).merge(unvisited_color)
  end

  # Draws grid lines to show the division of the grid into cells
  def render_grid_lines
    outputs.lines << (0..grid.width).map { |x| vertical_line(x) }
    outputs.lines << (0..grid.height).map { |y| horizontal_line(y) }
  end

  # Easy way to draw vertical lines given an index
  def vertical_line x
    line = { x: x, y: 0, w: 0, h: grid.height }
    line.transform_values { |v| v * grid.cell_size }
  end

  # Easy way to draw horizontal lines given an index
  def horizontal_line y
    line = { x: 0, y: y, w: grid.width, h: 0 }
    line.transform_values { |v| v * grid.cell_size }
  end

  # Draws the walls on both grids
  def render_walls
    outputs.solids << grid.walls.map do |key, value|
      scale_up(key).merge(wall_color)
    end
  end

  # Renders the star on both grids
  def render_star
    outputs.sprites << scale_up(grid.star).merge({ path: 'star.png' })
  end

  # Renders the target on both grids
  def render_target
    outputs.sprites << scale_up(grid.target).merge({ path: 'target.png'})
  end

  # Labels the grids
  def render_labels
    outputs.labels << [200, 625, "Without early exit"]
  end

  # Renders the path based off of the search.path hash
  def render_path
    # If the star and target are disconnected there will only be one path
    # The path should not render in that case
    unless search.path.size == 1
      search.path.each_key do | cell |
        # Renders path on both grids
        outputs.solids << [scale_up(cell), path_color]
      end
    end
  end

  # Calculates the path from the target to the star after the search is over
  # Relies on the came_from hash
  # Fills the search.path hash, which is later rendered on screen
  def calc_path
    endpoint = grid.target
    while endpoint
      search.path[endpoint] = true
      endpoint = search.came_from[endpoint]
    end
  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)
    x = cell.x * grid.cell_size
    y = cell.y * grid.cell_size
    w = cell.w.zero? ? grid.cell_size : cell.w * grid.cell_size
    h = cell.h.zero? ? grid.cell_size : cell.h * grid.cell_size
    { x: x, y: y, w: w, h: h }
  end

  # This method processes user input every tick
  # Any method with "1" is related to the first grid
  # Any method with "2" is related to the second grid
  def input
    # The program has to remember that the user is dragging an object
    # even when the mouse is no longer over that object
    # So detecting input and processing input is separate
    # detect_input
    # process_input
    if inputs.mouse.up
      state.current_input = :none
    elsif star_clicked?
      state.current_input = :star
    end

    if mouse_inside_grid?
      unless grid.target == cell_closest_to_mouse
        grid.target = cell_closest_to_mouse
      end
      if state.current_input == :star
        unless grid.star == cell_closest_to_mouse
          grid.star = cell_closest_to_mouse
        end
      end
    end
  end

  # Determines what the user is editing and stores the value
  # Storing the value allows the user to continue the same edit as long as the
  # mouse left click is held
  def detect_input
    # When the mouse is up, nothing is being edited
    if inputs.mouse.up
      state.current_input = :none
    # When the star in the no second grid is clicked
    elsif star_clicked?
      state.current_input = :star
    # When the target in the no second grid is clicked
    elsif target_clicked?
      state.current_input = :target
    # When a wall in the first grid is clicked
    elsif wall_clicked?
      state.current_input = :remove_wall
    # When the first grid is clicked
    elsif grid_clicked?
      state.current_input = :add_wall
    end
  end

  # Processes click and drag based on what the user is currently dragging
  def process_input
    if state.current_input == :star
      input_star
    elsif state.current_input == :target
      input_target
    elsif state.current_input == :remove_wall
      input_remove_wall
    elsif state.current_input == :add_wall
      input_add_wall
    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 = grid.star.clone
    grid.star = cell_closest_to_mouse
    unless old_star == grid.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 = grid.target.clone
    grid.target = cell_closest_to_mouse
    unless old_target == grid.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_inside_grid?
      if grid.walls.key?(cell_closest_to_mouse)
        grid.walls.delete(cell_closest_to_mouse)
        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_inside_grid?
      unless grid.walls.key?(cell_closest_to_mouse)
        grid.walls[cell_closest_to_mouse] = 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
    # Reset_Searchs the search
    search.frontier  = []
    search.came_from = {}
    search.path      = {}
  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 = (grid.star.x - x).abs
    distance_y = (grid.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

  # Signal that the user is going to be moving the star from the first grid
  def star_clicked?
    inputs.mouse.down && inputs.mouse.point.inside_rect?(scale_up(grid.star))
  end

  # Signal that the user is going to be moving the target from the first grid
  def target_clicked?
    inputs.mouse.down && inputs.mouse.point.inside_rect?(scale_up(grid.target))
  end

  # Signal that the user is going to be adding walls from the first grid
  def grid_clicked?
    inputs.mouse.down && mouse_inside_grid?
  end

  # Returns whether the mouse is inside of the first grid
  # Part of the condition that checks whether the user is adding a wall
  def mouse_inside_grid?
    inputs.mouse.point.inside_rect?(scale_up(grid.rect))
  end

  # These methods provide handy aliases to colors

  # Light brown
  def unvisited_color
    { r: 221, g: 212, b: 213 }
  end

  # Camo Green
  def wall_color
    { r: 134, g: 134, b: 120 }
  end

  # Pastel White
  def path_color
    [231, 230, 228]
  end

  def red
    [255, 0, 0]
  end

  def purple
    [149, 64, 191]
  end

  # Makes code more concise
  def grid
    state.grid
  end

  def search
    state.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
    GTK.reset
    reset
    return
  end

  # Every tick, new args are passed, and the Breadth First Search tick is called
  $breadcrumbs ||= Breadcrumbs.new
  $breadcrumbs.args = args
  $breadcrumbs.tick
end


def reset
  $breadcrumbs = nil
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_heat_map
 #    # THIS CODE NEEDS SOME FIXING DUE TO REFACTORING
 #    search.came_from.each_key do | cell |
 #      distance = (grid.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]
 #      # outputs.solids << [early_exit_scale_up(visited_cell), red, alpha]
 #    end
 #  end
