c++ - Painfully slow maze making program -
i writing program generates size maze want. first creating every cell in maze , assuming entirely walled in. each declared own set. random cell selected , random direction break down wall. random direction funcion makes sure valid direction cell. program makes sure 2 cells looking join arent connected somehow , if arent breaks wall. if connected either directly or indirectly selects new random cell , direction. continues until number of sets left 1 ensuring can point in maze other point. program works painfully slow. dont think should slow , unsure why.
i can imagine scenario cells connected one. take little while randomly select 1 cell , slow things down imagine when dealing under 100,000 cells still shouldn't take long does. rand should prettu fast @ spitting out numbers.
ive attatched code below. simple sorry lack of notes.
#include <iostream> #include <cstdlib> #include <ctime> #include <vector> #include <string> #include <sstream> #include <algorithm> using namespace std; class dset { struct element { element() { rank=0, parent=-1; } int rank; int parent; vector<int> connections; }; public: dset(int nr=0,int nc=0); int size() {return nsets; } int merge (int, int); int find(int); // functions bool isin(int i, vector<int> test); int randdir(int i); int randcell(); int dir(int, int); void print(); vector<int> possibledir(int cell); vector<int> walls(int cell, vector<int> possible); private: int nsets; int nrows, ncols; vector<element> s; }; int main(int argc, char* argv[]){ int nrows, ncols, cell, direction; if (argc != 3){ cout << "usage: nrows ncols\n"; } stringstream convert; convert << argv[1]; convert << " "; convert << argv[2]; convert >> ncols; convert >> nrows; dset maze(nrows,ncols); srand(time(null)); while(maze.size() != 1){ cell = maze.randcell(); // cell = 11; direction = maze.randdir(cell); // direction = 0; // cout << "cell: " << cell << " direction: " << direction << " new cell: " << maze.dir(cell, direction) <<endl << endl; // cout << maze.size() << endl<<endl;; maze.merge(cell, maze.dir(cell, direction)); } maze.print(); } dset::dset(int nr,int nc) { nrows = nr; ncols = nc; int n = (nrows * ncols); if (0<n) s.insert(s.end(), n, element()); nsets = n; } void dset::print(){ vector<int> wall; cout << "maze " << nrows << " " << ncols << endl; ( int = 0; < (nrows*ncols); i++ ){ wall = walls(i,possibledir(i)); for( int j = 0; j < wall.size(); j++){ if (i < wall[j]) cout << << " " << wall[j] << endl; } } } int dset::randcell(){ return (rand()%(nrows*ncols)); } int dset::dir(int cell, int direction){ if(direction == 0) return (cell - 1); if(direction == 1) return (cell - (ncols)); if(direction == 2) return (cell+1); if(direction == 3) return (cell + ncols); } int dset::randdir(int i){ srand(time(null)); int direction; vector<int> used; //cout << "i : " << << endl; while (true){ direction = rand() % 4; while (true){ if(isin(direction,used)) direction = rand()%4; else break; } // cout << "rand: " << direction << endl; if(direction ==0){ if( != 0){ // cout << 0 << " i%(ncols -1) :" << (i%(ncols -1)) << endl; if(i%(ncols) != 0){ break; } } } if(direction == 1){ // cout << 1 << " - ncols :" << (i-ncols) << endl; if(i-ncols > 0){ break; } } if (direction == 2){ // cout << 2 << " i%(ncols) :" << (i%ncols) << endl; if ( == 0 ) break; if (i%ncols != ncols-1){ break; } } if (direction == 3){ if (i+ncols < ((nrows*ncols))){ // cout << 3 << " i+ncols :" << (i+ncols) << endl; break; } } used.push_back(direction); } return direction; } vector<int> dset::possibledir(int cell){ vector<int> possible; // cout << "cell " << cell << " possible connections:\n"; (int = 0; < 4; i++){ if (i == 0){ if( cell != 0 ){ if(cell%(ncols) !=0){ // cout << dir(cell,i) <<endl; possible.push_back(dir(cell,i)); } } } if(i==1){ if (cell-ncols > 0){ // cout<<dir(cell,i) <<endl; possible.push_back(dir(cell,i)); } } if(i==2){ if(cell == 0){ // cout<<dir(cell,i) <<endl; possible.push_back(1); }else if(cell%ncols != ncols-1){ // cout<<dir(cell,i) <<endl; possible.push_back(dir(cell,i)); } } if(i==3){ if ( cell+ncols < ((nrows*ncols))){ // cout<<dir(cell,i) <<endl; possible.push_back(dir(cell,i)); } } } // cout << endl; return possible; } vector<int> dset::walls(int cell, vector<int> possible){ vector<int> walls; // cout << cell << " connection 0: " << s[cell].connections[0] << endl; for(int = 0; < possible.size(); i++){ if (!isin(possible[i], s[cell].connections)){ // cout << "true\n"; walls.push_back(possible[i]); } // cout << "false\n"; } return walls; } int dset::merge(int i, int j) { int cell1 = i; int cell2 = j; = find(i); j = find(j); if (i != j) { element &si = s[i]; element &sj = s[j]; // adjust adjacency list // cout << "inconnections\n"; s[cell1].connections.push_back(cell2); s[cell2].connections.push_back(cell1); // cout << "notinconnections\n"; // merge (union) rank if (si.rank > sj.rank) sj.parent = i; else if (si.rank < sj.rank) si.parent = j; else { sj.parent = i; si.rank +=1; } nsets -=1; } return find(i); } int dset::find(int i) { if (s[i].parent == -1){ return i; } // recursive path compression s[i].parent = find(s[i].parent); return s[i].parent; } bool dset::isin(int i, vector<int> test){ bool out = false; for(int j = 0; j < test.size(); j++){ if(test[j] == i) out = true; } return out; }
please learn pass reference, not value.
for example:
bool dset::isin(int i, vector<int> test) you passing vector value. means entire copy made when function called. if vector has 100,000 items, unnecessary copy made. change this:
bool dset::isin(int i, vector<int>& test) now no copy done. make same change in of other functions.
you return vector value, leave alone unless proven compiler can't or won't optimize copy away.
also, make sure timing release, optimized program, , not "debug" or unoptimized program. since didn't mention compiler you're using, use settings generate optimized code when building program.
Comments
Post a Comment