#include <SDL.h>
#include <SDL_gfxPrimitives.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>

/* Make size a multiple of 6 */
/* Maximum recommended value is 60 */
#define size 24
#define squaresize 20

#define WIDTH size*squaresize

/* Standard SDL timer function, pushes SDL_USEREVENT type events into the processing queue */
Uint32 timer(Uint32 ms, void *param) {
    SDL_Event ev;
    ev.type = SDL_USEREVENT;
    SDL_PushEvent(&ev);
    return ms;
}

/* Fills the map with walls, then builds path on the start and end points */
/* The two endpoints are static here, but they do scale if size parameter is changed */
void map_init(char map[size][size]) {
    int i, j;
    for(i = 0; i < size; i++)
        for(j = 0; j < size; j++)
            map[i][j] = 0;
    map[0][1] = 1;
    map[size-1][size-2] = 1;
}



/* Draws one square on the screen */
void draw_block(SDL_Surface *screen, int i, int j, int b) {
    /* Set colours here */        /* values */
    Uint32 wall = 0xAAAAAAFF;     /* 0 */
    Uint32 path = 0x555555FF;     /* 1 */
    Uint32 seeking = 0xFFFF00FF;  /* 2 */
    Uint32 found = 0x00FF44FF;    /* 3 */

    boxColor(screen, i*squaresize, j*squaresize, (i+1)*squaresize, (j+1)*squaresize, (b==3)?found:(b==2)?seeking:(b==1)?path:wall);
}

/* Draws the current state of the map on the screen */
void draw_map(SDL_Surface *screen, char map[size][size]) {
    int i, j;
    for(i = 0; i < size; i++)
        for(j = 0; j < size; j++) {
            draw_block(screen, i, j, map[i][j]);
        }
}


/* Prototypes here because these two functions will call each other */
void generate_lab(SDL_Surface *screen, char map[size][size], int startx, int starty, int endx, int endy, int currx, int curry);
void go_in_direction(int dir, SDL_Surface *screen, char map[size][size], int startx, int starty, int endx, int endy, int currx, int curry);


/* Proceeds in the direction passed with 75% probability */
/* Builds 3 units of path, then calls the recursive function again from the new position */
void go_in_direction(int dir, SDL_Surface *screen, char map[size][size], int startx, int starty, int endx, int endy, int currx, int curry) {
    SDL_Flip(screen);
    switch(dir) {
        case 0:
        /* Right */
        if(rand()%4 && currx+3 < size-1 && !map[currx+1][curry] && !map[currx+2][curry] && !map[currx+3][curry]) {
            map[currx+1][curry] = 1; draw_block(screen, currx+1, curry, map[currx][curry]);
            map[currx+2][curry] = 1; draw_block(screen, currx+2, curry, map[currx][curry]);
            generate_lab(screen, map, startx, starty, endx, endy, currx+3, curry);
        }
        break;
        case 1:
        /* Down */
        if(rand()%4 && curry+3 < size-1 && !map[currx][curry+1] && !map[currx][curry+2] && !map[currx][curry+3]) {
            map[currx][curry+1] = 1; draw_block(screen, currx, curry+1, map[currx][curry]);
            map[currx][curry+2] = 1; draw_block(screen, currx, curry+2, map[currx][curry]);
            generate_lab(screen, map, startx, starty, endx, endy, currx, curry+3);
        }
        break;
        case 2:
        /* Left */
        if(rand()%4 && currx-3 >= 0 && !map[currx-1][curry] && !map[currx-2][curry] && !map[currx-3][curry]) {
            map[currx-1][curry] = 1; draw_block(screen, currx-1, curry, map[currx][curry]);
            map[currx-2][curry] = 1; draw_block(screen, currx-2, curry, map[currx][curry]);
            generate_lab(screen, map, startx, starty, endx, endy, currx-3, curry);
        }
        break;
        case 3:
        /* Up */
        if(rand()%4 && curry-3 >= 0 && !map[currx][curry-1] && !map[currx][curry-2] && !map[currx][curry-3]) {
            map[currx][curry-1] = 1; draw_block(screen, currx, curry-1, map[currx][curry]);
            map[currx][curry-2] = 1; draw_block(screen, currx, curry-2, map[currx][curry]);
            generate_lab(screen, map, startx, starty, endx, endy, currx, curry-3);
        }
        break;
    }
}

/* For the function below */
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

/* Shuffles an array of 4 integers */
void shuffle(int dirs[4]) {
    int i;
    for(i = 0; i < 10; i++) {
        swap(&dirs[rand()%4], &dirs[rand()%4]);
    }
    /* Debug: careful, prints lots of lines */
    /*for(i = 0; i < 4; i++)
        printf("| %d ", dirs[i]);
    printf("|\n");*/
}

/* The recursive generator function */
/* Makes a path on the current position, then calls the above function to proceed in all directions, in random order */
void generate_lab(SDL_Surface *screen, char map[size][size], int startx, int starty, int endx, int endy, int currx, int curry) {
    map[currx][curry] = 1;
    draw_block(screen, currx, curry, map[currx][curry]);
    SDL_Flip(screen);

    int dirs[] = {0, 1, 2, 3};
    shuffle(dirs);

    int i;
    for(i = 0; i < 4; i++)
        go_in_direction(dirs[i], screen, map, startx, starty, endx, endy, currx, curry);
}

/* A wrapper for the function above, generates labyrinths recursively until the whole map is filled, and the endpoint is reached */
/* It retries until the whole map is filled, sometimes it isn't, because the recursive algorithm isn't exactly great  */
void generate_labyrinth(SDL_Surface *screen, char map[size][size], int startx, int starty, int endx, int endy) {
    int done = 0;
    while(!map[endx][endy] || !done) {
        map_init(map);
        draw_map(screen, map);
        SDL_Flip(screen);
        generate_lab(screen, map, startx, starty, endx, endy, startx, starty);
        done = 1;

        int i, j;
        for(i = startx; i <= endx; i+=3)
            for(j = starty; j <= endy; j+=3)
                if(!map[i][j])
                    done = 0;
    }
}

/* Solves the labyrinth by trying out every possible path throughout it */
int solve_lab(SDL_Surface *screen, SDL_Event *ev, char map[size][size], int startx, int starty, int endx, int endy, int currx, int curry) {
    if(map[currx][curry] != 1)
        return 0;

    while(SDL_WaitEvent(ev) && ev->type != SDL_USEREVENT);

    map[currx][curry] = 2;
    draw_block(screen, currx, curry, map[currx][curry]);
    SDL_Flip(screen);

    if( (currx == endx && curry == endy) ||
        solve_lab(screen, ev, map, startx, starty, endx, endy, currx+1, curry) || /* Right */
        solve_lab(screen, ev, map, startx, starty, endx, endy, currx, curry+1) || /* Down */
        solve_lab(screen, ev, map, startx, starty, endx, endy, currx-1, curry) || /* Left */
        solve_lab(screen, ev, map, startx, starty, endx, endy, currx, curry-1) ){ /* Up */
        map[currx][curry] = 3;
        draw_block(screen, currx, curry, map[currx][curry]);
        SDL_Flip(screen);
        return 1;
    }

    return 0;
}

/* Solves a labyrinth with the recursive funtcion above */
void solve_labyrinth(SDL_Surface *screen, SDL_Event *ev, char map[size][size], int startx, int starty, int endx, int endy) {
    SDL_TimerID id;
    id = SDL_AddTimer(35, timer, NULL);

    solve_lab(screen, ev, map, startx, starty, endx, endy, startx, starty);

    SDL_RemoveTimer(id);
}

int main(int argc, char *argv[]) {
    srand(time(0));

    SDL_Event ev;
    SDL_Surface *screen;

    SDL_Init(SDL_INIT_VIDEO | SDL_INIT_TIMER);
    screen=SDL_SetVideoMode(WIDTH, WIDTH, 0, SDL_ANYFORMAT);
    if (!screen) {
        fprintf(stderr, "Could not open SDL window\n");
        exit(1);
    }
    SDL_WM_SetCaption("Labyrinth generator", "Labyrinth generator");

    char map[size][size];

    /* Pushes a fake key press event on the SDL queue */
    SDL_Event firstevent;
    firstevent.type = SDL_KEYDOWN;
    SDL_PushEvent(&firstevent);

    /* Generates new labyrinth on key press */
    /* Solves current labyrinth on mouse click */
    while (SDL_WaitEvent(&ev) && ev.type!=SDL_QUIT) {
        switch(ev.type) {
            case SDL_KEYDOWN:
                generate_labyrinth(screen, map, 1, 1, size-2, size-2);
                draw_map(screen, map);
                SDL_Flip(screen);
            break;
            case SDL_MOUSEBUTTONDOWN:
                solve_labyrinth(screen, &ev, map, 0, 1, size-1, size-2);
            break;
        }
    }

    SDL_Quit();

    return 0;
}