{"id":1031,"date":"2015-04-02T07:10:45","date_gmt":"2015-04-02T14:10:45","guid":{"rendered":"http:\/\/www.giassa.net\/?page_id=1031"},"modified":"2025-08-24T08:03:52","modified_gmt":"2025-08-24T15:03:52","slug":"maze-generation-solving","status":"publish","type":"page","link":"https:\/\/www.giassa.net\/?page_id=1031","title":{"rendered":"Maze Generation &#038; Solving"},"content":{"rendered":"<p>Generating and solving a 2D maze is a surprisingly simple task. In order to first create a maze with a single unique solution, we define a maze, <img src='https:\/\/s0.wp.com\/latex.php?latex=A&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='A' title='A' class='latex' \/>, with dimensions <img src='https:\/\/s0.wp.com\/latex.php?latex=m&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='m' title='m' class='latex' \/> by <img src='https:\/\/s0.wp.com\/latex.php?latex=n&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='n' title='n' class='latex' \/>, to be an array of &#8220;cells&#8221;, which have four &#8220;sides&#8221;. Each side is a set of parameters:<\/p>\n<ul>\n<li>Border: whether or not that side is part of the outlying border surrounding the maze.<\/li>\n<li>Wall: whether or not that side is a wall which cannot be traversed.<\/li>\n<li>Solution: whether or not that side is an open area which is part of the path one takes to reach the end up the maze successfully.<\/li>\n<li>Backtrack: whether or not that size is an open area which has been traversed, but is not part of the &#8220;solution&#8221; path.<\/li>\n<li>Coordinates: the [x,y] coordinates of the cell.<\/li>\n<\/ul>\n<p>With these definitions in place, generating a maze is quite simple.<\/p>\n<ul>\n<li>Create a stack structure to hold a set of type &#8220;cell&#8221;.<\/li>\n<li>For each cell\n<ul>\n<li>For each side\n<ul>\n<li>Set all walls.<\/li>\n<li>Clear all solutions and backtracks.<\/li>\n<li>Set the coordinates appropriately.<\/li>\n<li>Set the borders appropriately.<\/li>\n<\/ul>\n<\/li>\n<li>Create an index to keep track of the number of &#8220;visited&#8221; cells, <img src='https:\/\/s0.wp.com\/latex.php?latex=v&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='v' title='v' class='latex' \/>, and set it to zero.<\/li>\n<li>Calculate the total number of cells, <img src='https:\/\/s0.wp.com\/latex.php?latex=T%3Dmn&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='T=mn' title='T=mn' class='latex' \/>.<\/li>\n<li>Pick an arbitrary starting point in the maze, <img src='https:\/\/s0.wp.com\/latex.php?latex=%5Bi%2Cj%5D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='[i,j]' title='[i,j]' class='latex' \/>.<\/li>\n<li>Define the current cell under analysis, <img src='https:\/\/s0.wp.com\/latex.php?latex=C&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='C' title='C' class='latex' \/>, as the cell located at <img src='https:\/\/s0.wp.com\/latex.php?latex=%5Bi%2Cj%5D&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='[i,j]' title='[i,j]' class='latex' \/>.<\/li>\n<li>While <img src='https:\/\/s0.wp.com\/latex.php?latex=v+%5Cle+T&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='v \\le T' title='v \\le T' class='latex' \/>:\n<ul>\n<li>Push the coordinates of <img src='https:\/\/s0.wp.com\/latex.php?latex=C&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='C' title='C' class='latex' \/> onto the stack.<\/li>\n<li>Mark <img src='https:\/\/s0.wp.com\/latex.php?latex=C&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='C' title='C' class='latex' \/> as &#8220;visited&#8221;.<\/li>\n<li>Generate a list of all the neighbouring cells of <img src='https:\/\/s0.wp.com\/latex.php?latex=C&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='C' title='C' class='latex' \/> with all four of their own walls untouched, <img src='https:\/\/s0.wp.com\/latex.php?latex=L&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='L' title='L' class='latex' \/>.<\/li>\n<li>If <img src='https:\/\/s0.wp.com\/latex.php?latex=%5C%7CL%5C%7C+%5Cgeq+1&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='\\|L\\| \\geq 1' title='\\|L\\| \\geq 1' class='latex' \/>\n<ul>\n<li>Randomly pick an element of <img src='https:\/\/s0.wp.com\/latex.php?latex=L&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='L' title='L' class='latex' \/>.<\/li>\n<li>Push <img src='https:\/\/s0.wp.com\/latex.php?latex=C&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='C' title='C' class='latex' \/> onto the stack.<\/li>\n<li>Smash down just the one wall between <img src='https:\/\/s0.wp.com\/latex.php?latex=C&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='C' title='C' class='latex' \/> and <img src='https:\/\/s0.wp.com\/latex.php?latex=L&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='L' title='L' class='latex' \/>.<\/li>\n<li>Set <img src='https:\/\/s0.wp.com\/latex.php?latex=C&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='C' title='C' class='latex' \/> to be <img src='https:\/\/s0.wp.com\/latex.php?latex=L&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='L' title='L' class='latex' \/>.<\/li>\n<\/ul>\n<\/li>\n<li>Else\n<ul>\n<li>Pop the top item off of the stack, and set <img src='https:\/\/s0.wp.com\/latex.php?latex=C&#038;bg=ffffff&#038;fg=000000&#038;s=0' alt='C' title='C' class='latex' \/> to be equal to it.<\/li>\n<\/ul>\n<\/li>\n<li>EndIf<\/li>\n<\/ul>\n<\/li>\n<li>EndWhile<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>The end result is a long winding maze where there is only a single unique path between any two points. Solving it is also very straight forward. We pick a start and end point, and repeat the depth-first search while keeping track of cells we&#8217;ve already visited. When we finally find the destination, we backtrack to the starting point, indicating whether part of our backtrack is part of the solution path.<\/p>\n<p>A final note: the depth-first search tends to generate long paths that are easy to solve even by hand. If you wish to generate more complicated mazes, consider doing a breadth-first search in the maze generation. Doing so is just a matter of swapping out the stack with a queue, and the majority of the pseudo code described above remains unchanged.<\/p>\n<p>An animation demonstrating this algorithm is shown below, along with the original source code used to generate it. The animated GIF was generated by printing the entire maze to a series of text files and using ImageMagick to create the individual frames of animation and combine them into a GIF.<\/p>\n<div id=\"attachment_1030\" style=\"width: 348px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" decoding=\"async\" aria-describedby=\"caption-attachment-1030\" class=\"size-full wp-image-1030\" src=\"https:\/\/www.giassa.net\/wp-content\/uploads\/2015\/04\/maze2.gif\" alt=\"Maze generation and solving animation\" width=\"338\" height=\"309\" \/><p id=\"caption-attachment-1030\" class=\"wp-caption-text\">Maze generation and solving animation<\/p><\/div>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<pre class=\"lang:default decode:true \" title=\"Header file for maze.c\">#ifndef MAZE_H \/\/ Prevent multiple inclusions\r\n#define MAZE_H\r\n\r\n\/*******************************************************************************\r\n * Preprocessor Directives\r\n ******************************************************************************\/\r\n#include &lt;stdint.h&gt;\r\n\r\n#include \"stack.h\"\r\n\r\n\/*******************************************************************************\r\n * Macros and Constants\r\n ******************************************************************************\/\r\n\/* Directional bit identities *\/\r\n#define WEST   (0x1&lt;&lt;3)\r\n#define SOUTH  (0x1&lt;&lt;2)\r\n#define EAST   (0x1&lt;&lt;1)\r\n#define NORTH  (0x1&lt;&lt;0)\r\n\r\n#define BITMAP_SIZE  (3)\r\n\r\n\/*******************************************************************************\r\n * Abstract Data Types\r\n ******************************************************************************\/\r\ntypedef struct status_t {\r\n   uint16_t backtrack : 4;\r\n   uint16_t solution  : 4;\r\n   uint16_t border    : 4;\r\n   uint16_t wall      : 4;\r\n} status_t;\r\n\r\n\r\ntypedef struct cell_t {\r\n   status_t status;\r\n   int      x;\r\n   int      y;\r\n   int      bVisited;\r\n   char     bitmap[BITMAP_SIZE][BITMAP_SIZE];\r\n} cell_t;\r\n\r\ntypedef struct maze_t {\r\n   cell_t** maze;\r\n   stack_t  stack;\r\n   int      xMax;\r\n   int      yMax;\r\n   int      totalCells;\r\n} maze_t;\r\n\r\n\r\n\/*******************************************************************************\r\n * Public Function Prototypes\r\n *******************************************************************************\/\r\n\/* Handle compiling C code as part of a C++ project *\/\r\n#ifdef __cplusplus\r\nextern \"C\" {\r\n#endif\r\n\r\n\/* @functionName: stackInit\r\n * @brief:        Initializes an empty stack.\r\n * @param:        stk: A pointer to the stack.\r\n *\/\r\n\/\/int stackInit(stack_t* stk);\r\nint  mazeInit(maze_t* maze, size_t width, size_t height);\r\nint  mazeDestroy(maze_t* maze);\r\nint  mazeSolve(maze_t* maze);\r\nvoid mazeRender(maze_t* m);\r\n\r\n\r\n#ifdef __cplusplus\r\n}\r\n#endif\r\n\r\n#endif \/\/ MAZE_H\r\n<\/pre>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<pre class=\"lang:c decode:true\" title=\"Depth-first maze generation and solving\">\/*******************************************************************************\r\n * @file:      maze.c\r\n * @author:    Matthew Giassa\r\n * @email:     matthew@giassa.net\r\n * @copyright: Matthew Giassa, 2009\r\n * @brief:     Used to generate and solve perfect mazes (every space utilized)\r\n *             as part of a robotic mouse-in-a-maze robotic vision project.\r\n *\/\r\n\r\n\/*******************************************************************************\r\n * Preprocessor Directives\r\n ******************************************************************************\/\r\n\/* System Includes *\/\r\n#include &lt;stdio.h&gt;\r\n#include &lt;errno.h&gt;\r\n#include &lt;stdlib.h&gt;\r\n#include &lt;string.h&gt;\r\n#include &lt;time.h&gt;\r\n#include &lt;stdbool.h&gt;\r\n#include &lt;unistd.h&gt;\r\n#include &lt;linux\/limits.h&gt;\r\n\r\n\/* Project Includes *\/\r\n#include \"inc\/linked_list.h\"\r\n#include \"inc\/maze.h\"\r\n\r\n\r\n\/*******************************************************************************\r\n * Macros and Constants\r\n ******************************************************************************\/\r\n#define EOK (0)\r\n#define ANIMATION_DELAY_US (50000)\r\n\r\n\/\/#define RENDER_GIF\r\n\/\/#define ANIMATED_ON_SCREEN\r\n\r\nstatic int outCount = 0;\r\n\r\n\/*******************************************************************************\r\n * Abstract Data Types\r\n ******************************************************************************\/\r\ntypedef struct coords_t {\r\n   int x;\r\n   int y;\r\n} coords_t;\r\n\r\ntypedef uint8_t direction_t;\r\n\r\n\r\n\/*******************************************************************************\r\n * Private Function Prototypes\r\n ******************************************************************************\/\r\n\/* Tells us if two cells are within the extremities of an array ie: [0, dimMax]\r\n * so a future operation does trigger a segfault due to addressing invalid\r\n * memory.\r\n *\/\r\nbool inRange(int x, int y, int xMax, int yMax);\r\n\r\n\/* Tells us if two cells are in range of each other (ie: 4-connected \r\n * neighbours.\r\n *\/\r\nbool isConnected4(int x1, int y1, int x2, int y2);\r\n\r\n\/* Takes a pair of coordinates, and if they are 4-neighbours, converts the\r\n * coordinates into a constants representing one of 4 cartesian unit vectors.\r\n *\/\r\ndirection_t direction(int x1, int y1, int x2, int y2);\r\n\r\n\/* Provides the inverse of the the direction() function.\r\n *\/\r\ndirection_t reverseDirection(int dir);\r\n\r\n\/* Tells us if it is possible to travel from one location to another, taking\r\n * into account whether there is a wall between the two coordinates.\r\n *\/\r\nbool isAccessible(int x1, int y1, status_t status1, int x2, int y2, status_t status2);\r\n\r\n\r\n\/*******************************************************************************\r\n * Function Definitions\r\n ******************************************************************************\/\r\n\/*----------------------------------------------------------------------------*\/\r\nint main(void) {\r\n   maze_t maze = { 0 };\r\n\r\n   \/* Initialize random seed *\/\r\n   srand(time(NULL));\r\n\r\n   setbuf(stdout, NULL);\r\n\r\n   \/* Determine size of map to generate *\/\r\n   const int x = 16;\r\n   const int y = 9;\r\n\r\n   \/* Generate random maze *\/\r\n   if (mazeInit(&amp;maze, x, y) != EOK) {\r\n      printf(\"Failed to generate maze.\\n\");\r\n      return (-EIO);\r\n   } else {\r\n      system(\"clear\");\r\n   }\r\n\r\n   \/* Solve the maze *\/\r\n   mazeSolve(&amp;maze);\r\n\r\n   \/* Print maze to screen *\/\r\n   mazeRender(&amp;maze);\r\n\r\n   \/* Clean up *\/\r\n   mazeDestroy(&amp;maze);\r\n\r\n#ifdef RENDER_GIF\r\n   system(\"convert *.png -set delay 10 output.gif\");\r\n#endif\r\n\r\n   return EOK;\r\n}\r\n\r\n\r\n\/*----------------------------------------------------------------------------*\/\r\nint mazeInit(maze_t* m, size_t width, size_t height) {\r\n   if (!m || width &lt;= 0 || height &lt;= 0) {\r\n      return (-EINVAL);\r\n   }\r\n   int i, j, k, a, b, ret = EOK;\r\n   llist_t list = { 0 };   \/* For storing \"neighbours\" during generation *\/\r\n   bool bErr = false;\r\n   int iVisited = 0;\r\n   coords_t cur;\r\n\r\n   \/* Initialize and dynamically allocate memory as needed *\/\r\n   if (stackInit(&amp;m-&gt;stack) != EOK) {\r\n      bErr = true;\r\n   }\r\n   \/* Store dimensions *\/\r\n   m-&gt;xMax = width;\r\n   m-&gt;yMax = height;\r\n   m-&gt;totalCells = m-&gt;xMax * m-&gt;yMax;\r\n   if (!bErr) {\r\n      if ((m-&gt;maze = (cell_t**)calloc(m-&gt;xMax, sizeof(cell_t*))) == NULL) {\r\n         bErr = true;\r\n      }\r\n      for (i=0; i&lt;m-&gt;xMax; i++) {\r\n         if ((m-&gt;maze[i] = (cell_t*)calloc(m-&gt;yMax, sizeof(cell_t))) == NULL) {\r\n            bErr = true;\r\n            break;\r\n         }\r\n      }\r\n   }\r\n\r\n   \/* Populate cells with coordinates, walls *\/\r\n   for (i=0; i&lt;m-&gt;xMax; i++) {\r\n      for (j=0; j&lt;m-&gt;yMax; j++) {\r\n         m-&gt;maze[i][j].x = j;\r\n         m-&gt;maze[i][j].y = i;\r\n         m-&gt;maze[i][j].bVisited = false;\r\n         \/* Build all walls *\/\r\n         m-&gt;maze[i][j].status.wall = NORTH | SOUTH | EAST | WEST;\r\n      }\r\n   }\r\n   \/* Populate borders *\/\r\n   for (i=0; i&lt;m-&gt;xMax; i++) {\r\n      a = i;\r\n      b = 0;\r\n      m-&gt;maze[a][b].status.border |= NORTH;\r\n   }\r\n   for (i=0; i&lt;m-&gt;xMax; i++) {\r\n      a = i;\r\n      b = m-&gt;yMax-1;\r\n      m-&gt;maze[a][b].status.border |= SOUTH;\r\n   }\r\n   for (i=0; i&lt;m-&gt;yMax; i++) {\r\n      a = 0;\r\n      b = i;\r\n      m-&gt;maze[a][b].status.border |= WEST;\r\n   }\r\n   for (i=0; i&lt;m-&gt;yMax; i++) {\r\n      a = m-&gt;xMax-1;\r\n      b = i;\r\n      m-&gt;maze[a][b].status.border |= EAST;\r\n   }\r\n\r\n   \/* Start depth-first-search generation of maze *\/\r\n   cur.x = 0;\r\n   cur.y = 0;\r\n   iVisited = 1;\r\n\r\n   \/* Evaluate all cells in maze to make this a \"perfect\" maze with a unique\r\n    * path between any two arbitrary points in the maze.\r\n    *\/\r\n   while (iVisited &lt; m-&gt;totalCells) {\r\n      (void)llistInit(&amp;list);\r\n      for (i=-1; i&lt;=1; i++) {\r\n         for (j=-1; j&lt;=1; j++) {\r\n            \/* Scan all valid neighboring cells *\/\r\n            if ((i==0) &amp;&amp; (j==0)) {\r\n               continue;\r\n            }\r\n            \/* Make sure we don't try to address out-of-bounds memory via\r\n             * sloppy indexing.\r\n             *\/\r\n            if (inRange(cur.x+i, cur.y+j, m-&gt;xMax, m-&gt;yMax)) {\r\n               \/* Are the two cells 4-neighbours *\/\r\n               if (isConnected4(cur.x, cur.y, cur.x+i, cur.y+j)) {\r\n                  \/* Are all 4 walls for the cell intact *\/\r\n                  if (m-&gt;maze[cur.x+i][cur.y+j].status.wall == (NORTH | SOUTH | WEST | EAST)) {\r\n                     \/* All walls are intact; Add cell coordinates to list *\/\r\n                     lnode_t tmp;\r\n                     coords_t coords;\r\n                     coords.x = cur.x+i;\r\n                     coords.y = cur.y+j;\r\n                     tmp.width = sizeof(coords_t);\r\n                     tmp.data = &amp;coords;\r\n                     if (EOK != llistInsert(&amp;list, &amp;tmp)) {\r\n                        printf(\"INSERT ERROR\\n\");\r\n                     }\r\n                  }\r\n               }\r\n            }\r\n         }\r\n      }\r\n      \/* Show maze being generated *\/\r\n#ifdef ANIMATED_ON_SCREEN\r\n      mazeRender(m);\r\n#endif\r\n      \/* Found a valid unvisited 4-neighbour cell *\/\r\n      if (list.length &gt; 0) {\r\n         \/* Pick a random cell from the list of neighbouring cells with intact walls *\/\r\n         int offset = rand() % list.length;\r\n         lnode_t* tmp = list.head;\r\n         for (k=0; k&lt;offset; k++) {\r\n            tmp = tmp-&gt;next;\r\n         }\r\n         \/* Knock down the wall between the current cell and the random neighbour *\/\r\n         coords_t* newCoords = (coords_t*)tmp-&gt;data;\r\n         cell_t* currentCell = &amp;m-&gt;maze[cur.x][cur.y];\r\n         cell_t* neighbourCell = &amp;m-&gt;maze[newCoords-&gt;x][newCoords-&gt;y];\r\n         direction_t dir = direction(cur.x, cur.y, newCoords-&gt;x, newCoords-&gt;y);\r\n         currentCell-&gt;status.wall &amp;= ~dir;\r\n         neighbourCell-&gt;status.wall &amp;= ~reverseDirection(dir);\r\n         \/* Push current cell on to the stack now that walls are knocked down *\/\r\n         snode_t node = { 0 };\r\n         node.data = &amp;cur;\r\n         node.width = sizeof(coords_t);\r\n         stackPush(&amp;m-&gt;stack, &amp;node);\r\n         cur.x = newCoords-&gt;x;\r\n         cur.y = newCoords-&gt;y;\r\n         iVisited++;\r\n      } else {\r\n         \/* Pop the top entry from the stack, set to current coordinates *\/\r\n         snode_t node = { 0 };\r\n         stackPop(&amp;m-&gt;stack, &amp;node);\r\n         coords_t* coords = node.data;\r\n         cur.x = coords-&gt;x;\r\n         cur.y = coords-&gt;y;\r\n         free(node.data);\r\n      }\r\n\r\n      \/* Clean up temporary list *\/\r\n      (void)llistDestroy(&amp;list);\r\n   }\r\n\r\n   \/* Cleanup on error *\/\r\n   if (bErr) {\r\n      for (i=0; i&lt;m-&gt;yMax; i++) {\r\n         free(m-&gt;maze[i]);\r\n         m-&gt;maze[i] = NULL;\r\n      }\r\n      free(m-&gt;maze);\r\n      m-&gt;maze = NULL;\r\n      ret = (-ENOMEM);\r\n   }\r\n   \/* Cleanup stack *\/\r\n   stackDestroy(&amp;m-&gt;stack);\r\n\r\n   return ret;\r\n}\r\n\r\n\r\n\/*----------------------------------------------------------------------------*\/\r\nint mazeSolve(maze_t* m) {\r\n   if (!m) {\r\n      return (-EINVAL);\r\n   }\r\n   int i, j;\r\n   int ret = EOK;\r\n   llist_t list = { 0 };   \/* For storing \"neighbours\" during generation *\/\r\n   bool bFound = false;\r\n   bool bErr = false;\r\n   coords_t cur, sol;\r\n   coords_t* next;\r\n\r\n   \/* Initialize and dynamically allocate memory as needed *\/\r\n   if (stackInit(&amp;m-&gt;stack) != EOK) {\r\n      return (-EIO);\r\n   }\r\n\r\n   \/* Start depth-first-search generation of maze *\/\r\n   cur.x = 0;\r\n   cur.y = 0;\r\n   sol.x = m-&gt;xMax-1;\r\n   sol.y = m-&gt;yMax-1;\r\n   m-&gt;maze[cur.x][cur.y].bVisited = true;\r\n\r\n   while (!bFound &amp;&amp; !bErr) {\r\n      (void)llistInit(&amp;list);\r\n      for (i=-1; i&lt;=1; i++) {\r\n         for (j=-1; j&lt;=1; j++) {\r\n            \/* Scan all valid neighboring cells *\/\r\n            if ((i==0) &amp;&amp; (j==0)) {\r\n               continue;\r\n            }\r\n            if ((cur.x == sol.x) &amp;&amp; (cur.y == sol.y)) {\r\n               bFound = true;\r\n               continue;\r\n            }\r\n            \/* Make sure we don't try to address out-of-bounds memory via\r\n             * sloppy indexing.\r\n             *\/\r\n            if (inRange(cur.x+i, cur.y+j, m-&gt;xMax, m-&gt;yMax)) {\r\n               \/* Are the two cells 4-neighbours *\/\r\n               if (isConnected4(cur.x, cur.y, cur.x+i, cur.y+j)) {\r\n                  \/* Is the destination cell unvisited *\/\r\n                  if (!m-&gt;maze[cur.x+i][cur.y+j].bVisited) {\r\n                     \/* Is the neighbouring cell accessible (ie: no walls in the way) *\/\r\n                     if (isAccessible(cur.x, cur.y, m-&gt;maze[cur.x][cur.y].status,\r\n                           cur.x+i, cur.y+j, m-&gt;maze[cur.x+i][cur.y+j].status)) {\r\n                        lnode_t tmp;\r\n                        coords_t coords;\r\n                        coords.x = cur.x+i;\r\n                        coords.y = cur.y+j;\r\n                        tmp.width = sizeof(coords_t);\r\n                        tmp.data = &amp;coords;\r\n                        if (EOK != llistInsert(&amp;list, &amp;tmp)) {\r\n                           printf(\"INSERT ERROR\\n\");\r\n                        }\r\n                     }\r\n                  }\r\n               }\r\n            }\r\n         }\r\n      }\r\n      \/* Show maze being solved *\/\r\n#ifdef ANIMATED_ON_SCREEN\r\n      mazeRender(m);\r\n#endif\r\n      \/* Handle completion when end of maze is found *\/\r\n      if (bFound) {\r\n         \/* Process entire stack *\/\r\n         while (m-&gt;stack.top != NULL) {\r\n            \/* Show maze being solved *\/\r\n#ifdef ANIMATED_ON_SCREEN\r\n            mazeRender(m);\r\n#endif\r\n            snode_t node = { 0 };\r\n            if (stackPop(&amp;m-&gt;stack, &amp;node) == EOK) {\r\n               coords_t* coords = node.data;\r\n               printf(\"Coordinates of solution path: [%02d,%02d]\\n\", coords-&gt;x, coords-&gt;y);\r\n               direction_t dir = direction(cur.x, cur.y, coords-&gt;x, coords-&gt;y);\r\n               if (bFound) {\r\n                  m-&gt;maze[cur.x][cur.y].status.solution |= dir;\r\n               }\r\n               cur.x = coords-&gt;x;\r\n               cur.y = coords-&gt;y;\r\n               if (bFound) {\r\n                  m-&gt;maze[cur.x][cur.y].status.solution |= reverseDirection(dir);\r\n               }\r\n               free(node.data);\r\n            }\r\n         }\r\n      } else {\r\n         \/* Still searching the maze *\/\r\n         if (list.length &gt; 0) {\r\n            \/* Found a valid accessible 4-neighbour cell. Pick a random cell\r\n             * from the list of valid cells.\r\n             *\/\r\n            int offset = rand() % list.length;\r\n            int k;\r\n            lnode_t* tmp = list.head;\r\n            for (k=0; k&lt;offset; k++) {\r\n               tmp = tmp-&gt;next;\r\n            }\r\n            next = (coords_t*)tmp-&gt;data;\r\n            \/* Push current cell on to the stack *\/\r\n            snode_t node = { 0 };\r\n            node.data = &amp;cur;\r\n            node.width = sizeof(coords_t);\r\n            if (stackPush(&amp;m-&gt;stack, &amp;node) != EOK) {\r\n               printf(\"Stack push error; Aborting\\n\");\r\n               bErr = true;\r\n            }\r\n            direction_t dir = direction(cur.x, cur.y, next-&gt;x, next-&gt;y);\r\n            m-&gt;maze[cur.x][cur.y].status.backtrack |= dir;\r\n            cur.x = next-&gt;x;\r\n            cur.y = next-&gt;y;\r\n            m-&gt;maze[cur.x][cur.y].status.backtrack = reverseDirection(dir);\r\n            m-&gt;maze[cur.x][cur.y].bVisited = true;\r\n         } else {\r\n            \/* Pop the top entry from the stack, set to current coordinates *\/\r\n            snode_t node = { 0 };\r\n            if (stackPop(&amp;m-&gt;stack, &amp;node) == EOK) {\r\n               coords_t* coords = node.data;\r\n               cur.x = coords-&gt;x;\r\n               cur.y = coords-&gt;y;\r\n               free(node.data);\r\n            } else {\r\n               printf(\"Could not pop node\\n\");\r\n               bErr = true;\r\n            }\r\n         }\r\n      }\r\n\r\n      \/* Clean up temporary list *\/\r\n      (void)llistDestroy(&amp;list);\r\n   }\r\n\r\n   \/* Cleanup on error *\/\r\n   stackDestroy(&amp;m-&gt;stack);\r\n\r\n   return ret;\r\n}\r\n\r\n\r\n\/*----------------------------------------------------------------------------*\/\r\nvoid mazeRender(maze_t* m) {\r\n   if (!m) {\r\n      return;\r\n   }\r\n   int i, j, k, l;\r\n   int dirSides[4] = { WEST, SOUTH, EAST, NORTH };\r\n   coords_t coordSides[4] = { {0, 1}, {1, 2}, {2, 1}, {1, 0} };\r\n   int dirDiags[4] = { NORTH | WEST, SOUTH | WEST, NORTH | EAST, SOUTH | EAST };\r\n   coords_t coordDiags[4] = { {0, 0}, {0, 2}, {2, 0}, {2, 2} };\r\n   cell_t* c;\r\n   direction_t wall, sol, bt, border;\r\n\r\n   \/* Generate bitmaps for each cell *\/\r\n   for (j=0; j&lt;m-&gt;yMax; j++) {\r\n      for (i=0; i&lt;m-&gt;xMax; i++) {\r\n         c = &amp;m-&gt;maze[i][j];\r\n         wall = c-&gt;status.wall;\r\n         sol = c-&gt;status.solution;\r\n         bt = c-&gt;status.backtrack;\r\n         border = c-&gt;status.border;\r\n         \/* Sanity check *\/\r\n         for (k=0; k&lt;4; k++) {\r\n            if (((wall &amp; dirSides[k]) || (border &amp; dirSides[k])) &amp;&amp;\r\n                  ((bt &amp; dirSides[k]) || (sol &amp; dirSides[k]))) {\r\n               \/* Cannot have a portion of the cell be simultaneously a wall\/border\r\n                * and a solution\/backtrack area (mutually exclusive).\r\n                *\/\r\n               printf(\"Portion of maze is broken\\n\");\r\n            }\r\n         }\r\n         \/* Set sides *\/\r\n         for (k=0; k&lt;4; k++) {\r\n            if (sol &amp; dirSides[k]) {\r\n               c-&gt;bitmap[coordSides[k].x][coordSides[k].y] = '*';\r\n            } else if (bt &amp; dirSides[k]) {\r\n               c-&gt;bitmap[coordSides[k].x][coordSides[k].y] = '.';\r\n            } else if (border &amp; dirSides[k]) {\r\n               c-&gt;bitmap[coordSides[k].x][coordSides[k].y] = '=';\r\n            } else if (wall &amp; dirSides[k]) {\r\n               c-&gt;bitmap[coordSides[k].x][coordSides[k].y] = '#';\r\n            } else {\r\n               c-&gt;bitmap[coordSides[k].x][coordSides[k].y] = ' ';\r\n            }\r\n         }\r\n         \/* Set corners *\/\r\n         for (k=0; k&lt;4; k++) {\r\n            if (border &amp; dirDiags[k]) {\r\n               c-&gt;bitmap[coordDiags[k].x][coordDiags[k].y] = '=';\r\n            } else {\r\n               c-&gt;bitmap[coordDiags[k].x][coordDiags[k].y] = '#';\r\n            }\r\n         }\r\n         \/* Set centre *\/\r\n         if (sol) {\r\n            c-&gt;bitmap[1][1] = '*';\r\n         } else if (bt) {\r\n            c-&gt;bitmap[1][1] = '.';\r\n         } else {\r\n            c-&gt;bitmap[1][1] = ' ';\r\n         }\r\n      }\r\n   }\r\n\r\n   char* buf;\r\n   size_t bufsize = (BITMAP_SIZE*BITMAP_SIZE*(m-&gt;xMax)*(m-&gt;yMax)) + (BITMAP_SIZE*m-&gt;yMax);\r\n   if ((buf = calloc(bufsize, sizeof(char))) == NULL) {\r\n      \/* Couldn't allocate output buffer; Abort *\/\r\n      return;\r\n   }\r\n\r\n   \/* Render maze *\/\r\n   int cnt = 0;\r\n   for (j=0; j&lt;m-&gt;yMax; j++) {\r\n      for (l=0; l&lt;BITMAP_SIZE; l++) {\r\n         for (i=0; i&lt;m-&gt;xMax; i++) {\r\n            c = &amp;m-&gt;maze[i][j];\r\n            for (k=0; k&lt;BITMAP_SIZE; k++) {\r\n               buf[cnt++] = c-&gt;bitmap[k][l];\r\n            }\r\n         }\r\n         buf[cnt++] = '\\n';\r\n      }\r\n   }\r\n\r\n#ifdef RENDER_GIF\r\n   FILE* fp;\r\n   char txtname[PATH_MAX];\r\n   char picname[PATH_MAX];\r\n   char command[PATH_MAX];\r\n   sprintf(txtname, \"%04d.txt\", outCount);\r\n   sprintf(picname, \"%04d.png\", outCount);\r\n   outCount++;\r\n   if ((fp = fopen(txtname, \"w\")) != NULL) {\r\n      fprintf(fp, \"%s\", buf);\r\n      fclose(fp);\r\n      sprintf(command, \"convert -font Courier -pointsize 12  \\\"label:@%s\\\" %s\", txtname, picname);\r\n      system(command);\r\n   }\r\n#endif\r\n   \/* Print buffer to screen *\/\r\n   write(STDOUT_FILENO, buf, strlen(buf));\r\n   printf(\"\\n\");\r\n   fflush(stdout);\r\n   usleep(ANIMATION_DELAY_US);\r\n   system(\"clear\");\r\n\r\n}\r\n\r\n\/*----------------------------------------------------------------------------*\/\r\nint mazeDestroy(maze_t* m) {\r\n   if (!m) {\r\n      return (-EINVAL);\r\n   }\r\n   int i;\r\n\r\n   stackDestroy(&amp;m-&gt;stack);\r\n\r\n   for (i=0; i&lt;m-&gt;xMax; i++) {\r\n      free(m-&gt;maze[i]);\r\n      m-&gt;maze[i] = NULL;\r\n   }\r\n   free(m-&gt;maze);\r\n   m-&gt;maze = NULL;\r\n\r\n   return EOK;\r\n}\r\n\r\n\r\n\/*----------------------------------------------------------------------------*\/\r\nbool inRange(int x, int y, int xMax, int yMax) {\r\n   return ((x &gt;= 0) &amp;&amp; (y &gt;= 0) &amp;&amp; (x &lt;= xMax-1) &amp;&amp; (y &lt;= yMax - 1));\r\n}\r\n\r\n\r\n\/*----------------------------------------------------------------------------*\/\r\nbool isConnected4(int x1, int y1, int x2, int y2) {\r\n   return (\r\n         ((x1 == x2)    &amp;&amp; (y1 == y2+1))  ||\r\n         ((x1 == x2)    &amp;&amp; (y1 == y2-1))  ||\r\n         ((x1 == x2+1)  &amp;&amp; (y1 == y2))    ||\r\n         ((x1 == x2-1)  &amp;&amp; (y1 == y2))\r\n         );\r\n}\r\n\r\n\r\n\/*----------------------------------------------------------------------------*\/\r\nbool isAccessible(int x1, int y1, status_t status1, int x2, int y2, status_t status2) {\r\n   bool ret = false;\r\n   if ((x1 == x2) &amp;&amp; (y1 == y2-1)) {\r\n      if (!(status1.wall &amp; SOUTH) &amp;&amp; !(status2.wall &amp; NORTH)) {\r\n         ret = true;\r\n      }\r\n   }\r\n   if( (x1 == x2) &amp;&amp; (y1 == y2+1)) {\r\n      if (!(status1.wall &amp; NORTH) &amp;&amp; !(status2.wall &amp; SOUTH)) {\r\n         ret = true;\r\n      }\r\n   }\r\n   if ((x1 == x2+1) &amp;&amp; (y1 == y2)) {\r\n      if (!(status1.wall &amp; WEST) &amp;&amp; !(status2.wall &amp; EAST)) {\r\n         ret = true;\r\n      }\r\n   }\r\n   if ((x1 == x2-1) &amp;&amp; (y1 == y2)) {\r\n      if (!(status1.wall &amp; EAST) &amp;&amp; !(status2.wall &amp; WEST)) {\r\n         ret = true;\r\n      }\r\n   }\r\n   return ret;\r\n}\r\n\r\n\r\n\/*----------------------------------------------------------------------------*\/\r\ndirection_t direction(int x1, int y1, int x2, int y2) {\r\n   direction_t ret = 0xff;\r\n   if (x1 == x2) {\r\n      if (y2 == y1+1) {\r\n         ret = SOUTH;\r\n      } else if (y2 == y1-1) {\r\n         ret = NORTH;\r\n      }\r\n   }\r\n   if (y1 == y2) {\r\n      if (x2 == x1 -1) {\r\n         ret = WEST;\r\n      } else if (x2 == x1+1) {\r\n         ret = EAST;\r\n      }\r\n   }\r\n   return ret;\r\n}\r\n\r\n\r\n\/*----------------------------------------------------------------------------*\/\r\ndirection_t reverseDirection(int dir) {\r\n   direction_t ret = 0xFF;\r\n   switch(dir) {\r\n      case NORTH:\r\n         ret = SOUTH;\r\n         break;\r\n      case SOUTH:\r\n         ret = NORTH;\r\n         break;\r\n      case EAST:\r\n         ret = WEST;\r\n         break;\r\n      case WEST:\r\n         ret = EAST;\r\n         break;\r\n      default:\r\n         break;\r\n   }\r\n   return ret;\r\n}\r\n\r\n\r\n\r\n<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Generating and solving a 2D maze is a surprisingly simple task. In order to first create a maze with a single unique solution, we define a maze, , with dimensions by , to be an array of &#8220;cells&#8221;, which have &hellip; <a href=\"https:\/\/www.giassa.net\/?page_id=1031\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":1075,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1031","page","type-page","status-publish","hentry"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.giassa.net\/index.php?rest_route=\/wp\/v2\/pages\/1031","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.giassa.net\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.giassa.net\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.giassa.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.giassa.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1031"}],"version-history":[{"count":40,"href":"https:\/\/www.giassa.net\/index.php?rest_route=\/wp\/v2\/pages\/1031\/revisions"}],"predecessor-version":[{"id":1344,"href":"https:\/\/www.giassa.net\/index.php?rest_route=\/wp\/v2\/pages\/1031\/revisions\/1344"}],"up":[{"embeddable":true,"href":"https:\/\/www.giassa.net\/index.php?rest_route=\/wp\/v2\/pages\/1075"}],"wp:attachment":[{"href":"https:\/\/www.giassa.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1031"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}