Maze Algorithms (1997)

https://www.astrolog.org/labyrnth/algrithm.htm

by marukodo • 4 months ago

91 36 4 months ago

astrolog.org

fjfaase5• 4 months ago

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

fc417fc8026• 4 months ago

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 cover an infinite area by simply tiling it. A common method to avoid boundary issues is to overlap the tiles slightly.

tasuki11• 4 months ago

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

fjfaase5• 4 months ago

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.

skulk2• 4 months ago

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.

tromp• 4 months ago

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 one row at time, so simply keep letting them add rows to the Maze forever.

My tiny obfuscated maze program at https://tromp.github.io/pearls.html#maze will print an infinitely long maze if you enter a negative height.

fjfaase5• 4 months ago

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

contravariant2• 4 months ago

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.

fjfaase5• 4 months ago

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.

skulk2• 4 months ago

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)

GavinAnderegg2• 4 months ago

This is a great list! A while back I also enjoyed reading “Mazes for Programers” and playing around with different maze generation algorithms from that book over a holiday break. The book isn’t super deep, but it has a fun set of projects and further ideas/reading as well. https://pragprog.com/titles/jbmaze/mazes-for-programmers/

signa11• 4 months ago

couple that with the "the ray tracer challenge" book, and you can generate some pretty cool images :o)

tasuki11• 4 months ago

The book isn’t super deep, but it has a fun set of projects and further ideas/reading as well.

Does it just regurgitate the well known maze generating algorithms? These generally do not lead to mazes interesting for humans...

GavinAnderegg2• 4 months ago

The book starts with generating fairly standard mazes, but transitions to making more interesting ones in later chapters. There are 12 algorithms explained in the book (listed in the link above), and the author does care about making pleasant mazes.

tomhow• 4 months ago

Previously:

Maze Algorithms (1997) - https://news.ycombinator.com/item?id=10101728 - Aug 2015 (10 comments)

tasuki11• 4 months ago

Yes, this page is a good overview of the sorry state of maze generation. The maze-creating algorithms might be interesting for computer scientists, but they're terrible at creating mazes interesting for humans!

First, I'm not sure "perfect maze" is a good requirement - well placed loops make mazes more interesting. Second, "uniform" is a useless metric: generating all mazes with equal probability leads to the mazes being visibly uninteresting, with many short dead ends. Same goes for the other metrics.

Sean C Jackson makes some good mazes: https://www.seancjackson.com/

---

Inspired by the above, I'm in the process of creating a maze game for my kid: https://maze.tasuki.org/

So far I hand-crafted the mazes. The initial idea was to generate them, but I quickly found out that generating interesting mazes was hard. And generating interesting mazes in 2.5D with with weave and without walls is even harder.

So I'm practicing maze creation. My newer mazes are much better (and take me less time to create) than the first attempts. I think eventually I'll be able to write down the algorithm I use for maze creation.

potro• 4 months ago

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

tasuki11• 4 months ago

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

fc417fc8026• 4 months ago

The maze-creating algorithms might be interesting for computer scientists, but they're terrible at creating mazes interesting for humans!

Not sure what would lead you to that conclusion. There's only so much you can do with (for example) a two color palette and no lawn art but it goes without saying that there's nothing restricting an implementation to the sort of minimalist methodology that's so useful for demonstrating an algorithm for the reader.

The last time this was posted [0] someone linked this article [1] which provides a nice visual demonstration of the structural differences between a few of the algorithms (scroll down for the color floods I'm referring to). Of course this can all be implemented as a graph (ie nodes that have coordinates) rather than as a grid, empty space expanded (ie coordinates subjected to an arbitrary series of affine transformations), branches of the tree overlaid after the fact to add weave (ie rotating and translating the coordinates of subtrees), nodes expanded to represent larger areas instead of single grid cells, whatever you'd like.

Also see the modifying in blocks algorithm applied to an escheresque tileset [2] (from this article [3]) which will produce a solvable 3D maze (multi-path and multi-solution) if given an appropriate tileset.

[0] https://news.ycombinator.com/item?id=10101728 [1] https://bost.ocks.org/mike/algorithms/#maze-generation [2] https://www.boristhebrave.com/wp-content/uploads/2021/10/esc... [3] https://www.boristhebrave.com/2021/10/26/model-synthesis-and...

tasuki11• 4 months ago

The WFC/model synthesis article is very interesting, thanks.

Yes the color floods are stunning, but these are exactly the algorithms which do not produce very interesting mazes. In particular, I don't think the "no loops" is a good maze property - the loops just have to be interesting.

derrak• 4 months ago

Wow! I really enjoyed this.

The 2.5D rendering gives a lot of opportunities to visually obscure the insight that’s necessary to solve the maze. It makes me think that a good maze should have a “oh, duh” moment. There were a few times where the false assumption I had to resolve was very close to the starting point. Tricky stuff.

And you designed all of these by hand? That is very impressive. How many mazes are there? The way I would start automating some of this would be to build a catalog of these visually tricky blocks that require the player to resolve a false assumption. Then I think it would be a matter of stitching these together in novel ways. Maybe the stitching procedure can be implemented by expressing a constraint system and solving for a stitching that has the properties you want.

I’m on a touch screen and I would say that the movement is a little bit sensitive. Concretely this means I found myself… going in a direction I didn’t intend to. Maybe this is a skill issue on my part. I don’t have alternative controls to suggest and I probably don’t understand the mechanics of the movement enough to even suggest which parameters to tweak.

Again, great work.

tasuki11• 4 months ago

Thanks! I keep creating new mazes by hand, right now I'm at 45 and the goal is 60, plan is that then the game is finished :)

Initially, I wanted to create a maze generator. But I had no idea how to write it. Creating mazes by hand, I'm slowly learning how to make them work (I've gotten waaay better than I was at the beginning). So, perhaps in the future, a maze generator that generates a daily maze seeded by the current date. Idea is to start with a simple maze every Monday and gradually increase the difficulty over the week. But I'm getting a little carried away: the more I think about it, the more I don't know how to create the maze generator.

FWIW, it's MIT licensed and available here: https://github.com/tasuki/iso-maze

Wrt sensitive controls: not sure which version you played, but I just reworked the controls a whole lot to automove to the next junction when you stop touching. It took my LLM and me a lot of time, mostly because I was searching in the dark, not entirely sure what I wanted. The controls are by far the least legible part of the codebase for me!

convexly• 4 months ago

There's something really satisfying about reading a 1997 paper and seeing that it is still completely relevant. The fundamentals haven't changed but the scale at which we can apply them has.

kcartlidge• 4 months ago

Some interesting stuff I wasn't familiar with, thanks.

I really like the book Mazes for Programmers by Jamis Buck [1].

Also, my open source Dungeon generator is a (slightly-misnamed) maze generator [2]. It produces 2D maps, and also 3D files (OBJ and MTL) for use in Blender etc. I like to think it does a more 'reasonable' job than many, but I am biased.

- [1] http://www.mazesforprogrammers.com

- [2] https://github.com/kcartlidge/Dungeon

Maze Algorithms (1997)

Related Stories