The Endless Maze algorithm (Atari 2600)

https://www.gamesthatwerent.com/2024/01/the-endless-maze-algorithm/

by todsacerdoti • 2 years ago

43 11 2 years ago

kazinator• 2 years ago

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:

  ##
  ##
  ###

(Assume we are scrolling upward, like a terminal, adding new rows at the bottom). You don't see consecutive thick walls. Always something like thisL

  ###
   #
   #

So for instance say we have this row:

  #### ##     # #### #    ###

Firstly, we ensure that all our spaces have at least one exit:

  #### ##     # #### #    ###
  ###########################  ;; start with a filled row

Now punch the holes:

  #### ##     # #### #    ###
  #### #### ########## # ####

Now, eliminate thick walls, careful not to make any new holes:

  #### ##     # #### #    ###
  #  # # ## #####  ### # ##

Now repeat:

  #### ##     # #### #    ###  (a)
  #  # # ## #####  ### # ## 
  ###########################

  #### ##     # #### #    ###  (b)
  #  # # ## #####  ### # ## 
  ## # # ## ##### #### # ## #
 
  #### ##     # #### #    ###  (c)
  #  # # ## #####  ### # ## 
  ## # # #  #     #    #  # #

Keep going:

  #### ##     # #### #    ###  (a)
  #  # # ## #####  ### # ## 
  ## # # #  #     #    #  # #
  ###########################

  #### ##     # #### #    ###  (a)
  #  # # ## #####  ### # ## 
  ## # # #  #     #    #  # #
  ## # # ## # ## ## ##### # #

Notice that here we have very little to do for step (c); only one parallel thick wall has occurred:

  #### ##     # #### #    ###  (c)
  #  # # ## #####  ### # ## 
  ## # # #  #     #    #  # #
   # # # ## # ## ## ##### # #

Then:

  #### ##     # #### #    ###  (a)
  #  # # ## #####  ### # ## 
  ## # # #  #     #    #  # #
   # # # ## # ## ## ##### # #
  ###########################

  #### ##     # #### #    ###  (b)
  #  # # ## #####  ### # ## 
  ## # # #  #     #    #  # #
   # # # ## # ## ## ##### # #
  ## # # ## # ## ## ##### # #

  #### ##     # #### #    ###  (c)
  #  # # ## #####  ### # ## 
  ## # # #  #     #    #  # #
   # # # ## # ## ## ##### # #
  ## # #  # # #   # #     # #


  #### ##     # #### #    ###  (a)
  #  # # ## #####  ### # ## 
  ## # # #  #     #    #  # #
   # # # ## # ## ## ##### # #
  ## # #  # # #   # #     # #
  ###########################

  #### ##     # #### #    ###  (b)
  #  # # ## #####  ### # ## 
  ## # # #  #     #    #  # #
   # # # ## # ## ## ##### # #
  ## # #  # # #   # #     # #
  ## # ## # # ### # ##### # #

  #### ##     # #### #    ###  (c)
  #  # # ## #####  ### # ## 
  ## # # #  #     #    #  # #
   # # # ## # ## ## ##### # #
  ## # #  # # #   # #     # #
  #  # ## # # ### # ##### # #

The trouble is that we have parallel, disjoint passages.

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:

  ##  ##
  ##  ##

In a two space hallway, we can carve out at most one exit into the next row. So if we then remove additional walls to make spaces, we have to keep that in mind; don't do it in such a way that parallel passages would arise.

bradrn• 2 years ago

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...

tromp2• 2 years ago

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,"_.":" |"];}

expecting a number on stdin and then generating a maze of that height line by line. For a negative number it will effectively produce an endless maze. As it turned out I had independently rediscovered Eller's algorithm (https://weblog.jamisbuck.org/2010/12/29/maze-generation-elle...).

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);

The program is explained in detail in https://tromp.github.io/maze.html

guenthert2• 2 years ago

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.

tromp2• 2 years ago

Does it successfully compile the above program?

toppy• 2 years ago

For Commodore there is this classic recipe [1] for infinite maze:

10 PRINT CHR$(205.5+RND(1)); : GOTO 10

[1] https://10print.org/

mkesper• 2 years ago

Note this doesn't guarantee passable maces.

teddyh• 2 years ago

  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))'

y42• 2 years ago

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...

DrFalkyn• 2 years ago

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.

The Endless Maze algorithm (Atari 2600)

Related Stories