# BFS Travel not in the sequence

• February 8th, 2012, 11:34 AM
keat84
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
Code Java:

```import java.io.BufferedReader; import java.io.FileReader; 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]; System.out.prinatln("-m detected, loading map from " + map + "\n"); readMap(map); } 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>();   FileReader reader = new FileReader(fileName); BufferedReader breader = new BufferedReader(reader);   while((line = breader.readLine()) != null) { Scanner scanner = new Scanner(line); while(scanner.hasNext()){ list.add(scanner.next()); } }   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
Code 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

Code java:

```import java.util.ArrayList; import java.util.LinkedList     public class bfs { //Copy the set of nodes from pathfinder class Node[][] nodes; LinkedList<Node> frontier = new LinkedList<Node>(); LinkedList<Node> explored = new LinkedList<Node>(); 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(); explored.add(current); 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); frontier.add(up); 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); frontier.add(down); 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); frontier.add(left); 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); frontier.add(right); 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?
• February 8th, 2012, 11:42 AM
Norm
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.
• February 8th, 2012, 05:30 PM
keat84
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.
• February 8th, 2012, 05:43 PM
Norm
Re: BFS Travel not in the sequence
Quote:

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?
• February 8th, 2012, 08:19 PM
keat84
Re: BFS Travel not in the sequence
Quote:

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...