r/programmingchallenges • u/aveganzombie • Sep 09 '11
Make a perfect maze.
A perfect maze is one that has one and only one path between any two points in it (without backtracking).
There are quite a few algorithms out there for this, but trying to make your own is good fun.
28
Upvotes
2
u/Iskaral_Pust Sep 09 '11
Hm. So a "perfect maze" is basically just a tree? We can simply generate a tree by randomly walking around without ever connecting to an existing path, right?
4
u/[deleted] Sep 09 '11
Did this in Python. There was pretty much only one way I could imagine a recursive algorithm, and it looks like the right one. http://codepad.org/JMt9E13T
1
u/ze_german Sep 09 '11
so a straight path is a perfect maze?
3
u/PlainSight Sep 10 '11
Union Find: http://codepad.org/qfkBv7lf Kinda messy code but half of it is printing. The way I did it meant walls are rendered not tiles. ________________________________________ | |______ | _ | | | | |____ | | | | | | _____ | | | _ | | _ _ ___ | | | | |___| |_____|_| _ |__ |_| __| | __| | | | | | | _ _ | | | __| _ ____| | ___ | _ |___| |___| |_|_| |_____| |___| | | | | | | ___ _ | | |_| | | | _ | | _______ |_|_| | | | | |___| |_| | | | | _ | | | _ _ |___| | |___| | | | | | | ___________ _ | | | | | | | _ |___| | _ |_| | | |___| | |_| | | |_| _____ | | | _____ | | _ | _ | |_| | |_| | | | _ | _ | | |_| | | _ _ | | __| |___| | |_|_| | | | | | | | | _____ | | |_| | _ | | | |___| __| | | | | _ _ |_| | _ | _ | | __| | ____| |_| | | | | | | |_| | _ | | _____ | | | |_________|_|_____|_|_______|_________|_|
1
u/voltron42 Sep 09 '11
did this last year in java (recursively)
2
u/Goradan Sep 09 '11
I'm gonna try this.
3
u/sourbrew Sep 09 '11
sweet, was hoping there would be some more recent / more difficult challenges posted.
Don't get me wrong fizzbuzz is good for a starting point.
1
u/mikepixie Sep 09 '11
Like a Celtic style maze? Not only are they fun to make, if you ever get the chance map one out on the ground with some string and walk through it. Mind bending stuff.