{"id":4472,"date":"2019-03-04T12:00:13","date_gmt":"2019-03-04T17:00:13","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=4472"},"modified":"2019-03-04T15:31:39","modified_gmt":"2019-03-04T20:31:39","slug":"amaze-a-maze-generator","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2019\/03\/04\/amaze-a-maze-generator\/","title":{"rendered":"Amaze, A Maze Generator"},"content":{"rendered":"\r\n\r\n<div class=\"content\"><!--introduction--><p>My MATLAB&reg; program, <tt>amaze<\/tt>, generates mazes by combining old friends, <tt>numgrid<\/tt> and <tt>delsq<\/tt>, with a new friend, the <tt>graph<\/tt> object. Let's see how we make this example maze.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/amaze_6.png\" alt=\"\"> <\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#2e8b7a8a-dfa6-4253-a3e4-801dfcac979b\">Beginnings<\/a><\/li><li><a href=\"#2c3e2bfb-5b16-4c9d-b301-adc6ec3d16ac\">Random walks<\/a><\/li><li><a href=\"#5c2aeef5-bdee-42d3-8613-c1cf0719829f\">Backtrack<\/a><\/li><li><a href=\"#ba53f119-8dd0-4941-9370-99de671e05d7\">Shortest path<\/a><\/li><li><a href=\"#88eaba21-246b-4016-be47-a828db160bd8\">Animation<\/a><\/li><li><a href=\"#bd6b4533-b3aa-4ead-b456-fca419b5ebed\">Software<\/a><\/li><li><a href=\"#73c6b53c-4ee3-40ba-a5a1-f85b2e6e1faf\">Thanks<\/a><\/li><\/ul><\/div><h4>Beginnings<a name=\"2e8b7a8a-dfa6-4253-a3e4-801dfcac979b\"><\/a><\/h4><p>Select a maze size.  Our example is 15-by-15.<\/p><pre class=\"codeinput\">    n = 15;\r\n<\/pre><p>We are going to make two graphs, the barriers and the cells. The barriers, <tt>B<\/tt>, is the graph of the classic five-point discrete Laplacian on an n-by-n square grid.  Each node is the interior is connected to its four closest neighbors and each node on the boundary has two or three neighbors.  The functions <tt>delsq<\/tt> and <tt>numgrid<\/tt> have been in the <tt>sparfun<\/tt> directory since sparse matrices were introduced in 1992.  The <tt>graph<\/tt> object was introduced in R2015b. We are going to carve a path through this grid.<\/p><pre class=\"codeinput\">    Db = delsq(numgrid(<span class=\"string\">'S'<\/span>,n+2));\r\n    B = graph(logical(Db),<span class=\"string\">'omitselfloops'<\/span>);\r\n<\/pre><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/amaze_0.png\" alt=\"\"> <\/p><p>The cells, <tt>C<\/tt>, are also based on the five-point discrete Laplacian, but on an (n-1)-by-(n-1) grid.  Initially <tt>C<\/tt> has just the nodes, no edges.  When we plot <tt>B<\/tt> and <tt>C<\/tt> together, the nodes of <tt>C<\/tt> are centered in the squares of <tt>B<\/tt>.<\/p><pre class=\"codeinput\">    m = n-1;\r\n    Dc = delsq(numgrid(<span class=\"string\">'S'<\/span>,m+2));\r\n    C = graph(logical(Dc),<span class=\"string\">'omitselfloops'<\/span>);\r\n<\/pre><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/amaze_1.png\" alt=\"\"> <\/p><h4>Random walks<a name=\"2c3e2bfb-5b16-4c9d-b301-adc6ec3d16ac\"><\/a><\/h4><pre class=\"codeinput\">    available = 1:m^2; <span class=\"comment\">% Nodes we haven't visited yet.<\/span>\r\n    branches = [];\r\n    branching = <span class=\"string\">'middle'<\/span>;\r\n    tree = zeros(0,2); <span class=\"comment\">% Depth first search.<\/span>\r\n    p = 1;\r\n<\/pre><p>Now we make a series of random walks on <tt>C<\/tt>.<\/p><pre class=\"codeinput\">   <span class=\"keyword\">while<\/span> true  <span class=\"comment\">% Break when available is empty<\/span>\r\n<\/pre><pre class=\"codeinput\">        available(p) = 0;\r\n        <span class=\"keyword\">if<\/span> ~any(available)\r\n            <span class=\"keyword\">break<\/span>\r\n        <span class=\"keyword\">end<\/span>\r\n<\/pre><p>Each step is from a node to a random choice of one of its neighbors that has not already been visited.<\/p><pre class=\"codeinput\">        [~,~,ngh] = find(available(neighbors(C,p)));\r\n\r\n        <span class=\"keyword\">if<\/span> ~isempty(ngh)\r\n<\/pre><pre class=\"codeinput\">            idx = randi(length(ngh));  <span class=\"comment\">% Random choice.<\/span>\r\n            q = ngh(idx);              <span class=\"comment\">% Next cell.<\/span>\r\n            tree(end+1,:) = [p q];\r\n<\/pre><p>At the same time, the edge in the barrier <tt>B<\/tt> that is blocking the step is removed.<\/p><pre class=\"codeinput\">            [i,j] = wall(p,q);\r\n            B = rmedge(B,i,j);\r\n<\/pre><p>We keep a list of the nodes where a random choice between two or three neighbors is made.<\/p><pre class=\"codeinput\">            <span class=\"keyword\">if<\/span> length(ngh) &gt; 1\r\n                branches(end+1) = p;\r\n            <span class=\"keyword\">end<\/span>\r\n\r\n            p = q;\r\n<\/pre><p>Eventually the walk reaches a dead end, a node whose neighbors have all been visited.  Here is the first such walk in our example.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/amaze_2.png\" alt=\"\"> <\/p><h4>Backtrack<a name=\"5c2aeef5-bdee-42d3-8613-c1cf0719829f\"><\/a><\/h4><p>When we reach a dead end, we backtrack to one of the nodes on our list of nodes where we had a choice of available neighbors.  Here another kind of choice is made.  We can go back to the <i>first<\/i> node on the list, to the node in the <i>middle<\/i> of the list, or to the <i>last<\/i> node on the list.<\/p><pre class=\"codeinput\">        <span class=\"keyword\">else<\/span>\r\n\r\n            <span class=\"keyword\">switch<\/span> branching\r\n                <span class=\"keyword\">case<\/span> <span class=\"string\">'first'<\/span>\r\n                    idx = 1;\r\n                <span class=\"keyword\">case<\/span> <span class=\"string\">'last'<\/span>\r\n                    idx = length(branches);\r\n                <span class=\"keyword\">otherwise<\/span>\r\n                    idx = round(length(branches)\/2);\r\n            <span class=\"keyword\">end<\/span>\r\n\r\n            p = branches(idx);\r\n            branches(idx) = [];\r\n        <span class=\"keyword\">end<\/span>\r\n<\/pre><p>Here is the result of backtracking to the middle and then walking to a second dead end.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/amaze_3.png\" alt=\"\"> <\/p><p>Here is the result after several more backtracks.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/amaze_4.png\" alt=\"\"> <\/p><pre class=\"codeinput\">    <span class=\"keyword\">end<\/span>\r\n    C = graph(tree(:,1),tree(:,2));\r\n<\/pre><p>Near the end of this process, the length of a path before a dead end and a backtrack becomes shorter and shorter.  A path may involve a single point.  Eventually all the nodes in <tt>C<\/tt> are covered. Here is the final result.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/amaze_5.png\" alt=\"\"> <\/p><p>When the entire path is plotted with <tt>linestyle = 'none'<\/tt> we have the maze.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/amaze_6.png\" alt=\"\"> <\/p><h4>Shortest path<a name=\"ba53f119-8dd0-4941-9370-99de671e05d7\"><\/a><\/h4><p>We can easily \"solve\" the maze by asking for the shortest path from one corner to another.<\/p><pre class=\"codeinput\">    path = shortestpath(C,1,m^2);\r\n<\/pre><p>(<i>Exercise<\/i>: How does the <tt>branching<\/tt> parameter affect the average length of this <tt>path<\/tt>?)<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/amaze_7.png\" alt=\"\"> <\/p><h4>Animation<a name=\"88eaba21-246b-4016-be47-a828db160bd8\"><\/a><\/h4><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/amaze_movie_1.gif\" alt=\"\"> <\/p><h4>Software<a name=\"bd6b4533-b3aa-4ead-b456-fca419b5ebed\"><\/a><\/h4><p>I have a program called <tt>amazing<\/tt> that allows you to investigate <tt>amaze<\/tt>.  I've submitted it to the <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\">MATLAB Central File Exchange<\/a> and will put the <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/70451-amaze-a-maze-generator\">link here<\/a>. I will also add <tt>amazing<\/tt> to version 4.40 of <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/59085-cleve_s-laboratory\">Cleve's Laboratory<\/a>.<\/p><h4>Thanks<a name=\"73c6b53c-4ee3-40ba-a5a1-f85b2e6e1faf\"><\/a><\/h4><p>Thanks to Pat Quillen who provided invaluable help.<\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_1d5efde86d0f4c3794e54d3aa617c6e3() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='1d5efde86d0f4c3794e54d3aa617c6e3 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 1d5efde86d0f4c3794e54d3aa617c6e3';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2019 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_1d5efde86d0f4c3794e54d3aa617c6e3()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; R2018b<br><\/p><\/div><!--\r\n1d5efde86d0f4c3794e54d3aa617c6e3 ##### SOURCE BEGIN #####\r\n%% Amaze, A Maze Generator\r\n% My MATLAB(R) program, |amaze|, generates mazes by combining old\r\n% friends, |numgrid| and |delsq|, with a new friend, the |graph| object.\r\n% Let's see how we make this example maze.\r\n%\r\n% <<amaze_6.png>>\r\n\r\n%% Beginnings\r\n% Select a maze size.  Our example is 15-by-15.\r\n\r\n    n = 15;\r\n\r\n%%\r\n% We are going to make two graphs, the barriers and the cells.\r\n% The barriers, |B|, is the graph of the classic five-point\r\n% discrete Laplacian on an n-by-n square grid.  Each node is the\r\n% interior is connected to its four closest neighbors and each node on\r\n% the boundary has two or three neighbors.  The functions |delsq| and\r\n% |numgrid| have been in the |sparfun| directory since sparse matrices\r\n% were introduced in 1992.  The |graph| object was introduced in R2015b.\r\n% We are going to carve a path through this grid.\r\n\r\n    Db = delsq(numgrid('S',n+2));\r\n    B = graph(logical(Db),'omitselfloops');\r\n    \r\n%%\r\n% <<amaze_0.png>>\r\n\r\n%%\r\n% The cells, |C|, are also based on the five-point discrete Laplacian,\r\n% but on an (n-1)-by-(n-1) grid.  Initially |C| has just the nodes,\r\n% no edges.  When we plot |B| and |C| together, the nodes of |C|\r\n% are centered in the squares of |B|.\r\n\r\n    m = n-1;\r\n    Dc = delsq(numgrid('S',m+2));\r\n    C = graph(logical(Dc),'omitselfloops');\r\n    \r\n%%\r\n% <<amaze_1.png>>\r\n\r\n%% Random walks\r\n\r\n    available = 1:m^2; % Nodes we haven't visited yet.\r\n    branches = [];\r\n    branching = 'middle';   \r\n    tree = zeros(0,2); % Depth first search.\r\n    p = 1;\r\n    \r\n%%\r\n% Now we make a series of random walks on |C|.\r\n   while true  % Break when available is empty\r\n        available(p) = 0;\r\n        if ~any(available)\r\n            break\r\n        end\r\n%%\r\n% Each step is from a node to a random choice\r\n% of one of its neighbors that has not already been visited.\r\n\r\n\r\n        [~,~,ngh] = find(available(neighbors(C,p)));\r\n\r\n        if ~isempty(ngh)\r\n            idx = randi(length(ngh));  % Random choice.\r\n            q = ngh(idx);              % Next cell.\r\n            tree(end+1,:) = [p q];\r\n\r\n%%\r\n% At the same time, the edge in the barrier |B| that is blocking\r\n% the step is removed. \r\n\r\n            [i,j] = wall(p,q);\r\n            B = rmedge(B,i,j);\r\n            \r\n%%  \r\n% We keep a list of the nodes where a random choice between\r\n% two or three neighbors is made.\r\n\r\n            if length(ngh) > 1\r\n                branches(end+1) = p;\r\n            end\r\n            \r\n            p = q;\r\n\r\n%%\r\n% Eventually the walk reaches a dead end, a node whose neighbors have\r\n% all been visited.  Here is the first such walk in our example.\r\n%\r\n% <<amaze_2.png>>\r\n\r\n%% Backtrack\r\n% When we reach a dead end,\r\n% we backtrack to one of the nodes on our list of nodes where we\r\n% had a choice of available neighbors.  Here another kind of choice\r\n% is made.  We can go back to the _first_ node on the list, to the node\r\n% in the _middle_ of the list, or to the _last_ node on the list.\r\n\r\n\r\n        else\r\n\r\n            switch branching\r\n                case 'first'\r\n                    idx = 1;\r\n                case 'last'\r\n                    idx = length(branches);\r\n                otherwise\r\n                    idx = round(length(branches)\/2);\r\n            end\r\n            \r\n            p = branches(idx);\r\n            branches(idx) = [];\r\n        end\r\n\r\n%%\r\n% Here is the result of backtracking to the middle and then walking to\r\n% a second dead end.\r\n%\r\n% <<amaze_3.png>>\r\n%\r\n% Here is the result after several more backtracks.\r\n%\r\n% <<amaze_4.png>>\r\n%%        \r\n\r\n    end\r\n    C = graph(tree(:,1),tree(:,2));\r\n    \r\n%%\r\n% Near the end of this process, the length of a path before a dead end\r\n% and a backtrack becomes shorter and shorter.  A path may involve a\r\n% single point.  Eventually all the nodes in |C| are covered.\r\n% Here is the final result.\r\n%\r\n% <<amaze_5.png>>\r\n\r\n%%\r\n% When the entire path is plotted with |linestyle = 'none'|\r\n% we have the maze.\r\n%\r\n% <<amaze_6.png>>\r\n%\r\n\r\n%% Shortest path\r\n% We can easily \"solve\" the maze by asking for the shortest path\r\n% from one corner to another.\r\n\r\n    path = shortestpath(C,1,m^2);\r\n    \r\n%%\r\n% (_Exercise_: How does the |branching| parameter affect the\r\n% average length of this |path|?) \r\n%\r\n% <<amaze_7.png>>\r\n\r\n%% Animation\r\n%\r\n% <<amaze_movie_1.gif>>\r\n\r\n%% Software\r\n% I have a program called |amazing| that allows you to investigate\r\n% |amaze|.  I've submitted it to the\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\r\n% MATLAB Central File Exchange> and will put the\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/70451-amaze-a-maze-generator\r\n% link here>.\r\n% I will also add |amazing| to version 4.40 of\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/59085-cleve_s-laboratory\r\n% Cleve's Laboratory>.\r\n\r\n%% Thanks\r\n% Thanks to Pat Quillen who provided invaluable help.\r\n##### SOURCE END ##### 1d5efde86d0f4c3794e54d3aa617c6e3\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/amaze_7.png\" class=\"img-responsive attachment-post-thumbnail size-post-thumbnail wp-post-image\" alt=\"\" decoding=\"async\" loading=\"lazy\" \/><\/div><!--introduction--><p>My MATLAB&reg; program, <tt>amaze<\/tt>, generates mazes by combining old friends, <tt>numgrid<\/tt> and <tt>delsq<\/tt>, with a new friend, the <tt>graph<\/tt> object. Let's see how we make this example maze.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2019\/03\/04\/amaze-a-maze-generator\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":4546,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[5,34],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/4472"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/users\/78"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/comments?post=4472"}],"version-history":[{"count":9,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/4472\/revisions"}],"predecessor-version":[{"id":4494,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/4472\/revisions\/4494"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media\/4546"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=4472"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=4472"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=4472"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}