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

21–30 of 33 posts

Re: Generating Mazes

#21

Post by at_a_remove »

Somewhat adjacent, I have been interested in generating mazes of the "cave" form. Many algorithms exist here, even some cellular automata approach for a more realistic simulationist approach. However, I have been kicking around ideas to take the very irregular results from that sort of tack and then abstract them back to a nodes-and-edges parallel data structure. Which is to ask, in this grid of filled in or empty cells, which gaps are the caves, and which are the twisty little passages?

At least for games, I am starting to lean toward the idea that humans like the simulationist approaches as "feeling right," but the abstract graph is better for the machines, and that the ability to start with one and then produce the other is where we will eventually go.

Re: Generating Mazes

#22

Post by fjfaase »

Maze generation is a fascinating topic. I also played with different maze generating algorithms and wrote a program [1] that generates SVG files that can be send to a laser-cutter. I used it to do some investigations on the statistics of different types of algorithms. I have some fascination with mazes that only have rooms with either one or three exits [2]. I used the program to create an kind of inverted maze with different heights which now hangs in my living room. [3]

[1] https://github.com/FransFaase/MazeGen

[2] https://www.iwriteiam.nl/counting.html#paper

[3] https://www.iwriteiam.nl/D2006.html#21

Re: Generating Mazes

#24

Post by devnull3 »

bollu wrote: post #19
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?

Under pressure, I suggested the following:

1. Only one solution (or path in this case) should exist

2. No loops (meaning the valid solution does not cross it-self)

3. The length of false path from correct path should not be more than 4

Re: Generating Mazes

#25

Post by remram »

tromp wrote: post #11

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…

This segfaults for me somehow.

Re: Generating Mazes

#26

Post by tromp »

remram wrote: post #25
tromp wrote: post #11

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…

This segfaults for me somehow.

See https://tromp.github.io/pearls.html for suggested changes to make thus run with modern compilers.

Re: Generating Mazes

#27

Post by kragen »

YeGoblynQueenne wrote: post #20
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: ■…

this is awesome! and the maze it produced looks great! yeah, the halving-dimensions thing is a form of what i did in the golang thing i linked

i'm pretty comfortable with prolog, and i'll take a look at your code later :)

Re: Generating Mazes

#28

Post by YeGoblynQueenne »

kragen wrote: post #27
YeGoblynQueenne wrote: post #20

Earlier quoted context omitted.

>> 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: ■…

this is awesome! and the maze it produced looks great! yeah, the halving-dimensions thing is a form of what i did in the golang thing i linked i'm pretty comfortable with prolog, and i'll take a look at your code later :)

Oh, right, of course you are! I thought I recognised your username :)
Post reply on HN