Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

# Thread: BFS Travel not in the sequence

1. ## BFS Travel not in the sequence

Dear All,

I am coding for my AI Assignment.

The assignment description as follow:-

Perform a BFS on the 10 x 10 elevation grid which X equal to obstacle. It suppose to travel from Start to End and mark * on the traveled path.

Map files as

10 10 <-- Grid Size 10 x 10
1 1 <-- Start Location
10 10 <-- End Location
1 1 1 1 1 1 4 7 8 X
1 1 1 1 1 1 1 5 8 8
1 1 1 1 1 1 1 4 6 7
1 1 1 1 1 X 1 1 3 6
1 1 1 1 1 X 1 1 1 1
1 1 1 1 1 1 1 1 1 1
6 1 1 1 1 X 1 1 1 1
7 7 1 X X X 1 1 1 1
8 8 1 1 1 1 1 1 1 1
X 8 7 1 1 1 1 1 1 1

The position for 3 on the grid is (4,9).

Below is how my algorithim and it travel

(2,1)(1,2)(1,1)(3,1)(2,2)(2,2)(1,1)(1,3)(2,1)(4,1) (3,2)(1,2)(3,2)(2,1)(2,3)(2,3)
(1,2)(1,4)(3,1)(5,1)(4,2)(2,2)(4,2)(3,1)(3,3)(1,3) (3,3)(2,2)(2,4)(2,4)(1,3)(1,5)
(4,1)(6,1)(5,2)(3,2)(5,2)(4,1)(4,3)(2,3)(4,3)(3,2) (3,4)(1,4)(3,4)(2,3)(2,5)(2,5)
(1,4)(1,6)(5,1)(7,1)(6,2)(4,2)(6,2)(5,1)(5,3)(3,3) (5,3)(4,2)(4,4)(2,4)(4,4)(3,3)
(3,5)(1,5)(3,5)(2,4)(2,6)(2,6)(1,5)(1,7)(6,1)(8,1) (7,2)(5,2)(7,2)(6,1)(6,3)(4,3)
(6,3)(5,2)(5,4)(3,4)(5,4)(4,3)(4,5)(2,5)(4,5)(3,4) (3,6)(1,6)(3,6)(2,5)(2,7)(2,7)
(1,6)(1,8)(7,1)(9,1)(8,2)(6,2)(8,2)(7,1)(7,3)(5,3) (7,3)(6,2)(6,4)(4,4)(6,4)(5,3)
(5,5)(3,5)(5,5)(4,4)(2,6)(3,5)(3,7)(1,7)(3,7)(2,6) (2,8)(2,8)(1,7)(1,9)(8,1)(9,2)
(7,2)(9,2)(8,1)(8,3)(6,3)(8,3)(7,2)(7,4)(5,4)(7,4) (6,3)(6,5)(4,5)(6,5)(5,4)(2,7)
(4,7)(3,6)(3,8)(1,8)(3,8)(2,7)(2,9)(2,9)(1,8)(8,2) <--- From this output, it just simple jump around without follow my pseudocode.

My code:-

pathfinder.java
```import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

public class pathfinder {

public static int ROW;
public static int COL;
public static int startX;
public static int startY;
public static int goalX;
public static int goalY;
public static ArrayList<String> list;

public static void main(String args[]) throws IOException {

String map = "";
String search = "";
String heauristic = "";

for(int i=0; i<args.length; i++) {
if(args[i].equals("-m")) {
map = (String)args[i+1];
}
if(args[i].equals("-s")){
search = (String)args[i+1];
System.out.println("-s detected, using specific algorithim");
bfs aa = new bfs();
}
if(args[i].equals("-h")) {
heauristic = (String)args[i+1];
System.out.println("-h detect	ed, selecting heauristic");
}
}
}

public static void readMap(String fileName) throws IOException{
String line = "";
list = new ArrayList<String>();

Scanner scanner = new Scanner(line);
while(scanner.hasNext()){
}
}

ROW = Integer.parseInt(list.get(0))+1;
COL = Integer.parseInt(list.get(1))+1;
startX = Integer.parseInt(list.get(2));
startY = Integer.parseInt(list.get(3));
goalX = Integer.parseInt(list.get(4));
goalY = Integer.parseInt(list.get(5));
}

public static Node[][] returnSetofNodes(){

//Convert list into 2 dimensional array
Node[][] nodes = new Node[ROW][COL];
int counter = 6;
for (int i=1;i<ROW;i++){
for(int j=1;j<COL;j++){
Node tempNode = new Node(list.get(counter), false, i, j);
nodes[i][j] = tempNode;
counter++;
}
}
return nodes;
}
}```

Node.java
```import java.util.ArrayList;

public class Node {
//Define variable to hold temporary value for Node Object
String label;
int x,y;
Node node;
boolean isGoal;
boolean visited = false;
Node rootNode, parentNode;

int counter = 0;

public Node() {

}
//Creating Node object with Label, Visited flag, x-coordinate and y-coordinate
public Node(String temp, boolean check, int x, int y) {
this.label = temp;
this.visited = check;
this.x = x;
this.y = y;
//Count total of nodes
counter++;
/*
System.out.println("Adding node: " + label + " at position " + "(" + x + "," + y + ")");
nodeLabel[counter] = label;
xPos[counter] = x;
yPos[counter] = y;
counter++;
*/
}

public String getNodeLabel() {
//Check if node is not empty
return label;
}

public void setNodeLabel() {
//Check if node is not empty
this.label = "*";
}

public int getxPos() {
return x;
}

public int getyPos() {
return y;
}

public int getnumNodes(){
return counter;
}

public boolean getState(){
return visited;
}

public void setRootNode(Node node){
this.rootNode = node;
}

public void setVisitedFlag(Boolean check) {
visited = check;
}

public boolean getVisitedFlag() {
return visited;
}

public void setParentNode(Node node){
this.parentNode = node;
}

public Node getParentNode(){
return parentNode;
}
}```

bfs.java

```import java.util.ArrayList;

public class bfs {
//Copy the set of nodes from pathfinder class
Node[][] nodes;
Node root, goal, up, down, left, right, current;
ArrayList<Node> solution;
int counter=0;

public bfs(){
nodes = pathfinder.returnSetofNodes();
root = nodes[pathfinder.startX][pathfinder.startY];
goal = nodes[pathfinder.goalX][pathfinder.goalY];
travel(root);
printPath();

}

public void travel(Node node){
checkConnectedNode(node);
if(!frontier.isEmpty()) {
current = frontier.getFirst();
frontier.removeFirst();
if(current.equals(goal)) {
goal.setVisitedFlag(true);
goal.setNodeLabel();
for(int i=0;i<explored.size();i++){
Node n = explored.getFirst();
explored.removeFirst();
System.out.print("(" + n.getxPos() + "," + n.getyPos() + ")");
}
} else {
travel(current);
counter++;
}
}
}

//Look for child on 4-connector
public void checkConnectedNode(Node node){
//Set the current node as visited
//System.out.println(node.getxPos() + "," + node.getyPos());
getUpNode(node);
getDownNode(node);
getLeftNode(node);
getRightNode(node);
node.setVisitedFlag(true);
}

public void getUpNode(Node node){
try{
if(nodes[node.getxPos()-1][node.getyPos()] != null && node.getVisitedFlag() == false
&& !nodes[node.getxPos()-1][node.getyPos()].getNodeLabel().equals("X")){
up = nodes[node.getxPos()-1][node.getyPos()];
up.setParentNode(node);
System.out.println("Checking for Node:" + node.getxPos() + "," + node.getyPos()
+ "- UP: " + up.getxPos() + "," + up.getyPos() + " - PARENT: "
+ up.getParentNode().getxPos() + "," +  up.getParentNode().getyPos() );
}
} catch (ArrayIndexOutOfBoundsException e){
return;
}

}

public void getDownNode(Node node){
try{
if(nodes[node.getxPos()+1][node.getyPos()] != null && node.getVisitedFlag() == false
&& !nodes[node.getxPos()+1][node.getyPos()].getNodeLabel().equals("X")){
down = nodes[node.getxPos()+1][node.getyPos()];
down.setParentNode(node);
System.out.println("Checking for Node:" + node.getxPos() + "," + node.getyPos()
+ "- DOWN: " + down.getxPos() + "," + down.getyPos() + " - PARENT: "
+ down.getParentNode().getxPos() + "," +  down.getParentNode().getyPos() );
}
} catch (ArrayIndexOutOfBoundsException e){
return;
}
}

public void getLeftNode(Node node){
try{
if(nodes[node.getxPos()][node.getyPos()-1] != null && node.getVisitedFlag() == false
&& !nodes[node.getxPos()][node.getyPos()-1].getNodeLabel().equals("X")){
left = nodes[node.getxPos()][node.getyPos()-1];
left.setParentNode(node);
System.out.println("Checking for Node:" + node.getxPos() + "," + node.getyPos()
+ "- LEFT: " + left.getxPos() + "," + left.getyPos() + " - PARENT: "
+ left.getParentNode().getxPos() + "," +  left.getParentNode().getyPos() );
}
} catch (ArrayIndexOutOfBoundsException e){
return;
}
}

public void getRightNode(Node node){
try{
if(nodes[node.getxPos()][node.getyPos()+1] != null && node.getVisitedFlag() == false
&& !nodes[node.getxPos()][node.getyPos()+1].getNodeLabel().equals("X")){
right = nodes[node.getxPos()][node.getyPos()+1];
right.setParentNode(node);
System.out.println("Checking for Node:" + node.getxPos() + "," + node.getyPos()
+ "- RIGHT: " + right.getxPos() + "," + right.getyPos() + " - PARENT: "
+ right.getParentNode().getxPos() + "," +  right.getParentNode().getyPos() );
}
} catch (ArrayIndexOutOfBoundsException e){
return;
}
}

public void printPath(){
for(int i=1;i<nodes.length;i++){
for(int j=1;j<nodes.length;j++){
System.out.print(nodes[i][j].getNodeLabel() + "-" + nodes[i][j].getVisitedFlag() + "|");
}
System.out.println("");
}
}

}```

What wrong with my code?

2. ## Re: BFS Travel not in the sequence

Do you know how to debug code?
If you don't have an interactive debugger, then use println statements to show the program's logic flow and the value of variables as they change. If you understand the program's logic and how it is supposed to work, the print out should show you where the code is going wrong and where you need to fix it.

3. ## Re: BFS Travel not in the sequence

Ya, i understand how the program logic works. I dont have any debugger.

Btw, the program suppose to travel by sequence Up, Down, Left and Right.

4. ## Re: BFS Travel not in the sequence

the program suppose to travel by sequence Up, Down, Left and Right.
Does it do that?

For easier debugging have you tried working with a much smaller map so there isn't so much printed out and it is easier to see if the program is working properly?

5. ## Re: BFS Travel not in the sequence

Originally Posted by Norm
Does it do that?

For easier debugging have you tried working with a much smaller map so there isn't so much printed out and it is easier to see if the program is working properly?

Yup, it should do that. Not sure which of my code did the wrong part ..

Ya. i am currently test on smaller map. Thanks for the suggestion thought...