After the ultra-simple "Hello, World!" program, another program programmers like to program early on to learn a language is a maze generator. There are a lot of ways to generate a maze that is both "complete" and "perfect." Complete in this sense means that the entire area of the maze is filled in. No voids or missing areas. Perfect means that there is always one and only one path from any one place in the maze to any other. No loops or walled off areas. I personally like a few loops, but that's just me. One way to do this is employ a DFS or depth first search. Start somewhere and pick a random neighbor that hasn't been visited yet. Move there and pick another random neighbor. If you find yourself in a dead end with no unvisited neighbors, backtrack until you find an open area and try again. When you've backtracked all the way back to your starting point, you're done. I suppose it's called depth first search because you go as deep as you can into the maze before you backtrack and try other options.The hard part of the DFS algorithm is the backtracking. In order to implement that, you have to use recursion, a stack, a list of visited cells, or leave breadcrumbs in the maze itself. I prefer the last method because it takes the least memory, is probably easiest to implement, and it was the first method I was exposed to way back in the ancient 1980's. For this article, I wondered if there was another way. It turns out, there is. I found I could use simple iteration. I had an old C college instructor I would irritate by pointing out that I could implement simple iteration for problems that he insisted required the use of recursion. I like iteration. `Repeat` ` done% = True` ` For y% = 1 To my% - 1 Step 2 : For x% = 1 To mx% - 1 Step 2` ` If maze(x%, y%) > 0 Then` ` d% = Rand(4)` ` For i% = 1 To 4` ` Inc d% : If d% > 3 Then d = 0` ` nx% = x% + dx%(d%) * 2 : ny% = y% + dy%(d%) * 2` ` If nx% > 0 And nx% < mx% And ny% > 0 And ny% < my% Then` ` If maze%(nx%, ny%) = 0 Then` ` maze%((x% + nx%) / 2, (y% + ny%) / 2) = 255` ` maze%(nx%, ny%) = 255` ` x% = nx% - 2 : y% = ny%` ` done% = False` ` Exit For` ` EndIf` ` EndIf` ` Next i%` ` EndIf` ` Next x% : Next y%` `Until done%` This is the heart of the code. By the time your program has reached this point, it's already dimensioned an array for the maze% of size mx% by my%. I use the value 0 for the solid rock out of which the maze will be carved and 255 for the open paths. It's also picked a random starting point and carved out that first cell. What this program does is iterates (cycles through all possible values) through the maze and finds a cell that's been carved out. Like the depth first search described above, it then picks an unvisited neighbor and carves a path to it. When it carves itself into a corner, however, it doesn't backtrack. Instead, it goes back to iterating through the maze until it finds another "jumping off" point and starts all over. When the program can iterate through the entire maze without finding a jumping off point, it knows that it's done. Here's a breakdown: The routine is wrapped in a REPEAT UNTIL loop. This simply means that the routine will repeat until a certain condition is met, in this case that the variable done% is found to be set to true or at least a non-zero value. In fact, we immediately set done% to true. Why doesn't the routine exit immediately? Well, the value of done% isn't checked until the end of the loop, so the routine will execute at least once. Once in the routine, if certain conditions are met done% is given the value of false or zero. The loop continues! Next we have a FOR NEXT loop. Actually, we have two of them, one nested inside the other. This is the part that does the iteration. x% and y% values cycle through so that the entire maze% is covered. In this case, x% and y% values go from 1 to 1 less than the size of the maze in steps of 2. So, if the size of the maze% is 10, x% and y% values will both go 1,3,5,7,9. The values at 0 and the max size of the maze are never visited because we need solid walls around the maze. For each x% and y%, we check to see if there's an opening in maze%(x%,y%), meaning any value higher than the 0 we decided is solid rock. If not, we just iterated to the next x% and y%. If we find an opening, we pick a random direction d%. We have another FOR NEXT loop where i% goes from 1 to 4. This is so we can try all 4 directions. Once inside this loop, d% is incremented (we add 1) and if it goes higher than 3, wraps back around to 0. This lets us check all 4 possible d% values but start at a random direction so the maze doesn't turn out the same every time. For each direction, we generate new x% and y% values called nx% and ny% based on delta values held in the arrays dx% and dy%. For example, dx%(1)=-1 and dy%(1)=0 would mean that for direction d%=1, we'd move one space up and no spaces over, or North. We multiply these delta values by 2 because we want to leave rock walls between our maze paths. Next, we check to make sure that nx% and ny% are still within the confines of our maze. It would be no good to generate a maze if we carved paths outside of it. If the new area we're looking at is solid rock, or maze%(nx%,ny%)=0, it's time to carve a path to it. We set the new location to 255 or carved path. If we add the old location coordinates and the new location coordinates together and divide by two, that gives us the cell in between, which we also set equal to 255. We've just carved a new pathway. Now, in order to keep moving down this path, we need to update our x% and y% coordinates to our new nx% and ny%. That way, next time around in the iteration, the routine will look at the end of our new pathway and not somewhere else. Since x% will be incremented by 2 when we reach the end of this segment, we'll set x% to 2 less than nx% (x% = nx% - 2) so when we reach the Next x% statement, it will put x% back to the value we want. Once that's done, we have to tell the routine that we're not done yet by setting done% to false. Since we've found a new path and don't need to check other directions this time, we can exit out of the i% FOR NEXT loop with the command EXIT FOR. Eventually, the routine will iterate through all possible x% and y% values. If it found one or more new paths to carve, done% will be false and it will iterate them all again. Eventually, the maze will be completely filled in. The program attached at the bottom of this page includes a lot more than just this routine, including code to display the maze as its being generated. This code will be discussed in a later article. In the mean time, feel free to play around with it. Might I suggest first changing the value of the SLEEP command to make the maze generate slower or more quickly. Take it out altogether and see that, on my system at least, the maze generates so fast it seems to spring forth fully formed. Not too bad for a clumsy, inefficient, iterative approach! |

GFA BASIC 32 > How To >