Maze game

[Becky Bloomwood]

Hi, i'd like some information on creating a very simple maze program. No graphical features of java need be used. The walls would be represented by asterixes and the robot would be made of the keyboards full stop character. The robot will try to find its way out of the maze. I would think that the maze would be made from a 2 dimensional array and the code would be looped until the robot found its way out, but other the that i'm not sure. Can anyone help?

Thanks in advance

[Bear Bibeault]

"de pressed",

There aren't many rules that you need to worry about here on the Ranch, but one that we take very seriously regards the use of proper names. Please take a look at the JavaRanch Naming Policy and adjust your display name to match it.

In particular, your display name must be a first and a last name separated by a space character, and must not be obviously fictitious.

Thanks!
bear
JavaRanch Sheriff

[Michael Dunn]

search the Programming Diversions forum for 'maze' and you'll find some
interesting threads

[Scott Selikoff]

"Becky Bloomwood"

Your name appears to be based on a fictitious character. Please choose a more appropriate name.

[Ryan McGuire]

As I see it, there are two pieces to this: A) Making a maze and B) Solving the maze.

A) Making a maze.
I agree that the most obvious data structure, a two-dimensional array, is probably correct. But an array of what? Strings? chars? ints? A custom class? Some standard library class? Well what information do you need for each cell? You might say that you need to know whether each of the four surrounding walls is solid or not, but then the state of any one wall has to be maintained in the the two squares that the wall separates.

The other option is to track the state of only two walls (perhaps the top and left walls) for each square. The plus side of this approach is that you have to manipulate only half as many values per cell. The minus side is that the entire right column and bottom row of the maze pose strange border condition problems.

There is a neat algorithm for generating a maze:

initialize the "groupNo" for all cells to 0 and all walls as solid
set the upper right groupNo to 1
while (there are still cells with a groupNo of 0) {
   while (true) {
      pick a random square, s1
      if (s1.groupNo == 0) continue
      pick a random orthogonal neighbor of s1, s2
      if (s2.groupNo != 0) continue
      break
   }
   break the wall between s1 and s2
   set s2.groupNo to s1.groupNo
}

B) Solving the maze
The simplest algorithm for solving a maze is to have the "robot" stay against one wall. Whenever the robot enters a new cell, it should try to turn left, go straight, turn right, or do a u-turn, in that order.

Cool?

[Stan James]

I started to write up some of my experience playing with mazes and then thought to look at Wikipedia. It's always worth a visit.

http://en.wikipedia.org/wiki/Maze