#include <stdio.h>
#include <stdlib.h>

#include <SDL.h>

#include <GL/gl.h>
#include <GL/glu.h>

int cnt;
int cnts[9];
int board[3][3];

int W, H;

int winner() {
    int n;
    for (int y = 0; y < 3; y++) {
        n = board[y][0];
        if (n && board[y][0] == board[y][1] && board[y][1] == board[y][2]) {
            return n;
        }
    }
    for (int x = 0; x < 3; x++) {
        n = board[0][x];
        if (n && board[0][x] == board[1][x] && board[1][x] == board[2][x]) {
            return n;
        }
    }
    n = board[0][0];
    if (n && board[0][0] == board[1][1] && board[1][1] == board[2][2]) {
        return n;
    }
    n = board[0][2];
    if (n && board[0][2] == board[1][1] && board[1][1] == board[2][0]) {
        return n;
    }
    return 0;
}

float getHeightFromDepth(int n) {
    return (n - 4) * 0.5;
}

void dfs(int n, float bx, float by, float scale) {
    cnt++;
    cnts[n]++;

    int w = winner();
    if (w) {
        return;
    }

    for (int y = 0; y < 3; y++) {
        for (int x = 0; x < 3; x++) {
            if (board[y][x]) continue;

            board[y][x] = n % 2 + 1;
            if (winner()) {
                board[y][x] = 0;
                continue;
            }

/*
            float nbx = bx + (x - 1) * scale;
            float nby = by + (y - 1) * scale;
*/
            float nbx = (x - 1) * 2.0 / 3 + bx / 3;
            float nby = (y - 1) * 2.0 / 3 + by / 3;
            float alpha = scale > 0.002 ? scale : 0.002;
            //float alpha = scale > 0.002 ? scale : 0.002;
            //float alpha = scale * 20;
/*
            float r = rand() % 256 / 256.0;
            float g = rand() % 256 / 256.0;
            float b = rand() % 256 / 256.0;
            glColor4f(r, g, b, alpha);
*/
            glColor4f(1, 1, 1, alpha);
            glBegin(GL_LINE);
            glVertex3f(bx, getHeightFromDepth(n - 1), by);
            glVertex3f(nbx, getHeightFromDepth(n), nby);
            glEnd();

            dfs(n + 1, nbx, nby, scale / 3);
            board[y][x] = 0;
        }
    }

    if (n < 5) {
        SDL_GL_SwapBuffers();
    }
}

int main() {
    W = 1024;
    H = 768;

    SDL_Init(SDL_INIT_VIDEO);
    SDL_SetVideoMode(W, H, 32, SDL_OPENGL);

    glViewport(0, 0, W, H);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    gluPerspective(25, (double)W/H, 1.0, 100.0);
    glTranslatef(0.0, 0.0, -5.0);
    gluLookAt(3, 1.5, 4, 0, 0, 0, 0, 1, 0);

    glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT);

    glMatrixMode(GL_MODELVIEW);
    glLoadIdentity();

    glEnable(GL_BLEND);
    glBlendFunc(GL_SRC_ALPHA, GL_ONE);
    glColor4f(1, 1, 1, 0.5);

    for (int i = 0; i < 9; i++) {
        float z = getHeightFromDepth(i);
        glBegin(GL_LINE_LOOP);
        glVertex3f(-1, z, -1);
        glVertex3f(-1, z, 1);
        glVertex3f(1, z, 1);
        glVertex3f(1, z, -1);
        glEnd();
    }

    dfs(0, 0, 0, 2.0 / 3);
    printf("%d nodes, %d leafs\n", cnt, cnts[9]);

    SDL_GL_SwapBuffers();

    SDL_Event ev;
    while (SDL_WaitEvent(&ev)) {
        if (ev.type == SDL_QUIT) {
            break;
        }
        else if (ev.type == SDL_KEYDOWN && ev.key.keysym.sym == SDLK_ESCAPE) {
            break;
        }
        SDL_GL_SwapBuffers();
    }

    SDL_Quit();
}