521 lines
14 KiB
C++
521 lines
14 KiB
C++
#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 */
|