More efficient way to create an ASCII maze using box characters

Question

I've written a C# program to generate a random maze, and then draw that maze in the Console mode using box-drawing characters, e.g. ─ │ ┌ ┐ ┬ ┼ etc. It works fine, as below, but I'm not convinced that the code used is remotely efficient, or that it couldn't be done better.

I have a Maze class with the following members:

int Width { get; }
int Height { get; }
int DisplayWidth { get; }
int DisplayHeight { get; }

Cell[,] Cells;
char[,] DisplayCells;
bool[,] Visited;

Random Rnd;

And these methods:

• Public Maze [constructor]
• Private Invert (params: Direction d; returns: Direction)
• Private GetNeighbours (params: Coord current; returns: List)
• Private GetDirection (params: Coord current, Coord neighbour, Direction dir; void)
• Private Create (void)
• Private SetDisplayGrid (void)
• Public DrawDisplayGrid (params: Coord startPosition)

Here's the code for Cell and Coord for context:

public struct Coord
{
    public int x;
    public int y;

    public Coord(int y, int x)
    {
        this.x = x;
        this.y = y;
    }
}

public class Cell
{
    public Cell()
    {
        north = true;
        east = true;
        south = true;
        west = true;
        icon = ' ';
    }
    public bool north;
    public bool east;
    public bool south;
    public bool west;
    public char icon;
}

I've omitted some fields and code because they're not relevant to the question.

When the user calls the Maze constructor, as in:

Maze m = new Maze(25, 12);

it initialises all fields, including the Cells 2D array, which is an array of Cell objects. A Cell has four "walls": north, east, south and west, and they're all initially set to true. The Maze constructor then calls the Create method, which traverses through each cell of the maze and "knocks down" walls until each cell has been visited, using the depth-first search algorithm outlined here: https://scipython.com/blog/making-a-maze/.

Once this is done, the SetDisplayGrid method is then called by the Maze constructor. This takes a 2D char array, DisplayGrid - which has the size 2n + 1 for each dimension of the Cells array n (meaning that if the Cells array is 5 x 10, DisplayGrid will be 11 x 21) - and populates it with box characters, according to the "wall" boolean values in each cell. This is where I think my code may be inefficient, because I have so many conditionals.

Broadly, the approach is:

1. For each cell, first set the north and west walls, then the upper-left corner
2. If the cell is the last one on its row, set the upper-right corner and the east wall
3. If the cell is the last one on its column, set the lower-left corner and the south wall
4. If the cell is the last cell in the table, set the lower-right corner

Here's the code for this method:

private void SetDisplayGrid()
{
    DisplayCells = new char[DisplayHeight, DisplayWidth];
    Coord current = new Coord();

    for (int h = 0; (h * 2) + 1 < DisplayHeight; h++)
    {
        for (int w = 0; (w * 2) + 1 < DisplayWidth; w++)
        {
            current.x = (w * 2) + 1;
            current.y = (h * 2) + 1;

            bool curNorth = Cells[h, w].north;
            bool curWest = Cells[h, w].west;
            bool curEast = Cells[h, w].east;
            bool curSouth = Cells[h, w].south;

            // The cell itself
            DisplayCells[current.y, current.x] = Cells[h, w].icon;

            // Orthogonal walls (NORTH AND WEST)
            if (curNorth) { DisplayCells[current.y - 1, current.x] = '─'; }    // NORTH WALL
            if (curWest) { DisplayCells[current.y, current.x - 1] = '│'; }     // WEST WALL

            // UPPER-LEFT CORNER
            if (current.y - 1 == 0 && current.x - 1 == 0) // Cell is at the top-left corner --> ┌
            {
                DisplayCells[current.y - 1, current.x - 1] = '┌';
            }
            else if (current.y - 1 == 0 && current.x - 1 > 0) // Cell is on the first row but not the first column
            {
                if (curWest) { DisplayCells[current.y - 1, current.x - 1] = '┬'; }
                else { DisplayCells[current.y - 1, current.x - 1] = '─'; }
            }
            else if (current.y - 1 > 0 && current.x - 1 == 0) // Cell is on the first column but not the first row
            {
                if (curNorth) { DisplayCells[current.y - 1, current.x - 1] = '├'; }
                else { DisplayCells[current.y - 1, current.x - 1] = '│'; }
            }
            else // Cell is in the middle (not the first column or row)
            {
                bool nextEast = Cells[h - 1, w - 1].east;
                bool nextSouth = Cells[h - 1, w - 1].south;

                char corner = '*';

                if (curNorth && curWest && nextEast && nextSouth) { corner = '┼'; }
                else if (curNorth && curWest && nextEast && nextSouth) { corner = '┼'; }
                else if (curNorth && curWest && !nextEast && nextSouth) { corner = '┬'; }
                else if (!curNorth && curWest && nextEast && nextSouth) { corner = '┤'; }
                else if (curNorth && !curWest && nextEast && nextSouth) { corner = '┴'; }
                else if (curNorth && curWest && nextEast && !nextSouth) { corner = '├'; }
                else if (!curNorth && curWest && !nextEast && nextSouth) { corner = '┐'; }
                else if (!curNorth && !curWest && nextEast && nextSouth) { corner = '┘'; }
                else if (curNorth && !curWest && nextEast && !nextSouth) { corner = '└'; }
                else if (curNorth && curWest && !nextEast && !nextSouth) { corner = '┌'; }
                else if (curNorth && !curWest && !nextEast && nextSouth) { corner = '─'; }
                else if (!curNorth && curWest && nextEast && !nextSouth) { corner = '│'; }
                else if (!curNorth && !curWest && nextEast && !nextSouth) { corner = '│'; }
                else if (curNorth && !curWest && !nextEast && !nextSouth) { corner = '─'; }
                else if (!curNorth && curWest && !nextEast && !nextSouth) { corner = '│'; }
                else if (!curNorth && !curWest && !nextEast && nextSouth) { corner = '─'; }
                else { corner = '*'; }

                DisplayCells[current.y - 1, current.x - 1] = corner;
            } 

            // EAST WALLS AND UPPER RIGHT CORNERS
            if (current.x + 1 == DisplayWidth - 1)
            {
                if (curEast) { DisplayCells[current.y, current.x + 1] = '│'; }  // EAST WALL

                // UPPER-RIGHT CORNER
                if (current.y - 1 == 0 && current.x + 1 == DisplayWidth - 1) { DisplayCells[current.y - 1, current.x + 1] = '┐'; }
                else
                {
                    if (curNorth) { DisplayCells[current.y - 1, current.x + 1] = '┤'; }
                    else { DisplayCells[current.y - 1, current.x + 1] = '│'; }
                }
            }

            // SOUTH WALLS AND LOWER-LEFT CORNERS
            if (current.y + 1 == DisplayHeight - 1)
            {
                if (curSouth) { DisplayCells[current.y + 1, current.x] = '─'; } // SOUTH WALL

                // LOWER-LEFT CORNER
                if (current.x - 1 == 0) { DisplayCells[current.y + 1, current.x - 1] = '└'; }
                else
                {
                    if (curWest) { DisplayCells[current.y + 1, current.x - 1] = '┴'; }
                    else { DisplayCells[current.y + 1, current.x - 1] = '─'; }
                }
            }
            // LOWER-RIGHT CORNER
            if (current.x + 1 == DisplayWidth - 1 && current.y + 1 == DisplayHeight - 1)
            {
                DisplayCells[current.y + 1, current.x + 1] = Block;
            }
        }
    }
}

As you can see, there are a lot of conditionals when I'm checking the upper-left corner in the middle of the table, because there are basically sixteen different possibilities for what character could occupy that space.

I'm not sure how I could simplify this code but would appreciate any suggestions - especially if there's any redundant calculations I've missed, or a way to make these checks without making so many conditional checks. If anything else jumps out, feel free to say so.

Answer 1

There are different possible approaches to assign the wall characters. One uses the new C# 8.0 switch expressions together with the tuple pattern.

char corner = (curNorth, curWest, nextEast, nextSouth) switch {
    (true, true, true, true)  => '┼',
    (true, true, false, true) => '┬',
    (false, true, true, true) => '┤',
    (true, false, true, true) => '┴',
    // ... other cases ...
    _ => '*'
};

Another possibility is to think of the wall parts as four digits in a binary number. e.g., north = 1, west = 2, east = 4, south = 8. Combined you get a number in the range 0 ... 15 (inclusive). You can use these numbers as index in a character array:

char[] walls = {
//   0    1    2    3    4    5    6    7    8    9   10   11   12   13   14   15
    '*', '─', '│', '┌', '│', '└', '│', '├', '─', '─', '┐', '┬', '┘', '┴', '┤', '┼' 
};

int index = (curNorth ? 1 : 0) + 
            (curWest ? 2 : 0) + 
            (nextEast ? 4 : 0) + 
            (nextSouth ? 8 : 0);
char corner = walls[index];

You could also get rid of many if-statements if you treated the surrounding walls separately. The nested loop would only be responsible for the core (middle) of the maze. Then a separate loop would create the top and the bottom walls. Another separate loop would create the left and right walls. The four corners need not to be in a loop at all.

I am not sure if I got the characters right. It seems that you have north pointing to the right and west downwards. Usually north points upwards and east to the right on geography maps.

---

Alternatively, instead of having four boolean fields, you could also use a flags enum.

[Flags]
public enum Direction
{
    None = 0,
    North = 1,
    West = 2,
    East = 4,
    South = 8
}

Now, you can combine directions like this:

Direction walls = Direction.North | Direction.East | Direction.South;
int index = (int)walls;

See also:

• Enumeration types (C# reference)
• What does the [Flags] Enum Attribute mean in C#?