Very cool. Thanks for the nice write-up and the fixes! Daniel Pope's maze generator, mentioned here [1], is a different implementation of the same algorithm.
~ [1] http://mail.python.org/pipermail/python-uk/2013-May/002942.html On 12 May 2013 10:01, Tom Viner <t...@viner.tv> wrote: > I mentioned some comments to Thomas about his elegant random spanning > tree maze script <https://gist.github.com/teh/5526976> and he insisted > that I post here so everyone can see the correction and > extensions<https://gist.github.com/tomviner/5536939> > . > > First there was a minor bug where the initial location wasn't included in > the seen set, that meant you could sometimes get cycles in > the supposedly acyclic graph. > > [image: Inline images 1](Note loop at bottom left) > > In testing this I found I needed a way repeating a certain random maze, so > I added this to the start: > > seed = sys.argv[1] if sys.argv[1:2] else random.randint(0, 999) > print "Replay with python maze.py", seed > random.seed(int(seed)) > > which picks a random seed unless you pass one in on the command line. > > Then I wanted to see how the backtracking worked, so I tried slowing down > the turtle but there was still a bit of a pause before anything was drawn. > This was because the maze was being pre-computed, then drawn afterwards. > Turning the maze algorithm into a generator fixed this. > > Finally I asked Thomas how he'd test if any given maze was solvable. He > said "The spanning tree connects all nodes. There are no unconnected > subgraphs. For that reason you can pick any two points as start and end and > have a solvable maze". > > At this point I realised I'd been looking at the maze drawing backwards: > he'd intended the lines the turtle draws to be the *paths*, and *everything > else* was walls. > > Rather than calculating exactly where all the walls would be, to contain a > given path, I just added a background and made the turtle carve out the > path of the maze. > > I also added entrances when the path hits the edge. So now we have a > familiar looking maze: > > [image: Inline images 1] > Instructions: Pick 2 opposite entrances and try to get from one to the > other. > > I wonder if we could let Mike's Physical Turtle loose on this... > > > Tom > > ---------- Forwarded message ---------- > From: Tim Golden <m...@timgolden.me.uk> > Date: 6 May 2013 19:33 > Subject: Re: [python-uk] more maze > To: python-uk@python.org > > > On 06/05/2013 19:26, Thomas Hunger wrote: > >> Here's an implementation of a random spanning tree where the nodes are >> coordinates on a plane so one can render them later: >> >> https://gist.github.com/teh/**5526976<https://gist.github.com/teh/5526976> >> > > Thanks, Thomas. > > For those wondering, last Thursday's London Python Dojo was all about > generating mazes. Most teams didn't have time to fulfil their solution's > entire potential and evidently a few people went home buzzing with ideas or > alternatives. Hence the flow of messages to the list promoting maze > solutions. > > Just so you knew... > > The next Dojo should be on the first Thursday of June, venue to be > announced. Keep an eye on this list and/or follow @ldnpydojo. > > TJG > > > ______________________________**_________________ > python-uk mailing list > python-uk@python.org > http://mail.python.org/**mailman/listinfo/python-uk<http://mail.python.org/mailman/listinfo/python-uk> > >
<<Screenshot from 2013-05-07 23:55:52.png>>
<<Screenshot from 2013-05-12 01:46:09.png>>
_______________________________________________ python-uk mailing list python-uk@python.org http://mail.python.org/mailman/listinfo/python-uk
