Pathfinding error help

[evildaddy911]

The cost of diagonal movement should be ~1.41* times the cost of an adjacent movement (up/down/left/right)
1.41 comes from Pythagorean theorem:
sqrt (right ** 2 + up **2)
sqrt (1 ** 2 + 1 ** 2)
sqrt (2)
~1.41

[Panphobia]

I am not so sure, because we will treat it as an integer in the end and also, I am treating each move on the grid so, up/down/left/right/diagonal, as 1 move, so cost of 1 not 1.41

[Panphobia]

HOLY, I used a dfs i think, and it had no bugs, coded it in literally 5 minutes, if you guys could suggest me if i should use bfs or dfs for dwite, here is the code that works

code:

package bfsv2; import java.util.*; import java.io.*; public class BFSV2 { //4 //2 //4 //5 //10     static int rows, col = 10;     static int dist = 0;     static int numSteps[][];     static int yEnd, xEnd;     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];             numSteps = new int[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;                     }                 }             } //            for(int i = 0;i<rows;i++){ //                for(int a = 0; a <col;a++){ //                    System.out.print(maze[a][i]); //                } //                System.out.println(); //            } //            System.out.println((bfs(maze, y, x, ' ', 'E') - 1));             for (int q = 0; q < rows; q++) {                 for (int u = 0; u < col; u++) {                     numSteps[u][q] = 9999;                 }             }             find(x, y, maze, 0, 'E');             System.out.println(numSteps[xEnd][yEnd]);         }     }     public static void find(int x, int y, char[][] maze, int c, char target) {         if (maze[x][y] == ' ') {             return;         }         if (c < numSteps[x][y]) {             numSteps[x][y] = c;         } else {             return;         }         if (maze[x][y] == target) {             xEnd = x;             yEnd = y;         }         //System.out.println(x-1);         //System.out.println(x+1);         //System.out.println(y-1);         //System.out.println(y+1);         try{         if (x > 0 && (maze[x - 1][y] != ' ')) {             find(x - 1, y, maze, c + 1, target);         }         if (x < col && (maze[x + 1][y] != ' ')) {             find(x + 1, y, maze, c + 1, target);         }         if (y > 0 && (maze[x][y - 1] != ' ')) {             find(x, y - 1, maze, c + 1, target);         }         if (y < rows && (maze[x][y + 1] != ' ')) {             find(x, y + 1, maze, c + 1, target);         }         //         if (x > 0 && y > 0 && (maze[x - 1][y - 1] != ' ')) {             find(x - 1, y - 1, maze, c + 1, target);         }         if (x < col && y < rows && (maze[x + 1][y + 1] != ' ')) {             find(x + 1, y + 1, maze, c + 1, target);         }         if (y > 0 && x < col && (maze[x + 1][y - 1] != ' ')) {             find(x + 1, y - 1, maze, c + 1, target);         }         if (y < rows && x > 0 && (maze[x - 1][y + 1] != ' ')) {             find(x - 1, y + 1, maze, c + 1, target);         }         }catch(Exception e){          };     } //    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]; //            //System.out.println(x+" "+y); //            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 = {{0, -1}, {0, 1}, {1, 0}, {-1, 0},{-1, -1}, {-1, 1}, {1, -1}, {1, 1}}; //            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; // //    } }

[mirhagk]

You can use DFS but please, PLEASE try to keep stuff like bounds checks all in one place.... there's not a lot of harm in making one extra function call if it makes your code look cleaner.

Your also checking if it's an empty space twice.... dunno why you're doing that....

You should be able to convert your BFS into DFS by switching from using a queue to a stack. If switching to a stack solves the problem, then the queue (or how your adding and removing) is the problem. If switching to DFS doesn't work, then there's obviously a problem with how you're adding or checking items

[Panphobia]

what do you mean checking if there is an empty space twice?

[mirhagk]

Panphobia @ Sat Nov 24, 2012 7:17 pm wrote:

HOLY, I used a dfs i think, and it had no bugs, coded it in literally 5 minutes, if you guys could suggest me if i should use bfs or dfs for dwite, here is the code that works

code:

public static void find(int x, int y, char[][] maze, int c, char target) {         if (maze[x][y] == ' ') {             return;         } ........         if (x > 0 && (maze[x - 1][y] != ' ')) {             find(x - 1, y, maze, c + 1, target);         } ....

You make sure that the new part isn't a space, then the first thing you do in the function is check if it is a space, in which case you return. This is checking it twice. Just out of curiosity how much of this code do you actually understand what it's doing? This find method is implementing Djikstra's which is exactly the same as BFS when the cost for moving to each new node is the same (as in this case). Not sure why you're BFS isn't working, but essentially you've written the same algorithm twice here.

[Panphobia]

Oh man you're right, total idiot moment right there trololo, but yea I understand what is being done here, basically I add numbers to an array of integers the same size as the char maze array, that would equate to the distance from start A, now what I do not really totally understand is that with the code

code:

if (c < numSteps[x][y]) {             numSteps[x][y] = c;         } else {             return;         }

it should give you the shortest distance from that point as see this grid

code:

........ ........ ...##... A..##... ...##... ...##... ...##..B ........

outputs this

code:

3 3 3 3 4 5 6 7 2 2 2 3 4 5 6 7 1 1 2 # # 5 6 7 0 1 2 # # 6 6 7 1 1 2 # # 7 7 7 2 2 2 # # 8 8 8 3 3 3 # # 7 8 9 4 4 4 4 5 6 7 8

you see where the B is supposed to be, there is a 9 instead of an 8, i have a theory about why it is wrong, but I can't implement it, guess I do not understand the algorithm well enough

[mirhagk]

I thought you coded it in 5 minutes and it had no bugs? And this output is different from what your program is producing. This seems to be from you're other forum post, so either have 2 forum posts about 2 separate problems/programs or only have 1, and don't open a 2nd up.

[Panphobia]

It accidentley popped up in this one, and the one that i coded in less than 5 mins, was the train question, it was a different one

[jr5000pwp]

I haven't looked into it too much, but trom what I can tell, your try block is preventing you from seeing an important out of bounds error.

Java:

if (x > 0 && (maze[x - 1][y] != ' ')) {      find(x - 1, y, maze, c + 1, target); } if (x < col && (maze[x + 1][y] != ' ')) {      find(x + 1, y, maze, c + 1, target); } if (y > 0 && (maze[x][y - 1] != ' ')) {      find(x, y - 1, maze, c + 1, target); } if (y < rows && (maze[x][y + 1] != ' ')) {      find(x, y + 1, maze, c + 1, target); }

Assume your maze is 8x8, and the currently point is 6,7, what will happen in there?
First if statement, x is greater than zero so the maze[x-1][y] succeeds.
Second if statement, x < 8, so it succeeds.
Third if statement, y is greater than 0, so it succeeds.
Fourth if statement, y is less than 8, so it goes to check maze[x][y+1], but since your array only goes from 0 to 7, you get an ArrayIndexOutOfBounds error, but that doesn't stop the program, it simply jumps to the catch statement.
What happens to all the if statements after you jump out of the code?? They aren't executed, and that is why you get 9 instead of 8.
I would recommend removing the try catch block because it appears that you don't know what it actually does and fix the errors as you come across them.

[Panphobia]

Yea that was the most stupid thing I have ever seen, I do not know why I did that, sorry, but I fixed it, and it works fine now

[Panphobia]

Thanks mirhagk for all the help, I guess I won't be able to do it with the BFS, I do not seem to understand it well enough, but now I have actually made the other method you said is dijkstra's, work well, and give me all the right output, thanks again

[Panphobia]

You too DemonWasp, thanks