okay - quick question: Say you had a 12x12 char array representing a map, with #''s representing the walls and .''s as the possible paths. I know that the correct way to do this is a recursive function that takes the maze array and the starting position as the values. I also know that the way to think your way through this is the ''right-hand rule'', where you keep your right hand on the wall. But how would this be implemented in the recursive function outlined above? ------------------------- Krunk Splein

breadcrumbs

[edit]
your teacher should have told you that :p
Magmai Kai Holmlor
- The disgruntled & disillusioned


Edited by - Magmai Kai Holmlor on March 27, 2001 12:13:38 AM

We had an assignment like that back in an early Java class, too, and they made us do the recursive solution, even though I probably could have come up with a better one. Hell, they even handed us the pseudo-code we were supposed to use. Took all the fun out of it. So I made up a large, simple maze, with the start near the finish, but set up so the recursive algorithm checked EVERY other path in the maze before finding the right one, just to show that it doesn''t always work so well.

Anyway, yeah, if you''re going to ask about homework problems on the boards, ask for a little hint or something, and tell us it''s a homework problem. Don''t try getting us to do your assignment for you.

-Ironblayde
 Aeon Software

Down with Tiberia!
"All your women are belong to me." - Nekrophidius

Don''t you think you should do assignments on your own??
I think your teacher prefers that.

Interesting. I was participating in programming competitions about 10 years ago where writing a program to solve exactly such a maze was one of the problems to be solved (in the 4 hours time we had, or whatever it was). The interesting thing is that neither our solution nor the solution provided at the end of the competition used such an algorithm to solve a maze. Instead the algorithm would simply fill in all the dead ends... quite simple to implement once you think of it, actually. It hadn''t occurred to me but it occurred to one of my teammates and I don''t know how everyone was coming up with that idea so easily. Personally, I enjoy writing maze generation algorithms more than maze solving algorithms. I''ve got one that does diagonal passages and everything in my Scrolling Game Development Kit .

Still, like the other respondents, I suggest you solve this problem as instructed if in fact it was an assignment.

"All you need to do to learn circular logic is learn circular logic"

quote:

---

Original post by BlueMonk

Instead the algorithm would simply fill in all the dead ends... quite simple to implement once you think of it, actually. It hadn''t occurred to me but it occurred to one of my teammates and I don''t know how everyone was coming up with that idea so easily. Personally, I enjoy writing maze generation algorithms more than maze solving algorithms.

---

Yeah, that was my idea as well, for the maze-solving program. And I''d have to agree, generation algorithms seem much more interesting, although that is something I haven''t tried.

-Ironblayde
 Aeon Software

Down with Tiberia!
"All your women are belong to me." - Nekrophidius

This was not a homework assignment. I wouldn''t have come to the boards if it were, and if I *did*, I would have mentioned that in my post. Now, if anyone has any constructive advice, feel free to add it here. This is just a problem that I found interesting and that stumped me.

Thanks for the vote of confidence =P


-------------------------
Krunk Splein

Sry, it''s an archtypical homework problem. Been dished out for decades to CS majors.

Magmai Kai Holmlor
- The disgruntled & disillusioned

Nevertheless, I''m still interested in help for it, if anyone can. I''m new to this type of thinking and could use it.


-------------------------
Krunk Splein

The basic recursive solution works like this. You have four functions, called MoveNorth(), MoveSouth(), MoveWest(), and MoveEast(). MoveNorth() is a recursive function that checks every possible path which begins by taking a single step to the north, and the other three functions are analogous to it. The way to solve the maze is simply to call MoveNorth(). If it succeeds, a path was found. (You''ll have to put some logic into MoveNorth() to have it log the path, more on that in a second.) If it fails, try MoveEast() instead. If that fails, try MoveSouth(), and if that fails, try MoveWest(). If all four functions fail, then the end of the maze is not accessible from where the player is standing.

Your maze is represented by an array of characters. Those characters should represent one of four states: that location in the maze is either blocked (wall), visited (dead-end), unvisited, or on the path. You should start by marking the location where the player is standing as being on the path.

The structure of MoveNorth() is as follows. If the location immediately to the north is unvisited, move to that square and mark it on the path. Now check if you are at the end of the maze. If you are, you can return success from the function. If you''re not, then the recursion comes in. You want to check all paths from this location, so you should call MoveNorth(), MoveWest(), then MoveEast(). Note that you do not call MoveSouth() because you just came from the south. If any one of them succeeds, you can return success without calling the others. If all three calls fail, then there are no paths from this position. Mark the space you''re standing on as ''visited'' instead of on the path, and move back to the south, where you came from.

The other three functions are analogous to this one. There''s no clear ''base case'' for the recursion so to speak, but since there are only a finite number of locations in the maze, only a finite number of function calls can be made.

Print out the array after the algorithm has run and you''ll see the path that was found to complete the maze. If you want to store the path as a sequence of locations, your best choice is probably a stack, pushing the locations on the stack as you move to them, and popping the top location from the stack if you need to backtrack.

Of course, if you have an extremely large maze, and the path is very long, this might cause problems with the system stack, but I haven''t tested how long the path needs to be before that would happen. The other thing is that this algorithm finds a path through the maze, but not an optimal path. It can do very poorly especially on ''mazes'' that are wide open and with a finish placed such that the algorithm spirals around the entire maze before closing in on the finish. In fact, you can create a maze that consists only of a single, rectangular, open room, and place the start and finish in such a way that the algorithm will spiral the room and find a path that includes EVERY open location in the maze, when the optimal path might have only been a few steps.

A program that finds an optimal path might work something like what we were talking about before, where the program just eliminates the dead ends until only a shortest path is left, but you''d have to be careful with that, since if you eliminate only positions which are blocked off from three sides, that algorithm is going to have trouble with an open room as well.

-Ironblayde
 Aeon Software

Down with Tiberia!
"All your women are belong to me." - Nekrophidius