<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=utf-8"><meta name=Generator content="Microsoft Word 15 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:"Segoe UI";
panose-1:2 11 5 2 4 2 4 2 2 3;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
p.quotation, li.quotation, div.quotation
{mso-style-name:quotation;
mso-style-link:"quotation Char";
margin-top:0in;
margin-right:0in;
margin-bottom:0in;
margin-left:.5in;
font-size:11.0pt;
font-family:"Times New Roman",serif;
font-weight:bold;
font-style:italic;}
span.quotationChar
{mso-style-name:"quotation Char";
mso-style-link:quotation;
font-family:"Times New Roman",serif;
font-weight:bold;
font-style:italic;}
span.EmailStyle22
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link=blue vlink=purple style='word-wrap:break-word'><div class=WordSection1><p class=MsoNormal>Hi Roger, <o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Here is a picture of a typical rat maze. I was going to crop it but I thought the image of a former English major trying to manipulate technology was too funny not to send along. Notice that it’s all t’s. <o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>You wrote:<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=quotation>If the graph of the maze contains loops, then wall following will get trapped in the loops, in fact, I think each loop defines a wall following domain, and to solve the maze you'll have to detect when you've completed a loop and switch to following the opposite wall when it's one you haven't already followed. If you just switch to the opposite wall at random, you'll most probably end up on the same loop going in the opposite direction.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>This is the kind of thing that rats should be extremely good at. If there is one thing a rat should know it’s where it’s been and how recently and even, how often. <o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Nick <o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Nick Thompson<o:p></o:p></p><p class=MsoNormal><a href="mailto:ThompNickSon2@gmail.com"><span style='color:#0563C1'>ThompNickSon2@gmail.com</span></a><o:p></o:p></p><p class=MsoNormal><a href="https://wordpress.clarku.edu/nthompson/"><span style='color:#0563C1'>https://wordpress.clarku.edu/nthompson/</span></a><o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><div style='border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in'><p class=MsoNormal><b>From:</b> Friam <friam-bounces@redfish.com> <b>On Behalf Of </b>Roger Critchlow<br><b>Sent:</b> Sunday, February 28, 2021 11:03 AM<br><b>To:</b> The Friday Morning Applied Complexity Coffee Group <friam@redfish.com><br><b>Subject:</b> Re: [FRIAM] solving mazes<o:p></o:p></p></div><p class=MsoNormal><o:p> </o:p></p><div><p class=MsoNormal>Okay Nick, <o:p></o:p></p><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>So you draw the maze as a graph where the nodes of the graph are positions in the maze that can be occupied, and the edges of the graph are one step open paths between adjacent positions. Easy to draw on graph paper, here is a site which generates graph paper pdfs for printing: <a href="https://incompetech.com/graphpaper/" target="_blank">https://incompetech.com/graphpaper/</a>, just fill in the cells that are walls and draw lines to connect the remaining open cells. Each open cell is a node, each line connecting adjacent cells is an edge.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>The graph of the maze must be connected or parts of the maze will be cut off from each other and no algorithm will ever work if it starts in the wrong connected component. Nasty trick to play on a rat. <o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>If the graph of the maze contains loops, then wall following will get trapped in the loops, in fact, I think each loop defines a wall following domain, and to solve the maze you'll have to detect when you've completed a loop and switch to following the opposite wall when it's one you haven't already followed. If you just switch to the opposite wall at random, you'll most probably end up on the same loop going in the opposite direction.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>Just to demonstrate how graph properties end up trapping the unwary, an open courtyard in your maze ends up being an area of fully connected graph, which is all loops all the time, which is a counter example to my proposal that "each loop defines a wall following domain" since lots of the loops in the courtyard will have no adjacent walls at all. So I must have meant something subtler than loop, something that is a loop that has walls on both sides.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>-- rec --<o:p></o:p></p></div></div><p class=MsoNormal><o:p> </o:p></p><div><div><p class=MsoNormal>On Sun, Feb 28, 2021 at 9:39 AM Jochen Fromm <<a href="mailto:jofr@cas-group.net" target="_blank">jofr@cas-group.net</a>> wrote:<o:p></o:p></p></div><blockquote style='border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in'><div><div><p class=MsoNormal>Jamis Buck is very interested in mazes. He even wrote a book about it named "Mazes for programmers"<o:p></o:p></p></div><div><p class=MsoNormal><a href="https://www.jamisbuck.org/mazes/" target="_blank">https://www.jamisbuck.org/mazes/</a><o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>It contains algorithms for generating and solving mazes<o:p></o:p></p></div><div><p class=MsoNormal><a href="https://pragprog.com/titles/jbmaze/mazes-for-programmers/" target="_blank">https://pragprog.com/titles/jbmaze/mazes-for-programmers/</a><o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>-J.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal><span style='color:black'>-------- Original message --------<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='color:black'>From: cody dooderson <<a href="mailto:d00d3rs0n@gmail.com" target="_blank">d00d3rs0n@gmail.com</a>> <o:p></o:p></span></p></div><div><p class=MsoNormal><span style='color:black'>Date: 2/28/21 01:10 (GMT+01:00) <o:p></o:p></span></p></div><div><p class=MsoNormal><span style='color:black'>To: The Friday Morning Applied Complexity Coffee Group <<a href="mailto:friam@redfish.com" target="_blank">friam@redfish.com</a>> <o:p></o:p></span></p></div><div><p class=MsoNormal><span style='color:black'>Subject: Re: [FRIAM] solving mazes <o:p></o:p></span></p></div><div><p class=MsoNormal><span style='color:black'><o:p> </o:p></span></p></div><div><p class=MsoNormal>I am assuming this is a 2D maze. Wikipedia does a better job at explaining the problems with wall following than I can. <o:p></o:p></p><div><p class=MsoNormal><o:p> </o:p></p></div><div><p style='mso-margin-top-alt:6.0pt;margin-right:0in;margin-bottom:12.0pt;margin-left:0in;background:white;vertical-align:baseline;line-height:inherit'><i><span style='font-size:12.0pt;font-family:"Segoe UI",sans-serif;color:#202122'>If the maze is not simply-connected (i.e. if the start or endpoints are in the center of the structure surrounded by passage loops, or the pathways cross over and under each other and such parts of the solution path are surrounded by passage loops), this method will not reach the goal.</span></i><span style='font-size:12.0pt;font-family:"Segoe UI",sans-serif;color:#202122'><o:p></o:p></span></p><p style='mso-margin-top-alt:6.0pt;margin-right:0in;margin-bottom:12.0pt;margin-left:0in;background:white;vertical-align:baseline;line-height:inherit'><span style='font-size:12.0pt;font-family:"Segoe UI",sans-serif;color:#202122'><o:p> </o:p></span></p></div><p class=MsoNormal style='margin-bottom:12.0pt'><o:p> </o:p></p><div><div><p class=MsoNormal>On Sat, Feb 27, 2021, 1:48 PM <<a href="mailto:thompnickson2@gmail.com" target="_blank">thompnickson2@gmail.com</a>> wrote:<o:p></o:p></p></div><blockquote style='border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in'><div><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>Hi, All,<o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>Due to a review I have been working on, I have been dragged back into thinking about maze learning in rats. Any animal I have ever known, when confined, will explore the boundaries of its enclosure. Cows, for instance will beat a path just inside the barbed wire that encloses them. So a maze is not only a series of pathways but it is also an enclosure. If the rat puts his left whisker against the left wall of the maze, he will eventually get to the goal box, right. It works with the Hampton Court Maze. On the second run, he can now use odor cues, such that any time he encounters his own odor both entering and leaving a passage way, he should just skip that passage way. <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>So I am wondering, you topologists (??) out there, how general is the statement, “every maze is an enclosure” and what is the limitation on the idea that any maze can be solved by putting your right or left hand on a wall and continuing to walk until you find the goal or are let out of the maze. Now I should quickly say that rat mazes are usually composed of a series of bifurcating choice points, where the rat can go either left or right. Some choices lead ultimately to dead ends. In sum, a runway in such a maze can go straight, turn R or L without choice or form a T with a right or left choice. My intuition is that no such maze can be designed that does not permit the boundary following strategy. <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>Nick <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'>Nick Thompson<o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><a href="mailto:ThompNickSon2@gmail.com" target="_blank">ThompNickSon2@gmail.com</a><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'><a href="https://wordpress.clarku.edu/nthompson/" target="_blank">https://wordpress.clarku.edu/nthompson/</a><o:p></o:p></p><p class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto'> <o:p></o:p></p></div><p class=MsoNormal>- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .<br>FRIAM Applied Complexity Group listserv<br>Zoom Fridays 9:30a-12p Mtn GMT-6 <a href="http://bit.ly/virtualfriam" target="_blank">bit.ly/virtualfriam</a><br>un/subscribe <a href="http://redfish.com/mailman/listinfo/friam_redfish.com" target="_blank">http://redfish.com/mailman/listinfo/friam_redfish.com</a><br>FRIAM-COMIC <a href="http://friam-comic.blogspot.com/" target="_blank">http://friam-comic.blogspot.com/</a><br>archives: <a href="http://friam.471366.n2.nabble.com/" target="_blank">http://friam.471366.n2.nabble.com/</a><o:p></o:p></p></blockquote></div></div></div><p class=MsoNormal>- .... . -..-. . -. -.. -..-. .. ... -..-. .... . .-. .<br>FRIAM Applied Complexity Group listserv<br>Zoom Fridays 9:30a-12p Mtn GMT-6 <a href="http://bit.ly/virtualfriam" target="_blank">bit.ly/virtualfriam</a><br>un/subscribe <a href="http://redfish.com/mailman/listinfo/friam_redfish.com" target="_blank">http://redfish.com/mailman/listinfo/friam_redfish.com</a><br>FRIAM-COMIC <a href="http://friam-comic.blogspot.com/" target="_blank">http://friam-comic.blogspot.com/</a><br>archives: <a href="http://friam.471366.n2.nabble.com/" target="_blank">http://friam.471366.n2.nabble.com/</a><o:p></o:p></p></blockquote></div></div></body></html>