Maze Algorithms (1997) • Hacker News Board

Re: Maze Algorithms (1997)

#21

Post by fc417fc802 » Fri, Apr 03, 2026, 12:56 PM UTC

tasuki wrote: post #20

fc417fc802 wrote: post #18

Earlier quoted context omitted.

It really depends on what you mean by "interesting". The algorithms that you're complaining produce uninteresting results are minimal cores for the purpose of illustrating the theory. Simply don't use them in isolation. A perfect maze is more difficult to generate than one with loops or multiple solutions. Assuming a simple two tone block representation simply convert some walls to pathways at random. Given a more co…

> It really depends on what you mean by "interesting". Yes. I haven't gotten far enough in my journey to be able to formulate that. The first insight is that the details of branching make a difference: humans don't pick the routes with the same likelihood at a crossroad. Loops seem fine for the wrong paths looping onto other wrong paths: having to backtrack is somewhat unsatisfying, plus loops make the solving less m…

So you only want dead ends to have loops? You might try computing the depth of each node, marking the solution, and then assigning each branch off of the solution a unique color.

At that point knocking out walls only within the same color won't interfere with the solution.

Alternatively you could take care to track depth and knock out walls between different colors only when the total resulting path length would be greater than the existing solution.

Just go try stuff! All of the examples on Bostock's page that I linked earlier link to JS implementations that you could fork.

Re: Maze Algorithms (1997)

#22

Post by fjfaase » Fri, Apr 03, 2026, 1:13 PM UTC

tromp wrote: post #9

fjfaase wrote: post #2

Are there also algorithms for (incremental) generation of infinite mazes?

The linked-to page mentions: > Infinite length Mazes: It's possible to create an infinitely long Maze (a finite number of columns by as many rows as you like) by only keeping part of the Maze in memory at a time and "scrolling" from one end to the other, discarding earlier rows while creating later rows. > An easier way to make an infinite Maze is with Eller's or the Sidewinder algorithms, as they already make Mazes…

Great idea. However it is infinite in one direction. Could be made infinite in two directions (I guess) by extending along a diagonal line that get long with each step. Probably could also make it infinite in all directions with a square that gets extended with each step. However, that would mean that if one walks away from the origin, the maze has to be generated in all directions. For practical applications it would be nice to only generate the part of the maze that is 'visible' from a certain point of view (either from the top or while walking inside the maze up to a certain distance).

Re: Maze Algorithms (1997)

#23

Post by fjfaase » Fri, Apr 03, 2026, 1:15 PM UTC

tasuki wrote: post #10

fc417fc802 wrote: post #5

Earlier quoted context omitted.

What would it mean for a maze to be infinite? It seems to me that a key part of the concept is having a goal to reach. Although I guess you could have an infinitely large map and an algorithm that guaranteed connectivity. Infinite ways to fail to reach the goal. But I doubt there would be much practical benefit. To actually answer your question it should be fairly easy to convert nearly any existing algorithm to cove…

I'm looking for such an algorithm, with intermediate goals: you start at the bottom, go up, and as you reach the goal, more maze appears. I left out some unimportant details :)

I maze that grows in one direction can be generated with Eller's or the Sidewinder algorithms (as also mentioned by the user John Tromp in one of the other replies).

Re: Maze Algorithms (1997)

#24

Post by fjfaase » Fri, Apr 03, 2026, 1:17 PM UTC

contravariant wrote: post #12

fjfaase wrote: post #2

Are there also algorithms for (incremental) generation of infinite mazes?

I'd probably go with something like the wave function collapse algorithm. It should be possible to make it generate trees with somewhat uniform probability.

Interesting idea, but the problem is that being connected and being non-cyclic (properties you want for a perfect maze where you can reach every location and where there is exactly one route between every two locations) are global conditions that are difficult to implement with function collapse algorithm that are local.

Re: Maze Algorithms (1997)

#25

Post by kdfjgbdfkjgb » Fri, Apr 03, 2026, 1:20 PM UTC

tasuki wrote: post #14

potro wrote: post #13

Earlier quoted context omitted.

Nice game. Thank you for sharing it. It brought some joy to my morning.

Thanks! I haven't really shared it with many people yet - if you have any feedback I'd be happy to hear.

the controls feel extremely sensitive

Re: Maze Algorithms (1997)

#26

Post by fc417fc802 » Fri, Apr 03, 2026, 1:52 PM UTC

fjfaase wrote: post #11

fc417fc802 wrote: post #5

Earlier quoted context omitted.

What would it mean for a maze to be infinite? It seems to me that a key part of the concept is having a goal to reach. Although I guess you could have an infinitely large map and an algorithm that guaranteed connectivity. Infinite ways to fail to reach the goal. But I doubt there would be much practical benefit. To actually answer your question it should be fairly easy to convert nearly any existing algorithm to cove…

Please explain how to deal with slightly overlapping tiles and still create a maze that has no cycles and locations that cannot be reached from any other location. These are properties that go tiles. I do know of an algorithm with 'nesting' that generate mazes but results in very long walls and thus does not feel random.

I'm not sure how to address that within the scope of an HN comment (and I don't think I have the time). To start with the problem is severely underspecified.

What do you mean by "infinity" exactly? 2^64? 2^128? Any arbitrary bigint? Periodic boundary condition?

Why perfect mazes - does that really matter? Are these supposed to be human solvable or is this some sort of abstract art? Anything human solvable requires at least one path of (very) finite length from start to finish.

Overlapping tiles and doing nothing else produces multiple paths. It's the quick and easy solution if the goal is practicality of implementation and human oriented puzzles.

If you insist on a perfect maze an obvious solution is 2^64, a periodic boundary condition, and a space partitioning tree with many children per node (ie n >>> 2). Connectivity is determined at each level. Long uniform walls can be reduced or even eliminated by warping block boundaries in various ways; among other things, you could potentially use the maze solution at each level to assign node membership for the next level.

Re: Maze Algorithms (1997)

#27

Post by skulk » Fri, Apr 03, 2026, 1:58 PM UTC

fjfaase wrote: post #2

Are there also algorithms for (incremental) generation of infinite mazes?

It's not really what you asked but the article does mention infinite recursive mazes in the fractal section and you might be able to do interesting transformations on those to make them more interesting for your purpose (such as block off obvious paths to force the player to venture further)

Re: Maze Algorithms (1997)

#28

Post by contravariant » Fri, Apr 03, 2026, 2:25 PM UTC

fjfaase wrote: post #24

contravariant wrote: post #12

Earlier quoted context omitted.

I'd probably go with something like the wave function collapse algorithm. It should be possible to make it generate trees with somewhat uniform probability.

Interesting idea, but the problem is that being connected and being non-cyclic (properties you want for a perfect maze where you can reach every location and where there is exactly one route between every two locations) are global conditions that are difficult to implement with function collapse algorithm that are local.

I think being connected is easy enough, being non-cyclic is trickier I suppose. If you do it badly the shape of the maze is going to depend on the order it's generated in. I imagine some people may have looked into it.

Re: Maze Algorithms (1997)

#29

Post by skulk » Fri, Apr 03, 2026, 2:52 PM UTC

fc417fc802 wrote: post #5

fjfaase wrote: post #2

Are there also algorithms for (incremental) generation of infinite mazes?

What would it mean for a maze to be infinite? It seems to me that a key part of the concept is having a goal to reach. Although I guess you could have an infinitely large map and an algorithm that guaranteed connectivity. Infinite ways to fail to reach the goal. But I doubt there would be much practical benefit. To actually answer your question it should be fairly easy to convert nearly any existing algorithm to cove…

I've always had a dream of creating an infinite braid maze algorithm:

The requirements I've come up with are:

1. Distribution of path length for any two points of a fixed taxicab distance should be some kind of long-tail distribution.

2. In general, the path between any two nearby points should often stray far outside the smallest box that contains both of those two points. Of course, this won't apply to nearby points in the same corridor. I'm not sure how best to state this formally.

3. It should be possible to calculate the exits for any cell in O(log(N)) time where N = abs(sum of the coordinates).

And the most hazy requirement of all: the maze should look decent.

AFAICT, no such algorithm exists.

Re: Maze Algorithms (1997)

#30

Post by tasuki » Fri, Apr 03, 2026, 5:45 PM UTC

fc417fc802 wrote: post #21

tasuki wrote: post #20

Earlier quoted context omitted.

> It really depends on what you mean by "interesting". Yes. I haven't gotten far enough in my journey to be able to formulate that. The first insight is that the details of branching make a difference: humans don't pick the routes with the same likelihood at a crossroad. Loops seem fine for the wrong paths looping onto other wrong paths: having to backtrack is somewhat unsatisfying, plus loops make the solving less m…

So you only want dead ends to have loops? You might try computing the depth of each node, marking the solution, and then assigning each branch off of the solution a unique color. At that point knocking out walls only within the same color won't interfere with the solution. Alternatively you could take care to track depth and knock out walls between different colors only when the total resulting path length would be g…

Well, I don't have "walls" - my maze is sort of 2.5 dimensions - so that complicates things somewhat. I wonder whether there's an algorithm to "lift" a 2d maze with walls into my 2.5d maze, and I think if it's possible it's WFC or model synthesis. I will go try stuff, just haven't gotten around to it yet :)