diff options
Diffstat (limited to 'samples/13_path_finding_algorithms/05_dijkstra/app/main.rb')
| -rw-r--r-- | samples/13_path_finding_algorithms/05_dijkstra/app/main.rb | 844 |
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 |