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

Maze Algorithms (1997)

astrolog.org

Post reply on HN
Print view View original

11–20 of 37 posts

Re: Maze Algorithms (1997)

#11

Post by fjfaase »

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…

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.

Re: Maze Algorithms (1997)

#13

Post by potro »

tasuki wrote: post #7

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 b…

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

Re: Maze Algorithms (1997)

#14

Post by tasuki »

potro wrote: post #13
tasuki wrote: post #7

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 b…

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.

Re: Maze Algorithms (1997)

#15

Post by fc417fc802 »

tasuki wrote: post #7

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 b…

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

Re: Maze Algorithms (1997)

#16

Post by GavinAnderegg »

tasuki wrote: post #8
GavinAnderegg wrote: post #3

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/

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

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.

Re: Maze Algorithms (1997)

#17

Post by tasuki »

fc417fc802 wrote: post #15
tasuki wrote: post #7

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 b…

> 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 demonst…

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.

Re: Maze Algorithms (1997)

#18

Post by fc417fc802 »

tasuki wrote: post #17
fc417fc802 wrote: post #15

Earlier quoted context omitted.

> 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 demonst…

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.

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 complex graph representation and assuming the use of a compatible data structure (ie no limitation on cycles) the conversion is similarly trivial. Add vertices between nodes at random, keeping away from the two terminal nodes and probably also making sure that there's a certain distance between the two newly interconnected nodes.

Re: Maze Algorithms (1997)

#19

Post by convexly »

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.

Re: Maze Algorithms (1997)

#20

Post by tasuki »

fc417fc802 wrote: post #18
tasuki wrote: post #17

Earlier quoted context omitted.

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.

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 mechanical - it's necessary to keep an eye where you'd been and where you haven't. It's possible to get confused and take the same wrong path twice, once from each direction. But certainly it matters where the loops are and how exactly they're formed - "simply convert some walls to pathways at random" is not the right way to construct them.

And I guess I think there should be one solution, though perhaps it can have few short loops somewhere in the middle (so it isn't really "one solution" anymore).

I wish there was research on how easy/difficult differently constructed mazes of a specific size are for humans to solve.

Post reply on HN