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.

enter image description here

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.

• RobH: You might be interested in looking at this: Visualising Algorithms, maze generation
• Lou: @RobH It doesn't address the problem I'm trying to solve in particular, but you're not wrong, that is a very interesting discussion with some beautiful gifs!
• RobH: yeah, I should have said it was only a "you may find this interesting" rather than a "you may find it helpful" :)
• pacmaninbw: It might be better if you posted entire classes including the using MODULE statements.

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#?

• Lou: Thanks Olivier, these are great suggestions. I like the idea of using binary encodings or tuple-switch statements for the central core section of the maze. I might try and do as you suggest and break out the loops as well.
• Lou: And yes, the way I've treated the characters does seem a bit confusing, I'll admit! So imagine you've got a current cell, and a neighbour which is the cell upper-left of current. To figure out what box character to put in the upper-left corner of your current cell, you need to check the north and west walls of the current cell, and the east and south walls of the cell to the upper-left. I hope that makes sense.
• aepot: @Lou if the answer was helpful, you may mark it accepted. The same for your previous question, you can find it on your profile page. Choose the most useful answer, then accept it.