General coding style and efficiency of a maze maker

Question

I have just finished making a maze maker. I took inspiration from this video, but its my own implementation. I just wanted to know what you guys thought of it and if there are any improvements that can be made like

1. Improving the way the algorithm is implemented
2. If the code should be less verbose or more lines of code for clarity.
3. This is not really an issue at all but if the algorithm could have been implemented in a more efficient (faster) way.

If you wish to run the code, its here.

Code:

#define OLC_PGE_APPLICATION
#include "pixelGameEngine.h"
#include <stack>
typedef std::pair<olc::vi2d, bool> mazevi2d;
class MazeMaker
{
public:
 MazeMaker(olc::vi2d mapSize) :
 map{ new int[(size_t)mapSize.x * mapSize.y] }, mapSize{ mapSize }
 {
 memset(map, 0, (size_t)mapSize.x * mapSize.y * sizeof(int));
 map[0] |= CELL_VISITED;
 cells.push({ 0, 0 });
 maze.push_back({ { 0, 0 }, false });
 }
 ~MazeMaker()
 {
 delete[] map; 
 }
public:
 std::vector<mazevi2d> Make()
 {
 bool popped = false;
 while (maze.size() < (size_t)mapSize.x * mapSize.y)
 {
 olc::vi2d lastCell = cells.top();
 olc::vi2d direction = GetRandomDirection(lastCell);
 if (direction != olc::vi2d{ -1, -1 })
 {
 olc::vi2d newCell = lastCell + direction;
 map[newCell.y * mapSize.x + newCell.x] = CELL_VISITED;
 cells.push(newCell);
 maze.push_back({ newCell, popped });
 popped = false;
 }
 else
 {
 popped = true;
 cells.pop();
 }
 }
 return maze;
 }
private:
 olc::vi2d GetRandomDirection(const olc::vi2d& currentCell)
 {
 int nChoices = 0;
 olc::vi2d choices[4];
 if (currentCell.y > 0)
 {
 int topVisited = (map[(currentCell.y - 1) * mapSize.x + currentCell.x] & CELL_VISITED) != CELL_VISITED;
 if (topVisited)
 choices[nChoices++] = { 0, -1 };
 }
 if (currentCell.y < mapSize.y - 1)
 {
 int bottomVisited = (map[(currentCell.y + 1) * mapSize.x + currentCell.x] & CELL_VISITED) != CELL_VISITED;
 if (bottomVisited)
 choices[nChoices++] = { 0, 1 };
 }
 if (currentCell.x < mapSize.x - 1) 
 {
 int rightVisited = (map[currentCell.y * mapSize.x + (currentCell.x + 1)] & CELL_VISITED) != CELL_VISITED;
 if (rightVisited)
 choices[nChoices++] = { 1, 0 };
 }
 if (currentCell.x > 0)
 {
 int leftVisited = (map[currentCell.y * mapSize.x + (currentCell.x - 1)] & CELL_VISITED) != CELL_VISITED;
 if (leftVisited)
 choices[nChoices++] = { -1, 0 };
 }
 if (nChoices)
 {
 return choices[rand() % nChoices];
 }
 return { -1, -1 };
 }
private:
 std::stack<olc::vi2d> cells;
 const olc::vi2d mapSize;
 int* map;
 std::vector<mazevi2d> maze;
 enum CELL
 {
 CELL_VISITED = 1 << 1, 
 };
};
class Application : public olc::PixelGameEngine
{
public:
 Application()
 {
 sAppName = "Maze Maker";
 }
private:
 static constexpr int mapSize = 50;
 MazeMaker mazeMaker{ { mapSize, mapSize } };
 olc::vi2d offset{ 1, 1 };
 std::vector<mazevi2d> maze;
 float scale;
public:
 bool OnUserCreate() override
 {
 srand((unsigned int)time(NULL));
 scale = ScreenWidth() / mapSize;
 maze = mazeMaker.Make();
 return true;
 }
 bool OnUserUpdate(float fElapsedTime) override
 {
 Clear(olc::BLACK);
 for (int i = 1; i < maze.size(); i++)
 {
 if (!maze[i].second)
 DrawLine((maze[i].first * scale) + offset, (maze[(size_t)i - 1].first * scale) + offset);
 }
 return true;
 }
};
int main()
{
 Application mazemaker;
 if (mazemaker.Construct(300, 300, 2, 2))
 mazemaker.Start();
 return 0;
}

• worldsmithhelper: The map could be represented more memory efficiently using a smaller datatype such as short or even just a few flags packed into a part of a short/int. In the packed case you would need some shifting logic that would be best to hide in a separate class, although there might not be a performance improvement.

Answer 1

Consider making mazevi2d a struct, and rename it

std::pair is sometimes useful, but the problem is that you access the two elements using .first and .second, and those names are not really describing what you want to do. So I would just create a struct for it, and give proper names to the two elements. Also, the name mazevi2d is not great either, choose a name that better describes what it represents: a segment of the wall. So:

struct WallSegment {
 olc::vi2d point;
 bool is_start;
};

Use a std::vector<bool> for map

It is strange that you are using std::vector and other STL containers in your code, but you manually allocate memory for map. Just use a std::vector for it as well, and you don't have to worry about memory allocation and deallocation. There there is another opportunity to rename it: map is actually tracking whether you have visited a spot on the map, so perhaps naming it visited is better as well. Finally, it only every is set or unset, so a bool is a more appropriate type for it, and then you can also benefit from the specialization of std::vector<bool> and save memory.

class MazeMaker {
public:
 MazeMaker(olc::vi2d mapSize) :
 mapSize{ mapSize },
 visited( mapSize.x * mapSize. y)
 {
 visited[0] = true;
 ...
 }
 ...
 const olc::vi2d mapSize;
 std::vector<bool> visited;
 ...
};

It also simplifies the code in GetRandomDirection(). It also brings to light that variables like topVisited actually mean topNotYetVisited. I would remove the temporary variables, and just write code like so:

if (!visited[(currentCell.y - 1) * mapSize.x + currentCell.x])
 choices[nChoices++] = { 0, -1 };

Consider turning MazeMaker into a function

The only purpose of class MazeMaker is to generate a vector with the walls of the maze, nothing else. All the other member variables are just temporary storage used while running Make(), they are useless afterwards. It also can only generate one maze, afterwards Make() doesn't do anything anymore. So it is better to turn the whole class into a single function that returns the data you actually want:

std::vector<WallSegment> MakeMaze(olc::vi2d mapSize) {
 const size_t nCells = mapSize.x * mapSize.y;
 std::vector<bool> visited(nCells);
 std::stack<olc::vi2d> cells;
 std::vector<WallSegment> walls;
 visited[0] = true;
 cells.push({0, 0});
 walls.push_back({{0, 0}, false});
 bool popped = false;
 while (maze.size() < nCells) {
 ...
 }
 return walls;
}

You have to do something with GetRandomDirection(); the simple thing to do is to pass it map and mapSize as const reference parameters.

Then in class Application, you don't need to have a member variable mazeMaker anymore, just initialize maze like so:

class Application: public olc::PixelGameEngine {
 ...
private:
 static constexpr size_t mapSize = 50;
 std::vector<WallSegment> walls = MakeMaze({mapSize, mapSize});
 ...
};

Better random number generation

rand() and srand() are the old C way of generating random numbers, and they are quite bad. Since C++11 there are much better ways of generating random numbers in C++. In particular, consider using a properly seeded std::mt19937 as the pseudo-random number generator, and use std::uniform_int_distribution to choose a number between 0 and nChoices inside GetRandomDirection().

Optimizing memory usage

As @worldsmithelper already mentioned, there are better ways to represent the map. In particular, you only need 2 bits per cell, one to indicate whether the cell as a wall on its left, one to indicate it has one at the bottom. You don't need to know whether a cell has a wall on the right, because the cell to the right will already know if it has a wall on the left, which would be the same wall.

This way, for a 50 by 50 maze, you only need 50 * 50 * 2 / 8 = 625 bytes, whereas your solution uses 50 * 50 * 12 = 30000 bytes.

For larger mazes, this might be a performance win, but for a 50 by 50 maze it probably won't make a difference.

Reduce how often you redraw the maze

Your program uses a lot of CPU, and that's because unfortunately by default, olcPixelGameEngine doesn't use vsync, and effectively calls OnUserUpdate() in a loop as fast as possible. The first thing to do is to call Construct() with a few extra parameters to enable vsync:

if (mazemaker.Construct(300, 300, 2, 2, false, true))
 mazemake.Start();

Secondly, olcPixelGameEngine retains the contents of the screen if you don't do anything in OnUserUpdate(). So you could make it draw the maze the first time OnUserUpdate() is called, and then set a flag. Next time OnUserUpdate() is called, if the flag is set, return true immediately.

Optimizing maze generation

The algorithm you are using to generate the maze is quite efficient, on average it evaluates the body of the while-loop twice the number of cells in the maze. It is one of the faster algorithms. However, the main reason to use a different algorithm would not be the speed, but what kind of maze it generates. The algorithm you chose results in long, twisty paths with few long straight runs. If that's what you wanted, perfect! Otherwise, look at this StackOverflow question for ideas:

What's a good algorithm to generate a maze?

Answer 2

• You should prefer using to typedef
• some of your names like olc::vi2d look more like cypher than an actual name. It might be fine if this is a well-known project-wide terminology, but for a single class it is confusing.
• There is no reason to use new[] to allocate the array. std::vector is a better alternative
• You should not use memset unless you have specific performance considerations. std::fill is a more safe alternative, however if you use vector, you won't need it at all
• You already know what your map contains after initialization, then why |= ?
• you repeat (size_t)mapSize.x * mapSize.y several times, it is better to have a function for that
• Your Maker can actually make only one maze, which is not something I'd expect from this class. You could just call it a Maze in this case or change it to create different mazes
• direction != olc::vi2d{ -1, -1 } this is a non-trivial action which is better extacted in a function just to give it a name
• it is better to have values that are not changed const and the functions that do not change the class stated marked as const
• MakeMaze should return a maze rather than a vector

• JDługosz: Please use code markup. In particular, words like using in a sentence, when not marked, make it difficult to read, and expressions of code look strange in general when typeset as text.