Drawing and representing maze with walls in array

Question

I'm trying to create a maze with depth first search and the algorithm works fine but I'm having issues actually drawing the maze in console and in general representing the maze.. My previous attempts included representing each position of the grid in a 3x3 block where for each position I drew a wall if there was one but this gave 2 walls for every direction left/right, up/down. My second attempt was to try and put the maze in a 2d array with dimension + (dimension - 1) and consider the walls as lines like here:

and this was my attempt for that:

    int dimTemp             =   dim + (dim - 1);
    String[][] mazeDrawn    =   new String[dimTemp][dimTemp];

    int posRow, posCol;
    int nodeRow = 0;
    int nodeCol;

    for(int wallRow = 1; wallRow <= dimTemp; wallRow += 2)
    {
        if(wallRow >= dimTemp)
        {
            wallRow--;
            posRow =   wallRow;
        }   

        else posRow =   wallRow - 1;
        nodeCol =   0;

        for(int wallCol = 1; wallCol <= dimTemp; wallCol += 2)
        {
            if(wallCol >= dimTemp) 
            {
                wallCol--;
                posCol          =   wallCol;
            }

            else posCol = wallCol - 1;

            Node current    =   maze[nodeRow][nodeCol];
            mazeDrawn[posRow][posCol] =   current.getPosValue();

            if(current.right) mazeDrawn[posRow][wallCol] = "#";
            else mazeDrawn[posRow][wallCol] = " ";

            mazeDrawn[wallRow][wallCol] = "#";
            if(current.down) mazeDrawn[wallRow][posCol] = "#";
            else mazeDrawn[wallRow][posCol] = " ";

            nodeCol++;
        }

        nodeRow++;
    }


    for(int row = 0; row < mazeDrawn.length; row++)
    {
        for(int col = 0; col < mazeDrawn.length; col++)
        {
            System.out.print(mazeDrawn[row][col]);
        }
        System.out.println();
    }

And here is the output for a 10x10 maze before I have run DFS where there is a wall between every position, # are "walls" and . are positions

.#.#.#.#.#.#.#.#.##
###################
.#.#.#.#.#.#*#.#.##
###################
.#.#.#.#.#.#.#.#.##
###################
.#.#.#.#.#.#.#.#.##
###################
.#.#.#.#.#.#.#.#.##
###################
.#.#.#.#.#.#.#.#.##
###################
.#.#.#.#.#.#.#.#.##
###################
.#.#.#.#.#.#.#.#.##
###################
.#.#.#.#.#.#.#.#.##
###################
###################

There are issues with the bottom and right edge and should follow the pattern before them. I am not sure if this is a good way to represent the maze. Also to clarify I am just trying to print to console .

Answer 1

You can represent a maze easily enough with one byte (actually, four bits) per cell. Assign each of the cell walls a single bit. For example:

   0
   _
3 |_| 1

   2

So a cell with all four walls present would be represented as binary 1111, or 15. If just the top and right walls are present, the value is 0011, or 3. A cell with no walls has the value 0.

You can do better than that, too. If you infer the existence of the top and left walls for all cells on the top and left edges of the maze, then you only need two bits per cell. If you're drawing the maze from top-left to bottom-right, then for each cell all you have to figure out is if the bottom or right walls exist. There's no reason to check for the left or top, because they would have been drawn by the previous column or row.

Of course, if you're at row 5, column 3 (i.e. cell [5, 3]), and you want to know if there is a wall above, you have to check cell [4, 3] to see if the wall on the bottom of the cell exists. It's a little more computation, but it comes with a 50% space savings.

Answer 2

it's ok to use a 3x3 matrix to represent your maze, you simply need to draw it as a 2x2 matrix

look at this image, you have

• yellow 3x3 grid
• red 3x3 grid
• blue 3x3 grid

when you draw each 3x3 grid you overlap each grid a bit...

this will only work if your maze is created properly:

• if a cell@x/y has a wall (/door) on the west, then cell@x-1/y has a wall (/door) on the east -> you don't have to draw the east part of cell@x-1/y

• if a cell@x/y has a wall (/door) on the north, then cellx/y-1 has a wall(/door) on the south -> you don't have to draw the south part of cellx/y-1

let's speak code:

for (int dy = 0; dy < maze.width; dy ++){

    String upperLine = ""; //first line of row
    String lowerLine = ""; //second line of row

    for (int dx = 0; dx < maze.width; dx ++){ 
         //first symbol always is #
         upperLine = upperline + "#"; //always there

         //second symbol depends on wall?#:.
         if(cell[dx][dy].hasWall[Direction.N]){
             upperline = upperline+"#";
         }else{
             upperline = upperline+".";
         }

         //thats all for the upper line right now

         //now comes lower line
          if(cell[dx][dy].hasWall[Direction.W]){
             lowerLine = lowerLine +"#";
         }else{
             lowerLine = lowerLine +".";
         }

         //center is always '.'
         lowerLine = lowerLine + ".";
    }

    System.out.println(upperLine);
    System.out.println(lowerLine);
}