#include "world.h"
#include <stdlib.h>
#include <string.h>
#include <math.h>

//---
// Jump-flood Voronoi diagram generation
//---

static void jumpFlood(int N, WorldCoord *seeds, int8_t *world,
    int px, int py, int qx, int qy)
{
    if((unsigned)qx >= (unsigned)N || (unsigned)qy >= (unsigned)N)
        return;

    int pi = N * py + px;
    int qi = N * qy + qx;
    int sp = world[pi];
    int sq = world[qi];

    if(sp < 0 && sq >= 0) {
        world[pi] = sq;
    }
    else if(world[pi] >= 0 && world[qi] >= 0) {
        WorldCoord spc = seeds[sp];
        WorldCoord sqc = seeds[sq];

        int dist_sp_2 = (py-spc.y) * (py-spc.y) + (px-spc.x) * (px-spc.x);
        int dist_sq_2 = (py-sqc.y) * (py-sqc.y) + (px-sqc.x) * (px-sqc.x);
        if(dist_sq_2 < dist_sp_2)
            world[pi] = sq;
    }
}

/* This assumes [world] to be of size N*N */
static void voronoi(int8_t *world, int N, WorldCoord *seeds)
{
    int k = N / 2;
    while(k > 0) {
        for(int py = 0; py < N; py++)
        for(int px = 0; px < N; px++) {
            jumpFlood(N, seeds, world, px, py, px - k, py - k);
            jumpFlood(N, seeds, world, px, py, px,     py - k);
            jumpFlood(N, seeds, world, px, py, px + k, py - k);
            jumpFlood(N, seeds, world, px, py, px - k, py);
            jumpFlood(N, seeds, world, px, py, px,     py);
            jumpFlood(N, seeds, world, px, py, px + k, py);
            jumpFlood(N, seeds, world, px, py, px - k, py + k);
            jumpFlood(N, seeds, world, px, py, px,     py + k);
            jumpFlood(N, seeds, world, px, py, px + k, py + k);
        }
        k >>= 1;
    }
}

//---
// Perlin noise
//---

static vec2 perlinGradients[16];

GCONSTRUCTOR
static void precomputeGradients(void)
{
    for(int i = 0; i < 16; i++) {
        float alpha = 2 * 3.14159 * i / 16;
        perlinGradients[i].x = num(cosf(alpha));
        perlinGradients[i].y = num(sinf(alpha));
    }
}

static vec2 randomUnitVector(void)
{
    return perlinGradients[rand() % 16];
}

static num smooth(num t)
{
    return t * t * t * (t * (6 * t - num(15)) + num(10));
}

static num lerp(num x, num y, num t)
{
    return x + t * (y - x);
}

static num dot(vec2 *grid, int GRID_N, int ix, int iy, num fx, num fy)
{
    /* Wrap the grid around to get a torus effect, so the noise does not appear
       discontinuous when we repeat it during fractal sampling */
    vec2 g = grid[(iy % GRID_N) * GRID_N + (ix % GRID_N)];
    return (fx - num(ix)) * g.x + (fy - num(iy)) * g.y;
}

static int8_t *perlinNoise(int N, int PERLIN_CELL_SIZE)
{
    int8_t *noise = new int8_t[N * N];
    if(!noise)
        return nullptr;

    int GRID_N = N / PERLIN_CELL_SIZE;
    vec2 *grid = new vec2[GRID_N * GRID_N];
    if(!grid) {
        delete[] noise;
        return nullptr;
    }
    for(int i = 0; i < GRID_N * GRID_N; i++)
        grid[i] = randomUnitVector();

    for(int y = 0; y < N; y++)
    for(int x = 0; x < N; x++) {
        num fx = num(x) / PERLIN_CELL_SIZE;
        num fy = num(y) / PERLIN_CELL_SIZE;

        int ix = (int)fx;
        int iy = (int)fy;

        num d0 = dot(grid, GRID_N, ix, iy, fx, fy);
        num d1 = dot(grid, GRID_N, ix+1, iy, fx, fy);

        num d2 = dot(grid, GRID_N, ix, iy+1, fx, fy);
        num d3 = dot(grid, GRID_N, ix+1, iy+1, fx, fy);

        num rx = smooth(fx - num(ix));
        num ry = smooth(fy - num(iy));

        num v = lerp(lerp(d0, d1, rx), lerp(d2, d3, rx), ry);
        noise[y * N + x] = (int)(v * num(128));
    }

    delete[] grid;
    return noise;
}

static int8_t samplePerlin(int8_t *noise, int N, int x, int y, int levels)
{
    int8_t result = 0;

    for(int i = 0; i < levels; i++) {
        /* Add something depending on i to decorrelate octaves */
        int wy = ((y << i) + (17 * i + 5)) % N;
        int wx = ((x << i) + (13 * i + 1)) % N;
        int tmp = result + (noise[wy * N + wx] >> i);
        result = max(-128, min(tmp, 127));
    }

    return result;
}

#include <gint/display.h>
#include <gint/keyboard.h>
void perlinTest(int8_t *noise, int N)
{
/*    int8_t *noise;
    int N = 128;
    int PERLIN_CELL_SIZE = 16;

    noise = perlinNoise(N, PERLIN_CELL_SIZE);
    dclear(C_RED); */

    if(noise)
    for(int y = 0; y < N; y++)
    for(int x = 0; x < N; x++) {
        int v = samplePerlin(noise, N, x, y, 1);
        int gray = 16 + (v >> 3);
        dpixel(x, y, C_RGB(gray, gray, gray));
//        dpixel(x, y, (v >= -16 && v < 16) ? C_WHITE : C_BLACK);
    }

    dupdate();
    getkey();
}

//---
// World object API
//---

WorldCoord WorldCoord::Up(0, -1);
WorldCoord WorldCoord::Down(0, 1);
WorldCoord WorldCoord::Left(-1, 0);
WorldCoord WorldCoord::Right(1, 0);

bool World::validSpawn(int x, int y) const
{
    if(!this->limits.contains(WorldCoord(x, y)))
        return false;
    BlockInfo *info = Nooncraft::getBlockInfo(this->cellAt(x, y));
    return info && info->walkable;
}

WorldCoord World::findSpawnPoint()
{
    int max_dist_x = max(-this->limits.xmin, this->limits.xmax);
    int max_dist_y = max(-this->limits.ymin, this->limits.ymax);
    int max_dist = max(max_dist_x, max_dist_y);

    for(int d = 0; d <= max_dist; d++) {
        /* Look for blocks at distance `d` of (0,0) for somewhere spawnable */
        for(int x = -d; x <= d; x++) {
            if(this->validSpawn(x, -d))
                return WorldCoord(x, -d);
            if(this->validSpawn(x, +d))
                return WorldCoord(x, +d);
        }
        for(int y = -d; y <= d; y++) {
            if(this->validSpawn(-d, y))
                return WorldCoord(-d, y);
            if(this->validSpawn(+d, y))
                return WorldCoord(+d, y);
        }
    }

    return WorldCoord(0, 0);
}

BlockInfo *World::blockInfoAt(WorldCoord p) const
{
    if(!this->limits.contains(p))
        return nullptr;
    return Nooncraft::getBlockInfo(this->cellAt(p.x, p.y));
}

bool World::canBreakBlock(WorldCoord p) const
{
    BlockInfo *info = blockInfoAt(p);
    return info && info->breakability != Breakability::Fluid
                && info->breakability != Breakability::Unbreakable;
}

bool World::canPlaceAt(WorldCoord p) const
{
    BlockInfo *info = this->blockInfoAt(p);
    return info && info->replaceable;
}

namespace Nooncraft {

World *mkWorld(int width, int height)
{
    WorldRect l, br;

    World *w = (World *)malloc(sizeof *w);
    if(!w) goto fail;

    w->cells = (Block *)malloc(width * height * sizeof *w->cells);
    if(!w->cells) goto fail;

    l = WorldRect(
        -width  / 2, width  - 1 - width  / 2,
        -height / 2, height - 1 - height / 2);
    br = WorldRect(
        l.xmin - 1, l.xmax + 1,
        l.ymin - 1, l.ymax + 1);

    w->limits = l;
    w->worldBorder = br;
    return w;

fail:
    if(w)
        free(w->cells);
    free(w);
    return nullptr;
}

static vec2 biomeSort_caveDir;
static WorldCoord *biomeSort_biomeCenters;

static int biomeSort_compare(void const *b1, void const *b2)
{
    int seed1 = *(int const *)b1;
    int seed2 = *(int const *)b2;

    vec2 caveDir = biomeSort_caveDir;
    WorldCoord *biomeCenters = biomeSort_biomeCenters;

    /* Largest dot product with caveDir wins */
    num dot1 = caveDir.x * biomeCenters[seed1].x
             + caveDir.y * biomeCenters[seed1].y;
    num dot2 = caveDir.x * biomeCenters[seed2].x
             + caveDir.y * biomeCenters[seed2].y;
    return (dot1 - dot2).v;
}

static Biome randomNonCaveBiome(void)
{
    Biome options[3] = { Biome::Plains, Biome::Forest, Biome::Ocean };
    return options[rand() % 3];
}

static void generateCluster(World *w, int xt, int yt, Block b, int count)
{
    int x = xt + w->limits.xmin;
    int y = yt + w->limits.ymin;

    /* Very bruteforcey solution. We iterate over a square of size `2*radius`
       and generate an average of `count` blocks there. We want it relatively
       compact so we arrange it so that `4*radius^2 ≈ N*count` with N ≥ 1
       larger for small clusters. */
    int radius = count;
    int N = (count < 10) ? 4 : (count < 30) ? 2 : 1;
    while((4 / N) * radius * radius > count) radius--;

    int x0 = max(x - radius, w->limits.xmin);
    int x1 = min(x + radius - 1, w->limits.xmax);
    int y0 = max(y - radius, w->limits.ymin);
    int y1 = min(y + radius - 1, w->limits.ymax);

    for(int y = y0; y <= y1; y++)
    for(int x = x0; x <= x1; x++) {
        if(rand() % (4 * radius * radius) < count)
            w->cellAt(x, y) = b;
    }
}

static void generateTree(World *w, int xt, int yt)
{
    int x = xt + w->limits.xmin;
    int y = yt + w->limits.ymin;

    Block log = BlockID(OAK_LOG);
    Block leaves = BlockID(OAK_LEAVES);

    w->trySetCellAt(x - 1, y - 4, leaves);
    w->trySetCellAt(x, y - 4, leaves);
    w->trySetCellAt(x + 1, y - 4, leaves);

    w->trySetCellAt(x - 2, y - 3, leaves);
    w->trySetCellAt(x - 1, y - 3, leaves);
    w->trySetCellAt(x + 1, y - 3, leaves);
    w->trySetCellAt(x + 2, y - 3, leaves);

    w->trySetCellAt(x - 2, y - 2, leaves);
    w->trySetCellAt(x - 1, y - 2, leaves);
    w->trySetCellAt(x + 1, y - 2, leaves);
    w->trySetCellAt(x + 2, y - 2, leaves);

    w->trySetCellAt(x - 1, y - 1, leaves);
    w->trySetCellAt(x + 1, y - 1, leaves);

    w->trySetCellAt(x, y - 3, log);
    w->trySetCellAt(x, y - 2, log);
    w->trySetCellAt(x, y - 1, log);
    w->trySetCellAt(x, y, log);

    w->trySetCellAt(x - 1, y - 2, log);
    w->trySetCellAt(x + 1, y - 2, log);
}

void genWorld(World *w)
{
    int WIDTH = w->limits.width();
    int HEIGHT = w->limits.height();

    // --== Generate a Perlin noise map for various random things --==

    int PERLIN_N = 128;
    int PERLIN_CELL_SIZE = 16;
    int8_t *noise = perlinNoise(PERLIN_N, PERLIN_CELL_SIZE);

    // --== Generate biome diagram ==--

    int8_t *biomeMap = new int8_t[WIDTH * HEIGHT];
    if(!biomeMap)
        return;
    memset(biomeMap, 0xff, WIDTH * HEIGHT);

    /* Generate random biome centers */
    int BIOME_COUNT = 16;
    WorldCoord biomeCenters[BIOME_COUNT];
    for(int i = 0; i < BIOME_COUNT; i++) {
        biomeCenters[i] = WorldCoord(rand() % WIDTH, rand() % HEIGHT);
        biomeMap[WIDTH * biomeCenters[i].y + biomeCenters[i].x] = i;
    }

    /* This will no longer work if we change Block to be a 16-bit value */
    static_assert(sizeof(Block) == 1);
    voronoi(biomeMap, min(WIDTH, HEIGHT), biomeCenters);

    /* Move the biome boundaries to have irregular shapes */
    for(int y = 0; y < HEIGHT; y++)
    for(int x = 0; x < WIDTH; x++) {
        /* Shake biomes around by copying the value of a nearby cell, with
           distance on x/y given by some Perlin map. We reuse the same map */
        int8_t dx = samplePerlin(noise, PERLIN_N, x, y, 3);
        int8_t dy = samplePerlin(noise, PERLIN_N, PERLIN_N-x, PERLIN_N-y, 3);
        /* Restrict the displacement from ±128 to ±4 */
        dx >>= 5;
        dy >>= 5;

        WorldCoord neighbor(x+dx + w->limits.xmin, y+dy + w->limits.ymin);
        if(w->limits.contains(neighbor)) {
            biomeMap[y * WIDTH + x] = biomeMap[(y+dy) * WIDTH + (x+dx)];
        }
    }

    // --== Fill in the biome types ==--

    Biome biomeTypes[BIOME_COUNT];

    for(int i = 0; i < BIOME_COUNT; i++) {
        biomeTypes[i] = randomNonCaveBiome();
    }

    // --== Fill in some cave biomes ==--

    /* Select a random direction where cave biomes will be */
    vec2 caveDir = randomUnitVector();

    /* Sort biomes by distance to caveDir */
    int biomeSort[BIOME_COUNT];
    for(int i = 0; i < BIOME_COUNT; i++)
        biomeSort[i] = i;

    biomeSort_caveDir = caveDir;
    biomeSort_biomeCenters = biomeCenters;
    qsort(biomeSort, BIOME_COUNT, sizeof biomeSort[0], biomeSort_compare);

    /* The top 6 biomes in this direction become cave biomes */
    for(int i = BIOME_COUNT - 1; i >= BIOME_COUNT - 6; i--) {
        biomeTypes[biomeSort[i]] = Biome::Cave;
    }

    // --== Ensure a spawn point near plains ==--

    int zero_zero_ix = -w->limits.ymin * WIDTH - w->limits.xmin;
    biomeTypes[biomeMap[zero_zero_ix]] = Biome::Plains;

    // --== Generate biomes' base layer ==--

    for(int y = 0; y <= HEIGHT; y++)
    for(int x = 0; x <= WIDTH; x++) {
        int id = biomeMap[y * WIDTH + x];
        Biome type = biomeTypes[id];
        Block *cell = &w->cells[y * WIDTH + x];

        if(type == Biome::Plains) {
            /* Use the noise map to distinguish grass and dirt areas */
            int8_t v = samplePerlin(noise, PERLIN_N, x, y, 2);
            *cell = (v >= 0) ? BlockID(GRASS) : BlockID(DIRT);
        }
        else if(type == Biome::Forest) {
            /* Small regions of grass */
            int8_t v = samplePerlin(noise, PERLIN_N, x, y, 2);
            *cell = (v >= 64) ? BlockID(GRASS) : BlockID(DIRT);
        }
        else if(type == Biome::Ocean) {
            *cell = BlockID(WATER_SOURCE);
        }
        else if(type == Biome::Cave) {
            *cell = BlockID(STONE);
        }
        else *cell = 0xff;
    }

    // --== Generate clusters of sub-blocks ==--

    for(int i = 0; i < WIDTH * HEIGHT / 64; i++) {
        int x = rand() % WIDTH;
        int y = rand() % HEIGHT;
        Biome b = biomeTypes[biomeMap[y * WIDTH + x]];

        if(b == Biome::Plains) {
            if(rand() % 2 == 0)
                generateCluster(w, x, y, BlockID(FLOWERS), 5);
        }
        if(b == Biome::Forest) {
            if(rand() % 2 == 0)
                w->trySetCellAt(x, y, BlockID(OAK_LEAVES));
        }
        if(b == Biome::Cave) {
            int r = rand() % 12;
            if(r >= 0 && r <= 2)
                generateCluster(w, x, y, BlockID(COAL_ORE), 8);
            else if(r >= 3 && r <= 5)
                generateCluster(w, x, y, BlockID(IRON_ORE), 8);
            else if(r == 6)
                generateCluster(w, x, y, BlockID(GOLD_ORE), 6);
            else if(r == 7)
                generateCluster(w, x, y, BlockID(DIAMOND_ORE), 3);
        }
    }

    // --== Carve caves ==--

    for(int y = 0; y <= HEIGHT; y++)
    for(int x = 0; x <= WIDTH; x++) {
        Biome b = biomeTypes[biomeMap[y * WIDTH + x]];
        if(b == Biome::Cave) {
            int v = samplePerlin(noise, PERLIN_N, x, y, 1);
            if(v >= -16 && v < 16)
                w->cells[y * WIDTH + x] =
                    (rand() % 16 == 0) ? BlockID(COBBLESTONE) : BlockID(AIR);
        }
    }

    // --== Generate basic structures ==--

    for(int i = 0; i < WIDTH * HEIGHT / 100; i++) {
        int x = rand() % WIDTH;
        int y = rand() % HEIGHT;
        Biome b = biomeTypes[biomeMap[y * WIDTH + x]];

        if((b == Biome::Plains && rand() % 4 == 0) || b == Biome::Forest) {
            generateTree(w, x, y);
        }
    }

    // --== Clean up ==--

    delete[] biomeMap;
}

void freeWorld(World *w)
{
    free(w->cells);
    free(w);
}

} /* namespace Nooncraft */