A long time ago i also wrote a maze generator. It's helpfull to understand the algebra of (fully accessible) mazes:
1. Every wall may intersect with some other wall at most once. (this includes the outer wall)
With the above rule in mind, you can create mazes with any type of random proccess (without the need for backtracking or bookkeeping). You don't have to check wether places are still accessible -- they just always are and will be. Back in those days (qbasic on a 268) just drawing randomly from some point in random directions was about ten times faster than the common path walking (backtracking) style algorithms. Taking two seconds instead of a full minute.
Don't take my word for it. Grab a pencil. Start drawing random lines. They may only cross some other line at most once. You'll end up with a fully accessible maze.
The maze may be complicated -- the walls in a proper maze are not. Its a great example of how understanding the invariants and rules that govern your problem domain will help you write faster and simpler code.
Two walls interact in only 3 ways - first, they don't touch. you get hallways: ||, second one intersects ends at the other like a T (which is a kind of degenerate version of 3). Third, they cross over, like a +. if you don't let walls touch multiple times, say like a D you'll never have a closed off space like the center of that D.
I got that by drawing an exterior square with a single entrance in the bottom right hand corner. I then drew a line from the top wall to the bottom wall parallel to the left and right walls. I then drew a diagonal line from about a quarter of the way down the right wall left and downwards towards the bottom wall. I then drew a diagonal line from about three quarters of the way down the right wall, up and to left towards the top wall. This blocks off most of the maze. So I'm not sure the algorithm works as has been described.
This additional twist makes the original statement of:
without the need for backtracking or bookkeeping
appear to be misleading. You have to do some bookkeeping in order to know if the wall that your line just hit is connected to the start point, or any midpoint of the line you are drawing. The complexity is just hidden behind simpler words (They may only cross some other line at most once.).
Also, I'm not sure how the backtracking is missing. Once you've hit a new wall with your line, and check connectivity, if it's actually connected, then you have to backtrack that line until it's back to a place where it's no longer connected. Connectivity could be checked right before hitting a wall, but then it's just backtracking by another name. So I'm really not understanding how this would be implemented in an simpler and/or faster way.
If you have a way to draw a wall (twisty line) that doesn't intersect with any other wall, then it's trivial. Just draw a new wall optionally anchored on a wall. The line crossing bookkeeping seems annoying. If i had to do something right now, i'd use a bitmap of cells to indicate the presence or absence of a wall. Can't set a bit with more than 1 adjacent (north/south/east/west) bit set.
Can't set a bit with more than 1 adjacent (north/south/east/west) bit set.
Then you couldn't make a T (or + intersection) because as the newly incoming line was about to attach to the existing wall (regardless of any other connectivity), the final "bit" that would attach to the line and existing wall would have 2 adjacent bits set. ex: assuming a wall that travels east/west, and a line coming from the south northwards, when drawing the last pixel of the line before it attaches to the wall, the test would fail. The "south" bit would be set because that bit was set just one step prior, and the "north" bit would be set because that's where the wall is.
---------
x
|
|
Can't set "x" because there is more than one "adjacent" bit set (north and south).
1. Every wall may intersect with some other wall at most once. (this includes the outer wall)
With the above rule in mind, you can create mazes with any type of random proccess (without the need for backtracking or bookkeeping). You don't have to check wether places are still accessible -- they just always are and will be. Back in those days (qbasic on a 268) just drawing randomly from some point in random directions was about ten times faster than the common path walking (backtracking) style algorithms. Taking two seconds instead of a full minute.
Don't take my word for it. Grab a pencil. Start drawing random lines. They may only cross some other line at most once. You'll end up with a fully accessible maze.
The maze may be complicated -- the walls in a proper maze are not. Its a great example of how understanding the invariants and rules that govern your problem domain will help you write faster and simpler code.