19 replies to this topic

[Kido]

I need help with making a java algorithm since I don't understand this damn course at all >.< It's primarily about recursion and 2D arrays.

In a nut shell I have to make a program that generates either a random maze or reads a maze from a file. Then I have to have the program find the shortest path from point a to point b and output the path using "+"s

The maze would look something like this:

BBBBBB
BOOOBB
BSBOBB
BOOOOB
BBBBXB

B = barrier
O= open path
X = exit
S = start

I don't even know how to start. The best I did was come up with a menu in the main method -_- I know I'll need a procedure to read a maze from a file but how do I randomize it? Can everyone just spit out ideas for an algorithm please?

*edit: essentially it's the same purpose as this: http://courses.engr....96/mp3/mp3.html
Only like a totally different comp language

Edited by Kuro, 06 April 2011 - 02:25 PM.

[Junsu]

Main Method with menu should have option of read from file or to generate a random maze.

Does the random maze have set dimensions to start with?

For the read from file part,

First open file, read it.
Change rows every time you get a "\n" character that way it'll be a 2d array instead of one line of input



For the algorithm, all I can think of is one where you go through all the possible paths and count the steps D:
But it seems too inefficient and feels like you're bruteforcing it .__.

And I dont even know where recursion comes O__o

[Pyro699]

What i would do is work backwards. Start with the solution (make a base path, no barriers or branches), then add random branches to your path with random lengths, etc.

I must say, this has to be an upper level class; this algorithm would really make one think.

~Cody

[Waser Lave]

One of the easiest ways to solve a maze is to simply follow the wall, so pick either left or right and follow the wall on that side. If all the walls of the maze are connected then you're guaranteed to find the exit without getting lost.

[artificial]

If you absolutely have to use recursion, you could call a function to test each surrounding coordinate. If it's a barrier, then just return, if it detects an open wall, call the function again with the new coordinate, making sure you record the old coordinate in a global variable. If it detects the exit, return.

Once it's run through it's cycle you'll have the path to go through.

[1337hunt3r]

This is a classic exercise of recursion; the trick is to "flood" the spaces and leave a trail of numbers, starting from the start, until you find the exit.

Use this helper method:

private void flood(char[] a, int x, int y, int step)
{
   if (x < 0 || x >= a.length || y < 0 || y >= a[0].length)
      return;
   if (a[x][y] = 'O')
   {
      a[x][y] = step;
      flood(a,x+1,y,step+1);
      flood(a,x-1,y,step+1);
      flood(a,x,y+1,step+1);
      flood(a,x,y-1,step+1);
   }
}

In your main, call flood(a,x,y,0), where x and y are the coordinates of the start. Then proceed to backtrack from the exit until you reach the start.

Edit: If you want to be even more efficient, you can actually have flood return an ArrayList of all the coordinates you have "flooded" and you wouldn't even need to do the backtracking. But for now, the above method is probably the best.

Edited by 1337hunt3r, 11 April 2011 - 02:19 PM.

[tematric]

I guess I would have to agree with 1337hunt3r

Just create a function that bruteforces every path in the maze. If this was using data algorithms and not a 2d array, you would just call the function with your next point of destination instead of a coordinate system.

For generating a maze, the difficultly increases exponentially because there are multiple formats and all should be using slightly more complex data management.

Based on what you said it should look like, I suppose it would be a little more complicated and like the above posters asked, are there set dimensions for the maze (length and width)?

EDIT: The generation algorithm should start from whichever end has the most constraints (in this case, the end since it must be along a wall).

Edited by tematric, 06 April 2011 - 11:10 PM.

[1337hunt3r]

Tematric, the algorithm I described does not bruteforce every path, it merely fills the entire path with numbers and backtracks, making it an O(n^2) algorithm for a n*n board.
Generating mazes is trickier and can be coded in a couple of different ways. Read this to find out more: http://en.wikipedia....ation_algorithm

[Kido]

Thanks to everyone so far! I have like basic pseudocode for the program (but no recursion since right now it's is confusing the fuck out of me) -_- But at least I have some vague idea of how to do it.


Feel free to keep shooting ideas though. It's due on the 12th

And the coordinates of the maze are supposed to also be given in a file (first 2 lines are row and column, lines 3-6 are variables used and 7 and on is the maze itself)

[1337hunt3r]

Thanks to everyone so far! I have like basic pseudocode for the program (but no recursion since right now it's is confusing the fuck out of me) -_- But at least I have some vague idea of how to do it.


Feel free to keep shooting ideas though. It's due on the 12th

And the coordinates of the maze are supposed to also be given in a file (first 2 lines are row and column, lines 3-6 are variables used and 7 and on is the maze itself)

I'm taking that as a "you don't understand my code at all" response.
Anyways, a visual will probably help you understand. Refer to the attached image.
The green arrow means the program has successfully found the exit, so it backtracks from 5 to 0 to find the start, generating the path.

Attached Files

•  Untitled.jpg   25.75KB   17 downloads

Edited by 1337hunt3r, 07 April 2011 - 05:58 PM.

[Junsu]

I'm taking that as a "you don't understand my code at all" response.
Anyways, a visual will probably help you understand. Refer to the attached image.
The green arrow means the program has successfully found the exit, so it backtracks from 5 to 0 to find the start, generating the path.

Extremely surprised at your algorithm

[1337hunt3r]

Actually, the example code I gave you has a little bit of a bug--it will find a path, but not necessarily the shortest one. There's an easy way to fix it, but I'll leave it to you since it's fairly simple.

[tematric]

Tematric, the algorithm I described does not bruteforce every path, it merely fills the entire path with numbers and backtracks, making it an O(n^2) algorithm for a n*n board.

For beginners, bruteforcing is the easiest way. If you have the experience, you can add shortcuts to shorten bruteforcing.

By adding 3 simple variables to each cell, you will only test each path at an intersection once during the entire search.

"back" will allow backtracking from the end.
"distance" will store the shortest distance if you were to follow the breadcrumbs back to start
"forward" will allow retracing the shortest path

Just pick a path and leave your bread crumbs and distance behind as you travel through each cell. If you come across a cell with breadcrumbs, compare the distances. If the path you came from is shorter, rewrite the breadcrumbs. Follow the breadcrumbs back to an untested intersection and begin the process. This uses only 1 local variable (cell you are currently in) and the entire function is just a while loop and no recursion at all. Since the starting cell has no back, when back is null, break out of the loop and report the results.

Edited by tematric, 07 April 2011 - 11:47 PM.

[1337hunt3r]

For beginners, bruteforcing is the easiest way. If you have the experience, you can add shortcuts to shorten bruteforcing.

By adding 3 simple variables to each cell, you will only test each path at an intersection once during the entire search.

"back" will allow backtracking from the end.
"distance" will store the shortest distance if you were to follow the breadcrumbs back to start
"forward" will allow retracing the shortest path

Just pick a path and leave your bread crumbs and distance behind as you travel through each cell. If you come across a cell with breadcrumbs, compare the distances. If the path you came from is shorter, rewrite the breadcrumbs. Follow the breadcrumbs back to an untested intersection and begin the process. This uses only 1 local variable (cell you are currently in) and the entire function is just a while loop and no recursion at all. Since the starting cell has no back, when back is null, break out of the loop and report the results.

This is an exercise in 2d arrays and recursion, so I assume the teacher would like them to use recursion.
And surely, a 10-line recursive method with only 1 variable in each cell is more elegant than a nasty while loop with 3 variables in each cell, no?

[Kido]

Yeah. I could do it with a loop and lots of if statements but for recursion I cam up with this code:

if ((col - 1) >= 0)  //check for left border
        {
            if (array [row] [col - 1] == 'X') //left
            {
                return true;
            }
        }

And do the same thing for each side (up, down, right)

And then I check for 'O'

 if ((col - 1) >= 0)  //check for left border
        {
            if (array [row] [col - 1] == 'O')
            {
                if (move (row, col + 1) == true)
                {
                    array [row] [col] = '+';

                    return true;
                }

            }

And again, same for each side.

Does that look about right guys?

I kinda gave up finding the shortest path since I realized I won't lose any marks on it.

Edited by Kuro, 11 April 2011 - 01:01 PM.

[1337hunt3r]

Instead of asking us if it looks right, you should just compile your code and see if it works (which it doesn't).
You should write the method names instead of just the code; I can't tell if you have 2 methods or just 1.

[Waser Lave]

Also, use code tags. [ code ][ / code]

[Kido]

Well by the time someone replied I compiled it lol. I keep getting array out of bounds or some other errors but I'm working on it.

Post edited with the code tags.

[1337hunt3r]

I'm so confused as to why you don't listen to anything I say
I'm just trying to help.

[Kido]

I'm sorry. I know you're trying to help but I'm like incapable of turning what you're saying into actual code and getting it to work. (I'm stupid like that). I did read your info and I've taken your ideas into thought, I just found a better way to actually code it that worked better for me.