{"id":1520,"date":"2015-12-21T15:42:07","date_gmt":"2015-12-21T20:42:07","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/?p=1520"},"modified":"2019-11-01T12:15:42","modified_gmt":"2019-11-01T16:15:42","slug":"a-cheating-maze-solver-with-image-graphs","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2015\/12\/21\/a-cheating-maze-solver-with-image-graphs\/","title":{"rendered":"A cheating maze solver with image graphs"},"content":{"rendered":"\r\n\r\n<div class=\"content\"><!--introduction--><p><i>Updated 04-Jan-2016 to fix a problem with the maze image that was causing an incorrect result for the cheating maze solver.<\/i><\/p><p>My <a href=\"https:\/\/blogs.mathworks.com\/steve\/2015\/11\/18\/graphs-in-matlab-r2015b\/\">18-Nov-2015 post<\/a> showed some of the basics of the new graph theory functionality in MATLAB R2015b. I followed that up <a href=\"https:\/\/blogs.mathworks.com\/steve\/2015\/12\/14\/image-based-graphs\/\">last week with a post<\/a> about my image-based graphs <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/53-shift\">submission to the File Exchange.<\/a><\/p><p>Today I want to show you a Cheating Maze Solver based on image graphs with weighted edges.<\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#abe44da2-389c-496f-bb1c-6e400c55a96a\">Solving a Maze Using Shortest Path<\/a><\/li><li><a href=\"#0a996362-bc78-47f8-a527-80791c9c505f\">A Cheating Maze Solver<\/a><\/li><\/ul><\/div><h4>Solving a Maze Using Shortest Path<a name=\"abe44da2-389c-496f-bb1c-6e400c55a96a\"><\/a><\/h4><p>Let's start with a maze solver that doesn't cheat. Here's the maze we'll be tackling:<\/p><pre class=\"codeinput\">url = <span class=\"string\">'https:\/\/blogs.mathworks.com\/steve\/files\/maze-51x51.png'<\/span>;\r\nmaze = imread(url);\r\nmaze = maze &gt;= 128;\r\nimshow(maze)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/image_graphs_mazes_01.png\" alt=\"\"> <p>The first step is to construct a graph from the binary image. The nodes of the graph will be the foreground pixels, which are the paths of the maze. (The background pixels form the maze walls.)<\/p><pre class=\"codeinput\">maze_graph = binaryImageGraph(maze)\r\n<\/pre><pre class=\"codeoutput\">\r\nmaze_graph = \r\n\r\n  graph with properties:\r\n\r\n    Edges: [515967x2 table]\r\n    Nodes: [138674x3 table]\r\n\r\n<\/pre><p>Notice that <tt>binaryImageGraph<\/tt> automatically added weights to the graph edges:<\/p><pre class=\"codeinput\">maze_graph.Edges(1:5,:)\r\n<\/pre><pre class=\"codeoutput\">\r\nans = \r\n\r\n    EndNodes    Weight\r\n    ________    ______\r\n\r\n    1     2          1\r\n    1    12          1\r\n    1    13     1.4142\r\n    2     3          1\r\n    2    12     1.4142\r\n\r\n<\/pre><p>These weights are the Euclidean distances between the centers of the neighboring foreground pixels.<\/p><p>The start and finish coordinates for the maze are (1,496) and (533,518), which we can use to find the corresponding graph nodes.<\/p><pre class=\"codeinput\">start_node = find((maze_graph.Nodes.x == 1) &amp; (maze_graph.Nodes.y == 496));\r\nfinish_node = find((maze_graph.Nodes.x == 533) &amp; (maze_graph.Nodes.y == 518));\r\n<\/pre><p>Now we just call <tt>shortestpath<\/tt> to find our way from the start node to the finish node. The function <tt>shortestpath<\/tt> returns a list of graph node indices.<\/p><pre class=\"codeinput\">p = shortestpath(maze_graph,start_node,finish_node);\r\np(1:5)\r\n<\/pre><pre class=\"codeoutput\">\r\nans =\r\n\r\n     5    16    27    38    49\r\n\r\n<\/pre><p>These values can be used to index into the Nodes table of the graph.<\/p><pre class=\"codeinput\">maze_graph.Nodes(p(1:5),:)\r\n<\/pre><pre class=\"codeoutput\">\r\nans = \r\n\r\n    x     y     PixelIndex\r\n    _    ___    __________\r\n\r\n    1    496     496      \r\n    2    496    1029      \r\n    3    496    1562      \r\n    4    496    2095      \r\n    5    496    2628      \r\n\r\n<\/pre><p>Notice that the graph's node table contains the x- and y- coordinates of the corresponding image pixels. The <tt>binaryImageGraph<\/tt> function automatically put that auxiliary information into the graph. We can use it now to plot the shortest path.<\/p><pre class=\"codeinput\">imshow(maze)\r\nhold <span class=\"string\">on<\/span>\r\nplot(maze_graph.Nodes.x(p),maze_graph.Nodes.y(p),<span class=\"string\">'r'<\/span>,<span class=\"string\">'LineWidth'<\/span>,5)\r\nhold <span class=\"string\">off<\/span>\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/image_graphs_mazes_02.png\" alt=\"\"> <h4>A Cheating Maze Solver<a name=\"0a996362-bc78-47f8-a527-80791c9c505f\"><\/a><\/h4><p>Now let's solve the maze by allowing the solution to tunnel through walls. To do that, we need a graph that includes foregound and background pixels, not just foreground pixels. So we build the graph using <tt>imageGraph<\/tt> instead of <tt>binaryImageGraph<\/tt>.<\/p><pre class=\"codeinput\">maze_graph2 = imageGraph(size(maze));\r\n<\/pre><p>For any edge that touches a wall (a background pixel), let's assign a tunneling \"penalty\" by upping the edge weight to 100.<\/p><pre class=\"codeinput\">tunneling_penalty = 100;\r\ntouches_wall = any(~maze(maze_graph2.Edges.EndNodes),2);\r\nmaze_graph2.Edges.Weight(touches_wall) = tunneling_penalty;\r\n<\/pre><p>This new graph has a different number of nodes, so we need to recompute the starting and finishing node numbers.<\/p><pre class=\"codeinput\">start_node = find((maze_graph2.Nodes.x == 1) &amp; (maze_graph2.Nodes.y == 496));\r\nfinish_node = find((maze_graph2.Nodes.x == 533) &amp; (maze_graph2.Nodes.y == 518));\r\n<\/pre><p>Now we're ready to compute the cheating path.<\/p><pre class=\"codeinput\">tunneling_p = shortestpath(maze_graph2,start_node,finish_node);\r\ntunneling_x = maze_graph2.Nodes.x(tunneling_p);\r\ntunneling_y = maze_graph2.Nodes.y(tunneling_p);\r\n\r\nimshow(maze,<span class=\"string\">'InitialMagnification'<\/span>,<span class=\"string\">'fit'<\/span>)\r\nhold <span class=\"string\">on<\/span>\r\nplot(tunneling_x,tunneling_y,<span class=\"string\">'r'<\/span>,<span class=\"string\">'LineWidth'<\/span>,5)\r\nhold <span class=\"string\">off<\/span>\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/image_graphs_mazes_03.png\" alt=\"\"> <p>You can see that the cheating solution tunneled through a wall in just one spot:<\/p><pre class=\"codeinput\">axis([425 535 465 535])\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/image_graphs_mazes_04.png\" alt=\"\"> <p>You can see that the shortest path jogs upwards briefly when tunneling through the wall. That's because I assigned the same edge weight penalty to diagonal neighbors as to horizontal and vertical neighbors. That means that the path length is the same for the up-and-down path as for the horizontal path. I could fix that with a somewhat more complicated edge weight computation.<\/p><p>Happy New Year, everyone!<\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_ae74db9b46104ef5b4b0e3554d368100() {\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='ae74db9b46104ef5b4b0e3554d368100 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' ae74db9b46104ef5b4b0e3554d368100';\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 2016 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_ae74db9b46104ef5b4b0e3554d368100()\"><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; R2015b<br><\/p><\/div><!--\r\nae74db9b46104ef5b4b0e3554d368100 ##### SOURCE BEGIN #####\r\n%% Image Graph Cheating Maze Solver\r\n% _Updated 04-Jan-2016 to fix a problem with the maze image that was causing \r\n% an incorrect result for the cheating maze solver._\r\n%\r\n% My <https:\/\/blogs.mathworks.com\/steve\/2015\/11\/18\/graphs-in-matlab-r2015b\/\r\n% 18-Nov-2015 post> showed some of the basics of the new graph theory\r\n% functionality in MATLAB R2015b. I followed that up\r\n% <https:\/\/blogs.mathworks.com\/steve\/2015\/12\/14\/image-based-graphs\/ last week\r\n% with a post> about my image-based graphs\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/53-shift\r\n% submission to the File Exchange.>\r\n%\r\n% Today I want to show you a Cheating Maze Solver based on image graphs with\r\n% weighted edges.\r\n\r\n%% Solving a Maze Using Shortest Path\r\n% Let's start with a maze solver that doesn't cheat. Here's the maze we'll\r\n% be tackling:\r\n\r\nurl = 'https:\/\/blogs.mathworks.com\/steve\/files\/maze-51x51.png';\r\nmaze = imread(url);\r\nmaze = maze >= 128;\r\nimshow(maze)\r\n\r\n%%\r\n% The first step is to construct a graph from the binary image. The nodes of\r\n% the graph will be the foreground pixels, which are the paths of the maze.\r\n% (The background pixels form the maze walls.)\r\n\r\nmaze_graph = binaryImageGraph(maze)\r\n\r\n%%\r\n% Notice that |binaryImageGraph| automatically added weights to the graph\r\n% edges:\r\n\r\nmaze_graph.Edges(1:5,:)\r\n\r\n%%\r\n% These weights are the Euclidean distances between the centers of the\r\n% neighboring foreground pixels.\r\n\r\n%% \r\n% The start and finish coordinates for the maze are (1,496) and (533,518), \r\n% which we can use to find the corresponding graph nodes.\r\n\r\nstart_node = find((maze_graph.Nodes.x == 1) & (maze_graph.Nodes.y == 496));\r\nfinish_node = find((maze_graph.Nodes.x == 533) & (maze_graph.Nodes.y == 518));\r\n\r\n%% \r\n% Now we just call |shortestpath| to find our way from the start node to the\r\n% finish node. The function |shortestpath| returns a list of graph node\r\n% indices.\r\n\r\np = shortestpath(maze_graph,start_node,finish_node);\r\np(1:5)\r\n\r\n%%\r\n% These values can be used to index into the Nodes table of the graph.\r\n\r\nmaze_graph.Nodes(p(1:5),:)\r\n\r\n%%\r\n% Notice that the graph's node table contains the x- and y- coordinates of\r\n% the corresponding image pixels. The |binaryImageGraph| function\r\n% automatically put that auxiliary information into the graph. We can use it\r\n% now to plot the shortest path.\r\n\r\n%%\r\nimshow(maze)\r\nhold on\r\nplot(maze_graph.Nodes.x(p),maze_graph.Nodes.y(p),'r','LineWidth',5)\r\nhold off\r\n\r\n%% A Cheating Maze Solver\r\n% Now let's solve the maze by allowing the solution to tunnel through walls. \r\n% To do that, we need a graph that includes foregound and background pixels, not \r\n% just foreground pixels. So we build the graph using |imageGraph| instead of \r\n% |binaryImageGraph|.\r\n\r\nmaze_graph2 = imageGraph(size(maze));\r\n%% \r\n% For any edge that touches a wall (a background pixel), let's assign a \r\n% tunneling \"penalty\" by upping the edge weight to 100.\r\n\r\ntunneling_penalty = 100;\r\ntouches_wall = any(~maze(maze_graph2.Edges.EndNodes),2);\r\nmaze_graph2.Edges.Weight(touches_wall) = tunneling_penalty;\r\n%% \r\n% This new graph has a different number of nodes, so we need to recompute \r\n% the starting and finishing node numbers.\r\n\r\nstart_node = find((maze_graph2.Nodes.x == 1) & (maze_graph2.Nodes.y == 496));\r\nfinish_node = find((maze_graph2.Nodes.x == 533) & (maze_graph2.Nodes.y == 518));\r\n%% \r\n% Now we're ready to compute the cheating path.\r\n\r\ntunneling_p = shortestpath(maze_graph2,start_node,finish_node);\r\ntunneling_x = maze_graph2.Nodes.x(tunneling_p);\r\ntunneling_y = maze_graph2.Nodes.y(tunneling_p);\r\n\r\nimshow(maze,'InitialMagnification','fit')\r\nhold on\r\nplot(tunneling_x,tunneling_y,'r','LineWidth',5)\r\nhold off\r\n%% \r\n% You can see that the cheating solution tunneled through a wall in just \r\n% one spot:\r\n\r\naxis([425 535 465 535])\r\n\r\n%%\r\n% You can see that the shortest path jogs upwards briefly when tunneling\r\n% through the wall. That's because I assigned the same edge weight penalty\r\n% to diagonal neighbors as to horizontal and vertical neighbors. That means\r\n% that the path length is the same for the up-and-down path as for the\r\n% horizontal path. I could fix that with a somewhat more complicated edge\r\n% weight computation.\r\n\r\n%%\r\n% Happy New Year, everyone!\r\n##### SOURCE END ##### ae74db9b46104ef5b4b0e3554d368100\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img decoding=\"async\"  class=\"img-responsive\" src=\"https:\/\/blogs.mathworks.com\/steve\/files\/image_graphs_mazes_04.png\" onError=\"this.style.display ='none';\" \/><\/div><!--introduction--><p><i>Updated 04-Jan-2016 to fix a problem with the maze image that was causing an incorrect result for the cheating maze solver.<\/i>... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/steve\/2015\/12\/21\/a-cheating-maze-solver-with-image-graphs\/\">read more >><\/a><\/p>","protected":false},"author":42,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[907,50,348,90,76,36,68,1133],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/1520"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/users\/42"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/comments?post=1520"}],"version-history":[{"count":4,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/1520\/revisions"}],"predecessor-version":[{"id":1537,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/1520\/revisions\/1537"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/media?parent=1520"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/categories?post=1520"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/tags?post=1520"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}