A valid path starts at the start point, ends at the end point
(the hummus!), and each step you take must be to a vertically or
horizontally adjacent space that is not a wall. In other words,
take a single step up, down, left, or right; no diagonals and no walls!
As long as your path is valid you’ll find the hummus,
but we challenge you to find it in the shortest path!
Requirements
-
Submit a Python file with a function named “pathfinder”
-
Function Parameters:
- board: A graph representing a 20x20 grid. Details below.
- startNode: The graph node to start at
- endNode: The graph node to end at
-
Return: A single List with the following 2 items in the following order
-
List of coordinates in the order visited in your search, strings in the format ‘x,y’
-
List of coordinates in your path including start and end, strings in the format ‘x,y’
Tips for using the board and its nodes
Everytime you move along your path, you will interact with a new node object.
These should be the only details you need.
Everything else about your algorithm is up to you!
-
Get the string value ‘x,y’ of the coordinate with
your_current_node.id
-
Get a list of the neighbors (vertically and horizontally adjacent
that are not walls) of a node with
board.neighbors(your_current_node.id)
-
Hint: Once you have found the hummus, you’ll want to trace your
path back to the start. Each time you are about to visit a new
neighbor node, set
new_neighbor_node.prevNode to your current
node (the actual object, not just the string id).
Good Luck!