diff options
| author | Amir Rajan <[email protected]> | 2021-08-07 00:13:33 -0500 |
|---|---|---|
| committer | Amir Rajan <[email protected]> | 2021-08-07 00:13:33 -0500 |
| commit | a503afe87619ff82201c0a43818fa1c3f070a548 (patch) | |
| tree | 0b228a6456d17f6d0c6ea54c9ecd6a045ddbdf59 /samples/13_path_finding_algorithms | |
| parent | bea150381f495630f92f89d23d5f3445ec289b2d (diff) | |
| download | dragonruby-game-toolkit-contrib-a503afe87619ff82201c0a43818fa1c3f070a548.tar.gz dragonruby-game-toolkit-contrib-a503afe87619ff82201c0a43818fa1c3f070a548.zip | |
Samples folder synced.
Diffstat (limited to 'samples/13_path_finding_algorithms')
4 files changed, 307 insertions, 307 deletions
diff --git a/samples/13_path_finding_algorithms/01_breadth_first_search/app/main.rb b/samples/13_path_finding_algorithms/01_breadth_first_search/app/main.rb index c8e1633..8b84f1c 100644 --- a/samples/13_path_finding_algorithms/01_breadth_first_search/app/main.rb +++ b/samples/13_path_finding_algorithms/01_breadth_first_search/app/main.rb @@ -35,19 +35,19 @@ class BreadthFirstSearch # Stores which step of the animation is being rendered # When the user moves the star or messes with the walls, # the breadth first search is recalculated up to this step - args.state.anim_steps = 0 + args.state.anim_steps = 0 # At some step the animation will end, # and further steps won't change anything (the whole grid will be explored) # This step is roughly the grid's width * height # When anim_steps equals max_steps no more calculations will occur # and the slider will be at the end - args.state.max_steps = args.state.grid.width * args.state.grid.height + args.state.max_steps = args.state.grid.width * args.state.grid.height # Whether the animation should play or not # If true, every tick moves anim_steps forward one # Pressing the stepwise animation buttons will pause the animation - args.state.play = true + args.state.play = true # The location of the star and walls of the grid # They can be modified to have a different initial grid @@ -116,7 +116,7 @@ class BreadthFirstSearch [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 @@ -132,7 +132,7 @@ class BreadthFirstSearch # 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. - args.state.click_and_drag = :none + args.state.click_and_drag = :none # Store the rects of the buttons that control the animation # They are here for user customization @@ -166,13 +166,13 @@ class BreadthFirstSearch # User input is processed, and # The next step in the search is calculated def tick - render - input + render + input # If animation is playing, and max steps have not been reached # Move the search a step forward if state.play && state.anim_steps < state.max_steps # Variable that tells the program what step to recalculate up to - state.anim_steps += 1 + state.anim_steps += 1 calc end end @@ -182,8 +182,8 @@ class BreadthFirstSearch render_buttons render_slider - render_background - render_visited + render_background + render_visited render_frontier render_walls render_star @@ -251,7 +251,7 @@ class BreadthFirstSearch outputs.primitives << [slider.x, slider.y, slider.x + slider.w, slider.y].line # The circle needs to be offset so that the center of the circle # overlaps the line instead of the upper right corner of the circle - # The circle's x value is also moved based on the current search step + # The circle's x value is also moved based on the current seach step circle_x = (slider.x - slider.offset) + (state.anim_steps * slider.spacing) circle_y = (slider.y - slider.offset) circle_rect = [circle_x, circle_y, 37, 37] @@ -260,8 +260,8 @@ class BreadthFirstSearch # Draws what the grid looks like with nothing on it def render_background - render_unvisited - render_grid_lines + render_unvisited + render_grid_lines end # Draws a rectangle the size of the entire grid to represent unvisited cells @@ -276,7 +276,7 @@ class BreadthFirstSearch end for y in 0..grid.height - outputs.lines << horizontal_line(y) + outputs.lines << horizontal_line(y) end end @@ -294,28 +294,28 @@ class BreadthFirstSearch # The frontier is the most outward parts of the search def render_frontier outputs.solids << state.frontier.map do |cell| - [scale_up(cell), frontier_color] + [scale_up([cell.x, cell.y]), frontier_color] end end # Draws the walls def render_walls outputs.solids << state.walls.map do |wall| - [scale_up(wall), wall_color] + [scale_up([wall.x, wall.y]), wall_color] end end # Renders cells that have been searched in the appropriate color def render_visited outputs.solids << state.visited.map do |cell| - [scale_up(cell), visited_color] + [scale_up([cell.x, cell.y]), visited_color] end end # Renders the star def render_star outputs.sprites << [scale_up(state.star), 'star.png'] - end + end # In code, the cells are represented as 1x1 rectangles # When drawn, the cells are larger than 1x1 rectangles @@ -369,20 +369,20 @@ class BreadthFirstSearch # The detection and processing of click and drag inputs are separate # The program has to remember that the user is dragging an object # even when the mouse is no longer over that object - detect_click_and_drag - process_click_and_drag + detect_click_and_drag + process_click_and_drag end # Detects and Process input for each button def input_buttons - input_left_button - input_center_button - input_next_step_button + input_left_button + input_center_button + input_next_step_button end # Checks if the previous step button is clicked # If it is, it pauses the animation and moves the search one step backward - def input_left_button + def input_left_button if left_button_clicked? state.play = false state.anim_steps -= 1 @@ -394,7 +394,7 @@ class BreadthFirstSearch # Inverses whether the animation is playing or not when clicked def input_center_button if center_button_clicked? or inputs.keyboard.key_down.space - state.play = !state.play + state.play = !state.play end end @@ -402,8 +402,8 @@ class BreadthFirstSearch # If it is, it pauses the animation and moves the search one step forward def input_next_step_button if right_button_clicked? - state.play = false - state.anim_steps += 1 + state.play = false + state.anim_steps += 1 calc end end @@ -412,29 +412,29 @@ class BreadthFirstSearch # Storing the value allows the user to continue the same edit as long as the # mouse left click is held def detect_click_and_drag - if inputs.mouse.up - state.click_and_drag = :none - elsif star_clicked? - state.click_and_drag = :star - elsif wall_clicked? - state.click_and_drag = :remove_wall - elsif grid_clicked? - state.click_and_drag = :add_wall - elsif slider_clicked? - state.click_and_drag = :slider + if inputs.mouse.up + state.click_and_drag = :none + elsif star_clicked? + state.click_and_drag = :star + elsif wall_clicked? + state.click_and_drag = :remove_wall + elsif grid_clicked? + state.click_and_drag = :add_wall + elsif slider_clicked? + state.click_and_drag = :slider end end # Processes click and drag based on what the user is currently dragging def process_click_and_drag - if state.click_and_drag == :star - input_star - elsif state.click_and_drag == :remove_wall - input_remove_wall - elsif state.click_and_drag == :add_wall - input_add_wall - elsif state.click_and_drag == :slider - input_slider + if state.click_and_drag == :star + input_star + elsif state.click_and_drag == :remove_wall + input_remove_wall + elsif state.click_and_drag == :add_wall + input_add_wall + elsif state.click_and_drag == :slider + input_slider end end @@ -442,10 +442,10 @@ class BreadthFirstSearch # Only recalculates 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 + old_star = state.star.clone state.star = cell_closest_to_mouse - unless old_star == state.star - recalculate + unless old_star == state.star + recalculate end end @@ -454,20 +454,20 @@ class BreadthFirstSearch # 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 mouse_inside_grid? if state.walls.has_key?(cell_closest_to_mouse) - state.walls.delete(cell_closest_to_mouse) - recalculate + state.walls.delete(cell_closest_to_mouse) + recalculate end end end # Adds walls at cells under the cursor def input_add_wall - if mouse_inside_grid? + if mouse_inside_grid? unless state.walls.has_key?(cell_closest_to_mouse) - state.walls[cell_closest_to_mouse] = true - recalculate + state.walls[cell_closest_to_mouse] = true + recalculate end end end @@ -477,18 +477,18 @@ class BreadthFirstSearch # on the slider # Changes the step of the search to be animated def input_slider - state.play = false + state.play = false mouse_x = inputs.mouse.point.x # Bounds the mouse_x to the closest x value on the slider line - mouse_x = slider.x if mouse_x < slider.x - mouse_x = slider.x + slider.w if mouse_x > slider.x + slider.w + mouse_x = slider.x if mouse_x < slider.x + mouse_x = slider.x + slider.w if mouse_x > slider.x + slider.w # Sets the current search step to the one represented by the mouse x value # The slider's circle moves due to the render_slider method using anim_steps state.anim_steps = ((mouse_x - slider.x) / slider.spacing).to_i - recalculate + recalculate end # Whenever the user edits the grid, @@ -496,11 +496,11 @@ class BreadthFirstSearch # with the current grid as the initial state of the grid def recalculate # Resets the search - state.frontier = [] - state.visited = {} + state.frontier = [] + state.visited = {} # Moves the animation forward one step at a time - state.anim_steps.times { calc } + state.anim_steps.times { calc } end @@ -515,39 +515,39 @@ class BreadthFirstSearch # The setup to the search # Runs once when the there is no frontier or visited cells - if state.frontier.empty? && state.visited.empty? - state.frontier << state.star - state.visited[state.star] = true + if state.frontier.empty? && state.visited.empty? + state.frontier << state.star + state.visited[state.star] = true end # A step in the search - unless state.frontier.empty? + unless state.frontier.empty? # Takes the next frontier cell - new_frontier = state.frontier.shift + new_frontier = state.frontier.shift # For each of its neighbors - adjacent_neighbors(new_frontier).each do |neighbor| + adjacent_neighbors(new_frontier).each do |neighbor| # That have not been visited and are not walls - unless state.visited.has_key?(neighbor) || state.walls.has_key?(neighbor) + unless state.visited.has_key?(neighbor) || state.walls.has_key?(neighbor) # Add them to the frontier and mark them as visited - state.frontier << neighbor - state.visited[neighbor] = true + state.frontier << neighbor + state.visited[neighbor] = true end end end 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 = [] + neighbors = [] - neighbors << [cell.x, cell.y + 1] unless cell.y == grid.height - 1 - neighbors << [cell.x + 1, cell.y] unless cell.x == grid.width - 1 - 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 + neighbors << [cell.x, cell.y - 1] unless cell.y == 0 + neighbors << [cell.x - 1, cell.y] unless cell.x == 0 - neighbors + neighbors end # When the user grabs the star and puts their cursor to the far right @@ -555,13 +555,13 @@ class BreadthFirstSearch # Finding the cell closest to the mouse helps with this def cell_closest_to_mouse # Closest cell to the mouse - x = (inputs.mouse.point.x / grid.cell_size).to_i - y = (inputs.mouse.point.y / grid.cell_size).to_i + 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 + x = grid.width - 1 if x > grid.width - 1 + y = grid.height - 1 if y > grid.height - 1 # Return closest cell - [x, y] + [x, y] end # These methods detect when the buttons are clicked @@ -605,7 +605,7 @@ class BreadthFirstSearch # Part of the condition that checks whether the user is removing a wall def mouse_inside_a_wall? state.walls.each_key do | wall | - return true if inputs.mouse.point.inside_rect?(scale_up(wall)) + return true if inputs.mouse.point.inside_rect?(scale_up([wall.x, wall.y])) end false @@ -622,27 +622,27 @@ class BreadthFirstSearch # Light brown def unvisited_color - [221, 212, 213] + [221, 212, 213] end # Black def grid_line_color - [255, 255, 255] + [255, 255, 255] end # Dark Brown def visited_color - [204, 191, 179] + [204, 191, 179] end # Blue def frontier_color - [103, 136, 204] + [103, 136, 204] end # Camo Green def wall_color - [134, 134, 120] + [134, 134, 120] end # Button Background diff --git a/samples/13_path_finding_algorithms/02_detailed_breadth_first_search/app/main.rb b/samples/13_path_finding_algorithms/02_detailed_breadth_first_search/app/main.rb index d4c9c1c..810ff7b 100644 --- a/samples/13_path_finding_algorithms/02_detailed_breadth_first_search/app/main.rb +++ b/samples/13_path_finding_algorithms/02_detailed_breadth_first_search/app/main.rb @@ -168,7 +168,7 @@ class DetailedBreadthFirstSearch outputs.primitives << [slider.x, slider.y, slider.x + slider.w, slider.y].line # The circle needs to be offset so that the center of the circle # overlaps the line instead of the upper right corner of the circle - # The circle's x value is also moved based on the current search step + # The circle's x value is also moved based on the current seach step circle_x = (slider.x - slider.offset) + (state.anim_steps * slider.spacing) circle_y = (slider.y - slider.offset) circle_rect = [circle_x, circle_y, 37, 37] diff --git a/samples/13_path_finding_algorithms/06_heuristic/app/main.rb b/samples/13_path_finding_algorithms/06_heuristic/app/main.rb index 10beba3..cbdfca7 100644 --- a/samples/13_path_finding_algorithms/06_heuristic/app/main.rb +++ b/samples/13_path_finding_algorithms/06_heuristic/app/main.rb @@ -10,13 +10,13 @@ class Heuristic_With_Walls def tick defaults - render - input + render + input # If animation is playing, and max steps have not been reached # Move the search a step forward if state.play && state.current_step < state.max_steps # Variable that tells the program what step to recalculate up to - state.current_step += 1 + state.current_step += 1 move_searches_one_step_forward end end @@ -38,7 +38,7 @@ class Heuristic_With_Walls # 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 + state.user_input ||= :none # These variables allow the breadth first search to take place # Came_from is a hash with a key of a cell and a value of the cell that was expanded from to find the key. @@ -63,7 +63,7 @@ class Heuristic_With_Walls # Unless the current step has a value unless state.current_step # Set the current step to 10 - state.current_step = 10 + state.current_step = 10 # And calculate the searches up to step 10 recalculate_searches end @@ -73,7 +73,7 @@ class Heuristic_With_Walls # This step is roughly the grid's width * height # When anim_steps equals max_steps no more calculations will occur # and the slider will be at the end - state.max_steps = grid.width * grid.height + state.max_steps = grid.width * grid.height # Whether the animation should play or not # If true, every tick moves anim_steps forward one @@ -166,7 +166,7 @@ class Heuristic_With_Walls # If the mouse was clicked this tick if inputs.mouse.down # Determine what the user is editing and appropriately edit the state.user_input variable - determine_input + determine_input end # Process user input based on user_input variable and current mouse position @@ -179,35 +179,35 @@ class Heuristic_With_Walls if mouse_over_slider? state.user_input = :slider # If the mouse is over the star in the first grid - elsif bfs_mouse_over_star? + elsif bfs_mouse_over_star? # The user is editing the star from the first grid - state.user_input = :bfs_star + state.user_input = :bfs_star # If the mouse is over the star in the second grid - elsif heuristic_mouse_over_star? + elsif heuristic_mouse_over_star? # The user is editing the star from the second grid - state.user_input = :heuristic_star + state.user_input = :heuristic_star # If the mouse is over the target in the first grid - elsif bfs_mouse_over_target? + elsif bfs_mouse_over_target? # The user is editing the target from the first grid - state.user_input = :bfs_target + state.user_input = :bfs_target # If the mouse is over the target in the second grid - elsif heuristic_mouse_over_target? + elsif heuristic_mouse_over_target? # The user is editing the target from the second grid - state.user_input = :heuristic_target + state.user_input = :heuristic_target # If the mouse is over a wall in the first grid - elsif bfs_mouse_over_wall? + elsif bfs_mouse_over_wall? # The user is removing a wall from the first grid - state.user_input = :bfs_remove_wall + state.user_input = :bfs_remove_wall # If the mouse is over a wall in the second grid - elsif heuristic_mouse_over_wall? + elsif heuristic_mouse_over_wall? # The user is removing a wall from the second grid state.user_input = :heuristic_remove_wall # If the mouse is over the first grid - elsif bfs_mouse_over_grid? + elsif bfs_mouse_over_grid? # The user is adding a wall from the first grid state.user_input = :bfs_add_wall # If the mouse is over the second grid - elsif heuristic_mouse_over_grid? + elsif heuristic_mouse_over_grid? # The user is adding a wall from the second grid state.user_input = :heuristic_add_wall end @@ -217,22 +217,22 @@ class Heuristic_With_Walls def process_input if state.user_input == :slider process_input_slider - elsif state.user_input == :bfs_star - process_input_bfs_star + elsif state.user_input == :bfs_star + process_input_bfs_star elsif state.user_input == :heuristic_star - process_input_heuristic_star - elsif state.user_input == :bfs_target - process_input_bfs_target - elsif state.user_input == :heuristic_target - process_input_heuristic_target - elsif state.user_input == :bfs_remove_wall - process_input_bfs_remove_wall + process_input_heuristic_star + elsif state.user_input == :bfs_target + process_input_bfs_target + elsif state.user_input == :heuristic_target + process_input_heuristic_target + elsif state.user_input == :bfs_remove_wall + process_input_bfs_remove_wall elsif state.user_input == :heuristic_remove_wall - process_input_heuristic_remove_wall - elsif state.user_input == :bfs_add_wall - process_input_bfs_add_wall - elsif state.user_input == :heuristic_add_wall - process_input_heuristic_add_wall + process_input_heuristic_remove_wall + elsif state.user_input == :bfs_add_wall + process_input_bfs_add_wall + elsif state.user_input == :heuristic_add_wall + process_input_heuristic_add_wall end end @@ -242,7 +242,7 @@ class Heuristic_With_Walls outputs.primitives << [slider.x, slider.y, slider.x + slider.w, slider.y].line # The circle needs to be offset so that the center of the circle # overlaps the line instead of the upper right corner of the circle - # The circle's x value is also moved based on the current search step + # The circle's x value is also moved based on the current seach step circle_x = (slider.x - slider.offset) + (state.current_step * slider.spacing) circle_y = (slider.y - slider.offset) circle_rect = [circle_x, circle_y, 37, 37] @@ -309,7 +309,7 @@ class Heuristic_With_Walls # The horizontal grid lines for y in 0..grid.height - outputs.lines << bfs_horizontal_line(y) + outputs.lines << bfs_horizontal_line(y) end end @@ -324,10 +324,10 @@ class Heuristic_With_Walls # The horizontal grid lines for y in 0..grid.height - outputs.lines << heuristic_horizontal_line(y) + outputs.lines << heuristic_horizontal_line(y) end end - + # Returns a vertical line for a column of the first grid def bfs_vertical_line column bfs_scale_up([column, 0, column, grid.height]) @@ -362,7 +362,7 @@ class Heuristic_With_Walls def render_bfs_target outputs.sprites << [bfs_scale_up(grid.target), 'target.png'] end - + # Renders the target on the second grid def render_heuristic_target outputs.sprites << [heuristic_scale_up(grid.target), 'target.png'] @@ -370,14 +370,14 @@ class Heuristic_With_Walls # Renders the walls on the first grid def render_bfs_walls - grid.walls.each_key do | wall | + grid.walls.each_key do | wall | outputs.solids << [bfs_scale_up(wall), wall_color] end end # Renders the walls on the second grid def render_heuristic_walls - grid.walls.each_key do | wall | + grid.walls.each_key do | wall | outputs.solids << [heuristic_scale_up(wall), wall_color] end end @@ -398,14 +398,14 @@ class Heuristic_With_Walls # Renders the frontier cells on the first grid def render_bfs_frontier - bfs.frontier.each do | frontier_cell | + bfs.frontier.each do | frontier_cell | outputs.solids << [bfs_scale_up(frontier_cell), frontier_color, 200] end end # Renders the frontier cells on the second grid def render_heuristic_frontier - heuristic.frontier.each do | frontier_cell | + heuristic.frontier.each do | frontier_cell | outputs.solids << [heuristic_scale_up(frontier_cell), frontier_color, 200] end end @@ -489,14 +489,14 @@ class Heuristic_With_Walls # Checks and handles input for the buttons # Called when the mouse is lifted def input_buttons - input_left_button - input_center_button - input_right_button + input_left_button + input_center_button + input_right_button end # Checks if the previous step button is clicked # If it is, it pauses the animation and moves the search one step backward - def input_left_button + def input_left_button if left_button_clicked? state.play = false state.current_step -= 1 @@ -508,7 +508,7 @@ class Heuristic_With_Walls # Inverses whether the animation is playing or not when clicked def input_center_button if center_button_clicked? || inputs.keyboard.key_down.space - state.play = !state.play + state.play = !state.play end end @@ -516,8 +516,8 @@ class Heuristic_With_Walls # If it is, it pauses the animation and moves the search one step forward def input_right_button if right_button_clicked? - state.play = false - state.current_step += 1 + state.play = false + state.current_step += 1 move_searches_one_step_forward end end @@ -598,12 +598,12 @@ class Heuristic_With_Walls # on the slider # Changes the step of the search to be animated def process_input_slider - state.play = false + state.play = false mouse_x = inputs.mouse.point.x # Bounds the mouse_x to the closest x value on the slider line - mouse_x = slider.x if mouse_x < slider.x - mouse_x = slider.x + slider.w if mouse_x > slider.x + slider.w + mouse_x = slider.x if mouse_x < slider.x + mouse_x = slider.x + slider.w if mouse_x > slider.x + slider.w # Sets the current search step to the one represented by the mouse x value # The slider's circle moves due to the render_slider method using anim_steps @@ -616,12 +616,12 @@ class Heuristic_With_Walls # Only resets the search if the star changes position # Called whenever the user is editing the star (puts mouse down on star) def process_input_bfs_star - old_star = grid.star.clone + old_star = grid.star.clone unless bfs_cell_closest_to_mouse == grid.target - grid.star = bfs_cell_closest_to_mouse + grid.star = bfs_cell_closest_to_mouse end - unless old_star == grid.star - recalculate_searches + unless old_star == grid.star + recalculate_searches end end @@ -629,12 +629,12 @@ class Heuristic_With_Walls # Only resets the search if the star changes position # Called whenever the user is editing the star (puts mouse down on star) def process_input_heuristic_star - old_star = grid.star.clone + old_star = grid.star.clone unless heuristic_cell_closest_to_mouse == grid.target grid.star = heuristic_cell_closest_to_mouse end - unless old_star == grid.star - recalculate_searches + unless old_star == grid.star + recalculate_searches end end @@ -642,12 +642,12 @@ class Heuristic_With_Walls # Only recalculate_searchess the search if the target changes position # Called whenever the user is editing the target (puts mouse down on target) def process_input_bfs_target - old_target = grid.target.clone + old_target = grid.target.clone unless bfs_cell_closest_to_mouse == grid.star grid.target = bfs_cell_closest_to_mouse end - unless old_target == grid.target - recalculate_searches + unless old_target == grid.target + recalculate_searches end end @@ -655,12 +655,12 @@ class Heuristic_With_Walls # Only recalculate_searchess the search if the target changes position # Called whenever the user is editing the target (puts mouse down on target) def process_input_heuristic_target - old_target = grid.target.clone + old_target = grid.target.clone unless heuristic_cell_closest_to_mouse == grid.star grid.target = heuristic_cell_closest_to_mouse end - unless old_target == grid.target - recalculate_searches + unless old_target == grid.target + recalculate_searches end end @@ -669,10 +669,10 @@ class Heuristic_With_Walls # 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 bfs_mouse_over_grid? + if bfs_mouse_over_grid? if grid.walls.has_key?(bfs_cell_closest_to_mouse) - grid.walls.delete(bfs_cell_closest_to_mouse) - recalculate_searches + grid.walls.delete(bfs_cell_closest_to_mouse) + recalculate_searches end end end @@ -682,29 +682,29 @@ class Heuristic_With_Walls # 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 heuristic_mouse_over_grid? + if heuristic_mouse_over_grid? if grid.walls.has_key?(heuristic_cell_closest_to_mouse) - grid.walls.delete(heuristic_cell_closest_to_mouse) - recalculate_searches + grid.walls.delete(heuristic_cell_closest_to_mouse) + recalculate_searches end end end # Adds a wall in the first grid in the cell the mouse is over def process_input_bfs_add_wall - if bfs_mouse_over_grid? + if bfs_mouse_over_grid? unless grid.walls.has_key?(bfs_cell_closest_to_mouse) - grid.walls[bfs_cell_closest_to_mouse] = true - recalculate_searches + grid.walls[bfs_cell_closest_to_mouse] = true + recalculate_searches end end end # Adds a wall in the second grid in the cell the mouse is over def process_input_heuristic_add_wall - if heuristic_mouse_over_grid? + if heuristic_mouse_over_grid? unless grid.walls.has_key?(heuristic_cell_closest_to_mouse) - grid.walls[heuristic_cell_closest_to_mouse] = true - recalculate_searches + grid.walls[heuristic_cell_closest_to_mouse] = true + recalculate_searches end end end @@ -714,13 +714,13 @@ class Heuristic_With_Walls # Finding the cell closest to the mouse helps with this def bfs_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 + 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 + x = grid.width - 1 if x > grid.width - 1 + y = grid.height - 1 if y > grid.height - 1 # Return closest cell - [x, y] + [x, y] end # When the user grabs the star and puts their cursor to the far right @@ -728,17 +728,17 @@ class Heuristic_With_Walls # Finding the cell closest to the mouse in the second grid helps with this def heuristic_cell_closest_to_mouse # 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 + 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 + x = grid.width - 1 if x > grid.width - 1 + y = grid.height - 1 if y > grid.height - 1 # Return closest cell - [x, y] + [x, y] end def recalculate_searches @@ -763,22 +763,22 @@ class Heuristic_With_Walls return if bfs.came_from.has_key?(grid.target) # Only runs at the beginning of the search as setup. - if bfs.came_from.empty? - bfs.frontier << grid.star - bfs.came_from[grid.star] = nil + if bfs.came_from.empty? + bfs.frontier << grid.star + bfs.came_from[grid.star] = nil end # A step in the search - unless bfs.frontier.empty? + unless bfs.frontier.empty? # Takes the next frontier cell - new_frontier = bfs.frontier.shift + new_frontier = bfs.frontier.shift # For each of its neighbors - adjacent_neighbors(new_frontier).each do |neighbor| + adjacent_neighbors(new_frontier).each do |neighbor| # That have not been visited and are not walls - unless bfs.came_from.has_key?(neighbor) || grid.walls.has_key?(neighbor) + unless bfs.came_from.has_key?(neighbor) || grid.walls.has_key?(neighbor) # Add them to the frontier and mark them as visited - bfs.frontier << neighbor - bfs.came_from[neighbor] = new_frontier + bfs.frontier << neighbor + bfs.came_from[neighbor] = new_frontier end end end @@ -833,12 +833,12 @@ class Heuristic_With_Walls # Get the next cell to explore from new_frontier = heuristic.frontier.shift # For each of its neighbors - adjacent_neighbors(new_frontier).each do |neighbor| + adjacent_neighbors(new_frontier).each do |neighbor| # That have not been visited and are not walls - unless heuristic.came_from.has_key?(neighbor) || grid.walls.has_key?(neighbor) + unless heuristic.came_from.has_key?(neighbor) || grid.walls.has_key?(neighbor) # Add them to the frontier and mark them as visited - heuristic.frontier << neighbor - heuristic.came_from[neighbor] = new_frontier + heuristic.frontier << neighbor + heuristic.came_from[neighbor] = new_frontier end end end @@ -882,16 +882,16 @@ class Heuristic_With_Walls # 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 = [] + 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 + 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 - neighbors + neighbors end # Finds the vertical and horizontal distance of a cell from the star @@ -940,7 +940,7 @@ class Heuristic_With_Walls def wall_color [134, 134, 120] # Camo Green end - + def visited_color [204, 191, 179] # Dark Brown end @@ -948,7 +948,7 @@ class Heuristic_With_Walls def frontier_color [103, 136, 204] # Blue end - + def path_color [231, 230, 228] # Pastel White end diff --git a/samples/13_path_finding_algorithms/07_heuristic_with_walls/app/main.rb b/samples/13_path_finding_algorithms/07_heuristic_with_walls/app/main.rb index 7b8f653..b106e34 100644 --- a/samples/13_path_finding_algorithms/07_heuristic_with_walls/app/main.rb +++ b/samples/13_path_finding_algorithms/07_heuristic_with_walls/app/main.rb @@ -10,13 +10,13 @@ class Heuristic def tick defaults - render - input + render + input # If animation is playing, and max steps have not been reached # Move the search a step forward if state.play && state.current_step < state.max_steps # Variable that tells the program what step to recalculate up to - state.current_step += 1 + state.current_step += 1 move_searches_one_step_forward end end @@ -71,7 +71,7 @@ class Heuristic # 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 + state.user_input ||= :none # These variables allow the breadth first search to take place # Came_from is a hash with a key of a cell and a value of the cell that was expanded from to find the key. @@ -96,7 +96,7 @@ class Heuristic # Unless the current step has a value unless state.current_step # Set the current step to 10 - state.current_step = 10 + state.current_step = 10 # And calculate the searches up to step 10 recalculate_searches end @@ -106,7 +106,7 @@ class Heuristic # This step is roughly the grid's width * height # When anim_steps equals max_steps no more calculations will occur # and the slider will be at the end - state.max_steps = grid.width * grid.height + state.max_steps = grid.width * grid.height # Whether the animation should play or not # If true, every tick moves anim_steps forward one @@ -199,7 +199,7 @@ class Heuristic # If the mouse was clicked this tick if inputs.mouse.down # Determine what the user is editing and appropriately edit the state.user_input variable - determine_input + determine_input end # Process user input based on user_input variable and current mouse position @@ -212,35 +212,35 @@ class Heuristic if mouse_over_slider? state.user_input = :slider # If the mouse is over the star in the first grid - elsif bfs_mouse_over_star? + elsif bfs_mouse_over_star? # The user is editing the star from the first grid - state.user_input = :bfs_star + state.user_input = :bfs_star # If the mouse is over the star in the second grid - elsif heuristic_mouse_over_star? + elsif heuristic_mouse_over_star? # The user is editing the star from the second grid - state.user_input = :heuristic_star + state.user_input = :heuristic_star # If the mouse is over the target in the first grid - elsif bfs_mouse_over_target? + elsif bfs_mouse_over_target? # The user is editing the target from the first grid - state.user_input = :bfs_target + state.user_input = :bfs_target # If the mouse is over the target in the second grid - elsif heuristic_mouse_over_target? + elsif heuristic_mouse_over_target? # The user is editing the target from the second grid - state.user_input = :heuristic_target + state.user_input = :heuristic_target # If the mouse is over a wall in the first grid - elsif bfs_mouse_over_wall? + elsif bfs_mouse_over_wall? # The user is removing a wall from the first grid - state.user_input = :bfs_remove_wall + state.user_input = :bfs_remove_wall # If the mouse is over a wall in the second grid - elsif heuristic_mouse_over_wall? + elsif heuristic_mouse_over_wall? # The user is removing a wall from the second grid state.user_input = :heuristic_remove_wall # If the mouse is over the first grid - elsif bfs_mouse_over_grid? + elsif bfs_mouse_over_grid? # The user is adding a wall from the first grid state.user_input = :bfs_add_wall # If the mouse is over the second grid - elsif heuristic_mouse_over_grid? + elsif heuristic_mouse_over_grid? # The user is adding a wall from the second grid state.user_input = :heuristic_add_wall end @@ -250,22 +250,22 @@ class Heuristic def process_input if state.user_input == :slider process_input_slider - elsif state.user_input == :bfs_star - process_input_bfs_star + elsif state.user_input == :bfs_star + process_input_bfs_star elsif state.user_input == :heuristic_star - process_input_heuristic_star - elsif state.user_input == :bfs_target - process_input_bfs_target - elsif state.user_input == :heuristic_target - process_input_heuristic_target - elsif state.user_input == :bfs_remove_wall - process_input_bfs_remove_wall + process_input_heuristic_star + elsif state.user_input == :bfs_target + process_input_bfs_target + elsif state.user_input == :heuristic_target + process_input_heuristic_target + elsif state.user_input == :bfs_remove_wall + process_input_bfs_remove_wall elsif state.user_input == :heuristic_remove_wall - process_input_heuristic_remove_wall - elsif state.user_input == :bfs_add_wall - process_input_bfs_add_wall - elsif state.user_input == :heuristic_add_wall - process_input_heuristic_add_wall + process_input_heuristic_remove_wall + elsif state.user_input == :bfs_add_wall + process_input_bfs_add_wall + elsif state.user_input == :heuristic_add_wall + process_input_heuristic_add_wall end end @@ -275,7 +275,7 @@ class Heuristic outputs.primitives << [slider.x, slider.y, slider.x + slider.w, slider.y].line # The circle needs to be offset so that the center of the circle # overlaps the line instead of the upper right corner of the circle - # The circle's x value is also moved based on the current search step + # The circle's x value is also moved based on the current seach step circle_x = (slider.x - slider.offset) + (state.current_step * slider.spacing) circle_y = (slider.y - slider.offset) circle_rect = [circle_x, circle_y, 37, 37] @@ -342,7 +342,7 @@ class Heuristic # The horizontal grid lines for y in 0..grid.height - outputs.lines << bfs_horizontal_line(y) + outputs.lines << bfs_horizontal_line(y) end end @@ -357,10 +357,10 @@ class Heuristic # The horizontal grid lines for y in 0..grid.height - outputs.lines << heuristic_horizontal_line(y) + outputs.lines << heuristic_horizontal_line(y) end end - + # Returns a vertical line for a column of the first grid def bfs_vertical_line column bfs_scale_up([column, 0, column, grid.height]) @@ -395,7 +395,7 @@ class Heuristic def render_bfs_target outputs.sprites << [bfs_scale_up(grid.target), 'target.png'] end - + # Renders the target on the second grid def render_heuristic_target outputs.sprites << [heuristic_scale_up(grid.target), 'target.png'] @@ -403,14 +403,14 @@ class Heuristic # Renders the walls on the first grid def render_bfs_walls - grid.walls.each_key do | wall | + grid.walls.each_key do | wall | outputs.solids << [bfs_scale_up(wall), wall_color] end end # Renders the walls on the second grid def render_heuristic_walls - grid.walls.each_key do | wall | + grid.walls.each_key do | wall | outputs.solids << [heuristic_scale_up(wall), wall_color] end end @@ -431,14 +431,14 @@ class Heuristic # Renders the frontier cells on the first grid def render_bfs_frontier - bfs.frontier.each do | frontier_cell | + bfs.frontier.each do | frontier_cell | outputs.solids << [bfs_scale_up(frontier_cell), frontier_color, 200] end end # Renders the frontier cells on the second grid def render_heuristic_frontier - heuristic.frontier.each do | frontier_cell | + heuristic.frontier.each do | frontier_cell | outputs.solids << [heuristic_scale_up(frontier_cell), frontier_color, 200] end end @@ -522,14 +522,14 @@ class Heuristic # Checks and handles input for the buttons # Called when the mouse is lifted def input_buttons - input_left_button - input_center_button - input_right_button + input_left_button + input_center_button + input_right_button end # Checks if the previous step button is clicked # If it is, it pauses the animation and moves the search one step backward - def input_left_button + def input_left_button if left_button_clicked? state.play = false state.current_step -= 1 @@ -541,7 +541,7 @@ class Heuristic # Inverses whether the animation is playing or not when clicked def input_center_button if center_button_clicked? || inputs.keyboard.key_down.space - state.play = !state.play + state.play = !state.play end end @@ -549,8 +549,8 @@ class Heuristic # If it is, it pauses the animation and moves the search one step forward def input_right_button if right_button_clicked? - state.play = false - state.current_step += 1 + state.play = false + state.current_step += 1 move_searches_one_step_forward end end @@ -631,12 +631,12 @@ class Heuristic # on the slider # Changes the step of the search to be animated def process_input_slider - state.play = false + state.play = false mouse_x = inputs.mouse.point.x # Bounds the mouse_x to the closest x value on the slider line - mouse_x = slider.x if mouse_x < slider.x - mouse_x = slider.x + slider.w if mouse_x > slider.x + slider.w + mouse_x = slider.x if mouse_x < slider.x + mouse_x = slider.x + slider.w if mouse_x > slider.x + slider.w # Sets the current search step to the one represented by the mouse x value # The slider's circle moves due to the render_slider method using anim_steps @@ -649,12 +649,12 @@ class Heuristic # Only resets the search if the star changes position # Called whenever the user is editing the star (puts mouse down on star) def process_input_bfs_star - old_star = grid.star.clone + old_star = grid.star.clone unless bfs_cell_closest_to_mouse == grid.target - grid.star = bfs_cell_closest_to_mouse + grid.star = bfs_cell_closest_to_mouse end - unless old_star == grid.star - recalculate_searches + unless old_star == grid.star + recalculate_searches end end @@ -662,12 +662,12 @@ class Heuristic # Only resets the search if the star changes position # Called whenever the user is editing the star (puts mouse down on star) def process_input_heuristic_star - old_star = grid.star.clone + old_star = grid.star.clone unless heuristic_cell_closest_to_mouse == grid.target grid.star = heuristic_cell_closest_to_mouse end - unless old_star == grid.star - recalculate_searches + unless old_star == grid.star + recalculate_searches end end @@ -675,12 +675,12 @@ class Heuristic # Only recalculate_searchess the search if the target changes position # Called whenever the user is editing the target (puts mouse down on target) def process_input_bfs_target - old_target = grid.target.clone + old_target = grid.target.clone unless bfs_cell_closest_to_mouse == grid.star grid.target = bfs_cell_closest_to_mouse end - unless old_target == grid.target - recalculate_searches + unless old_target == grid.target + recalculate_searches end end @@ -688,12 +688,12 @@ class Heuristic # Only recalculate_searchess the search if the target changes position # Called whenever the user is editing the target (puts mouse down on target) def process_input_heuristic_target - old_target = grid.target.clone + old_target = grid.target.clone unless heuristic_cell_closest_to_mouse == grid.star grid.target = heuristic_cell_closest_to_mouse end - unless old_target == grid.target - recalculate_searches + unless old_target == grid.target + recalculate_searches end end @@ -702,10 +702,10 @@ class Heuristic # 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 bfs_mouse_over_grid? + if bfs_mouse_over_grid? if grid.walls.has_key?(bfs_cell_closest_to_mouse) - grid.walls.delete(bfs_cell_closest_to_mouse) - recalculate_searches + grid.walls.delete(bfs_cell_closest_to_mouse) + recalculate_searches end end end @@ -715,29 +715,29 @@ class Heuristic # 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 heuristic_mouse_over_grid? + if heuristic_mouse_over_grid? if grid.walls.has_key?(heuristic_cell_closest_to_mouse) - grid.walls.delete(heuristic_cell_closest_to_mouse) - recalculate_searches + grid.walls.delete(heuristic_cell_closest_to_mouse) + recalculate_searches end end end # Adds a wall in the first grid in the cell the mouse is over def process_input_bfs_add_wall - if bfs_mouse_over_grid? + if bfs_mouse_over_grid? unless grid.walls.has_key?(bfs_cell_closest_to_mouse) - grid.walls[bfs_cell_closest_to_mouse] = true - recalculate_searches + grid.walls[bfs_cell_closest_to_mouse] = true + recalculate_searches end end end # Adds a wall in the second grid in the cell the mouse is over def process_input_heuristic_add_wall - if heuristic_mouse_over_grid? + if heuristic_mouse_over_grid? unless grid.walls.has_key?(heuristic_cell_closest_to_mouse) - grid.walls[heuristic_cell_closest_to_mouse] = true - recalculate_searches + grid.walls[heuristic_cell_closest_to_mouse] = true + recalculate_searches end end end @@ -747,13 +747,13 @@ class Heuristic # Finding the cell closest to the mouse helps with this def bfs_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 + 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 + x = grid.width - 1 if x > grid.width - 1 + y = grid.height - 1 if y > grid.height - 1 # Return closest cell - [x, y] + [x, y] end # When the user grabs the star and puts their cursor to the far right @@ -761,17 +761,17 @@ class Heuristic # Finding the cell closest to the mouse in the second grid helps with this def heuristic_cell_closest_to_mouse # 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 + 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 + x = grid.width - 1 if x > grid.width - 1 + y = grid.height - 1 if y > grid.height - 1 # Return closest cell - [x, y] + [x, y] end def recalculate_searches @@ -796,22 +796,22 @@ class Heuristic return if bfs.came_from.has_key?(grid.target) # Only runs at the beginning of the search as setup. - if bfs.came_from.empty? - bfs.frontier << grid.star - bfs.came_from[grid.star] = nil + if bfs.came_from.empty? + bfs.frontier << grid.star + bfs.came_from[grid.star] = nil end # A step in the search - unless bfs.frontier.empty? + unless bfs.frontier.empty? # Takes the next frontier cell - new_frontier = bfs.frontier.shift + new_frontier = bfs.frontier.shift # For each of its neighbors - adjacent_neighbors(new_frontier).each do |neighbor| + adjacent_neighbors(new_frontier).each do |neighbor| # That have not been visited and are not walls - unless bfs.came_from.has_key?(neighbor) || grid.walls.has_key?(neighbor) + unless bfs.came_from.has_key?(neighbor) || grid.walls.has_key?(neighbor) # Add them to the frontier and mark them as visited - bfs.frontier << neighbor - bfs.came_from[neighbor] = new_frontier + bfs.frontier << neighbor + bfs.came_from[neighbor] = new_frontier end end end @@ -866,12 +866,12 @@ class Heuristic # Get the next cell to explore from new_frontier = heuristic.frontier.shift # For each of its neighbors - adjacent_neighbors(new_frontier).each do |neighbor| + adjacent_neighbors(new_frontier).each do |neighbor| # That have not been visited and are not walls - unless heuristic.came_from.has_key?(neighbor) || grid.walls.has_key?(neighbor) + unless heuristic.came_from.has_key?(neighbor) || grid.walls.has_key?(neighbor) # Add them to the frontier and mark them as visited - heuristic.frontier << neighbor - heuristic.came_from[neighbor] = new_frontier + heuristic.frontier << neighbor + heuristic.came_from[neighbor] = new_frontier end end end @@ -915,16 +915,16 @@ class Heuristic # 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 = [] + 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 + 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 - neighbors + neighbors end # Finds the vertical and horizontal distance of a cell from the star @@ -973,7 +973,7 @@ class Heuristic def wall_color [134, 134, 120] # Camo Green end - + def visited_color [204, 191, 179] # Dark Brown end @@ -981,7 +981,7 @@ class Heuristic def frontier_color [103, 136, 204] # Blue end - + def path_color [231, 230, 228] # Pastel White end |
