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

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;
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?

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.

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.

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?

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