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/
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.
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.
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.
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.
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!
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.
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.
8 comments
[ 2.9 ms ] story [ 25.4 ms ] threadMaze Algorithms (1997) - https://news.ycombinator.com/item?id=10101728 - Aug 2015 (10 comments)
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.
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.
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!
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