summaryrefslogtreecommitdiffhomepage
path: root/samples/13_path_finding_algorithms
diff options
context:
space:
mode:
authorAmir Rajan <[email protected]>2021-08-07 00:13:33 -0500
committerAmir Rajan <[email protected]>2021-08-07 00:13:33 -0500
commita503afe87619ff82201c0a43818fa1c3f070a548 (patch)
tree0b228a6456d17f6d0c6ea54c9ecd6a045ddbdf59 /samples/13_path_finding_algorithms
parentbea150381f495630f92f89d23d5f3445ec289b2d (diff)
downloaddragonruby-game-toolkit-contrib-a503afe87619ff82201c0a43818fa1c3f070a548.tar.gz
dragonruby-game-toolkit-contrib-a503afe87619ff82201c0a43818fa1c3f070a548.zip
Samples folder synced.
Diffstat (limited to 'samples/13_path_finding_algorithms')
-rw-r--r--samples/13_path_finding_algorithms/01_breadth_first_search/app/main.rb176
-rw-r--r--samples/13_path_finding_algorithms/02_detailed_breadth_first_search/app/main.rb2
-rw-r--r--samples/13_path_finding_algorithms/06_heuristic/app/main.rb218
-rw-r--r--samples/13_path_finding_algorithms/07_heuristic_with_walls/app/main.rb218
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