[python-uk] Fwd: more maze

[Tom Viner]

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/ff570aa1/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/ff570aa1/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/ff570aa1/attachment-0001.png>