Maze Generator mit C ++ und SFML
Ich habe einen DFS-Backtracking-Labyrinth-Generator (nicht rekursiv) mit C ++ und SFML erstellt. Es funktioniert hervorragend, aber das Endergebnis beim Erstellen eines 9000 x 9000 mit Zellengröße 2 liegt bei 1 Minute und 46 Sekunden <-> 1 Minute und 30 Sekunden, um das generierte Labyrinth direkt als Bild ohne irgendeine Art von GUI zu speichern.
Ich werde versuchen, meinen Code zu erklären. Die vorletzte Funktion drawMaze()ist die Hauptlogik. Ich habe einen für die x- und einen für die y-Koordinate gestapelt, um den Backtrack zu speichern.
//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;
}
Das saveImage()speichert das Bild des Labyrinths und es dauert ungefähr 30 Sekunden (ich weiß, dass dies ein riesiger Flaschenhals ist, aber jetzt werde ich mich daran halten).
Die Hauptlogik benötigt ungefähr 56 Sekunden, um das gesamte mathematische Modell des Labyrinths zu erstellen. Hier möchte ich mich nach Möglichkeit verbessern.
Anstatt ein 2D-Array für das Raster zu verwenden, verwende ich ein 1D-Array, um alle Daten zu speichern und den Zustand der Wände zu speichern, und ob die Zelle besucht wird oder nicht, ich verwende Bitmaskierung und Einzelbit-Byte-Datumstyp.
Verbesserungsvorschläge?
Ich werde versuchen, die mathematische Generation und die Grafiken zu trennen. Ich hoffe, dass die Lösung aktualisiert wird.
Ich habe es versucht und nur einen sauberen DFS-Algorithmus ohne Grafik implementiert und dieselbe Arraygröße verwendet. Dies dauert auch lange, daher schätze ich, dass der Engpass durch Bitmaskierung / Bitumschaltung usw. verursacht wird.
Nur für den Fall, dass hier in Zukunft jemand stolpert, ist meine zweite Bearbeitung etwas falsch, da Bitfelder das Programm nicht verlangsamen.
Bearbeiten: Ich habe es noch weiter optimiert, indem ich die for-Schleife während der Animation entfernt und nur die betroffene Zelle geändert habe.
Dieser Code ist der gleiche wie beim ersten Mal, ich habe keine der Änderungen geteilt
Antworten
Unten finden Sie eine nicht umfassende Überprüfung Ihres Codes.
Auswahl eines Labyrinth-Generierungsalgorithmus
Es gibt viele Algorithmen zur Erzeugung von Labyrinthen, von denen jeder seine eigenen Vor- und Nachteile hat. Wenn Sie wirklich so schnell wie möglich riesige Labyrinthe erstellen müssen, ist Ihr Backtracking-Algorithmus möglicherweise nicht der beste. Jeder Algorithmus hat jedoch normalerweise seine eigene Tendenz, bestimmte Labyrinthe zu erzeugen. Sie können ihn also nicht einfach gegen einen zufälligen anderen Algorithmus austauschen und dieselben Ergebnisse erwarten. Auf dieser Website finden Sie eine umfangreiche Liste von Algorithmen zur Labyrinthgenerierung:
http://www.astrolog.org/labyrnth/algrithm.htm
Das heißt, der Backtracking-Algorithmus ist sicherlich nicht der schlechteste und erzeugt angenehm aussehende Labyrinthe ohne offensichtliche Verzerrungen.
Trennen Sie die Labyrinth-Erstellung vom Labyrinth-Rendering
Die Funktion erstellt Maze::createMaze()nicht nur ein Labyrinth, sondern rendert auch eine Animation, wie das Labyrinth erstellt wird. Der Code ist miteinander verflochten, was das Lesen erschwert. Ich schlage vor, Sie strukturieren es so um, dass Sie class Mazenur für die Erzeugung des Labyrinths selbst verantwortlich sind, und erstellen eine Funktion, die den aktuellen Status von a wiedergeben kann Maze. Finden Sie dann einen Weg, damit Sie animieren können, was los ist. Dies kann auf zwei Arten geschehen:
- Fügen Sie eine
step()Funktion hinzuMaze, die einen Schritt des Algorithmus ausführt. Lassen Sie es einenboolHinweis zurückgeben, ob das Labyrinth noch unvollendet ist. Dann können Sie im Grunde schreiben:while (maze.step()) { render(maze); window.display(); // handle window events here } - Geben Sie eine Rückruffunktion an,
maze()die nach jedem Schritt in ihrem Labyrinthgenerierungsalgorithmus aufgerufen werden kann. Verwenden Sie std::functiondiese Option , um einen Verweis auf die Rückruffunktion zu speichern. Die Rückruffunktion sollte dann folgendermaßen aussehen:void render_cb(const Maze &maze) { // render maze // update window // handle events }
Die erste Lösung ist meiner Meinung nach die sauberste, aber der Nachteil ist, dass Sie so etwas wie eine step()Funktion haben müssen. In diesem Fall ist dies jedoch in Ordnung, da Sie keine rekursiven Funktionsaufrufe zum Generieren des Labyrinths verwenden und den Status des Algorithmus in btxund beibehalten bty.
Speichern Sie die x- und y-Koordinaten in einer einzigen std::stack
Sie haben zwei std::stackVariablen, eine für die x- und eine für die y-Koordinaten. Sie drücken und knallen jedoch immer gleichzeitig. Jede Operation auf einem Stapel erfordert eine gewisse Buchhaltung, einschließlich möglicherweise Speicherzuweisungen. Eine einfache Optimierung besteht also darin, die x- und y-Koordinaten zu a zu kombinieren und eine zu struct Positionhaben std::stack<Position> bt.
CellZustand optimieren
Zuerst würde ich es so machen, dass der Zustand jeder Zelle zu Beginn des Algorithmus alle Nullbits hat. Dies spart einige Zeit beim Initialisieren des Labyrinths, da maze.resize()der Inhalt danach bereits alle Nullen enthält. Dies bedeutet, dass Sie ein oberes / unteres / linkes / rechtes Bit einschalten müssen, um anzuzeigen, dass es sich nicht um eine Wand handelt, oder dass Sie sich eine vorstellen können, die einen Durchgang anstelle einer Wand bedeutet. Zweitens sollten Sie berücksichtigen, dass Sie das visitedMaskBit immer eingeschaltet haben, wenn Sie eines der anderen Bits entfernt haben. Nachdem die Bedeutung der anderen Bits umgedreht wurde, setzen Sie immer, visitedMaskwenn Sie auch ein anderes Bit setzen. Dies bedeutet, dass Sie diese Zelle immer dann besucht haben, wenn eines der Durchgangsbits gesetzt ist. Und das bedeutet, dass Sie überhaupt nicht mehr speichern müssen visitedMask, es kann von den anderen Bits abgeleitet werden. Tatsächlich:
int visited = checkBit(maze[...], visitedMask);
if (!visited)
{
...
}
Kann jetzt ersetzt werden durch:
if (maze[...])
{
...
}
Dies ist etwas effizienter als das Überprüfen auf ein bestimmtes Bit, und es ist auch weniger tippend. Das einzige Problem ist die erste Zelle des Labyrinths. Ich würde es so machen, dass oben oder rechts immer am Anfang gesetzt wird, um die Richtung des Eingangs zum Labyrinth anzuzeigen.
Überprüfung auf die Wände
Der Code für den Umgang mit Wänden ist sehr verwirrend geschrieben. invalidNeighbour()nimmt Parameter xund y, was wie x- und y-Koordinaten klingt, aber sie sind tatsächlich Array-Indizes des Nachbarn und der aktuellen Position. Außerdem gibt es 0( false) zurück, wenn die Position des Nachbarn ungültig ist, und 1( true), wenn sie gültig ist, das Gegenteil von dem, was der Name andeutet. Last but not least ist es furchtbar ineffizient, zuerst Konvertierungen xund yKoordinaten in Array-Indizes zu konvertieren , um zu überprüfen, ob Sie sich an einer Wand befinden, wenn Sie dies anhand der Koordinaten selbst leicht erkennen können. Also würde ich invalidNeighbour()ganz loswerden und checkNeighbour()schriftlich:
void Maze::checkNeighbours(int x,int y)
{
...
if (x >= 0) // we are not at the top
{
if (!maze[cols * (x - 1) + y])
{
direction...
}
}
...
Vermeiden Sie unnötige Speicherzuordnungen
A std::vectorordnet Speicher vom Heap zu. In checkNeighbours()müssen Sie nur vier Bits verfolgen: Welche der vier Richtungen wurde noch nicht besucht? A std::vectorist übertrieben und führt teure Speicherzuweisungen durch. Sie können stattdessen nur ein Array mit fester Größe und einen Zähler verwenden:
char direction[4];
size_t count = 0;
...
if (...)
{
direction[count++] = 't';
}
Die checkBitFunktion ist sehr ausführlich. Es kann viel kürzer und vielleicht sogar schneller sein, ohne an Klarheit zu verlieren:
bool checkBit(unsigned char cell, unsigned char mask) {
return cell & mask;
}
Im Allgemeinen verwenden Sie intfür boolesche Werte, aber es gibt booljetzt einen neuen Typ in C ++, den ich empfehlen würde.