Writing a Procedural Puzzle Generator | Hacker News Reader

Writing a Procedural Puzzle Generator

snellman.net

70 pointsluu17 comments

Simon Tatham has some advice on writing puzzle generators from his collection of games https://www.chiark.greenend.org.uk/~sgtatham/puzzles/devel/w...

I was wondering who would’ve already mentioned him, I wasn’t expecting it to be someone else who also used to go to the Carlton. Tech’s a small world sometimes.

> And for a game like this, there's really no point in trying to make those puzzles by hand. That's a job for a computer.

A hundred good puzzles with a difficulty ramp-up would be way preferable than 100 randomly-generated 'probably? interesting' ones.

I much prefer puzzle games where there's a 'trick' to solving a puzzle (like the puzzlescript genre, Pipe Push Paradise, Build Me a Snowman, Stephen's Sausage Roll), or mindless automatically-generated puzzles from Simon Tatham's collection.

You mean "over", not "or"?

I've somehow caught the Slitherlink bug and solved countless Slitherlink puzzles. For that use case, I suppose automatically generated is the only feasible way to go.

Maybe it also makes sense to use computer assistance in handcrafted puzzles at times.

> You mean "over", not "or"?

clarification: I mean what I wrote. I tried the author's game and found it lifeless and too much work, the worst combination of attributes from my two preferred puzzles styles I described

How is this puzzle style different than the procedurally generated ones in Simon Tatham's collection?

So I guess I was pretty condensed in my post:

> mindless automatically-generated

the 'mindless' is: solving is mindless application of heuristics/solving rules & the challenge is not to complete the puzzle but to do it in minimal moves/time.

The author's puzzle is too hard to solve mindlessly & then doesn't generate goodwill the way a hand-crafted stumper does in the puzzlescript-type games

Ah, so you're saying, you want them to either be easier, or more clever? I guess that makes sense; I like solving Picross puzzles, but I enjoy them most when I can work through them at a rapid clip, just chasing clues and following the patterns. Harder ones can be fun, but I don't get the same sense of relaxation out of them.

I'd say 'more mechanical' instead of easier, but yeah, pretty much

Reminds me of the puzzles for an iOS game I put out a couple of years ago: Little Broken Robots. In that game you had numbers but could “walk” out from a number that many spaces. You had to fill in all the empty spaces.

My strategy for generating puzzles was island based. I had a board checker that would scan through the grid and place all empty spaces that could be reached contiguously into a single “island.” I would then pick a random island (the first island was always the full grid), pick a random tile in the island, pick a random number with a max value of either the puzzle’s max (up to 8), and then drunk walk outward. In the event the drunk walk got “stuck” it would just pick a different starting tile within that island.

Recompute islands and repeat until there are no spaces left. Island with only 1 square are “dead” and just get filled in with blocker tiles.

Each puzzle had many solutions, but because there was always a “right” pregenerated solution we could give hints based on the canonical solution.

I love the human responses are that the puzzles seem to have a gotcha, as if designed by a human.

"A common theme for positive comments has been about how the puzzles always feel like there's a clever gotcha in there."

I have tried generating fun minesweeper boards, where 'fun' is moves requiring multiple pieces of information to progress.

The boards I initially generated tended to be annoyingly difficult because the last moves required reasoning about 4 mines left. Assigning funness to moves requiring too many pieces of information turned out to be too difficult for humans (or me at least) to solve and thus became un-fun.

http://danamlund.dk/funminesweeper/funminesweeper_idea.html

This is cool! I once wrote a method for generating logical deduction problems:

https://github.com/shaungallagher/cheryls-murder/blob/master...

As with the procedural puzzle generator, it takes a bit of sifting to find puzzles that are both possible and challenging to solve. But it gets you most of the way there!

Very interesting write-up. I have ran into a similar problem with generating mazes that are interesting to solve for humans. Depending on the desired difficulty you want the path to have a certain length and a certain number of forks as well as a certain length for dead-ends.

I wonder whether omitting the grid was a conscious decision, I feel the images would be more clear with a grid of some sort.

Since the game was out [1] I was hooked into the game for a solid month. It's the kind of essential and basic puzzle with a fresh and new mechanics that can pass the test of time. There should be tons of clones in mobile app stores already.

[1] https://news.ycombinator.com/item?id=19075490

I think theres a middleground to autogenerated puzzles, they can be curated by humans. Puzzles could be autogenerated by the author of the game, played and the good ones saved and ranked a level of difficulty.

Yay, I was hoping there were some information about this out there! I've developed a few types of puzzles that I've been trying to come up with the puzzles by hand, and it's been really slow going.

I do agree that coming up with them by hand and designing puzzles with intent and possibly a theme is still probably for the best, but I think a hybrid approach, where you can use these generators to help give you ideas or starting points or fill in some gaps can be useful.

I've been wondering if the book "Mazes for Programmers" might also contain some useful advice. Or maybe the algorithms can be found elsewhere, too.

It describes various strategies for proceduarly creating mazes. Perhaps many puzzles can be mapped to a maze, as the search tree for solving them would essentially be a maze?

Reply on news.ycombinator.com