I really need some help implementing a recursive backtracking algorithm to solve a maze. The link below provides full documentation of the classes that have been created along with their methods. The algorithm basically goes like this: When you first enter the maze, drop bread crumbs in the first room, then as you walk through the rooms, drop breadcrumbs in each room. If you come to a dead-end follow the breadcrumbs backwards, picking them up, until you get back to someplace where you can go a different direction. As you come to each new place, scratch a mark on the floor so you know which places you have already explored.
NOTE: This maze is not a typical java maze, this maze has room objects and wall objects. Rooms that are next to each other share walls so the east wall of room (0,0) is the same object as the west wall of room (1,0). The grid goes from top left corner to the right for the x axis, and down for the y axis. (i.e. the top left corner is (0,0) ).
Any help is much appreciated. I suggest you check out the documentation here. The .mht only opens with Internet Explorer as far as I know.
If you know how to perform a depth-first search on a graph, then you have the tools you need to solve this problem. If not, it might help to think of each room in the maze as a container that holds: a collection of doorways connected to other rooms, an optional breadcrumb, and something that tells whether we've searched this room before (this can be the breadcrumb itself if you're very careful about how you pick it back up -- personally, I prefer a wholly independent indicator). Design a Java class representing such a room, and build out the maze by connecting rooms with doorways. Now you just need some code that can examine the doorways in a room and explore the rooms they're connected to, and determine whether we're at a dead end. It may be rather less code than you might imagine you'd need, thanks to the power of recursion. Each time a new room is entered, a new recursion is launched. Hope this helps.
I have fixed the link in the first post and also posted it here. I believe all of your will understand the confusion I am having when you see the documentation. The .mht only opens with Internet Explorer as far as I know.
William Koch wrote:Anyone take a look at the documentation yet? I could really use a hand here. I am fairly new to java and need some assistance in doing recursion and backtracking.
Then I suggest you read Dennis's post again. Thoroughly. Because what he describes is exactly how I (and I suspect quite a few others here) would go about it.
Ulf is also quite right, describe the problem(s) you're having, and post relevant code here, not on some 3rd party site; and please make sure it is relevant - we don't want to plough through a complete source dump of your application.
This page describes exactly the sort of thing we're looking for.
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here