Pathfinding error help

[Panphobia]

Ok so I was trying to finish this dwite question http://dwite.org/questions/ABCA_maze.html , and in my code I get an arrayoutofbounds error where I print the total path from A-B-C-A here is my code

code:

package bfs; import java.util.*; import java.io.*; public class BFS { static int x1,y1;     public static void main(String[] args) throws FileNotFoundException {         Scanner s = new Scanner(new File("C:\\Users\\DANIEL\\Desktop\\Java\\BFS\\src\\bfs\\DATA4.txt"));         while(s.hasNext()){         String[] yx=s.nextLine().split(" ");     y1 = Integer.parseInt(yx[0]);     x1 = Integer.parseInt(yx[1]);         char[][] maze = new char[y1][x1];         for (int x = 0; x < y1; x++) {             String text = s.nextLine();             for (int y = 0; y < x1; y++) {                 maze[x][y]=text.charAt(y);             }         }         char[] goal = {'A', 'B', 'C', 'A'};         int x[], y[];         x = new int[4];         y = new int[4];         for (int z = 0; z < y1; z++) {             for (int a = 0; a < x1; a++) {                 if (maze[z][a] == 'A') {                     x[0] = a;                     x[3] = a;                     y[0] = z;                     y[0] = z;                 } else if (maze[z][a] == 'B') {                     x[1] = a;                     y[1] = z;                 } else if (maze[z][a] == 'C') {                     x[2] = a;                     y[2] = z;                 }             }         }         System.out.println(bfs(maze, x[0], y[0], '#', goal[0]) + bfs(maze, x[1], y[1], '#', goal[1])                 + bfs(maze, x[2], y[2], '#', goal[2]) + bfs(maze, x[3], y[3], '#', goal[3]));     }     }     public static int bfs(char[][] maze, int x, int y, char wall, char goal) {         Queue<int[]> queue = new LinkedList<int[]>();         int[] start = {y, x, 0};         queue.add(start);         while (queue.peek() != null) {             int[] array = queue.remove();             if (array[0] - 1 > -1 && maze[array[0] - 1][array[1]] != wall) {                 if (maze[array[0] - 1][array[1]] == goal) {                     return array[2] + 1;                 } else {                     maze[array[0] - 1][array[1]] = wall;                     int[] temp = {array[0] - 1, array[1], array[2] + 1};                     queue.add(temp);                 }             }             if (array[1] - 1 > -1 && maze[array[0]][array[1] - 1] != wall) {                 if (maze[array[0]][array[1] - 1] == goal) {                     return array[2] + 1;                 } else {                     maze[array[0]][array[1] - 1] = wall;                     int[] temp = {array[0], array[1] - 1, array[2] + 1};                     queue.add(temp);                 }             }             if (array[1] + 1 < x1 && maze[array[0]][array[1] + 1] != wall) {                 if (maze[array[0]][array[1] + 1] == goal) {                     return array[2] + 1;                 } else {                     maze[array[0]][array[1] + 1] = wall;                     int[] temp = {array[0], array[1] + 1, array[2] + 1};                     queue.add(temp);                 }             }             if (array[0] + 1 < x1 && maze[array[0] + 1][array[1]] != wall) {                 if (maze[array[0] + 1][array[1]] == goal) {                     return array[2] + 1;                 } else {                     maze[array[0] + 1][array[1]] = wall;                     int[] temp = {array[0] + 1, array[1], array[2] + 1};                     queue.add(temp);                 }             }         }         return 0;     } }

[Panphobia]

Fixed the problem, but it will not give me the right path >.<, any suggestions?

code:

package bfs; import java.util.*; import java.io.*; public class BFS {     static int x1, y1;     public static void main(String[] args) throws FileNotFoundException {         Scanner s = new Scanner(new File("C:\\Users\\DANIEL\\Desktop\\Java\\BFS\\src\\bfs\\DATA4.txt"));         while (s.hasNext()) {             String[] yx = s.nextLine().split(" ");             y1 = Integer.parseInt(yx[0]);             x1 = Integer.parseInt(yx[1]);             char[][] maze = new char[y1][x1];             for (int x = 0; x < y1; x++) {                 String text = s.nextLine();                 for (int y = 0; y < x1; y++) {                     maze[x][y] = text.charAt(y);                 }             }             char[] goal = {'A', 'B', 'C'};             int x[], y[];             x = new int[3];             y = new int[3];             for (int z = 0; z < y1; z++) {                 for (int a = 0; a < x1; a++) {                     if (maze[z][a] == 'A') {                         x[0] = a;                         y[0] = z;                     }                     if (maze[z][a] == 'B') {                         x[1] = a;                         y[1] = z;                     }                     if (maze[z][a] == 'C') {                         x[2] = a;                         y[2] = z;                     }                 }             }             System.out.println(bfs(maze, y[0], x[0], '#', goal[1]) + bfs(maze, y[1], x[1], '#', goal[2])                     + bfs(maze, y[2], x[2], '#', goal[0]));         }     }     public static int bfs(char[][] maze, int y, int x, char wall, char goal) {         Queue<int[]> queue = new LinkedList<int[]>();         int[] start = {y, x, 0};         queue.add(start);         while (queue.peek() != null) {             int[] array = queue.remove();             if (array[0] - 1 > -1 && maze[array[0] - 1][array[1]] != wall) {                 if (maze[array[0] - 1][array[1]] == goal) {                     return array[2] + 1;                 } else {                     maze[array[0] - 1][array[1]] = wall;                     int[] temp = {array[0] - 1, array[1], array[2] + 1};                     queue.add(temp);                 }             }             if (array[1] - 1 > -1 && maze[array[0]][array[1] - 1] != wall) {                 if (maze[array[0]][array[1] - 1] == goal) {                     return array[2] + 1;                 } else {                     maze[array[0]][array[1] - 1] = wall;                     int[] temp = {array[0], array[1] - 1, array[2] + 1};                     queue.add(temp);                 }             }             if (array[1] + 1 < y1 && maze[array[0]][array[1] + 1] != wall) {                 if (maze[array[0]][array[1] + 1] == goal) {                     return array[2] + 1;                 } else {                     maze[array[0]][array[1] + 1] = wall;                     int[] temp = {array[0], array[1] + 1, array[2] + 1};                     queue.add(temp);                 }             }             if (array[0] + 1 < y1 && maze[array[0] + 1][array[1]] != wall) {                 if (maze[array[0] + 1][array[1]] == goal) {                     return array[2] + 1;                 } else {                     maze[array[0] + 1][array[1]] = wall;                     int[] temp = {array[0] + 1, array[1], array[2] + 1};                     queue.add(temp);                 }             }         }         return 0;     } }

[mirhagk]

I would try to help, but this contest solutions are always coded so ugly, and I can't understand what you're trying to do.

[Panphobia]

basically i am trying to add together the distances of A-B with B-C with C-A, the BFS method works with one distance sooo.

[mirhagk]

A big tip on your BFS, check the bounds and whether it's a wall at the top of checking it. You only need to have that code in one spot instead of 4, reducing potential for errors, and looking a lot cleaner.

You can and should also alias the variable sections with what values they actually are. Do

code:

x=array[0]; y=array[1];

instead of trying to remember and use array[0] you'll only have to do x. Most compilers should compile to the same code for both methods anyways (and if not, indexing the array once instead of many times probably would be faster than not using a variable).

Java:

public static int bfs(char[][] maze, int yStart, int xStart, char wall, char goal) {         Queue<int[]> queue = new LinkedList<int[]>();         int[] start = {yStart, xStart, 0};         queue.add(start);         while (queue.peek() != null) {             int[] array = queue.remove();                         int xIn = array[0];                         int y = array[1];                         if (x<0 || x>=y1 || y<0 || y>= y1)                                 continue;                         if (maze[x][y] ==wall)                                 continue;                         if (maze[x][y] == goal)                                 return array[2]+1;                         int[][] newPoints = {{-1,-1},{-1,1},{1,-1},{1,1}};                         for(int i = 0;i<4;i++)                         {                                 int[] temp = {x+newPoints[i][0],y+newPoints[i][1],array[2]+1};                                 queue.add(temp);                         }         }         return 0;     }

There, now doesn't that look a LOT cleaner. It's also faster to write, and works pretty much just as fast. Note that this solution doesn't give you the path, it gives you the length of the shortest path.

I don't have java installed on my computer, but this should be the same as you wrote, just with a much cleaner way of organizing it. At the very least this should help you discover what is wrong.

[Panphobia]

actually, it prints out two 0's and then, it doesnt stop executing but keeps on going forever until I stop the program lol

[Panphobia]

This is my input

code:

1 5 #ABC# 1 5 B.AC# 5 5 A.... .###. .B... .###. .C... 5 5 .B... ..... ..A.. ..... ...C. 10 10 ########## ##..#..### #.#...#.## #..#.#..## ##..A..### #..#C#..## #.#...#.## ##..#..### ##B####### ##########

And this is what happens when it runs.

[DemonWasp]

Your program prints two zeroes because you are printing the sum of the distances (A to B, B to C, C to D) for each problem, as calculated by your bfs() routine. I believe the root cause is that you have your x and y coordinates so thoroughly confused that you're accidentally swapping them, so that on the first iteration of the loop it decides that your start point is out-of-bounds, discards it, then falls through to the "return 0" catch-all at the end.

Try to sort out your x and y coordinates. If it helps, consider labeling them "column" or "col" (x coordinate) and "row" (y coordinate).

Your program then runs forever in the "while ( s.hasNext() )" loop, though I'm not exactly clear on why. It's probably blocking while waiting for input that will never arrive.

[Panphobia]

Ok I will try that

[Panphobia]

Hmmmm I tried switching a lot of things around, but it actually does not work.

[DemonWasp]

Have you tried switching them around in an intelligent way? Have you made sure that you are always comparing x with x and y with y, and never x with y?

The code looks mostly correct; I think the biggest problem is that x and y seem to change order frequently. You should choose one order (probably x, y) and stick to it.

If the output changed, then what happens now?

[Panphobia]

Ok in the bfs it was comparing x >= y1 and I changed it and it is still doing the same thing

code:

public static int bfs(char[][] maze, int yStart, int xStart, char wall, char goal) {         Queue<int[]> queue = new LinkedList<int[]>();         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 >= x1 || y < 0 || y >= y1) {                 continue;             }             if (maze[x][y] == wall) {                 continue;             }             if (maze[x][y] == goal) {                 return array[2] + 1;             }             int[][] newPoints = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};             for (int i = 0; i < 4; i++) {                 int[] temp = {x + newPoints[i][0], y + newPoints[i][1], array[2] + 1};                 queue.add(temp);             }         }         return 0;

[DemonWasp]

I didn't just mean within the bfs() method. You've clearly got xStart and yStart reversed in the arguments list, and there's a lot of confusion going on in your main method too. Resolve all those (always put x before y).

If the problem still occurs, include your entire program, so that I can walk you through debugging it.

[Panphobia]

isnt it supposed to go array[y][x] that is why im doing it like that, like row column type stuff, and here is my program, i did what you said and it didnt work, and the txt file is there too, just change the path

[DemonWasp]

You can choose whichever scheme you want (technically they are called "row major" if it's row/y first and "column major" if it's column/x first). The only thing is you have to use them the same way everywhere. Since you seem to be having a hard time deciding, always put X before Y.

So step one is fix your program to always always always put the X coordinate before the Y coordinate.

Step two is to output the entire maze after you finish loading it (but before you try to solve the problem). I'll even give you the output code:

code:

// Print the maze, from top row to bottom row for ( int y = 0; y < rows; ++y ) {         for ( int x = 0; x < cols; ++x ) {                 System.out.print ( maze[x][y] );         }         System.out.println(); }

The maze that gets output should be exactly equal to the one in the data file.

Once you've managed that, I can help you debug the rest.

P.S. Mirhagk accidentally made a silly mistake. He gave you a move-set that was all diagonal moves, like a bishop in chess. I assume you want adjacent moves, from one square to any square beside it (otherwise, puzzles with a single row or column are impossible). Change the "newPoints" array to this:

code:

int[][] newPoints = {{0, -1}, {0, +1}, {+1, 0}, {-1, 0}};