Solution for Milestone $3$:

$3\mathrm{.}3$ Milestone $3$: Finding the path

For Milestone $3,$ you will implement the getPath method of class PathSolver and printEnvStdout method in

main.cpp$.$

$3\mathrm{.}3\mathrm{.}1$ Implementing getPath method

This method finds a path from the robot's starting position to the specified goal position using the NodeList

stored in field nodesExplored $($generated in your Milestone $2)-$ The backtracking algorithm. Then the path

found should be returned as a deep copy. The path should contain an ordered sequence of Node objects including

the starting position and the given goal position. You may assume that the goal co$-$ordinate can be reached

from the starting position.

The backtracking algorithm is not given to you as a pseudo code. However, the following hint is given to help

you formulate a pseudo$-$code.

Hint: "Start from the goal node in the list nodesExplored. This would be your final element of the path.

Then search for the the four neighbours of the goal node in nodesExplored. If there is a neighbour that has

distance$\_$traveled one less than the goal node. Then that should be the node in the path before the goal node.

Repeat this backtracking process for each node you add to the path until you reach the start node."

Think carefully the path that you return must be from start to finish, not finish to start.

Be aware that the returned path is a deep copy of the path, so you need to return a new NodeList object. The next step is showing the path the robot should take in navigating from where it started until it reached the

goal. You should implement this in printEnvStdout method in main.cpp$.$ For example, using the environment

from the Introduction section, the robot's path is below:

When showing the output of the path, it must show the direction in needs to be in order to get to the next

position. To represent the robot's direction, we use the $4$ symbols shown below:

When printing the environment, you might find it easier to first update the environment with navigation path,

and then print out the whole environment.