- Joined
- Apr 16, 2022

- Messages
- 1

- Reaction score
- 0

Input: E - the environment

Input: S - start location of the robot in the environment

Let O be a list of nodes (positions with distances) the robot can reach. Initially contains S. This is

also called the open-list.

Let C be a temporary list of nodes. Initially empty. This is also called the closed-list. Define a variable p and point it to the start node in O

repeat

for Each node q that the robot can reach from pa do

Set the distanceToS of q to be one more that that of p

Add q to O if and only if there is no item in O with the same co-ordinate as q.

end

Add p to closed-list C.

Select a node p from the open-list, O, that is NOT in the closed-list C. until no such position p can be found

awhen picking q, you should do that in the following order relative to p: up, right, down, left

And here is my implementation of the algorithm below. Dismiss the functions unknown to you like getRow() or containsNode(), these are used appropriately in my function.

NodeList* PathPlanner::getReachableNodes(){

// create list to be returned

NodeList* openList = new NodeList();

// add initial position to the

openList->addBack(getInitialPosition(env));

// make p the start node for now

NodePtr p = openList->get(0);

// temporary list

NodeList* closedList = new NodeList();

int m = 0;

while(openList->get(m) != closedList->get(m)){

for(int i=0; i<=3; ++i){

if (i==0) { // search up

int upRow = p->getRow()-1;

int upCol = p->getCol();

if(this->env[upRow][upCol] == SYMBOL_EMPTY || this->env[upRow] [upCol] == SYMBOL_GOAL){

NodePtr reachableNode = new Node(upRow, upCol, distanceToS+1);

if (openList->containsNode(reachableNode) == 0){

openList->addBack(reachableNode);

p = reachableNode;

}

}

}

if (i==1) { // search right

int rightRow = p->getRow();

int rightCol = p->getCol()+1;

if(this->env[rightRow][rightCol] == SYMBOL_EMPTY || this->env[rightRow][rightCol] == SYMBOL_GOAL){

NodePtr reachableNode = new Node(rightRow, rightCol, distanceToS+1);

if (openList->containsNode(reachableNode) == 0){

openList->addBack(reachableNode);

p = reachableNode;

}

}

}

if (i==2) { // search down

int downRow = p->getRow()-1;

int downCol = p->getCol();

if(this->env[downRow][downCol] == SYMBOL_EMPTY || this->env[downRow][downCol] == SYMBOL_GOAL){

NodePtr reachableNode = new Node(downRow, downCol, distanceToS+1);

if (openList->containsNode(reachableNode) == 0){

openList->addBack(reachableNode);

p = reachableNode;

}

}

}

if (i==3) { // search down

int leftRow = p->getRow();

int leftCol = p->getCol()-1;

if(this->env[leftRow][leftCol] == SYMBOL_EMPTY || this->env[leftRow][leftCol] == SYMBOL_GOAL){

NodePtr reachableNode = new Node(leftRow, leftCol, distanceToS+1);

if (openList->containsNode(reachableNode) == 0){

openList->addBack(reachableNode);

p = reachableNode;

}

}

}

}

}

if(!closedList->containsNode(p)){

closedList->addBack(p);

}

m++;

return openList;

}