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
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:
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.
But my program only print out 1 possible pad instead of ALL pads.
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)
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.
Hi thanks for your reactions.
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)
Joined: Mar 12, 2011
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.
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>>.
Joined: Mar 12, 2011
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
Joined: Sep 20, 2010
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.
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.