: New:

I had some thoughts about automatically-generated mazes rattling around in the back of my head and figured out a way to apply an algorithm from that Mazes for Programmers book to a problem I'd noticed a while back.

The problem: I wanted to create a maze with thick walls; and I wanted to choose the maze's entrance and exit squares ahead of time. Alas, the naive algorithms I had were more likely than not to block off the entrance and/or exit with walls. But I'd had Kruskal's algorithm (as applied to mazes) on my mind, and I saw how to apply it here: choose an entrance and an exit, then grow a maze-tree from each; when the two maze-trees collide, treat them as a single maze-tree and continue growing to fill in the rest:

(This problem doesn't show up with normal "skinny-wall" mazes; you can choose any square as the entrance and any as the exit/goal/whatever. You can get from any point to any other point in a normal maze; you can always be assured that there's one way to get from start to finish.)

Tags: programming puzzle scene

blog comments powered by Disqus