[python-uk] more maze

[Thomas Hunger]

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 <tom at 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 <mail at timgolden.me.uk>
> Date: 6 May 2013 19:33
> Subject: Re: [python-uk] more maze
> To: python-uk at 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 at python.org
> http://mail.python.org/**mailman/listinfo/python-uk<http://mail.python.org/mailman/listinfo/python-uk>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-uk/attachments/20130512/a7dc5264/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Screenshot from 2013-05-07 23:55:52.png
Type: image/png
Size: 706 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/python-uk/attachments/20130512/a7dc5264/attachment.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Screenshot from 2013-05-12 01:46:09.png
Type: image/png
Size: 1060 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/python-uk/attachments/20130512/a7dc5264/attachment-0001.png>