Pathfinding error help

[Panphobia]

this is what i hate, I solve one problem just to be greeted by another, NOW it outputs -1 for shortest path, It is skipping to the end of BFS, and then returning 0 where i subtract and output -1, hmmmmm trying to think on why this is

[mirhagk]

Does your IDE support stepping through code? You should step through the BFS with the compiler and see exactly what each variable is at each point in time.

[Panphobia]

I use netbeans 7.0.1, just because of class, i would be using eclipse but eh, and by stepping through the BFS you mean breaking at certain points?

[mirhagk]

Yes, and then view what each variable around you is, and step through (set a breakpoint then do step over to go through line by line, once it reaches that breakpoint).

[Panphobia]

Using your method of using the breakpoints, I actually found that it never reaches this in the code

code:

if (maze[x][y] == goal) {                 System.out.println(goal+wall+array[2]);                 return array[2] + 1;             }

which is probably why it keeps outputting -1, because it skips the loop and returns 0 then i subtract 1 from it, now i have to check why the maze is never equal to the goal

[Panphobia]

Ok I think now I fixed the problem with -1, but, when fixed(all i did was change x>=col to x>col and same with y), it goes into an infinite loop after the first value is outputted, I am going to try to debug, if you guys know the problem, could you point me in the direction or show me, that would be nice thank

code:

package bfsv2; import java.util.*; import java.io.*; public class BFSV2 {     static int rows, col=10;     public static void main(String[] args) throws FileNotFoundException {         Scanner s = new Scanner(new File("C:\\Users\\DANIEL\\Desktop\\Java\\BFSV2\\src\\bfsv2\\DATA4.txt"));         while (s.hasNext()) {                         List<String> text = new ArrayList<String>();             char[][] maze;             String line = "";             while (!line.contains("x")) {                 line = s.nextLine();                 // if the line contains 'x' then stop reading                 // otherwise, add the line to the list                 if (!line.contains("x")) {                     text.add(line);                 }             } // Convert to 2D array             int rows = text.size();             maze = new char[col][rows];             String texts;             for (int y = 0; y < rows; y++) {                 texts = text.get(y);                 for (int x = 0; x < col; x++) {                     maze[x][y] = texts.charAt(x);                 }             }             int x=0,y=0;             for (int z = 0; z < rows; z++) {                 for (int a = 0; a < col; a++) {                     if (maze[a][z] == 'S') {                         //System.out.println(a+" "+z);                          x = a;                         y = z;                     }                 }             }             System.out.println((bfs(maze, y, x, ' ', 'E') - 1));         }     }     public static int bfs(char[][] maze, int yStart, int xStart, char wall, char goal) {         Queue<int[]> queue = new LinkedList<int[]>();         //System.out.println(yStart+" "+xStart);         int[] start = {yStart, xStart, 0};         queue.add(start);         while (queue.peek() != null) {             int[] array = queue.remove();             int x = array[0];             int y = array[1];             if (x < 0 || x > col || y < 0 || y > rows) {                 continue;             }                         if (maze[x][y] == wall) {                 continue;             }             if (maze[x][y] == goal) {                 //System.out.println(goal+wall+array[2]);                 return array[2] + 1;             }             //int[][] newPoints = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};             int[][] newPoints = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}, {0, -1}, {0, 1}, {1, 0}, {-1, 0}};             for (int i = 0; i < 8; i++) {                 int[] temp = {x + newPoints[i][0], y + newPoints[i][1], array[2] + 1};                 queue.add(temp);             }         }         return 0;     } }

[Panphobia]

I put breakpoints on every line and still it wont work, I think I know around where it goes wrong but I do not know why, like once it gets to the for loop with making it go left right up down whatever, it never progresses past the first line, it always goes 0,0...8,0...0,0 etc but never actually goes to the end, but maybe it does but it takes too long, anyone have suggestions on how to fix?

[jr5000pwp]

Have you checked what the value of rows in

Java:

static int rows, col = 10;

is?
You have 2 variables named the same thing in your code, both in different scopes. Your rows in the outer scope is never initialized and will always have the default value of 0, so you either need to set it in the declaration, or set it later in your code.

If your rows is set to 0 what happens at this if statement?

Java:

if (x < 0 || x > col || y < 0 || y > rows) {      continue; }

That line will make your code continue whenever the y is not equal to 0, which is a problem for any maze that isn't one tall, also, I think it should be >=, which you had earlier.

Also, to fix the rows issue, you should be able to change

Java:

// Convert to 2D array int rows = text.size();

to

Java:

// Convert to 2D array rows = text.size();

or alternatively set it the same way you do with col by changing

Java:

static int rows, col = 10;

to

Java:

static int rows = 10; static int col = 10;

[mirhagk]

If you stepped through you'd find it checks the same node twice, which is not correct. You need to make sure it doesn't do that, an easy way would be to just make that part of the maze a wall so that when it checks again it will be a wall.

[Panphobia]

Ok I will do that

[Panphobia]

Ok mah I did exactly what you said, for another program and it worked like a charm in the 'executing' aspect, but i think there was a loss of precision lol, here is the past program which has the same loss in precision,

code:

package bfsv2; import java.util.*; import java.io.*; public class BFSV2 {     static int rows, col = 10;     public static void main(String[] args) throws FileNotFoundException {         Scanner s = new Scanner(new File("C:\\Users\\DANIEL\\Desktop\\Java\\BFSV2\\src\\bfsv2\\DATA4.txt"));         while (s.hasNext()) {             List<String> text = new ArrayList<String>();             char[][] maze;             String line = "";             while (!line.contains("x")) {                 line = s.nextLine();                 // if the line contains 'x' then stop reading                 // otherwise, add the line to the list                 if (!line.contains("x")) {                     text.add(line);                 }             } // Convert to 2D array             rows = text.size();             maze = new char[col][rows];             String texts;             for (int y = 0; y < rows; y++) {                 texts = text.get(y);                 for (int x = 0; x < col; x++) {                     maze[x][y] = texts.charAt(x);                 }             }             int x = 0, y = 0;             for (int z = 0; z < rows; z++) {                 for (int a = 0; a < col; a++) {                     if (maze[a][z] == 'S') {                         //System.out.println(a+" "+z);                         x = a;                         y = z;                     }                 }             }             System.out.println((bfs(maze, y, x, ' ', 'E') - 1));         }     }     public static int bfs(char[][] maze, int yStart, int xStart, char wall, char goal) {         Queue<int[]> queue = new LinkedList<int[]>();         //System.out.println(yStart+" "+xStart);         int[] start = {yStart, xStart, 0};         queue.add(start);         while (queue.peek() != null) {             int[] array = queue.remove();             int x = array[0];             int y = array[1];             if (x < 0 || x >= col || y < 0 || y >= rows) {                 continue;             }             if (maze[x][y] == wall) {                 continue;             }                         if (maze[x][y] == goal) {                 //System.out.println(goal+wall+array[2]);                 return array[2] + 1;             }             maze[x][y]=wall;             //int[][] newPoints = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};             int[][] newPoints = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}, {0, -1}, {0, 1}, {1, 0}, {-1, 0}};             for (int i = 0; i < 8; i++) {                 int[] temp = {x + newPoints[i][0], y + newPoints[i][1], array[2] + 1};                 queue.add(temp);             }         }         return 0;     } }

[Panphobia]

*sigh*, trying everything, yes it outputs, but i dont think it outputs the shortest path now lol

[Panphobia]

I've been debugging this whole day with almost no success

[mirhagk]

is moving diagonal the same cost as moving up-down-left-right? If not you'll need to alter the cost for moving diagonal.

Other than that, is the maze being constructed correctly? Output it and see.

Try having the program output the path and verify it's the shortest path yourself.

[Panphobia]

well it outputs the grid correctly, the cost of moving diagonal is 1 is it not, and i outputting the program showing the path it chose, and it isnt it, this is depressing