5
\$\begingroup\$

I have created a DFS backtracking maze generator (non-recursive) using C++ and SFML. It works great but the final results of creating a 9000 x 9000 with cell size 2 is around 1 min and 46 seconds <-> 1 min and 30 seconds, to directly store the generated maze as an image without any kind of GUI.

I'll try to explain my code. The second last function drawMaze() is the main logic. I have used to stacks one for x and other for y coordinate to store the backtrack.

//maze.cpp
#define SFML_STATIC
#include "Maze.h"
#include "SFML/Graphics.hpp"
#include<iostream>
#include<stack>
#include <chrono>
#include <thread>
#include<time.h>

using namespace std;
using namespace std::this_thread; // sleep_for, sleep_until
using namespace std::chrono; // 

void Maze::setWidth(int width)
{
    this->width=width;
}

void Maze::setHeight(int height)
{
    this->height=height;
}

void Maze::setCellSize(int size)
{
    cellSize=size;
    rows=height/cellSize;
    cols=width/cellSize;
}

void Maze::setNotVisitedCellColor(sf::Color color)
{
    notVisitedColor=color;
}

void Maze::setCurrentCellColor(sf::Color color)
{
    currentColor=color;
}

void Maze::setVisitedCellColor(sf::Color start, sf::Color end)
{
    this->start=start;
    this->end=end;
}

void Maze::setBorderColor(sf::Color color)
{
    borderColor=color;
}

void Maze::setBackgroundColor(sf::Color color)
{
    backgroundColor=color;
}

void Maze::handleBorder(sf::VertexArray &Border,int borderCounter,sf::Color borderColor,int x,int y)
{
    if(checkBit(maze[(cols*x)+y],topMask))
    {
        Border[borderCounter].color = this->borderColor;
        Border[borderCounter+1].color = this->borderColor;
    }
    else
    {
        Border[borderCounter].color =borderColor;
        Border[borderCounter+1].color =borderColor;
    }    
    if(checkBit(maze[(cols*x)+y],rightMask))
    {
        Border[borderCounter+2].color = this->borderColor;
        Border[borderCounter+3].color = this->borderColor;
    }
    else
    {
        Border[borderCounter+2].color =borderColor;
        Border[borderCounter+3].color = borderColor;
    }
    if(checkBit(maze[(cols*x)+y],bottomMask))
    {
        Border[borderCounter+4].color = this->borderColor;
        Border[borderCounter+5].color = this->borderColor;
    }
    else
    {
        Border[borderCounter+4].color =borderColor;
        Border[borderCounter+5].color = borderColor;
    }
    if(checkBit(maze[(cols*x)+y],leftMask))
    {
        Border[borderCounter+6].color = this->borderColor;
        Border[borderCounter+7].color = this->borderColor;
    }
    else
    {
        Border[borderCounter+6].color = borderColor;
        Border[borderCounter+7].color =borderColor;
    }
}

int Maze::invalidNeighbour(int x,int y,char dir)
{
  
    if(dir=='t' || dir=='b')
    {
        if(x<0 || x>((rows*cols)-1))
        {
            return 0;
        }
        else
        {
            return 1;
        }
    }
    else
    {
        if(x<0 || x>((rows*cols)-1) || abs((y/cols)-(x/cols))!=0)
        {
            return 0;
        }
        else
        {
            return 1;
        }
    }
}

void Maze::checkNeighbours(int x,int y)
{
    vector<char> direction;

    int top=invalidNeighbour(cols*(x-1)+y,cols*x+y,'t');
    int right=invalidNeighbour(cols*x+(y+1),cols*x+y,'r');
    int bottom=invalidNeighbour(cols*(x+1)+y,cols*x+y,'b');
    int left=invalidNeighbour(cols*x+(y-1),cols*x+y,'l');

    if(top)
    {
        int visited=checkBit(maze[((cols*(x-1))+y)],visitedMask);
        if(!visited)
        {
            direction.push_back('t');
        }
    }
    if(right)
    {
        int visited=checkBit(maze[(cols*x)+(y+1)],visitedMask);
        if(!visited)
        {
            direction.push_back('r');
        }
    }
    if(bottom)
    {
        int visited=checkBit(maze[(cols*(x+1)+y)],visitedMask);
        if(!visited)
        {
            direction.push_back('b');
        }
    }
    if(left)
    {
        int visited=checkBit(maze[(cols*x+(y-1))],visitedMask);
        if(!visited)
        {
            direction.push_back('l');
        }
    }

    if(direction.size()>0)
    {
        int randomNumber=rand()%direction.size();
        btx.push(x);
        bty.push(y);

        if(direction[randomNumber]=='t')
        {
            turnOnBit(maze[((cols*(x-1))+y)],visitedMask);
            btx.push(x-1);
            bty.push(y);
            turnOffBit(maze[cols*x+y],topMask);
            turnOffBit(maze[((cols*(x-1))+y)],bottomMask);
        }
        else if(direction[randomNumber]=='r')
        {
            turnOnBit(maze[(cols*x)+(y+1)],visitedMask);
            turnOffBit(maze[cols*x+y],rightMask);
            turnOffBit(maze[(cols*x)+(y+1)],leftMask);
            btx.push(x);
            bty.push(y+1);
        }
        else if(direction[randomNumber]=='b')
        {
            turnOnBit(maze[(cols*(x+1)+y)],visitedMask);
            turnOffBit(maze[cols*x+y],bottomMask);
            turnOffBit(maze[(cols*(x+1)+y)],topMask);
            btx.push(x+1);
            bty.push(y);
        }
        else if(direction[randomNumber]=='l')
        {
            turnOnBit(maze[(cols*x+(y-1))],visitedMask);
            turnOffBit(maze[cols*x+y],leftMask);
            btx.push(x);
            bty.push(y-1);
            turnOffBit(maze[(cols*(x)+(y-1))],rightMask);
        }
    }
}

void Maze::saveImage()
{
    float initial=0.9;

    sf::Image image;
    image.create((cols*cellSize)+(2*10),(rows*cellSize)+(2*10), backgroundColor);

    for(int x=0;x<rows;x++)
    {
        for(int y=0;y<cols;y++)
        {
            sf::Color testing;
            testing.r=(start.r*initial)+(end.r*(1-initial));
            testing.g=(start.g*initial)+(end.g*(1-initial));
            testing.b=(start.b*initial)+(end.b*(1-initial));

            for(int i=(y*cellSize)+10;i<=(y*cellSize)+10+cellSize;i++)
            {
                for(int j=(x*cellSize)+10;j<=(x*cellSize)+10+cellSize;j++)
                {
                    image.setPixel(i,j, testing);
                }
            }
            if(checkBit(maze[cols*x+y],topMask))
            {
                for(int i=(y*cellSize)+10;i<=(y*cellSize)+10+cellSize;i++)
                {
                    image.setPixel(i, (x*cellSize)+10, borderColor);
                }
            }
            if(checkBit(maze[cols*x+y],rightMask))
            {
                for(int i=(x*cellSize)+10;i<=(x*cellSize)+10+cellSize;i++)
                {
                    image.setPixel((y*cellSize)+10+cellSize,i, borderColor);
                }
            }
            if(checkBit(maze[cols*x+y],bottomMask))
            {
                for(int i=(y*cellSize)+10;i<=(y*cellSize)+10+cellSize;i++)
                {
                    image.setPixel(i,(x*cellSize)+10+cellSize, borderColor);
                }
            }
            if(checkBit(maze[cols*x+y],leftMask))
            {
                for(int i=(x*cellSize)+10;i<=(x*cellSize)+10+cellSize;i++)
                {
                    image.setPixel((y*cellSize)+10,i, borderColor);
                }
            }
        }
        initial=initial-(initial/rows);
    }
    if (!image.saveToFile("finally.png"))
        cout<<"unsuccessfull image saving";
    else
        cout<<"successful image save";

    maze.clear();
    // vector<unsigned char> emptyMaze(0);
    // vector<unsigned char> emptyMaze().swap(maze);
}

void Maze::drawMaze(string mazeName,int animate,int fps=200)
{
    float initial=0.9;

    sf::Color borderColor;
    
    int padding=10;
    
    turnOnBit(maze[0],visitedMask);

    btx.push(0);
    bty.push(0);

    sf::VertexArray Quad(sf::Quads,4*rows*cols);
    sf::VertexArray Border(sf::Lines,rows*cols*8);
  
    if(animate!=-1)
    {
        window.create(sf::VideoMode(width+padding+padding,height+padding+padding),mazeName);

        if(animate)
        {
            window.setFramerateLimit(fps);
        }
    }
    while(window.isOpen() || animate==-1)
    {
        if(animate!=-1)
        {
            sf::Event event;
            while(window.pollEvent(event))
            {
                if(event.type==sf::Event::Closed)
                {
                    window.close();
                }
            }
            window.clear(backgroundColor);
        }
        int counter=0;
        int borderCounter=0;
        if(animate)
        {
            if(!btx.empty() && !bty.empty())
            {
                int x=btx.top();
                int y=bty.top();
                btx.pop();
                bty.pop();

                checkNeighbours(x,y);
            }    
        }
        float p=initial;
        for(int i=0;i<rows;i++)
        {
            for(int j=0;j<cols;j++)
            {        
               if(animate==0 || animate==-1)
               { 
                   if(!btx.empty() && !bty.empty())
                    {                     
                        int x=btx.top();
                        int y=bty.top();
                        btx.pop();
                        bty.pop();

                        checkNeighbours(x,y);
                    }
                }     

                Quad[counter].position = sf::Vector2f((j*cellSize)+padding, (i*cellSize)+cellSize+padding);
                Quad[counter+1].position = sf::Vector2f(j*cellSize+padding, i*cellSize+padding);
                Quad[counter+2].position = sf::Vector2f((j*cellSize)+cellSize+padding, i*cellSize+padding);
                Quad[counter+3].position = sf::Vector2f((j*cellSize)+cellSize+padding,(i*cellSize)+cellSize+padding);

                Border[borderCounter].position = sf::Vector2f((j*cellSize)+padding,(i*cellSize)+padding);
                Border[borderCounter+1].position = sf::Vector2f((j*cellSize)+cellSize+padding,i*cellSize+padding);
                Border[borderCounter+2].position = sf::Vector2f((j*cellSize)+cellSize+padding,i*cellSize+padding);
                Border[borderCounter+3].position = sf::Vector2f((j*cellSize)+cellSize+padding,(i*cellSize)+cellSize+padding);
                Border[borderCounter+4].position = sf::Vector2f((j*cellSize)+cellSize+padding,(i*cellSize)+cellSize+padding);
                Border[borderCounter+5].position = sf::Vector2f((j*cellSize)+padding,(i*cellSize)+cellSize+padding);
                Border[borderCounter+6].position = sf::Vector2f((j*cellSize)+padding,(i*cellSize)+cellSize+padding);
                Border[borderCounter+7].position = sf::Vector2f((j*cellSize)+padding,(i*cellSize)+padding);

            if(animate!=-1)
            {
                int visited=checkBit(maze[(cols*i)+j],visitedMask);
                if(!visited)
                {   
                    Quad[counter].color = notVisitedColor;
                    Quad[counter+1].color = notVisitedColor;
                    Quad[counter+2].color = notVisitedColor;
                    Quad[counter+3].color =notVisitedColor;
                }
                else
                {
                    sf::Color testing;
                    testing.r=(start.r*p)+(end.r*(1-p));
                    testing.g=(start.g*p)+(end.g*(1-p));
                    testing.b=(start.b*p)+(end.b*(1-p));

                    Quad[counter].color = testing;
                    Quad[counter+1].color = testing;
                    Quad[counter+2].color = testing;
                    Quad[counter+3].color =testing;

                    borderColor=testing;
                }
            }
         
            handleBorder(Border,borderCounter,borderColor,i,j);

            if(animate==1 && !btx.empty() && !bty.empty())
            {
                int topx=btx.top();
                int topy=bty.top();
                if(topx==i && topy==j)   
                {
                    Quad[counter].color = currentColor;
                    Quad[counter+1].color =currentColor;
                    Quad[counter+2].color = currentColor;
                    Quad[counter+3].color =currentColor;
                }                
            }            
            counter=counter+4;
            borderCounter=borderCounter+8;  
            }
            p=p-((initial/rows));
        }
        if(animate==0 || animate==1)
        {
            window.draw(Quad);
            window.draw(Border);
       
            window.display();  
        } 
        else if(animate==-1)
        {
            if(btx.empty() || bty.empty())
            {
                break;
            }
        }
    }
}

void Maze::createMaze(string mazeName,int animate,int fps)
{
    srand(time(NULL));

    unsigned char initial=0b0000'1111;

    maze.resize(rows*cols);
    for(int i=0;i<rows*cols;i++)
    {
        maze[i]=initial;
    }

    drawMaze(mazeName,animate,fps);
}



//maze.h
#ifndef _MAZE_H_
#define _MAZE_H_

#define SFML_STATIC
#include "SFML/Graphics.hpp"
#include "Cell.h"
#include<stack>
#include<vector>

using namespace std;

class Maze
{
    private:
        vector<unsigned char> maze;
        
        int width;
        int height;
        int cellSize;
        int rows;
        int cols;
        
        sf::Color start;
        sf::Color end;
        sf::Color notVisitedColor;
        sf::Color currentColor;
         stack<int> btx;
    stack<int> bty;
        sf::RenderWindow window;
        sf::Color borderColor;
        sf::Color backgroundColor;

    public:
        void setWidth(int width);
        void setHeight(int height);
        void setCellSize(int size);
        void setVisitedCellColor(sf::Color start,sf::Color end);
        void setNotVisitedCellColor(sf::Color color);
        void setCurrentCellColor(sf::Color color);
        void setBorderColor(sf::Color color);
        void setBackgroundColor(sf::Color color);
        void drawMaze(string mazeName,int animate,int fps);
        void checkNeighbours(int x,int y);
        int invalidNeighbour(int x,int y,char dir);
        void createMaze(string mazeName,int animate,int fps=200);
        void handleBorder(sf::VertexArray &Border,int borderCounter,sf::Color borderColor,int x,int y);
        void saveImage();
};

#endif


//cell.h
#ifndef _CELL_H_
#define _CELL_H_

void turnOnBit(unsigned char &cell, unsigned char mask);
void turnOffBit(unsigned char &cell, unsigned char mask);
int checkBit(unsigned char &cell,unsigned char mask);

const unsigned char topMask = 0b0000'0001;
const unsigned char rightMask = 0b0000'0010;
const unsigned char bottomMask = 0b0000'0100;
const unsigned char leftMask = 0b0000'1000;
const unsigned char visitedMask = 0b0001'0000;

#endif
//cell.cpp
#include "Cell.h"

void turnOnBit(unsigned char &cell, unsigned char mask)
{
    cell |= mask;
}

void turnOffBit(unsigned char &cell, unsigned char mask)
{
    cell &= ~mask;
}

int checkBit(unsigned char &cell,unsigned char mask)
{
    if(cell & mask)
    {
        return 1;
    }
    else
    {
        return 0;
    }
    
} 


//main.cpp
// g++ -c main.cpp -o main.o -I"I:/SFML/include"
// g++ -c cell.cpp -o cell.o -I"I:/SFML/include"
// g++ -c maze.cpp -o maze.o -I"I:/SFML/include"

// g++ main.o maze.o cell.o -o main -L"I:/SFML/lib" -lsfml-graphics-s -lsfml-window-s -lsfml-audio-s -lsfml-system-s -lsfml-network-s -lwinmm -lopengl32 -lopenal32 -lflac -lvorbisenc -lvorbisfile -lvorbis -logg -lws2_32 -lgdi32 -lkernel32 -luser32 -lwinspool -lshell32 -lole32 -luuid -lcomdlg32 -lfreetype -ladvapi32

#define SFML_STATIC
#include "Maze.h"
#include "SFML/Graphics.hpp"

using namespace std;

int main()
{
    sf::Color grey(200,200,200);
    sf::Color start(255,100,45);
    sf::Color end(30,150,200);

    Maze maze;

    maze.setWidth(1000);
    maze.setHeight(600);
    maze.setCellSize(25);
    maze.setBackgroundColor(grey);
    maze.setBorderColor(sf::Color::White);
    maze.setCurrentCellColor(sf::Color::Red);
    maze.setNotVisitedCellColor(grey);
    maze.setVisitedCellColor(start,end);
    maze.createMaze("First Maze",1,25);
    maze.saveImage();

    return 0;
}

The saveImage() saves the image of the maze and it takes around 30 seconds for this (I know this is a huge bottle neck, but for now I am gonna stick to it).

The main logic takes around 56 seconds to create the entire mathematical model of the maze. This is where I want to improve, if possible.

Instead of using a 2d array for the grid I am using 1D array to store all of the data and to store the state of walls and whether the cell is visited or not i use bit masking and single bit byte date type.

Any suggestions for improvement?

I am going to try and separate the mathematical generation and the graphics. I hope that is going to be the solution will update.

I tried it and just implemented a clean DFS algorithm without any graphics and used the same array size. This takes long too, so my guess is that the bottleneck is caused by bit masking / bit toggling etc.

Just in case anyone stumbles here in the future, my second edit is kind of wrong because bit fields do not make the program slow.

edit : I optimized it even more by eliminating the for loop during animation and only changing the affected cell.

This code is the same as posted the first time, i have not shared any of the edits

\$\endgroup\$
3
\$\begingroup\$

Below is a non-comprehensive review of your code.

Choosing a maze generation algorithm

There are many algorithms for generating mazes, each with their own pros and cons. If you really need to create huge mazes as fast as possible, your backtracking algorithm might not be the best. However, each algorithm typically has its own bias for generating particular mazes, so you can't just swap it out for a random other algorithm and expect the same results. Have a look at this website for an extensive list of maze generation algorithms:

http://www.astrolog.org/labyrnth/algrithm.htm

That said, the backtracking algorithm is certainly not the worst, and generates pleasing looking mazes without obvious biases.

Separate maze creation from maze rendering

The function Maze::createMaze() not only creates a maze, it also renders an animation of how it creates the maze. The code is intertwined, which makes it hard to read. I suggest you restructure it so you have class Maze responsible only for generating the maze itself, and create a function that can render the current state of a Maze. Then, find some way so you can animate what is going on. This could be done in two ways:

  1. Add a step() function to Maze that performs one step of the algorithm. Have it return a bool indicating whether the maze is still unfinished. Then, you can basically write:
    while (maze.step()) {
        render(maze);
        window.display();
        // handle window events here
    }
    
  2. Give a callback function to maze() which it can call in its maze generation algorithm after each step. Use std::function to store a reference to the callback function. The callback function should then look like:
    void render_cb(const Maze &maze) {
         // render maze
         // update window
         // handle events
    }
    

The first solution is the cleanest in my opinion, but the drawback is that you need to have something like a step() function. In this case it is fine though, since you are not using recursive function calls to generate the maze, and you keep the state of the algorithm in btx and bty.

Store x and y coordinates in a single std::stack

You have two std::stack variables, one for the x and one for the y coordinates. However, you always push and pop simultaneously. Each operation on a stack requires some bookkeeping, including possibly memory allocations. So, a simple optimization is to combine the x and y coordinates into a struct Position, and have one std::stack<Position> bt.

Optimize Cell state

First, I would make it so that the state of each cell at the start of the algorithm has all zero-bits. This saves some time initializing the maze, since after maze.resize(), the contents will be all zeroes already. This means you have to turn on a top/bottom/left/right bit to indicate it is not a wall, or perhaps you can think of a one meaning a passage instead of a wall. Second, consider that you always turned on the visitedMask bit whenever you removed one of the other bits. Now that the meaning of the other bits is flipped, you always set visitedMask if you also set another bit. This means that whenever one of the passage bits is set, you have necessarily also visited this cell. And that means you no longer need to store visitedMask at all, it can be derived from the other bits. In fact:

int visited = checkBit(maze[...], visitedMask);
if (!visited)
{
     ...
}

Can now be replaced by:

if (maze[...])
{
    ...
}

This is slightly more efficient than checking for a particular bit, and it's also less typing. The only issue is the first cell of the maze. I would make it so the top or right is always set at the start, to indicate the direction of the entrance to the maze.

Checking for the walls

The code to deal with walls is written in a very confusing way. invalidNeighbour() takes parameters x and y, which sounds like x and y coordinates, but they are actually array indices of the neighbour and the current position. Furthermore, it returns 0 (false) if the position of the neighbour is invalid, and 1 (true) if it is valid, the opposite of that the name suggests. Last but not least, it is terribly inefficient to first convert x and y coordinates to array indices just to check if you are at a wall, when you can easily see that from the coordinates themselves. So, I would get rid of invalidNeighbour() entirely, and in checkNeighbour() write:

void Maze::checkNeighbours(int x,int y)
{
    ...
    if (x >= 0) // we are not at the top
    {
        if (!maze[cols * (x - 1) + y])
        {
            direction...
        }
    }
    ...

Avoid unnecessary memory allocations

A std::vector allocates memory from the heap. In checkNeighbours(), you only need to track of four bits: which of the four directions have not been visited yet. A std::vector is overkill and will do expensive memory allocations. What you can do instead is just have a fixed-size array, and a counter:

char direction[4];
size_t count = 0;
...
if (...)
{
    direction[count++] = 't';
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ WHAT!!!!, thanks for the extensive reply, i appreciate it. \$\endgroup\$ – theirrevocableSake Sep 5 at 14:40
0
\$\begingroup\$

The checkBit function is very verbose. It can be much shorter and maybe even faster without losing clarity:

    bool checkBit(unsigned char cell, unsigned char mask) {
        return cell & mask;
    }

In general you use int for boolean values but there is a new bool type in C++ now that I would recommend.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ bool was introduced in the previous millenium, it's not exactly new anymore. \$\endgroup\$ – G. Sliepen Sep 5 at 20:57
  • \$\begingroup\$ But this likely means even more that it should be used were relevant. \$\endgroup\$ – h22 Sep 5 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.