Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Generating Mazes

healeycodes.com

Post reply on HN
Print view View original

11–20 of 33 posts

Re: Generating Mazes

#11

Post by tromp »

With my 1988 IOCCC entry

    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
discussed in more detail in Don Libes' "Obfuscated C and Other Mysteries" [1], I turned out to have rediscovered Eller's algorithm, which only keeps one line of the maze in memory.

[1] https://tromp.github.io/maze.html

Re: Generating Mazes

#13

Post by devnull3 »

Maze(s) triggers PTSD in me. I was asked to write a code to generate one using a 100x100 grid in an Google interview in 40 min such that it was "fair". It was for L6/L7 (IC) position. I wrote a working code and the interviewer even acknowledged that I had atleast have a working code compared to others. The actual time I had was 30 min as 10 min included upfront discussion about what "fair" means and some time after-the-code discussion on improvements.

I was rejected with lean-no-hire (or weak-no-hire .. I don't remember the exact term but basically not a strong reject).

Re: Generating Mazes

#14

Post by jnurmine »

I was very young when I first saw the Commodore C64 maze generation trick using forward slash and backward slash. The characters are randomly selected and just printed one after another, the result is a maze-like pattern.

Such a maze is probably not a real maze, not solvable always (I don't know). But it was mind-boggling back then, and still is.

There's a video here: https://www.youtube.com/watch?v=Ym2nimY1hs0

Re: Generating Mazes

#15

Post by blue1 »

jnurmine wrote: post #14

I was very young when I first saw the Commodore C64 maze generation trick using forward slash and backward slash. The characters are randomly selected and just printed one after another, the result is a maze-like pattern. Such a maze is probably not a real maze, not solvable always (I don't know). But it was mind-boggling back then, and still is. There's a video here: https://www.youtube.com/watch?v=Ym2nimY1hs0

There's a whole book devoted to that, titled "10 PRINT CHR$(205.5+RND(1));:GOTO 10"

Re: Generating Mazes

#16

Post by jnurmine »

blue1 wrote: post #15
jnurmine wrote: post #14

I was very young when I first saw the Commodore C64 maze generation trick using forward slash and backward slash. The characters are randomly selected and just printed one after another, the result is a maze-like pattern. Such a maze is probably not a real maze, not solvable always (I don't know). But it was mind-boggling back then, and still is. There's a video here: https://www.youtube.com/watch?v=Ym2nimY1hs0

There's a whole book devoted to that, titled "10 PRINT CHR$(205.5+RND(1));:GOTO 10"

Nice, it's a free download too. Thanks!

Re: Generating Mazes

#17

Post by YeGoblynQueenne »

efilife wrote: post #10

I don't understand. The article is about maze generation and it only talks about traversing predefined mazes. I had a similar thought after reading an article about generating sudokus. Like they were alreadt generated and the article was about creating a solver. I am surely missing something, what's the part I don't understand? Ok, after rereading I think I'm starting to understand. The walls of the cells are generat…

Yeah, it's confusing. The standard maze generation algorithms start with a fully-blocked grid where each cell has four walls, then proceed to punch holes through one wall at a time. This is basically the same procedure as solving a maze, except when solving a maze you only move between cells that already have holes punched between them. So a solver is really a generator run backwards.

Think of it as an automaton: it can both accept and generate a string. The string here is the path through the maze.

But I think the main, shall we say, contribution of the article is the method they use to find the farthest two points on a maze, that they then set as the entry and exit point of the maze. It's at the end of the article, after the discussion of their preferred method to generate a maze.

Re: Generating Mazes

#19

Post by bollu »

devnull3 wrote: post #13

Maze(s) triggers PTSD in me. I was asked to write a code to generate one using a 100x100 grid in an Google interview in 40 min such that it was "fair". It was for L6/L7 (IC) position. I wrote a working code and the interviewer even acknowledged that I had atleast have a working code compared to others. The actual time I had was 30 min as 10 min included upfront discussion about what "fair" means and some time after-t…

what definition of "fair" was reached upon?

Re: Generating Mazes

#20

Post by YeGoblynQueenne »

kragen wrote: post #6

mike bostock did this fantastic visualization of maze generation algorithms a few years ago, including wilson's algorithm but not aldous–broder: https://bost.ocks.org/mike/algorithms/#maze-generation i wrote a minimal roguelike a couple of weeks ago in forth: http://canonical.org/~kragen/sw/dev3/wmaze.fs (2-minute asciicast at https://asciinema.org/a/672405 , or you can run it in gforth) and tried to generate the lev…

>> however, in rogue, and in wmaze, walls occupy a whole grid cell.

I think I know what you mean and I had the same kind of problem: pretty much evey maze-generation algorithm assumes the map is initially a grid of cells with four walls and proceeds by removing those walls one-by-one, systematically.

The problem you had, and that I had in my project, is that your grid is made up of single characters, say like this:

  ■ ■ ■ ■
  ■ ■ ■ ■
  ■ ■ ■ ■
  ■ ■ ■ ■
Where "■" is a wall. It is not clear how you can "remove a wall" from this grid. If you just replace each wall character with a floor character, say, "□", you have removed _four_ walls, not just one. Then if you use any of the standard maze-generation algos you end up with "maze snow", like this:

  □ □ □ ■ □ □ □ □ 
  □ ■ □ □ □ ■ □ ■ 
  □ □ □ ■ ■ □ ■ □ 
  □ ■ □ □ □ □ □ □ 
  □ □ □ ■ □ ■ □ ■ 
  □ ■ □ □ □ ■ □ □ 
  □ □ □ ■ □ □ □ ■ 
  □ ■ □ □ □ ■ □ □
One way to work around this that I found online is to implicitly pad every wall with an extra character, so that for example, if you carved a two-step path starting at the top-left corner of the fully blocked maze above and going to the right, it would look like this:

  ■ ■ ■ ■
  □ □ ■ ■
  ■ ■ ■ ■
  ■ ■ ■ ■
Instead of like this:

  □ □ ■ ■
  ■ ■ ■ ■
  ■ ■ ■ ■
  ■ ■ ■ ■
I didn't like that because it effectively halves the dimensions of every maze. So I had a cunning plan and came up with an alternative that models an agent moving through a grid representing a maze and "discovering" the maze as it goes, as usual, but with some constraints that ensure the maze never loops back to itself. I'm working in Prolog so you might find it as hard to read my code as I found it to read your Forth :) but it's here anyway:

https://github.com/stassa/ijclr_2024_experiments/blob/6cf3cc...

The idea is that, at any timestep, an agent navigating a grid is observing the following cells, with the agent centered on 1/1:

  0/0  1/0  2/0
  0/1 >1/1
Where the cells in this 3 × 3 grid (I call it an "observation matrix") are populated at random, with wall or floor tiles, which may result e.g. in an observation matrix like this:

  □ ■ ■  
  □ @ ■ 
  ■ ■ ■
With the agent as a '@'. Now it's obvious that if the agent moves one step up it will create a four-cell open-space, a "plaza", like so (there's a floor tile under the agent now):

  □ @ ■  
  □ □ ■ 
  ■ ■ ■
So in this case you don't let the agent move up, only right, or down (it probably came from the left so you don't let it go back that way or it will enter a military oscillation: right-left-right-left-right... ). In a similar way you can avoid looping (it gets a bit complicated but you can find the logic in my comments in maze_generator.pl linked above).

Then it's a matter of moving through a fully-blocked initial grid cell-by-cell and laying down "observation matrices" at random, while respecting the anti-plaza and anti-looping constraints. You have to restart the process from a wall cell in a "hunt-and-kill" fashion every time it reaches a dead end to complete the maze but you get mazes that look like this (for a 40 × 40 maze):

  □ ■ □ □ □ □ ■ ■ □ □ □ ■ ■ ■ ■ □ □ □ ■ □ □ □ □ □ □ □ □ ■ ■ □ □ □ □ □ ■ □ □ □ □ □ 
  □ ■ □ ■ ■ □ ■ □ □ ■ □ □ ■ ■ □ □ ■ □ □ □ ■ ■ ■ ■ ■ ■ □ ■ □ □ ■ ■ ■ □ ■ □ ■ ■ □ ■ 
  □ ■ □ ■ ■ □ □ □ ■ ■ ■ □ ■ □ □ ■ ■ ■ □ ■ ■ □ □ □ □ ■ □ □ □ ■ ■ □ ■ □ ■ ■ ■ □ □ □ 
  □ ■ □ □ ■ □ ■ ■ ■ □ ■ □ ■ □ ■ ■ □ ■ □ ■ □ □ ■ ■ □ ■ ■ ■ ■ ■ □ □ ■ □ □ ■ □ □ ■ □ 
  □ ■ ■ □ ■ ■ ■ □ □ □ ■ □ □ □ ■ ■ □ ■ □ ■ ■ □ □ ■ ■ ■ □ □ □ ■ □ ■ ■ ■ □ □ □ ■ ■ □ 
  □ ■ ■ □ □ ■ □ □ ■ □ ■ ■ ■ □ □ □ □ ■ □ □ ■ ■ □ □ ■ ■ □ ■ □ □ □ □ ■ ■ ■ ■ ■ ■ ■ □ 
  □ □ ■ ■ □ ■ □ ■ ■ □ □ □ ■ ■ ■ ■ ■ ■ ■ □ □ ■ ■ □ □ ■ ■ ■ ■ □ ■ □ □ □ □ □ ■ ■ ■ □ 
  ■ □ □ ■ □ □ □ ■ ■ ■ ■ □ □ ■ ■ □ □ □ ■ ■ □ □ ■ ■ □ □ ■ ■ □ □ ■ ■ ■ ■ ■ □ □ ■ ■ □ 
  ■ ■ □ ■ ■ ■ □ ■ □ □ ■ ■ □ ■ □ □ ■ □ ■ ■ ■ □ □ ■ ■ □ □ ■ □ ■ ■ ■ □ □ ■ ■ □ ■ □ □ 
  □ □ □ □ □ □ □ ■ ■ □ □ □ □ ■ □ ■ ■ □ ■ □ ■ ■ □ □ ■ ■ □ ■ □ □ □ ■ □ ■ ■ □ □ □ □ ■ 
  □ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ □ ■ ■ □ ■ □ □ ■ ■ □ □ ■ □ ■ ■ ■ □ □ □ ■ ■ ■ ■ ■ ■ ■ 
  □ ■ ■ □ □ □ □ □ ■ □ □ □ □ ■ E ■ ■ □ ■ ■ □ □ ■ ■ □ ■ □ □ ■ ■ ■ ■ □ □ ■ ■ □ ■ □ □ 
  □ ■ □ □ ■ ■ ■ □ □ □ ■ ■ □ ■ □ ■ ■ □ ■ ■ ■ □ □ ■ □ ■ ■ □ □ □ ■ ■ ■ □ □ ■ □ □ □ ■ 
  □ ■ □ ■ ■ ■ ■ ■ ■ ■ ■ ■ □ □ □ □ ■ □ □ □ ■ ■ □ □ □ □ ■ ■ ■ □ □ □ ■ ■ □ ■ ■ □ ■ ■ 
  ■ ■ □ ■ □ ■ ■ □ □ □ □ ■ ■ ■ ■ ■ ■ □ ■ □ □ □ □ ■ ■ ■ ■ ■ □ □ ■ □ ■ ■ □ □ □ □ □ □ 
  □ □ □ ■ □ □ □ □ ■ □ ■ ■ ■ □ □ □ ■ ■ ■ ■ ■ ■ ■ ■ □ ■ ■ □ □ ■ ■ □ □ ■ ■ ■ ■ ■ ■ □ 
  □ ■ ■ ■ □ ■ ■ ■ ■ □ □ ■ □ □ ■ □ □ ■ □ □ □ ■ ■ □ □ □ □ □ ■ ■ ■ ■ □ □ □ □ ■ ■ ■ □ 
  □ ■ □ ■ □ □ ■ □ ■ ■ □ □ □ ■ ■ ■ □ □ □ ■ □ ■ □ □ ■ □ ■ ■ ■ □ □ ■ □ ■ ■ □ □ ■ □ □ 
  □ ■ □ ■ ■ □ □ □ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ □ ■ □ ■ ■ □ □ ■ ■ ■ □ ■ □ ■ ■ ■ □ ■ □ ■ 
  □ ■ □ □ ■ ■ ■ □ □ □ ■ □ □ ■ ■ □ □ ■ ■ □ □ ■ □ □ ■ ■ □ □ ■ ■ □ □ □ □ □ ■ □ ■ □ □ 
  □ ■ ■ □ □ □ ■ □ ■ □ □ □ ■ ■ □ □ ■ ■ □ □ ■ ■ ■ □ □ ■ ■ □ □ ■ ■ ■ ■ ■ □ ■ □ ■ ■ □ 
  ■ ■ ■ ■ □ ■ ■ ■ ■ ■ ■ □ ■ □ □ ■ ■ ■ □ ■ ■ ■ ■ ■ □ □ ■ ■ □ □ □ □ □ ■ □ ■ □ ■ □ □ 
  □ □ ■ ■ □ ■ □ □ □ □ ■ □ □ □ ■ ■ ■ □ □ □ ■ ■ ■ ■ ■ □ □ ■ ■ ■ ■ ■ □ ■ ■ ■ □ ■ □ ■ 
  ■ □ □ □ □ ■ □ ■ ■ □ ■ ■ ■ □ □ □ ■ ■ ■ □ □ □ □ □ ■ ■ □ □ ■ □ □ ■ □ □ ■ ■ □ ■ □ ■ 
  ■ ■ □ ■ □ ■ □ □ ■ □ □ □ ■ ■ ■ □ ■ □ ■ ■ ■ □ ■ □ □ ■ ■ □ □ □ ■ ■ ■ □ □ ■ ■ ■ □ □ 
  □ □ □ ■ ■ ■ ■ □ ■ ■ ■ □ □ □ ■ □ □ □ □ □ ■ □ ■ ■ S □ ■ ■ ■ □ □ □ ■ ■ □ □ □ ■ ■ □ 
  □ ■ ■ ■ ■ □ □ □ ■ □ ■ ■ □ ■ ■ ■ ■ ■ ■ □ ■ □ ■ ■ ■ □ □ □ ■ ■ ■ □ ■ ■ ■ ■ □ □ □ □ 
  □ ■ ■ □ □ □ ■ ■ ■ □ □ ■ □ □ □ □ □ □ ■ □ ■ □ □ □ ■ □ ■ □ ■ □ ■ □ □ □ ■ ■ □ ■ ■ ■ 
  □ ■ □ □ ■ ■ ■ □ □ □ ■ ■ ■ □ ■ ■ ■ □ ■ □ ■ ■ □ ■ ■ □ ■ □ □ □ ■ ■ ■ □ □ ■ ■ ■ ■ □ 
  □ ■ □ ■ ■ □ ■ ■ □ ■ ■ □ ■ □ ■ □ ■ ■ ■ □ ■ □ □ □ ■ □ ■ □ ■ □ □ ■ ■ ■ □ □ ■ ■ □ □ 
  □ ■ □ □ ■ □ ■ ■ □ ■ ■ □ □ □ □ □ ■ □ □ □ ■ ■ ■ □ ■ ■ ■ □ ■ ■ □ □ ■ ■ ■ □ □ ■ □ ■ 
  □ ■ ■ □ □ □ ■ □ □ □ ■ ■ ■ ■ ■ □ □ □ ■ ■ ■ □ ■ □ □ □ ■ □ □ ■ ■ □ ■ □ ■ ■ □ ■ □ ■ 
  □ □ ■ ■ ■ □ ■ □ ■ □ □ ■ □ □ ■ ■ ■ ■ ■ □ □ □ ■ □ ■ □ ■ ■ □ □ ■ □ ■ □ ■ ■ □ ■ □ □ 
  ■ □ □ □ ■ □ □ □ ■ ■ □ ■ ■ □ ■ □ ■ □ □ □ ■ □ ■ ■ ■ □ □ ■ ■ □ ■ □ □ □ ■ ■ □ ■ ■ □ 
  ■ ■ □ ■ ■ ■ ■ ■ ■ ■ □ □ □ □ ■ □ □ □ ■ ■ ■ □ □ ■ ■ ■ □ □ ■ ■ ■ □ ■ □ □ ■ □ □ ■ □ 
  ■ ■ □ □ □ □ □ □ □ ■ ■ ■ ■ □ ■ ■ □ ■ ■ □ ■ ■ □ □ □ ■ ■ □ □ □ ■ ■ ■ ■ □ ■ ■ □ □ □ 
  ■ ■ □ ■ □ ■ ■ ■ □ □ □ □ ■ □ □ □ □ ■ □ □ □ ■ ■ ■ □ □ ■ ■ ■ □ □ ■ ■ □ □ □ ■ ■ ■ □ 
  ■ □ □ ■ □ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ □ ■ ■ ■ □ ■ ■ □ □ □ ■ ■ □ □ ■ ■ ■ ■ ■ □ ■ □ 
  □ □ ■ ■ □ □ ■ □ □ □ ■ ■ □ □ □ □ ■ ■ □ ■ □ □ □ ■ ■ □ ■ □ □ ■ ■ □ □ ■ ■ □ □ □ ■ □ 
  □ ■ ■ ■ ■ □ □ □ ■ □ □ □ □ ■ ■ □ □ □ □ □ □ ■ □ □ □ □ ■ ■ □ □ ■ ■ □ □ □ □ ■ □ □ □
Oh and you randomly place the S[tart] and E[nd] tiles of course. And you know generated mazes are always solvable because you solve them to generate them (like with DFS etc).

But note that in the maps you get this way there are blocked-out regions, "clumps" of wall tiles. There may be a better set of constraints that gets rid of those, but the result was good enough for my needs and I didn't bother.

And of course you can use the same technique to solve a maze and even do a bit of SLAM (Simultaneous Localisation and Mapping) by placing observation matrices in an expanding grid as the agent moves in an initially unseen map. OK, TMI, I'm stopping here.

Post reply on HN