[python-uk] Fwd: more maze

[Tom Viner]

I mentioned some comments to Thomas about his elegant random spanning tree
maze script  and he insisted that I
post here so everyone can see the correction and
extensions
.

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 
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
>

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
<><>___
python-uk mailing list
python-uk@python.org
http://mail.python.org/mailman/listinfo/python-uk

Re: [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  wrote:

> I mentioned some comments to Thomas about his elegant random spanning
> tree maze script  and he insisted
> that I post here so everyone can see the correction and 
> extensions
> .
>
> 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 
> 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
>>
>
> 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
>
>
<><>___
python-uk mailing list
python-uk@python.org
http://mail.python.org/mailman/listinfo/python-uk