Computer Science Canada :: View topic - Pathfinding error help

Computer Science Canada

Pathfinding error help

Author:

Panphobia [ Tue Nov 20, 2012 12:43 am ]

Post subject:

Pathfinding error help

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

Author:

Panphobia [ Tue Nov 20, 2012 12:46 am ]

Post subject:

Re: Pathfinding error help

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

Author:	mirhagk [ Tue Nov 20, 2012 7:43 am ]
Post subject:	RE:Pathfinding error help
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.

Author:	Panphobia [ Tue Nov 20, 2012 8:32 am ]
Post subject:	RE:Pathfinding error help
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.

Author:

mirhagk [ Tue Nov 20, 2012 11:15 am ]

Post subject:

Re: Pathfinding error help

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.

Author:	Panphobia [ Tue Nov 20, 2012 11:21 am ]
Post subject:	RE:Pathfinding error help
actually, it prints out two 0's and then, it doesnt stop executing but keeps on going forever until I stop the program lol

Author:

Panphobia [ Tue Nov 20, 2012 11:29 am ]

Post subject:

Re: Pathfinding error help

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. Posted Image, might have been reduced in size. Click Image to view fullscreen.

Author:	DemonWasp [ Tue Nov 20, 2012 1:14 pm ]
Post subject:	Re: Pathfinding error help
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.

Author:	Panphobia [ Tue Nov 20, 2012 1:39 pm ]
Post subject:	RE:Pathfinding error help
Ok I will try that

Author:	Panphobia [ Tue Nov 20, 2012 2:11 pm ]
Post subject:	RE:Pathfinding error help
Hmmmm I tried switching a lot of things around, but it actually does not work.

Author:	DemonWasp [ Tue Nov 20, 2012 2:26 pm ]
Post subject:	RE:Pathfinding error help
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?

Author:

Panphobia [ Tue Nov 20, 2012 2:36 pm ]

Post subject:

Re: Pathfinding error help

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;

Author:	DemonWasp [ Tue Nov 20, 2012 6:01 pm ]
Post subject:	RE:Pathfinding error help
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.

Author:	Panphobia [ Tue Nov 20, 2012 6:13 pm ]
Post subject:	Re: Pathfinding error help
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

Author:

DemonWasp [ Tue Nov 20, 2012 6:48 pm ]

Post subject:

RE:Pathfinding error help

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

Author:

Panphobia [ Tue Nov 20, 2012 7:05 pm ]

Post subject:

Re: Pathfinding error help

Ok I think I did everything to your specifications, here is ALL the code

code:

package bfs;

import java.util.*;
import java.io.*;

public class BFS {

static int rows, col;

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(" ");
rows = Integer.parseInt(yx[0]);
col = Integer.parseInt(yx[1]);
char[][] maze = new char[col][rows];
for (int y = 0; y < rows; y++) {
String text = s.nextLine();
for (int x = 0; x < col; x++) {
maze[x][y] = text.charAt(x);
}
}

int x[], y[];
x = new int[3];
y = new int[3];
for (int z = 0; z < rows; z++) {
for (int a = 0; a < col; a++) {
if (maze[a][z] == 'A') {

x[0] = z;
y[0] = a;

}
if (maze[a][z] == 'B') {
x[1] = z;
y[1] = a;
}
if (maze[a][z] == 'C') {
x[2] = z;
y[2] = a;
}
}
}

System.out.println(bfs(maze, y[0], x[0], '#', 'B') + bfs(maze, y[1], x[1], '#', 'C')
+ bfs(maze, y[2], x[2], '#', 'A'));

}
}

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 >= col || y < 0 || y >= rows) {
continue;
}
if (maze[x][y] == wall) {
continue;
}
if (maze[x][y] == goal) {
return array[2] + 1;
}
int[][] newPoints = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
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;

}
}

and the contents of the data file are right here

code:

Author:	Panphobia [ Tue Nov 20, 2012 7:10 pm ]
Post subject:	RE:Pathfinding error help
wait nvm i got it all i had to do to fix it is System.out.println((bfs(maze, y[0], x[0], '#', 'B')-1)+(bfs(maze, y[1], x[1], '#', 'C')-1)+(bfs(maze, y[2], x[2], '#', 'A')-1)); silly meeee, thank you so much maj, and demon

Author:

Panphobia [ Wed Nov 21, 2012 12:32 am ]

Post subject:

Re: Pathfinding error help

Ok so I think this is going to be my last question on BFS, and then I will know how to implement correctly, this question in dwite http://dwite.org/questions/train_ride.html , i finished, and it works as long as you do not bring in the xxxxxx into it, when i do, the arraylist causes a null pointer exception (the dreaded), here is my code

code:

package bfsv2;

import java.util.*;
import java.io.*;

public class BFSV2 {

static int rows, col;

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()) {
ArrayList<String> text = new ArrayList<String>(5);
char[][] maze;
int c = 0;
rows = 0;
col = 10;
text.add(null);
while (text.get(c).charAt(0) != 'x'||text.get(c)==null) {
text.add(c, s.nextLine());
c += 1;
}
rows = c;
maze = new char[col][rows];
for (int y = 0; y < rows; y++) {
for (int x = 0; x < col; x++) {
maze[x][y] = text.get(y).charAt(x);
}
}
int x = 0;
int y = 0;
for (int z = 0; z < rows; z++) {
for (int a = 0; a < col; a++) {
if (maze[a][z] == 'S') {
x = z;
y = a;
}
}
}
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[]>();
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) {
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;

}
}

Author:

DemonWasp [ Wed Nov 21, 2012 1:03 am ]

Post subject:

RE:Pathfinding error help

code:

text.add(null);

Explain to me exactly what that line is doing.

Author:	Panphobia [ Wed Nov 21, 2012 1:14 am ]
Post subject:	RE:Pathfinding error help
Well basically I am trying to figure out the number of rows and am using a counter to figure out that, then I store the rows in an array list,when I try to run the while loop that says while the Next line isn't x it says nullpointerexcePtion, before that it was indexoutofbounds, so the. I just added null to position 0 and then I got this

Author:	Panphobia [ Wed Nov 21, 2012 1:16 am ]
Post subject:	RE:Pathfinding error help
I needed the test.add null to add something to the first position to compare it to x

Author:

DemonWasp [ Wed Nov 21, 2012 3:16 am ]

Post subject:

Re: Pathfinding error help

Stop doing things at random: that only works if you have evolutionary timescales and a massively parallel set of processors (you don't: you have limited time and only one "processor", you).

Here's how you write code to solve a problem:
1. State clearly how you want to solve the problem. Be precise: say exactly what you mean. You aren't allowed to use words or phrases like "kinda", "look at", "sorta", etc.
2. Break down the process from step #1 into the smallest steps possible.
3. Turn each step into a few lines of code (most of them should be one line).

For example, suppose you are trying to solve the following problem: "Read a single maze problem from an input file, stopping when you hit a line that contains an 'x'."

Step 1: Read lines from the file one at a time. If that line contains an 'x', discard it and stop reading; otherwise, add it to the list. Once we have the complete list, transfer the contents into a 2D array.

Step 2: Open the file for reading. Create a list to store results. Read lines one at a time; if the line contains 'x' then stop reading, otherwise, add the line to the list. After reading, convert every line in the list to a row of the 2D array.

Step 3:

code:

// Open the file for reading.
Scanner in = new Scanner(new File("DATA4.txt")); // Note: you can use relative paths.

// Create a list to store results
List<String> lines = new ArrayList<String>(); // Note: don't use a custom default size until you know what you're doing

while ( in.hasNext() ) {
// Read lines one at a time;
String line = in.nextLine();

// if the line contains 'x' then stop reading
if ( line.contains ( 'x' ) ) {
break;
}

// otherwise, add the line to the list
lines.add ( line );
}

// Convert to 2D array
int rows = lines.size(); // Helpfully, List keeps track of how many entries it has.
// Your code actually does this correctly.

Eventually this process will become natural: you won't have to think about each step, you'll just understand how the code should look.

Author:	Panphobia [ Wed Nov 21, 2012 8:46 am ]
Post subject:	RE:Pathfinding error help
The way you implied is that it adds a line to the List until the end, not until the first set of xx's, what I was getting at was, to add the lines to the arraylist until you get to a line containing x, and THEN making the 2D array and solve the answer, the way you did it was, while there is a nextline in the file you will keep adding a line to the list, see what i am trying to get at is I cannot then differentiate between which maze is which if they are all in the same boat, that is why i tried to put the line.contains('x') in a while loop, so it will add to the list while the nextline is not x, and then i convert it to array etc

Author:

Panphobia [ Wed Nov 21, 2012 8:55 am ]

Post subject:

Re: Pathfinding error help

I am sorry I might be stupid as shit, but it still gives me an IndexOutOfBound exception, here is the code that is responsible

code:

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")){
break;
}else{
text.add(line);
}

}
System.out.println(text.get(1));

Author:

DemonWasp [ Wed Nov 21, 2012 12:37 pm ]

Post subject:

RE:Pathfinding error help

You're not stupid. You are moving too fast. Slow down: programming is best done as slowly and methodically as you need to.

If something doesn't go exactly like you want, take a deep breath, close your eyes and count to 10, then look at it again, methodically. Go through it line-by-line. Explain what each line does to yourself (talk to yourself!). Don't take anything for granted: make sure each line does what you think it does as you go.

As a corollary, if you think something is working just the way you want, test it to make sure!

Look at this line:

code:

System.out.println(text.get(1));

You're getting an IndexOutOfBounds exception. What is the index there? Well, it has to be the 1.

How can a 1 be out of bounds? Well, consider the equivalent with arrays:

code:

int[] myArray = new int[1];
myArray[1] = 3; // ArrayIndexOutOfBoundsException

This happens because arrays start at 0 (called "0-indexed"). So if you have an array of length 1, then the only in-bounds index is 0.

The same is true for arrays. If the while loop only ran once, there may be 1 element in the list, which means the only valid index is 0, so text.get(1) will be out of bounds.

It's even possible that you have two lines containing 'x' in a row. In that case, you may have an empty list: text.size() will return 0, and there is no valid index (any number you pass to text.get(number) will throw an IndexOutOfBoundsException). You can probably ignore that case here, but you should remember it for later.

Author:	Panphobia [ Wed Nov 21, 2012 1:35 pm ]
Post subject:	RE:Pathfinding error help
Ok i fixed that, now only one problem, when i have the array of chars, and try to output them, there is nothing in it, even when i give it values from the list

Author:

Panphobia [ Wed Nov 21, 2012 8:45 pm ]

Post subject:

Re: Pathfinding error help

When I try to output the array, it only outputs the lines printed with system.out.println and nothing in the actual array is outputted, so I do not know why the array is not getting the values from the arraylist, because the arraylist actually has the values

code:

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")) {
break;
} else {
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;
int y = 0;

for (int z = 0; z < rows; z++) {
for (int a = 0; a < col; a++) {
if (maze[a][z] == 'S') {
x = z;
y = a;
}
}
}
// System.out.println(maze[0][0]);
// System.out.println((bfs(maze, y, x, ' ', 'E') - 1));
}
}

Author:	DemonWasp [ Wed Nov 21, 2012 11:56 pm ]
Post subject:	RE:Pathfinding error help
It's pretty clear you didn't even try debugging that. Look at your code and try to figure out why your code doesn't print anything. I'm pretty sure that the array does contain the correct values, you just aren't printing them correctly.

Author:

Panphobia [ Thu Nov 22, 2012 12:04 am ]

Post subject:

Re: Pathfinding error help

I know that I wasn't outputting, but even when I do, it doesnt work, here is the code that I use to output,

code:

for(int q = 0;q<rows;q++){
for(int w=0;w<col;w++){
System.out.print(maze[w][q]);
}
System.out.println();
}

Author:	Panphobia [ Thu Nov 22, 2012 12:12 am ]
Post subject:	RE:Pathfinding error help
yep you were right, it was right in front of my face (facepalm) I did not initialize col

Author:	Panphobia [ Thu Nov 22, 2012 12:15 am ]
Post subject:	RE:Pathfinding error help
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

Author:	mirhagk [ Thu Nov 22, 2012 11:49 am ]
Post subject:	RE:Pathfinding error help
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.

Author:	Panphobia [ Thu Nov 22, 2012 12:45 pm ]
Post subject:	RE:Pathfinding error help
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?

Author:	mirhagk [ Thu Nov 22, 2012 2:51 pm ]
Post subject:	RE:Pathfinding error help
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).

Author:

Panphobia [ Thu Nov 22, 2012 3:55 pm ]

Post subject:

Re: Pathfinding error help

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

Author:

Panphobia [ Thu Nov 22, 2012 4:04 pm ]

Post subject:

Re: Pathfinding error help

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 Very Happy

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;

}
}

Author:	Panphobia [ Thu Nov 22, 2012 11:14 pm ]
Post subject:	RE:Pathfinding error help
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?

Author:

jr5000pwp [ Fri Nov 23, 2012 11:45 am ]

Post subject:

Re: Pathfinding error help

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();

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;

Java:

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

Author:	mirhagk [ Fri Nov 23, 2012 2:39 pm ]
Post subject:	RE:Pathfinding error help
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.

Author:	Panphobia [ Fri Nov 23, 2012 2:48 pm ]
Post subject:	RE:Pathfinding error help
Ok I will do that

Author:

Panphobia [ Fri Nov 23, 2012 3:33 pm ]

Post subject:

Re: Pathfinding error help

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;

}
}

Author:	Panphobia [ Fri Nov 23, 2012 5:28 pm ]
Post subject:	RE:Pathfinding error help
sigh, trying everything, yes it outputs, but i dont think it outputs the shortest path now lol

Author:	Panphobia [ Sat Nov 24, 2012 1:44 am ]
Post subject:	RE:Pathfinding error help
I've been debugging this whole day with almost no success

Author:	mirhagk [ Sat Nov 24, 2012 10:01 am ]
Post subject:	RE:Pathfinding error help
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.

Author:	Panphobia [ Sat Nov 24, 2012 12:09 pm ]
Post subject:	RE:Pathfinding error help
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

Author:	evildaddy911 [ Sat Nov 24, 2012 12:53 pm ]
Post subject:	RE:Pathfinding error help
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

Author:	Panphobia [ Sat Nov 24, 2012 1:01 pm ]
Post subject:	RE:Pathfinding error help
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

Author:

Panphobia [ Sat Nov 24, 2012 7:17 pm ]

Post subject:

Re: Pathfinding error help

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 Razz

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;
//
// }
}

Author:	mirhagk [ Sun Nov 25, 2012 1:22 am ]
Post subject:	RE:Pathfinding error help
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

Author:	Panphobia [ Sun Nov 25, 2012 1:25 am ]
Post subject:	RE:Pathfinding error help
what do you mean checking if there is an empty space twice?

Author:

mirhagk [ Sun Nov 25, 2012 1:30 am ]

Post subject:

Re: Pathfinding error help

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 Razz

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.

Author:

Panphobia [ Sun Nov 25, 2012 1:38 am ]

Post subject:

Re: Pathfinding error help

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

Author:	mirhagk [ Sun Nov 25, 2012 1:43 am ]
Post subject:	RE:Pathfinding error help
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.

Author:	Panphobia [ Sun Nov 25, 2012 1:49 am ]
Post subject:	RE:Pathfinding error help
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

Author:

jr5000pwp [ Sun Nov 25, 2012 11:48 am ]

Post subject:

Re: Pathfinding error help

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.

Author:	Panphobia [ Sun Nov 25, 2012 1:29 pm ]
Post subject:	RE:Pathfinding error help
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

Author:	Panphobia [ Sun Nov 25, 2012 9:46 pm ]
Post subject:	RE:Pathfinding error help
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

Author:	Panphobia [ Sun Nov 25, 2012 9:48 pm ]
Post subject:	RE:Pathfinding error help
You too DemonWasp, thanks

You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy