Maze Generator utilizzando C ++ e SFML
Ho creato un generatore di labirinti di backtracking DFS (non ricorsivo) usando C ++ e SFML. Funziona benissimo ma il risultato finale della creazione di un 9000 x 9000 con cella di dimensione 2 è di circa 1 minuto e 46 secondi <-> 1 minuto e 30 secondi, per memorizzare direttamente il labirinto generato come immagine senza alcun tipo di GUI.
Proverò a spiegare il mio codice. La penultima funzione drawMaze()è la logica principale. Ho usato per impilare uno per xe l'altro per la coordinata y per memorizzare il 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;
}
Il saveImage()salva l'immagine del labirinto e ci vogliono circa 30 secondi per questo (so che questo è un enorme collo di bottiglia, ma per ora mi atterrò ad esso).
La logica principale impiega circa 56 secondi per creare l'intero modello matematico del labirinto. È qui che voglio migliorare, se possibile.
Invece di utilizzare un array 2d per la griglia, sto usando un array 1D per memorizzare tutti i dati e per memorizzare lo stato dei muri e se la cella è visitata o meno, utilizzo il mascheramento dei bit e il tipo di data a byte singolo.
Qualche suggerimento per il miglioramento?
Proverò a separare la generazione matematica e la grafica. Spero che la soluzione verrà aggiornata.
L'ho provato e ho appena implementato un algoritmo DFS pulito senza grafica e ho utilizzato la stessa dimensione dell'array. Anche questo richiede molto tempo, quindi la mia ipotesi è che il collo di bottiglia sia causato dal mascheramento dei bit / commutazione dei bit ecc.
Nel caso qualcuno dovesse inciampare qui in futuro, la mia seconda modifica è un po 'sbagliata perché i campi di bit non rallentano il programma.
modifica: l'ho ottimizzato ancora di più eliminando il ciclo for durante l'animazione e cambiando solo la cella interessata.
Questo codice è lo stesso pubblicato la prima volta, non ho condiviso nessuna delle modifiche
Risposte
Di seguito è riportata una revisione non completa del codice.
Scegliere un algoritmo di generazione del labirinto
Esistono molti algoritmi per generare labirinti, ciascuno con i propri pro e contro. Se hai davvero bisogno di creare enormi labirinti il più velocemente possibile, il tuo algoritmo di backtracking potrebbe non essere il migliore. Tuttavia, ogni algoritmo ha in genere il proprio pregiudizio per la generazione di labirinti particolari, quindi non puoi semplicemente sostituirlo con un altro algoritmo casuale e aspettarti gli stessi risultati. Dai un'occhiata a questo sito Web per un ampio elenco di algoritmi di generazione di labirinti:
http://www.astrolog.org/labyrnth/algrithm.htm
Detto questo, l'algoritmo di backtracking non è certamente il peggiore e genera labirinti dall'aspetto piacevole senza pregiudizi evidenti.
Creazione labirinto separata dal rendering labirinto
La funzione Maze::createMaze()non solo crea un labirinto, ma rende anche un'animazione di come crea il labirinto. Il codice è intrecciato, il che lo rende difficile da leggere. Ti suggerisco di ristrutturarlo in modo da avere la class Mazeresponsabilità solo della generazione del labirinto stesso e di creare una funzione che possa rendere lo stato corrente di un file Maze. Quindi, trova un modo in modo da poter animare ciò che sta accadendo. Questo potrebbe essere fatto in due modi:
- Aggiungere una
step()funzione aMazeche esegue un passaggio dell'algoritmo. Fallo restituire un cheboolindica se il labirinto è ancora incompiuto. Quindi, puoi sostanzialmente scrivere:while (maze.step()) { render(maze); window.display(); // handle window events here } - Dare una funzione di callback a
maze()cui può chiamare nel suo algoritmo di generazione del labirinto dopo ogni passaggio. Utilizzare std::functionper memorizzare un riferimento alla funzione di callback. La funzione di callback dovrebbe quindi assomigliare a:void render_cb(const Maze &maze) { // render maze // update window // handle events }
La prima soluzione è la più pulita secondo me, ma lo svantaggio è che devi avere qualcosa come una step()funzione. In questo caso va bene, dal momento che non stai usando chiamate di funzione ricorsive per generare il labirinto, e mantieni lo stato dell'algoritmo in btxebty .
Memorizza le coordinate xey in un unico file std::stack
Hai due std::stackvariabili, una per le coordinate x e una per le coordinate y. Tuttavia, spingi e fai sempre scoppiare contemporaneamente. Ogni operazione su uno stack richiede una certa contabilità, incluse possibilmente allocazioni di memoria. Quindi, una semplice ottimizzazione consiste nel combinare le coordinate xey in a struct Position, e averne unastd::stack<Position> bt .
Ottimizzare Cell stato
Innanzitutto, farei in modo che lo stato di ogni cella all'inizio dell'algoritmo abbia tutti i bit zero. Ciò consente di risparmiare un po 'di tempo nell'inizializzazione del labirinto, poiché dopo maze.resize(), i contenuti saranno già tutti zeri. Ciò significa che devi attivare una punta in alto / in basso / sinistra / destra per indicare che non è un muro, o forse puoi pensare a uno che significhi un passaggio anziché un muro. Secondo, considera che hai sempre acceso il visitedMaskbit ogni volta che hai rimosso uno degli altri bit. Ora che il significato degli altri bit è capovolto, imposti sempre visitedMaskse imposti anche un altro bit. Ciò significa che ogni volta che viene impostato uno dei bit di passaggio, hai necessariamente visitato anche questa cella. Ciò significa che non è più necessario archiviarlo visitedMask, può essere derivato dagli altri bit. Infatti:
int visited = checkBit(maze[...], visitedMask);
if (!visited)
{
...
}
Ora può essere sostituito da:
if (maze[...])
{
...
}
Questo è leggermente più efficiente rispetto al controllo di un bit particolare ed è anche meno digitato. L'unico problema è la prima cella del labirinto. Farei in modo che la parte superiore o destra sia sempre impostata all'inizio, per indicare la direzione dell'ingresso del labirinto.
Controllo dei muri
Il codice per gestire i muri è scritto in modo molto confuso. invalidNeighbour()accetta i parametri xe y, che suona come coordinate xey, ma in realtà sono indici di array del vicino e della posizione corrente. Inoltre, restituisce 0( false) se la posizione del vicino non è valida e 1( true) se è valida, l'opposto di quello che suggerisce il nome. Ultimo ma non meno importante, è terribilmente inefficiente prima convertire xe ycoordinate in indici di array solo per verificare se sei su un muro, quando puoi facilmente vederlo dalle coordinate stesse. Quindi, mi sbarazzerei del invalidNeighbour()tutto e per checkNeighbour()iscritto:
void Maze::checkNeighbours(int x,int y)
{
...
if (x >= 0) // we are not at the top
{
if (!maze[cols * (x - 1) + y])
{
direction...
}
}
...
Evita allocazioni di memoria non necessarie
A std::vectoralloca la memoria dall'heap. In checkNeighbours(), devi solo tenere traccia di quattro bit: quale delle quattro direzioni non è stata ancora visitata. A std::vectorè eccessivo e farà costose allocazioni di memoria. Quello che puoi fare invece è avere solo un array di dimensioni fisse e un contatore:
char direction[4];
size_t count = 0;
...
if (...)
{
direction[count++] = 't';
}
La checkBitfunzione è molto dettagliata. Può essere molto più breve e forse anche più veloce senza perdere chiarezza:
bool checkBit(unsigned char cell, unsigned char mask) {
return cell & mask;
}
In generale si utilizza intper i valori booleani, ma ora c'è un nuovo booltipo in C ++ che consiglierei.