/////////////////////////////////////// // Labyrinth ////////////////////////////////////// // Paul Caron //////////////////////////////////////// // Do not copy /////////////////////////////////////// #include #include #include #include #include #define matrixSize 30 using namespace std; char nullchar ='X'; char getChar(bool top,bool right,bool bottom,bool left){ if(top&&!right&&bottom&&!left)return char(179); if(top&&!right&&bottom&&left)return char(180); if(!top&&!right&&bottom&&left)return char(191); if(top&&right&&!bottom&&!left)return char(192); if(top&&right&&!bottom&&left)return char(193); if(!top&&right&&bottom&&left)return char(194); if(top&&right&&bottom&&!left)return char(195); if(!top&&right&&!bottom&&left)return char(196); if(top&&right&&bottom&&left)return char(197); if(top&&!right&&!bottom&&left)return char(217); if(!top&&right&&bottom&&!left)return char(218); if(!top&&right&&!bottom&&!left)return char(452); if(!top&&!right&&!bottom&&left)return char(452); if(top&&!right&&!bottom&&!left)return char(179); if(!top&&!right&&bottom&&!left)return char(179); return nullchar; } char getCharAI(char c){ if(c==char(179)){return char(186);} if(c==char(180)){return char(185);} if(c==char(191)){return char(187);} if(c==char(192)){return char(200);} if(c==char(193)){return char(202);} if(c==char(194)){return char(203);} if(c==char(195)){return char(204);} if(c==char(196)){return char(205);} if(c==char(197)){return char(206);} if(c==char(217)){return char(188);} if(c==char(218)){return char(201);} if(c==char(452)){return char(205);} return c ; } class Cell{ static int count; public: int x,y; char c=nullchar; bool top=false; bool right=false; bool bottom=false; bool left=false; Cell(){ this->x=count%matrixSize; this->y=count/matrixSize; count++; } }; int Cell::count=0; Cell matrix[matrixSize][matrixSize]; Cell* findNext(Cell* current){ vector nexts; vector connectionsCurrent; vector connectionsNext; int x=current->x; int y=current->y; if(y-1>=0){ if((matrix[y-1][x]).c==nullchar){ nexts.push_back(&(matrix[y-1][x]));//add top connectionsCurrent.push_back(&(current->top)); connectionsNext.push_back(&((matrix[y-1][x]).bottom)); } } if(y+1bottom)); connectionsNext.push_back(&((matrix[y+1][x]).top)); } } if(x-1>=0){ if((matrix[y][x-1]).c==nullchar){ nexts.push_back(&(matrix[y][x-1]));//add left connectionsCurrent.push_back(&(current->left)); connectionsNext.push_back(&((matrix[y][x-1]).right)); } } if(x+1right)); connectionsNext.push_back(&((matrix[y][x+1]).left)); } } int n=nexts.size(); if(n==0){ return current; } int r=rand()%n; Cell* next=nexts.at(r); bool* connection=(connectionsCurrent.at(r)); *connection=true; *(connectionsNext.at(r))=true; current->c=getChar(current->top,current->right,current->bottom,current->left); return next; } int main() { stack backtracker; stack ai_backtracker; srand(time(0)); int x=0; int y=0; cout<<"Labyrinth\n\nThe lines are not the walls.\nThe lines are the paths.\n\n"; Cell* current=&(matrix[y][x]); Cell* next=current; Cell* copy; bool solved=false; do{ do{ copy=current; next=findNext(current); current=next; if(next==copy){ break; } backtracker.push(copy); if(!solved){ ai_backtracker.push(copy); if(next->x==matrixSize-1&&next->y==matrixSize-1){ solved=true; } } }while(next!=copy); backtracker.pop(); if(!solved){ ai_backtracker.pop(); } if(backtracker.size()>0){ current=backtracker.top();} next->c=getChar(next->top,next->right,next->bottom,next->left); }while(backtracker.size()!=0); for(int a=0;ac=getCharAI((cl->c)); ai_backtracker.pop(); } (matrix[matrixSize-1][matrixSize-1]).c=getCharAI((matrix[matrixSize-1][matrixSize-1]).c); for(int a=0;a

Labyrinth solutionner-AI