Генератор лабиринта

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <windows.h>
#include <string.h>
 
using namespace std;
 
#define MAX 299  // 30 * 2 + 1
#define CELL 9000  // 30 * 30
#define WALL -1  // ну стена
#define PATH -2  // ну путь
#define begun -3 // бегунок
#define wi -4  // точка конца
 
void init_maze(int maze[MAX][MAX]);
void maze_generator(int indeks, int maze[MAX][MAX], int backtrack_x[CELL], int bactrack_y[CELL], int x, int y, int n, int visited);
void print_maze(int maze[MAX][MAX], int maze_size);
int is_closed(int maze[MAX][MAX], int x, int y);
unsigned short keysArrow;
 
LARGE_INTEGER timerFrequency, timerStart, timerStop;
 
int s1=1, s2=1,b=0;
int maze[MAX][MAX];
int size;
int len,p=1;
int val=0;
double t1,t2,t3;
 
bool validate(int xIn, int yIn, int xOut, int yOut);
 
void gotoXY(int line, int column)
{
    COORD coord;
    coord.X = column;
    coord.Y = line;
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), coord);
}
 
void win()
{
    system("cls");
    printf("\n\n\n\n\n\n\n\n\n\n\n\n\t\t  TpaTaTa ! risovka=%f labgen=%f %.10f\n\n\n\n\n\n\n\n\n\n\n", t3, t1, t2);
    b=1;
    s1=1;s2=1;
    gotoXY(s1,s2);
}
 
int main(void)
{
    QueryPerformanceFrequency(&timerFrequency);
    short int flag;
    int indeks = 0;
    char cc[15];
    printf("MAZE CREATOR\n\n");
    printf("s - navigator\n\n");
    printf("q - exit\n\n3");
    printf("input  (5 ~ 30): ");
    
    do
    {
        gets(cc);
        flag=1;
 
        for (int i=0; i < strlen(cc); i++)
        {
            sscanf(cc, "%d", &size);
 
            if (cc[i]<48||cc[i]>57) 
                {flag=0;printf("5 ~ 30\n");break;}
 
            else if((size<5)||(size>150))
                {printf ("5 ~ 30\n"); flag=0;break;}
        }
    }
    while(flag!=1);
 
    sscanf(cc, "%d", &size);
    printf("\n");
 
    int backtrack_x[CELL];
    int backtrack_y[CELL];
    s1=1, s2=1;
 
    for(int i=0; i < 1000; i++)
    {
        QueryPerformanceCounter(&timerStart);
 
        init_maze(maze);
        backtrack_x[indeks] = 1;
        backtrack_y[indeks] = 1;
        maze_generator(indeks, maze, backtrack_x, backtrack_y, 1, 1, size, 1);
        
        QueryPerformanceCounter(&timerStop);    
        double const f( static_cast<double>( timerStop.QuadPart - timerStart.QuadPart ) / timerFrequency.QuadPart );
        t1+=f;
    }
 
    maze [size * 2 ][size * 2-1]=wi;
    maze [s1][s2]=begun;
 
    system("cls");
    QueryPerformanceCounter(&timerStart);
 
    for(int a = 0; a < (size) * 2 + 1; a++)
    {
        for(int b = 0; b < size * 2 + 1; b++)
        { 
            if(maze[a][b] == WALL)
                printf("%c",176);
            else if ((maze[a][b]==begun)) 
                printf("%c",4);
            else if (maze[a][b]==wi) 
                printf("#");
            else if (maze[a][b]==-7) 
                 printf("#");
            else
                printf(" ");
        }
        printf("\n");
    }
 
    //printf("%d",maze[size*2][size*2-1]);
    QueryPerformanceCounter(&timerStop);
    double const t( static_cast<double>( timerStop.QuadPart - timerStart.QuadPart ) / timerFrequency.QuadPart );
    t3+=t;
    maze [(size)*2 ][size * 2-1]=wi; 
 
    do
    {
        keysArrow = getch();
 
        //timer 3
 
        if(keysArrow == 72)
        { 
            // Вверх
            maze[s1][s2] = 0; // ну и эта штука тоже
            s1--;
            if (maze[s1][s2] ==WALL) 
                {s1++;}
            else 
            { 
                maze[s1][s2] = begun;
                gotoXY(s1,s2);
                printf("%c",4);
                gotoXY(s1+1,s2);
                printf(" ");
            }
            gotoXY(size*2,size*2);
        }
 
        if(keysArrow == 80)
        {
            // Вниз
            maze[s1][s2] = 0;
            s1++;
            if (maze[s1][s2] ==wi) {win();getch();return 0;}
            if (maze[s1][s2] ==WALL) {s1--;}
            else
            {  
                maze[s1][s2] = begun;
                gotoXY(s1,s2);
                printf("%c",4);
                gotoXY(s1-1,s2);
                printf(" ");
            }
            gotoXY(size*2,size*2);
        }
 
        if(keysArrow == 77)
        {
            // Вправо
            maze[s1][s2] = 0;
            s2++;
            // if (maze[s1][s2] ==wi) {win();}
            if (maze[s1][s2] ==WALL) 
                {s2--;}
            else
            { 
                maze[s1][s2] = begun;
                gotoXY(s1,s2);
                printf("\b %c",4);
            }
            gotoXY(size*2,size*2);
        }
 
        if(keysArrow == 75)
        {
            // Влево
            maze[s1][s2] = 0;
            s2--;
            // if (maze[s1][s2] ==wi) {win();}
            if (maze[s1][s2] ==WALL) 
                {s2++;}
            else 
            {
                maze[s1][s2] = begun;
                gotoXY(s1,s2);
                printf("  \b\b%c",4);
            }
            gotoXY(size*2,size*2);
        }
 
        if (keysArrow=='s')
        {
            QueryPerformanceCounter(&timerStart);
            if(val==0) 
            {
                validate (s1,s2,size*2,size*2-1); val=1;//строим выход при нажатии
                int v,b; 
                p= maze[(size)*2-1 ][size * 2-1];
 
                b=size*2-1;
                v=size*2-1;
 
                while (p > 1)
                {
                    if (maze[b-1][v]==p-1) 
                    {
                        b--;p--;
                        gotoXY(b,v);
                        printf("#");
                    }
                    else if (maze[b][v-1]==p-1) 
                    {
                        v--;p--;
                        gotoXY(b,v);
                        printf("#");
                    }
                    else if (maze[b+1][v]==p-1) 
                    {
                        b++;p--;
                        gotoXY(b,v);
                        printf("#");
                    }
                    else 
                    {
                        v++;p--;
                        gotoXY(b,v);
                        printf("#");
                    } 
                }
 
                //вынес проверку на равенство p из цикла и поменял местами сравнения, убрал последний иф, ибо зачем
 
                QueryPerformanceCounter(&timerStop);
                double const f1( static_cast<double>( timerStop.QuadPart - timerStart.QuadPart ) / timerFrequency.QuadPart );
                t2+=f1;
                maze [(size)*2 ][size * 2-1]=wi; 
            }
        }
 
        if (keysArrow=='q')
        {
            s1=size*2-1;
            s2=size*2-1;
        }
  
    }
    while(b!=1);
 
    getch();
    return 0;
}
 
bool validate(int xIn, int yIn, int xOut, int yOut) // ищем выход
{
    if (xIn == xOut && yIn == yOut)//|| (maze[xIn][yIn] == WALL) ||(maze[xIn][yIn] > 0) )
 
        return 0;
 
    if (maze[xIn][yIn] == WALL) 
        return false;
 
    if (maze[xIn][yIn] > 0) 
        {return false;}
 
    if(maze[xIn][yIn-1]>0) 
        {p=maze[xIn][yIn-1]+1;}
        
    else if(maze[xIn-1][yIn]>0) 
        {p=maze[xIn-1][yIn]+1;}
 
    else if(maze[xIn+1][yIn]>0)
        {p=maze[xIn+1][yIn]+1;}
 
    else if(maze[xIn][yIn+1]>0) 
        {p=maze[xIn][yIn+1]+1;}
 
    maze[xIn][yIn] =  p;
    p++;
 
    validate(xIn, yIn + 1, xOut, yOut);
    validate(xIn + 1, yIn, xOut, yOut);
    validate(xIn, yIn - 1, xOut, yOut);
    validate(xIn - 1, yIn, xOut, yOut);
}
 
void init_maze(int maze[MAX][MAX]) // построение лабиринта, а точнее начального поля, ну как видно если хотя бы одна координата четная, то это стена
{
     for(int a = 0; a < MAX; a++)
     {
         for(int b = 0; b < MAX; b++)
         {
             if(a % 2 == 0 || b % 2 == 0)
                 maze[a][b] = WALL;
             else
                 maze[a][b] = PATH;
         }
     }
}
 
void maze_generator(int indeks, int maze[MAX][MAX], int backtrack_x[CELL], int backtrack_y[CELL],
                     int x, int y, int n, int visited) // вот тут короч магия основная, уф уф уф(
{
    if(visited < n * n)
    {
        int neighbour_valid = -1;
        int neighbour_x[4];
        int neighbour_y[4];
        int step[4];
 
        int x_next;
        int y_next;
 
        if(x - 2 > 0 && is_closed(maze, x - 2, y))  // upside
        {
            neighbour_valid++;
            neighbour_x[neighbour_valid]=x - 2;
            neighbour_y[neighbour_valid]=y;
            step[neighbour_valid]=1;
        }
 
        if(y - 2 > 0 && is_closed(maze, x, y - 2))  // leftside
        {
            neighbour_valid++;
            neighbour_x[neighbour_valid]=x;
            neighbour_y[neighbour_valid]=y - 2;
            step[neighbour_valid]=2;
        }
 
        if(y + 2 < n * 2 + 1 && is_closed(maze, x, y + 2))  // rightside
        {
            neighbour_valid++;
            neighbour_x[neighbour_valid]=x;
            neighbour_y[neighbour_valid]=y + 2;
            step[neighbour_valid]=3;
        }
 
        if(x + 2 < n * 2 + 1 && is_closed(maze, x + 2, y))  // downside
        {
            neighbour_valid++;
            neighbour_x[neighbour_valid]=x+2;
            neighbour_y[neighbour_valid]=y;
            step[neighbour_valid]=4;
        }
 
        if(neighbour_valid == -1)
        {
            // backtrack
            x_next = backtrack_x[indeks];
            y_next = backtrack_y[indeks];
            indeks--;
        }
 
        if(neighbour_valid != -1) // меняем на else, в 1.1 раза быстрее
        {
            int randomization = neighbour_valid + 1;
            int random = rand()%randomization;
            x_next = neighbour_x[random];
            y_next = neighbour_y[random];
            indeks++;
            backtrack_x[indeks] = x_next;
            backtrack_y[indeks] = y_next;
 
            int rstep = step[random];
 
            if(rstep == 1)
                maze[x_next+1][y_next] = PATH;
            else if(rstep == 2)
                maze[x_next][y_next + 1] = PATH;
            else if(rstep == 3)
                maze[x_next][y_next - 1] = PATH;
            else 
                maze[x_next - 1][y_next] = PATH;
            visited++;
        }
        maze_generator(indeks, maze, backtrack_x, backtrack_y, x_next, y_next, n, visited); //рек
    }
}
 
int is_closed(int maze[MAX][MAX], int x, int y)
{
    if
        (
        maze[x - 1][y]  == WALL
        && maze[x][y - 1] == WALL
        && maze[x][y + 1] == WALL
        && maze[x + 1][y] == WALL
        )
        return 1;
 
    return 0;
}