I need solution for Milestone $2$

$3\mathrm{.}2$ Milestone $2$: Forward Search

In this milestone, you will implement a forward search algorithm that starts from the "start" position and explore

the environment is a systematic way until it reaches the "goal" position. The pseudo$-$code for the algorithm you

need to implement is provided below:

$3\mathrm{.}2\mathrm{.}1$ Forward Search Algorithm

In this algorithm, a position in the environment that the robot can reach is denoted by a node and each node

will contain the $($col$,$row$)$ co$-$ordinate and distance$\_$travelled $($the distance that the algorithm took to reach

that position from the robot's starting position$).$

Pseudocode for the forward Search algorithm $3\mathrm{.}2\mathrm{.}2$ Estimated distance

For the above algorithm we need to estimate the distance from a given node to the goal node. It is not possible

to know the exact distance from a given node to the goal before solving the path planning problem. However

we can come up with an approximation. In this implementation we use the following approximation as the

estimated distance from a given node, $p,$ to the goal node $G.$

Estimated distance $=distanc{e}_t$ravelled $of$ node $p+$ Manhattan distance from $ptoG$

The Manhattan distance from node $p$ with coordinates $($colp$,$ row $)$ to node $G$ with coordinates $($col $l_G,$ row $w_G)$ is

computed as:

$Manhatta{n}_d$istance $=|co{l}_p-$ col ${?}_{(}()G)|+|$ row ${?}_{(}()p)-$ row ${?}_{(}()G)|$

here $x|$ is the absolute value of $x.$ The Manhattan distance represent the shortest distance from a node to goal

if there are no obstacles.

$3\mathrm{.}2\mathrm{.}3$ Implementation details

It is important to have a good design for our programs and use suitable data structures and classes. In

Assignment $1,$ you will implement our design ${?}^1.$ You will implement $3$ classes:

Node class $-$ to represent a position $($col$,$ row, distance$\_$travelled$)$ of the robot.

NodeList class $-$ provides a method for storing a list of node objects as used in pseudo$-$code above.

PathSolver class $-$ that executes the forward search and backtracking algorithms.

The main file that uses these classes, and does any reading$/$writing to standard input$/$output$.$

You are given these classes in the starter code. You may add any of your own code, but you must not modify

the definitions of the provided class methods and fields.

$3\mathrm{.}2\mathrm{.}4$ Node Class

The Node class represents a position of the robot. It is a tuple $($col$,$row,distance$\_$travelled$),$ which is the $x-$

y location of the robot, and the distance that the algorithm took to reach that position from the robot's

starting position. It contains getters for this information and setter for distance$\_$travelled.

${?}^1$ This won't be the case for Assignment $2,$ where you will have to make these decisions for yourself. $3\mathrm{.}2\mathrm{.}5$ NodeList Class

The NodeList class provides a method for storing a list of Node objects. It stores an array of Node objects.

Since it's an array we also need to track the number of position objects in the NodeList.

You must implement the NodeList class using an array.

The constant NODE$\_$LIST$\_$ARRAY$\_$MAX$\_$SIZE is the maximum number of objects that can be in a NodeList. This

constant is given in the Types.h header file. The NodeLsit class has the following methods:

These methods let you add positions to the NodeList, and get a pointer to an existing position. Be aware, that

the NodeList class has full control over all position objects that are stored in the array. Thus, if position objects

are removed from the array you must remember to "delete" the objects$\mathrm{.}3\mathrm{.}2\mathrm{.}6$ PathSolver Class

The PathSolver class executes the two parts $($forward search, backtracking$)$ of the path planning algorithm by

using the NodeList and Node classes. It has three main components:

forwardSearch: Execute the forward search algorithm.

getNodesExplored: returns a DEEP COPY of the explored NodeList in forward search.

getPath: Execute backtracking and Get a DEEP COPY of the path the robot should travel. To be

implemented for milestone $3.$

This uses a custom data type Env, which is given in the Types.h$.$ It is a $2$D array of characters that represents

a environment using the format in Section $2.$ It is a fixed size, because we assume the size of the environment

is known.

It is very important to understand the Env type. It is defined as a $2$ D array. If you recall from lectures$/$labs$,$ a