diff options
| author | _Tradam <[email protected]> | 2021-12-16 19:22:26 -0500 |
|---|---|---|
| committer | GitHub <[email protected]> | 2021-12-16 19:22:26 -0500 |
| commit | 5954b9beb4d4a3b4f248d72d1851195f030558a8 (patch) | |
| tree | fecd8aa840a25afdb502915b0fdb4d03b7ed339a /samples/13_path_finding_algorithms/01_breadth_first_search | |
| parent | 2f845281f133849256b57bb08fd3e9ae57600784 (diff) | |
| parent | eaa29e72939f5edf61735ccbb73c36ee89369f65 (diff) | |
| download | dragonruby-game-toolkit-contrib-5954b9beb4d4a3b4f248d72d1851195f030558a8.tar.gz dragonruby-game-toolkit-contrib-5954b9beb4d4a3b4f248d72d1851195f030558a8.zip | |
Diffstat (limited to 'samples/13_path_finding_algorithms/01_breadth_first_search')
| -rw-r--r-- | samples/13_path_finding_algorithms/01_breadth_first_search/app/main.rb | 174 | ||||
| -rw-r--r-- | samples/13_path_finding_algorithms/01_breadth_first_search/replay.txt | 203 |
2 files changed, 290 insertions, 87 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 7f98509..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 @@ -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/01_breadth_first_search/replay.txt b/samples/13_path_finding_algorithms/01_breadth_first_search/replay.txt new file mode 100644 index 0000000..62f4aca --- /dev/null +++ b/samples/13_path_finding_algorithms/01_breadth_first_search/replay.txt @@ -0,0 +1,203 @@ +replay_version 2.0 +stopped_at 213 +seed 100 +recorded_at 2021-11-20 11:17:21 -0600 +[:mouse_button_up, 1, 0, 1, 1, 4] +[:mouse_move, 780, 95, 2, 2, 11] +[:mouse_move, 781, 95, 2, 3, 12] +[:mouse_move, 782, 95, 2, 4, 13] +[:mouse_move, 783, 95, 2, 5, 14] +[:mouse_move, 771, 95, 2, 6, 32] +[:mouse_move, 752, 95, 2, 7, 32] +[:mouse_move, 718, 95, 2, 8, 34] +[:mouse_move, 652, 95, 2, 9, 34] +[:mouse_move, 549, 95, 2, 10, 35] +[:mouse_move, 462, 101, 2, 11, 36] +[:mouse_move, 425, 106, 2, 12, 37] +[:mouse_move, 405, 108, 2, 13, 38] +[:mouse_move, 406, 109, 2, 14, 39] +[:mouse_move, 412, 111, 2, 15, 40] +[:mouse_move, 429, 111, 2, 16, 41] +[:mouse_move, 450, 109, 2, 17, 42] +[:mouse_move, 460, 107, 2, 18, 42] +[:mouse_move, 460, 106, 2, 19, 43] +[:mouse_move, 460, 105, 2, 20, 45] +[:mouse_move, 460, 104, 2, 21, 46] +[:mouse_move, 456, 104, 2, 22, 47] +[:mouse_move, 469, 104, 2, 23, 49] +[:mouse_move, 489, 103, 2, 24, 50] +[:mouse_move, 512, 100, 2, 25, 51] +[:mouse_move, 536, 96, 2, 26, 52] +[:mouse_move, 565, 92, 2, 27, 52] +[:mouse_move, 587, 92, 2, 28, 53] +[:mouse_move, 597, 92, 2, 29, 54] +[:mouse_move, 599, 92, 2, 30, 55] +[:mouse_button_pressed, 1, 0, 1, 31, 59] +[:mouse_button_up, 1, 0, 1, 32, 62] +[:mouse_move, 599, 91, 2, 33, 65] +[:mouse_move, 590, 86, 2, 34, 65] +[:mouse_move, 570, 78, 2, 35, 66] +[:mouse_move, 543, 70, 2, 36, 66] +[:mouse_move, 516, 65, 2, 37, 67] +[:mouse_move, 481, 61, 2, 38, 68] +[:mouse_move, 449, 59, 2, 39, 69] +[:mouse_move, 429, 57, 2, 40, 69] +[:mouse_move, 424, 56, 2, 41, 70] +[:mouse_move, 426, 56, 2, 42, 74] +[:mouse_move, 429, 56, 2, 43, 75] +[:mouse_move, 431, 56, 2, 44, 75] +[:mouse_move, 433, 56, 2, 45, 76] +[:mouse_move, 435, 55, 2, 46, 77] +[:mouse_move, 437, 55, 2, 47, 78] +[:mouse_move, 440, 55, 2, 48, 78] +[:mouse_move, 444, 55, 2, 49, 79] +[:mouse_move, 445, 54, 2, 50, 79] +[:mouse_move, 444, 53, 2, 51, 81] +[:mouse_move, 444, 52, 2, 52, 82] +[:mouse_move, 443, 51, 2, 53, 89] +[:mouse_button_pressed, 1, 0, 1, 54, 89] +[:mouse_move, 442, 51, 2, 55, 89] +[:mouse_move, 436, 51, 2, 56, 90] +[:mouse_move, 432, 49, 2, 57, 91] +[:mouse_move, 431, 49, 2, 58, 91] +[:mouse_move, 429, 49, 2, 59, 92] +[:mouse_move, 428, 49, 2, 60, 93] +[:mouse_move, 426, 49, 2, 61, 94] +[:mouse_move, 425, 49, 2, 62, 94] +[:mouse_move, 424, 49, 2, 63, 95] +[:mouse_move, 423, 49, 2, 64, 96] +[:mouse_move, 422, 49, 2, 65, 98] +[:mouse_move, 421, 49, 2, 66, 99] +[:mouse_move, 420, 49, 2, 67, 99] +[:mouse_move, 419, 49, 2, 68, 100] +[:mouse_move, 417, 49, 2, 69, 100] +[:mouse_move, 415, 49, 2, 70, 101] +[:mouse_move, 414, 49, 2, 71, 102] +[:mouse_move, 413, 49, 2, 72, 108] +[:mouse_move, 415, 49, 2, 73, 124] +[:mouse_move, 416, 49, 2, 74, 125] +[:mouse_move, 420, 49, 2, 75, 126] +[:mouse_move, 424, 49, 2, 76, 127] +[:mouse_move, 429, 49, 2, 77, 128] +[:mouse_move, 433, 49, 2, 78, 128] +[:mouse_move, 441, 49, 2, 79, 129] +[:mouse_move, 450, 49, 2, 80, 129] +[:mouse_move, 460, 49, 2, 81, 130] +[:mouse_move, 472, 49, 2, 82, 131] +[:mouse_move, 480, 49, 2, 83, 131] +[:mouse_move, 486, 49, 2, 84, 132] +[:mouse_move, 488, 49, 2, 85, 132] +[:mouse_move, 492, 49, 2, 86, 132] +[:mouse_move, 498, 49, 2, 87, 133] +[:mouse_move, 507, 49, 2, 88, 133] +[:mouse_move, 513, 48, 2, 89, 134] +[:mouse_move, 518, 47, 2, 90, 134] +[:mouse_move, 523, 47, 2, 91, 134] +[:mouse_move, 529, 46, 2, 92, 135] +[:mouse_move, 533, 46, 2, 93, 135] +[:mouse_move, 538, 46, 2, 94, 135] +[:mouse_move, 543, 46, 2, 95, 136] +[:mouse_move, 545, 46, 2, 96, 136] +[:mouse_move, 546, 46, 2, 97, 136] +[:mouse_move, 551, 46, 2, 98, 137] +[:mouse_move, 558, 46, 2, 99, 137] +[:mouse_move, 567, 46, 2, 100, 138] +[:mouse_move, 573, 46, 2, 101, 138] +[:mouse_move, 576, 45, 2, 102, 138] +[:mouse_move, 579, 45, 2, 103, 138] +[:mouse_move, 581, 45, 2, 104, 138] +[:mouse_move, 584, 45, 2, 105, 139] +[:mouse_move, 590, 45, 2, 106, 139] +[:mouse_move, 597, 45, 2, 107, 139] +[:mouse_move, 602, 45, 2, 108, 140] +[:mouse_move, 606, 45, 2, 109, 140] +[:mouse_move, 611, 45, 2, 110, 140] +[:mouse_move, 617, 45, 2, 111, 140] +[:mouse_move, 625, 45, 2, 112, 140] +[:mouse_move, 632, 45, 2, 113, 140] +[:mouse_move, 638, 45, 2, 114, 141] +[:mouse_move, 643, 45, 2, 115, 141] +[:mouse_move, 644, 44, 2, 116, 141] +[:mouse_move, 646, 44, 2, 117, 141] +[:mouse_move, 647, 44, 2, 118, 142] +[:mouse_move, 650, 44, 2, 119, 142] +[:mouse_move, 653, 44, 2, 120, 142] +[:mouse_move, 656, 44, 2, 121, 142] +[:mouse_move, 658, 43, 2, 122, 142] +[:mouse_move, 659, 43, 2, 123, 143] +[:mouse_move, 663, 43, 2, 124, 143] +[:mouse_move, 665, 43, 2, 125, 143] +[:mouse_move, 667, 43, 2, 126, 143] +[:mouse_move, 669, 43, 2, 127, 143] +[:mouse_move, 670, 43, 2, 128, 143] +[:mouse_move, 671, 43, 2, 129, 143] +[:mouse_move, 672, 43, 2, 130, 144] +[:mouse_move, 674, 43, 2, 131, 144] +[:mouse_move, 677, 43, 2, 132, 144] +[:mouse_move, 679, 43, 2, 133, 144] +[:mouse_move, 680, 43, 2, 134, 144] +[:mouse_move, 681, 43, 2, 135, 144] +[:mouse_move, 683, 43, 2, 136, 145] +[:mouse_move, 684, 43, 2, 137, 145] +[:mouse_move, 685, 43, 2, 138, 145] +[:mouse_move, 686, 43, 2, 139, 145] +[:mouse_move, 687, 43, 2, 140, 145] +[:mouse_move, 688, 43, 2, 141, 146] +[:mouse_button_up, 1, 0, 1, 142, 150] +[:mouse_move, 688, 44, 2, 143, 150] +[:mouse_move, 685, 45, 2, 144, 150] +[:mouse_move, 674, 47, 2, 145, 150] +[:mouse_move, 657, 52, 2, 146, 150] +[:mouse_move, 621, 57, 2, 147, 151] +[:mouse_move, 593, 62, 2, 148, 151] +[:mouse_move, 568, 65, 2, 149, 151] +[:mouse_move, 550, 68, 2, 150, 151] +[:mouse_move, 542, 69, 2, 151, 152] +[:mouse_move, 539, 69, 2, 152, 152] +[:mouse_move, 536, 70, 2, 153, 152] +[:mouse_move, 534, 70, 2, 154, 153] +[:mouse_move, 531, 72, 2, 155, 153] +[:mouse_move, 528, 73, 2, 156, 153] +[:mouse_move, 522, 75, 2, 157, 154] +[:mouse_move, 515, 80, 2, 158, 154] +[:mouse_move, 514, 81, 2, 159, 154] +[:mouse_move, 513, 81, 2, 160, 154] +[:mouse_move, 509, 84, 2, 161, 156] +[:mouse_move, 502, 88, 2, 162, 156] +[:mouse_move, 491, 93, 2, 163, 156] +[:mouse_move, 487, 97, 2, 164, 156] +[:mouse_move, 486, 97, 2, 165, 156] +[:mouse_move, 487, 96, 2, 166, 157] +[:mouse_button_pressed, 1, 0, 1, 167, 159] +[:mouse_button_up, 1, 0, 1, 168, 160] +[:mouse_button_pressed, 1, 0, 1, 169, 161] +[:mouse_move, 488, 96, 2, 170, 161] +[:mouse_button_up, 1, 0, 1, 171, 161] +[:mouse_move, 488, 97, 2, 172, 166] +[:mouse_move, 487, 97, 2, 173, 166] +[:mouse_move, 486, 97, 2, 174, 167] +[:mouse_move, 485, 97, 2, 175, 167] +[:mouse_move, 484, 97, 2, 176, 168] +[:mouse_button_pressed, 1, 0, 1, 177, 172] +[:mouse_button_up, 1, 0, 1, 178, 173] +[:mouse_move, 485, 97, 2, 179, 185] +[:key_down_raw, 96, 0, 2, 180, 191] +[:mouse_move, 486, 96, 2, 181, 192] +[:mouse_move, 488, 96, 2, 182, 192] +[:mouse_move, 495, 94, 2, 183, 192] +[:key_up_raw, 96, 0, 2, 184, 192] +[:mouse_move, 503, 93, 2, 185, 193] +[:mouse_move, 514, 92, 2, 186, 193] +[:mouse_move, 544, 92, 2, 187, 193] +[:mouse_move, 573, 92, 2, 188, 194] +[:mouse_move, 607, 92, 2, 189, 194] +[:mouse_move, 641, 89, 2, 190, 194] +[:mouse_move, 674, 89, 2, 191, 194] +[:mouse_move, 705, 89, 2, 192, 194] +[:mouse_move, 735, 89, 2, 193, 195] +[:mouse_move, 759, 89, 2, 194, 195] +[:mouse_move, 776, 89, 2, 195, 195] +[:mouse_move, 784, 89, 2, 196, 195] +[:mouse_move, 786, 89, 2, 197, 196] +[:mouse_move, 786, 90, 2, 198, 204] +[:key_down_raw, 13, 0, 2, 199, 213] |
