Hacker News Reader

Comment by emadehsan | Hacker News Reader

Captivating! So, while generating the puzzle, you are essentially creating a random Spanning Tree for the given nodes (hexagon) arrangement? Then you randomize each pipe piece's direction within a hexagon?

What algorithm are you using for it Spanning Tree?

I have been working on Maze Generation[0] and found randomized Prim's, Kruskal's to be useful for Spanning Tree creation but the good old Depth First Search increases the difficulty of solving a Maze.

[0] https://github.com/emadehsan/maze/blob/main/media/hexagonal....

View on HN

Well the way I wrote my pipes solver was to keep a set of possible orientations of every tile and gradually remove impossible options by using border conditions and some heuristics like avoiding islands and loops. And when this doesn't turn up any new info I resort to depth-first search.

The generator basically does the same but every tile starts out with a full set of possible orientations - every rotation of every tile shape (there are 62 I think). I remove some orientations due to border conditions, then pick a random possible orientation for some tile and so on till the board is filled. There usually is some backtracking involved.

This isn't terribly efficient and can get stuck for quite long when generating large puzzles. I actually want to look into adapting maze generation algorithms for creating these puzzles, so thanks for the link, I'll check it out.

I see. Amazing work you have done! This game is enticing.

My understanding is that since the game mentions:

"Rotate the tiles so that all pipes are connected with no loops."

These is exactly what a Spanning Tree is. So, any spanning tree generation algorithm would do. You just generate a random ST each time and cut this tree where the hexagon borders intersect with it (to get pipe pieces) and randomize their orientation.

These algorithms are not going to disappoint you in terms of performance.

I made tutorials on the topic as well. Might help me clear my point: https://youtu.be/d5yzKkG1n1U?t=36

Apologies for spamming. Sorry, if I'm suggesting premature optimization.

There might still be issues with multiple solutions... Because when a board has multiple solutions they're all valid Spanning Trees. But there probably is some way around this.

An efficient generator could perhaps even work client side, so I wouldn't have to store premade puzzle instances in the repo. That would be cool =).

Could perhaps look into the source of Simon Tatham's variant? Those are generated client side.

Reply on news.ycombinator.com