Dfs maze generation, optimization?

0
votes

I am trying to learn to implement all of the maze generation algorithms one by one, my first maze generation algorithm was dfs backtracking ( non recursive ) and i am done with the implementation, i have used cpp and sfml for it.

I optimized it by using 1d vector and bit fields and the final results for rendering a maze of 9000 x 9000 with a cell size of 2 is around 1 min and 46 seconds ( directly writing to image no gui ).

Can this be still improved? ( I think my image writing method is quite slow. )

1
c++depth-first-searchmaze
Everything can be improved; can you show your code? - Vlad Feinstein
@VladFeinstein here you go : github.com/irrevocablesake/maze_generator/blob/master/Maze.cpp The draw maze function is the main logic ( second last function ) and i use two stacks btx and bty to store all of the visited position to backtrack in those stacks. There are three possible ways to generate : 1-> animate at a certain fps 0-> do not animate but directly pop up the maze on the screen -1->do not animate and do not show a pop up of the maze on the screen - theirrevocableSake
I am getting 404... - Vlad Feinstein
@VladFeinstein try again in a min or two, i'll do something about it - theirrevocableSake
@VladFeinstein here you go : github.com/irrevocablesake/maze/blob/master/main.cpp - theirrevocableSake

1 Answers

0
votes

It's not easy to follow the logic in your code. Looks like in Maze::checkNeighbours you use x and y as coordinates (where x for some reason is vertical), while in Maze::invalidNeighbour x is new linear offset and y is old?

Anyway, you can remove all that math and replace your conditions as follows:

  • if(top) -> if(x > 0)
  • if(right) -> if(y + 1 < cols)
  • if(bottom) -> if(x + 1 < rows)
  • if(left) -> if(y > 0) As this are used a lot of time, you may save some time.

I am not sure how compiler would optimize your frequent creation of sf::Vector2f and their assignment to another sf::Vector2f; even if they are moved, you lost time on constructing them in the first place. So, instead of:

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

I would do:

Quad[counter].position.x = (j*cellSize)+padding;
Quad[counter].position.y = (i*cellSize)+cellSize+padding;

Since you have a dozen of those, executed millions of times, my guess is that you will see some improvement.

Then you can avoid multiplications in (j*cellSize) and (i*cellSize) by replacing them with the increment in the for statements, like:

for(int i=0, iScaled=0; i<rows; i++, iScaled += cellSize)
{
    for(int j=0, jScaled = 0; j<cols; j++, jScaled += cellSize)

Your compiler would probably do that, but I think it will make it easier to read.

Quad[counter].position.x = jScaled+padding;
Quad[counter].position.y = iScaled+cellSize+padding;

I would also like to see your turnOnBit, turnOffBit and checkBit as they are called a LOT.

As for saving the image, although I don't know sfml, using SetPixel is typically very bad for performance. Looks like there is sf::Image::loadFromMemory. Can you arrange your internal representation of the maze so it could just be loaded?

[CORRECTION] My micro-optimizations didn't make much difference; as expected - the compiler optimization took care of that.

However, I ran a profiler and noticed that most of the time is spent in GL and GDI. Then I change the fps rate from 25 to 250 and got 10 times performance improvement! Could it be that window.display(); throttles your loop?If I change the fps to 2, it slows down to a crawl...