hckrnws
My 1988 submission to the International Obfuscated C Code Contest was this maze generator:
char*M,A,Z,E=40,J[40],T[40];main(C){for(*J=A=scanf(M="%d",&C);
-- E; J[ E] =T
[E ]= E) printf("._"); for(;(A-=Z=!Z) || (printf("\n|"
) , A = 39 ,C --
) ; Z || printf (M ))M[Z]=Z[A-(E =A[J-Z])&&!C
& A == T[ A]
|6<<27<rand()||!C&!Z?J[T[E]=T[A]]=E,J[T[A]=A-Z]=A,"_.":" |"];}
Note that the constant 27 assumes a 31-bit random number generator, and needs to be replaced with 11 if rand() produces 15-bit numbers instead. Modern C compilers don't allow constant strings to be overwritten, which can be avoided by changing the first line to
char M[3],A,Z,E=40,J[40],T[40];main(C){for(*J=A=scanf("%d",&C);
> Modern C compilers don't allow constant strings to be overwritten
One compiler available on contemporary Linux distributions still able to handle not so modern C is Fabrice Bellard's Tiny C Compiler, tcc.
Does it successfully compile the above program?
Yes, it does (with the expected warnings). Thanks for the fun!
If generating left to right, it seems to me the condition almost always hold that both the number of empty cells and filled cells to the immediate left and to the lower left, directly underneath, and lower right (four known neighbors at the time of generation) is always equal to two, except occasionally you get three filled, but never four, which would create a thick wall. I’m not sure about the left edges, those would only have two known neighbors (directly underneath and lower right)Al So maybe with a good intial rowthat’s all you need to do.
For Commodore there is this classic recipe [1] for infinite maze:
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
python3 -c 'import random, time, itertools; any(time.sleep(0.01) or print(random.choice("\u2571\u2572"), end="", flush=True) for x in itertools.repeat(None))'Note this doesn't guarantee passable maces.
Looking at the animation, I feel I have a pretty good idea on how to go about implementing an endless scrolling random maze, without reading any paper, studying anyone's code.
It looks like in every horizontal hallway (run of adjacent empty squares), there is at least one exit in the next row; i.e. at least one empty square.
Furthermore, there is definitely an even-odd row alternating pattern. The odd rows have more horizontal passages (runs of empty squares). The even rows have more single-square passages, as if connecting the odd rows. It's not entirely consistent across the field. It might be the result of some game-of-life like rules, like when multiple through-passages are clumped close together in the previous row, a connecting hallway will appear. Or, no, here is the thing. The algorithm avoids consecutive thick walls. So that is to say, if a given row has two or more adjacent walls ### there will be at most wall there in the next row. Nowhere in the maze animation do you see this:
##
##
###
###
#
#
#### ## # #### # ###
#### ## # #### # ###
########################### ;; start with a filled row
#### ## # #### # ###
#### #### ########## # ####
#### ## # #### # ###
# # # ## ##### ### # ##
#### ## # #### # ### (a)
# # # ## ##### ### # ##
###########################
#### ## # #### # ### (b)
# # # ## ##### ### # ##
## # # ## ##### #### # ## #
#### ## # #### # ### (c)
# # # ## ##### ### # ##
## # # # # # # # #
#### ## # #### # ### (a)
# # # ## ##### ### # ##
## # # # # # # # #
###########################
#### ## # #### # ### (a)
# # # ## ##### ### # ##
## # # # # # # # #
## # # ## # ## ## ##### # #
#### ## # #### # ### (c)
# # # ## ##### ### # ##
## # # # # # # # #
# # # ## # ## ## ##### # #
#### ## # #### # ### (a)
# # # ## ##### ### # ##
## # # # # # # # #
# # # ## # ## ## ##### # #
###########################
#### ## # #### # ### (b)
# # # ## ##### ### # ##
## # # # # # # # #
# # # ## # ## ## ##### # #
## # # ## # ## ## ##### # #
#### ## # #### # ### (c)
# # # ## ##### ### # ##
## # # # # # # # #
# # # ## # ## ## ##### # #
## # # # # # # # # #
#### ## # #### # ### (a)
# # # ## ##### ### # ##
## # # # # # # # #
# # # ## # ## ## ##### # #
## # # # # # # # # #
###########################
#### ## # #### # ### (b)
# # # ## ##### ### # ##
## # # # # # # # #
# # # ## # ## ## ##### # #
## # # # # # # # # #
## # ## # # ### # ##### # #
#### ## # #### # ### (c)
# # # ## ##### ### # ##
## # # # # # # # #
# # # ## # ## ## ##### # #
## # # # # # # # # #
# # ## # # ### # ##### # #
We need one more behavior, so that the adjacent passages can merge together. For instance, sometimes if we have _#_ (space hash space), we replace the hash with a space. Or something like that.
An important observation is that not only do parallel walls not occur, but parallel passages do not occur. I.e we don't see two spaces going to two spaces:
## ##
## ##
The actual algorithm is somewhat different, and documented here: https://intarch.ac.uk/journal/issue59/3/full-text.html
What you have described feels like a variant of Eller’s algorithm: https://weblog.jamisbuck.org/2010/12/29/maze-generation-elle...
shameless self promotion - I felt into a rabbit hole about mazes a couple of years ago:
https://medium.com/swlh/how-to-create-a-maze-with-javascript...
Crafted by Rajat
Source Code