Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

Java Recursion method

Rivosk Hogerop
Greenhorn
Posts: 3
Hi,

I have a question about a small pathfinding problem.
I got a 2D table which symbolize a labyrinth.
The table only contains a ' '(white space), a 'B', a 'E' and a 'W'
B: begin position
E: end position
W: wall

I need to write out all the pads from B to E.
(a) I may not cross a wall
(b) I may not move to a position I have already been before. (in the same pad)

for example I have the following labyrinth: (ignore the [])
[M][ ][ ][ ][ ]
[B][ ][M][ ][E]
[M][ ][ ][ ][ ]

My java program needs to print out ALL the possible pads from B to E:
rurrrd
rurrdr
rurrddru
rdrrru
rdrrur
rdrruurd

I have written this little program.
It's an excercice from the exam from last year and I should be able to solve it with recursion.
If someone can point me where and what I'm doing wrong I would be verry gratefull. (I'm practicing for my upcomming exam)
(excuse me for my bad english)

dennis deems
Ranch Hand
Posts: 808
Are you sure that an Array is the best data structure to model your labyrinth? I might suggest exploring what you can do with a tree structure. I think a tree is better suited to your problem because the relationship of parent and child nodes is inherently suited to representing a path.

Randall Twede
Ranch Hand
Posts: 4396
3
i am not sure recursion is the best answer. i wrote an old homework that is similar to this. it only had to find one path though. i used an array and a stack of points. the code is here

Rivosk Hogerop
Greenhorn
Posts: 3
It's not that i'm looking for the best way to solve this problem.
It's an exercise and we need to solve it with recursion. (on the exam I will have no other choice then recursion.)
(P.s.:we haven't seen any OOP)

dennis deems
Ranch Hand
Posts: 808
I would create a node object which contains: the attribute of the room ('','B','E' or 'W'), a set of child nodes (the adjoining rooms), and a marker to tell whether or not it has been visited.

I would build out the tree from the labyrinth you have laid out in the arrays. We also need some indicator of how we are getting from room to room -- the path (u,d,l,r), and that will be the most difficult part of the problem.

But assuming you have that sorted, the pathfinding algorithm would be:

It is probably better, now I think of it, to wait until E is reached and then collect the path as we come out of the recursion, but you get the idea.

Greenhorn
Posts: 16
The code itself, with very minor adjustments, does work. Not saying anything about recursion being the best option or arrays being worse.

Think about possible problems and ways of testing them.

You need to keep track of where you visited for the current path without blocking off the path for other solutions.

The large if statement could use some white space to make it more readable, for easier testing.

Campbell Ritchie
Sheriff
Posts: 48952
60
Welcome to the Ranch Curly Stoge.

Stephan van Hulst
Bartender
Posts: 5810
61
Hi Rivosk. Problems like this become much easier when you first create some basic data structures to work with, which provide a few handy operations.

For instance, let's make a basic Labyrinth data type which provides methods to look at different directions, and to move into a new direction:
You now have a simple Labyrinth that has look(Direction) and move(Direction) methods. This should be plenty to implement some recursive method that finds all the paths to an exit.

Note that the trick here is that the move() method returns a new Labyrinth. You can call this method without worrying that your old labyrinth will be modified. In fact, the entire Labyrinth class here is immutable. This makes it very easy to work with.

As already has been mentioned, a tree is a good structure to represent paths with. If you don't want to use a tree, you can also use something like:List<List<Direction>>.

dennis deems
Ranch Hand
Posts: 808
Honestly, without a tree I don't know how you will be able to be sure that you have found every possible path. As Curly observed, your code works, but how can it be adapted to find more than one solution, let alone to exhaust all possibilities? With a tree you know definitively whether or not a branch has been explored.

Stephan van Hulst
Bartender
Posts: 5810
61
The algorithm to find all the paths doesn't need to inspect a tree to figure out whether it exhausted all possibilities. Recursion takes care of this automatically.

You can write a simple recursive method getPathsToExit() that returns a list of paths, without ever using a tree.

Randall Twede
Ranch Hand
Posts: 4396
3
sure seems a lot harder than the homework i had
recursion is great, it is just hard for most of us mortals to figure out
glad you got some great help with it. i think i might have had a hard time with this one.

Stephan van Hulst
Bartender
Posts: 5810
61
Some pseudo code: