From: Clifford Heath Date: 2005-05-17T13:40:31+09:00 Subject: Re: [SUMMARY] Amazing Mazes (#31) Glenn M. Lewis wrote: > Could you please elaborate? It's been quite a while since I did this stuff, but I do recall solving the problem, and only afterwards finding some other work that reflected the same solution. It'd be very cool to do this again in Ruby with OpenGL :-))). The idea is to start as Dominik did, with a maze having all walls intact - every cell has two intact walls so it's closed from every other cell. Every cell is numbered, say top-left to bottom-right, 0..(W*H-1). This number is known as the domain number, and every cell bearing a certain number is defined to be reachable from any cell in that domain. Whenever you break a wall separating two distinct domains, you join them into one domain, because any cell in either domain can now reach any cell in the other domain. So to keep things intact, you must eliminate one domain by changing all occurrences of that number to the other one. I always eliminate the higher numbered one, so the maze ends up as one domain numbered zero. Whenever you consider a wall you might want to break, check the domain numbers on either side. If they're the same, there is already a path between the two cells, and breaking this wall will make a duplicate path - which is not what you want. If they're different however, there is no path between the two cells and it's ok to break this wall, eliminating one of the two domains. The only remaining task is to find an efficient and random search for a wall to break. The easiest way is to choose a cell at random, check both walls (in random order), and if that wall divides two domains, break it. If not, consider the next cell (circular search) until you find a wall you can break. Because you have W*H cells, there are initially that many domains, and because every break reduces the domain count by one, you must break exactly W*H-1 walls to get to a maze where every cell is reachable from every other. I set my son the challenge of doing this in three dimensions, and we arranged things so the ladders (=broken floors) were much less numerous than the horizontal connections. You can do this simply by skewing the random number generator that chooses which wall to break. If it tries the north wall 45% of the time, the east wall 45%, and the floor only 10%, you get the desired outcome. Similarly in a 2-D maze, you can skew the generation so that more of the paths are E-W rather than N-S. Then we created a 3-D perspective view looking in from near one corner between two layers, so you can see all the passages, the ladders climbing up to the layer above, and the manholes where ladders appear from below, so you can wander around the maze at will. We even animated the ladder climbing using double buffering, moving the camera up past the floor to the next floor. All in Turbo-Pascal for a year 10 assignment :-). My son solved a 20x20x20 maze in about 10 minutes, much to his teacher's astonishment - he has an amazing visual memory. I used to print him 2-D mazes with a 1/8" cell size, full page on letter paper - perhaps 60x80 in size. When he was four years old, he complained that he needed some new ones, and my wife pointed out that he had a stack of sixty that were unmarked. He quickly went through the stack, pointing to the solution on each one. He had not only solved them all by eye, but he recognised each one and remembered its solution! Scary... Clifford Heath.