This week's book giveaway is in the OO, Patterns, UML and Refactoring forum. We're giving away four copies of Refactoring for Software Design Smells: Managing Technical Debt and have Girish Suryanarayana, Ganesh Samarthyam & Tushar Sharma on-line! See this thread for details.
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>>.
The mind is a strange and wonderful thing. I'm not sure that it will ever be able to figure itself out, everything else, maybe. From the atom to the universe, everything, except itself.
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.
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.