• Post Reply Bookmark Topic Watch Topic
  • New Topic

Recursive BackTracking for Solving a Maze  RSS feed

 
William Koch
Ranch Hand
Posts: 76
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Steve Luke
Bartender
Posts: 4181
22
IntelliJ IDE Java Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What problem are you having? You have done a decent job describing your assignment but not the trouble you are having and so it is real hard for us to help you.
 
Steve Luke
Bartender
Posts: 4181
22
IntelliJ IDE Java Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
p.s. The documentation you posted is broken. The links to all the classes are at http://www-internal.eecs.usma.edu/courses/cs384/exercises/minos/doc/minos/... Since we don't have access to www-internal.eecs.usma.edu we can't see the documentation you intended to provide.
 
dennis deems
Ranch Hand
Posts: 808
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
William Koch
Ranch Hand
Posts: 76
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 76
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Ulf Dittmer
Rancher
Posts: 42972
73
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think it's unlikely that people will download some file from a file sharing site which then is in some proprietary format that only runs on a particular browser on a particular OS.

But the documentation doesn't matter much, as you still haven't stated what your code does so far, what is still missing, and in which way you're stuck implementing the missing pieces.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

Winston
 
William Koch
Ranch Hand
Posts: 76
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
here is my working solution(it wont make complete sense to yall because you cannot see the GUI and all the other classes and stuff unless you originally viewed the documentation

 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!