Refactoring and basic map generation.

8 files changed, 246 insertions, 55 deletions

diff --git a/Makefile b/Makefile
index 8ceb27a..df63398 100644
--- a/Makefile
+++ b/Makefile
@@ -1,5 +1,5 @@
 CC ?= gcc
-CFLAGS += -g3 -O3 -Wall
+CFLAGS += -g3 -O3 -Wall -std=gnu++11
 CPPFLAGS += -MMD
 LDFLAGS += -lstdc++ -lm -lsfml-system -lsfml-window -lsfml-graphics
 
@@ -12,6 +12,7 @@ PP_RM := $(PP_BOLD)$(shell tput setf 4)RM$(PP_RESET)
 SRC := src/game.cpp \
        src/interface.cpp \
        src/main.cpp \
+       src/procgen.cpp \
        src/render.cpp \
        src/world.cpp
        
diff --git a/src/common.hpp b/src/common.hpp
index aaf1cad..2dd7c45 100644
--- a/src/common.hpp
+++ b/src/common.hpp
@@ -2,16 +2,37 @@
 #include <cstdint>
 #include <cmath>
 #include <map>
+#include <unordered_set>
 #include <SFML/Graphics.hpp>
 
-namespace game {
-	class entity_t {
-		virtual void render(sf::RenderWindow *window) = 0;
+namespace procgen {
+	class prng_t {
+		uint32_t state = 0;
+
+	public:
+		void seed(uint32_t seed);
+		uint32_t next(void);
+		float next_float(void);
+		void unit_vec(float out[2]);
+
+	};
+
+	class perlin_noise_t {
+		size_t size;
+		float (*table)[2] = nullptr;
+
+		float table_dot(size_t nx, size_t ny, float dx, float dy);
+
+	public:
+		~perlin_noise_t();
+
+		void generate(prng_t *prng, size_t size);
+		float get(float x, float y, float scale);
 	};
 }
 
 namespace world {
-	#define SECTOR_SIZE 16
+	#define SECTOR_SIZE 8
 
 	class tile_t {
 	public:
@@ -27,30 +48,59 @@ namespace world {
 		bool operator<(sector_index_t B) const;
 	};
 
+	class entity_t;
+
 	class sector_t {
-		std::vector<game::entity_t*> entities;
 	public:
+		sf::FloatRect bounds;
+		std::unordered_set<entity_t*> ents;
+
 		bool empty = true;
 		tile_t tiles[SECTOR_SIZE * SECTOR_SIZE];
-
-		void generate(sector_index_t index);
 	};
 
 	class world_t {
+		procgen::prng_t prng;
+		procgen::perlin_noise_t perlin;
 		std::map<sector_index_t, sector_t> sectors;
 
+		void generate(sector_t *sector, sector_index_t index);
+
 	public:
+		world_t(void);
 		sector_t *get_sector(sector_index_t index);
 		tile_t *get_tile(ssize_t x, ssize_t y);
 
-		void link(game::entity_t *entity);
-		void unlink(game::entity_t *entity);
 		void render(sf::RenderWindow *window);
 	};
+
+	class entity_t {
+		world_t *parent_world;
+		std::vector<sector_t*> parents;
+
+	public:
+		sf::Vector2f origin, size;
+
+		void link(world_t *world);
+		void unlink();
+	};
+}
+
+namespace game {
+	class state_t {
+		world::world_t world;
+
+	public:
+		void tick(void);
+		void render(sf::RenderWindow *window_);
+	};
 }
 
 namespace interface {
 	class state_t {
+		sf::RenderWindow *window;
+		game::state_t *game;
+
 		struct {
 			sf::Vector2f center;
 			int target_zoom = 3;
@@ -60,11 +110,49 @@ namespace interface {
 		} camera;
 
 	public:
-		sf::RenderWindow *window;
-		world::world_t *world;
-
-		state_t(sf::RenderWindow *window_, world::world_t *world_);
+		state_t(sf::RenderWindow *window_, game::state_t *game);
 		void tick(void);
 		void render(void);
 	};
 }
+
+// Divide and round to minus infinity.
+template <typename T>
+T divide_rmi(T x, T y, T *rem)
+{
+	T rv;
+
+	if (x >= 0) {
+		*rem = x % y;
+		return x / y;
+	}
+
+	rv = (x + 1) / y - 1;
+	*rem = x - rv * y;
+	return rv;
+}
+
+// Modulo operation. y is expected to be positive.
+template <typename T>
+T mod(T x, T y)
+{
+	return (x % y) + (x < 0 ? y : 0);
+}
+
+// Linear interpolation.
+template <typename T>
+T lerp(T a, T b, T x)
+{
+	return a * (1 - x) + b * x;
+}
+
+// Bilinear interpolation.
+template <typename T>
+T bilerp(T a, T b, T c, T d, T x, T y)
+{
+	T ab, cd;
+
+	ab = lerp(a, b, x);
+	cd = lerp(c, d, x);
+	return lerp(ab, cd, y);
+}
diff --git a/src/game.cpp b/src/game.cpp
index 9ce0a82..05b0139 100644
--- a/src/game.cpp
+++ b/src/game.cpp
@@ -2,6 +2,12 @@
 
 namespace game {
 
+class entity_t : world::entity_t {
+	virtual void render(sf::RenderWindow *window) = 0;
+};
 
+void state_t::tick(void)
+{
+}
 
 } //namespace game
diff --git a/src/interface.cpp b/src/interface.cpp
index aacc4b0..16fc77d 100644
--- a/src/interface.cpp
+++ b/src/interface.cpp
@@ -2,10 +2,10 @@
 
 namespace interface {
 
-state_t::state_t(sf::RenderWindow *window_, world::world_t *world_)
+state_t::state_t(sf::RenderWindow *window_, game::state_t *game_)
 {
 	window = window_;
-	world = world_;
+	game = game_;
 }
 
 static sf::Vector2f compute_drag(sf::RenderWindow *window, sf::Vector2f drag_ref)
@@ -48,12 +48,6 @@ void state_t::tick(void)
 			return;
 
 		case sf::Event::MouseButtonPressed:
-			if (event.mouseButton.button == 0) {
-				sf::Vector2f vmouse = window->mapPixelToCoords(
-				                      sf::Vector2i(event.mouseButton.x,
-				                      event.mouseButton.y));
-				world->get_tile(vmouse.x, vmouse.y)->type = 0;
-			}
 			if (event.mouseButton.button == 1) {
 				camera.dragging = true;
 				camera.drag_ref = window->mapPixelToCoords(
diff --git a/src/main.cpp b/src/main.cpp
index 1f69582..d1afc2f 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -2,19 +2,20 @@
 
 int main()
 {
-	sf::RenderWindow window(sf::VideoMode(800, 600), "SFML");
-	world::world_t world;
-	interface::state_t interface(&window, &world);
+	sf::RenderWindow window(sf::VideoMode(800, 600), "Minitrem");
+	game::state_t game;
+	interface::state_t interface(&window, &game);
 
 	window.setVerticalSyncEnabled(true);
 
 	while (1) {
+		game.tick();
 		interface.tick();
 		if (!window.isOpen())
 			break;
 		 
 		window.clear();
-		world.render(&window);
+		game.render(&window);
 		interface.render();
 		window.display();
 	}
diff --git a/src/procgen.cpp b/src/procgen.cpp
new file mode 100644
index 0000000..09ccae5
--- /dev/null
+++ b/src/procgen.cpp
@@ -0,0 +1,87 @@
+#include "common.hpp"
+#include <cmath>
+
+namespace procgen {
+
+void prng_t::seed(uint32_t seed)
+{
+	state = seed;
+	next();
+	next();
+}
+
+uint32_t prng_t::next(void)
+{
+	// glibc's LCG parameters (with m = 2^32 - 1).
+	state *= 1103515245;
+	state += 12345;
+	return state;
+}
+
+float prng_t::next_float(void)
+{
+	return (float)next() / 4294967295.0f;
+}
+
+void prng_t::unit_vec(float out[2])
+{
+	float t;
+
+	t = next_float() * 2.0f * M_PI;
+	out[0] = cos(t);
+	out[1] = sin(t);
+}
+
+void perlin_noise_t::generate(prng_t *prng, size_t size_)
+{
+	if (table)
+		delete table;
+
+	size = size_;
+	table = new float[size * size][2];
+
+	for (size_t y = 0; y < size; y++)
+	for (size_t x = 0; x < size; x++)
+		prng->unit_vec(table[y * size + x]);
+}
+
+float perlin_noise_t::table_dot(size_t nx, size_t ny, float dx, float dy)
+{
+	return table[ny * size + nx][0] * dx + table[ny * size + nx][1] * dy;
+}
+
+static float smooth_step(float x)
+{
+	return 3 * x * x - 2 * x * x * x;
+}
+
+float perlin_noise_t::get(float x, float y, float scale)
+{
+	size_t nx, ny, nx1, ny1;
+	float s, t, a, b, c, d;
+
+	x /= scale;
+	y /= scale;
+
+	nx = mod<ssize_t>(floor(x), size);
+	ny = mod<ssize_t>(floor(y), size);
+	nx1 = (nx == size - 1 ? 0 : nx + 1);
+	ny1 = (ny == size - 1 ? 0 : ny + 1);
+
+	s = smooth_step(x - floor(x));
+	t = smooth_step(y - floor(y));
+
+	a = table_dot(nx,  ny,  -s,        -t);
+	b = table_dot(nx1, ny,  -s + 1.0f, -t);
+	c = table_dot(nx,  ny1, -s,        -t + 1.0f);
+	d = table_dot(nx1, ny1, -s + 1.0f, -t + 1.0f);
+
+	return bilerp(a, b, c, d, s, t);
+}
+
+perlin_noise_t::~perlin_noise_t()
+{
+	delete table;
+}
+
+} // namespace procgen
diff --git a/src/render.cpp b/src/render.cpp
index 218dff0..05785ae 100644
--- a/src/render.cpp
+++ b/src/render.cpp
@@ -7,7 +7,7 @@ static void draw_tile(sf::RenderWindow *window, float x, float y,
 {
 	wot_rect.setSize(sf::Vector2f(1.0f, 1.0f));
 	wot_rect.setPosition(sf::Vector2f(x, y));
-	wot_rect.setFillColor(sf::Color(tile->type, 255 - tile->type, tile->type + 128));
+	wot_rect.setFillColor(sf::Color(tile->type, tile->type, tile->type));
 	wot_rect.setOutlineColor(sf::Color::Transparent);
 	window->draw(wot_rect);
 }
@@ -28,14 +28,14 @@ static void draw_sector(sf::RenderWindow *window, world::world_t *world,
 	}
 
 	wot_rect.setSize(sf::Vector2f(SECTOR_SIZE, SECTOR_SIZE));
-	wot_rect.setPosition(sf::Vector2f(index.x * 16, index.y * 16));
+	wot_rect.setPosition(sf::Vector2f(index.x * SECTOR_SIZE, index.y * SECTOR_SIZE));
 	wot_rect.setOutlineColor(sf::Color::Yellow);
 	wot_rect.setOutlineThickness(0.06f);
 	wot_rect.setFillColor(sf::Color::Transparent);
 	window->draw(wot_rect);
 }
 
-void world::world_t::render(sf::RenderWindow *window)
+void game::state_t::render(sf::RenderWindow *window)
 {
 	sf::Vector2u size = window->getSize();
 	sf::Vector2f A, B, C, D;
@@ -59,7 +59,7 @@ void world::world_t::render(sf::RenderWindow *window)
 
 	for (ssize_t y = index_box.top; y < index_box.height; y++)
 	for (ssize_t x = index_box.left; x < index_box.width; x++)
-		draw_sector(window, this, world::sector_index_t(x, y));
+		draw_sector(window, &world, world::sector_index_t(x, y));
 }
 
 void interface::state_t::render()
diff --git a/src/world.cpp b/src/world.cpp
index b5aeea2..dc25f66 100644
--- a/src/world.cpp
+++ b/src/world.cpp
@@ -23,21 +23,39 @@ bool sector_index_t::operator<(sector_index_t B) const
 	return false;
 }
 
-void sector_t::generate(sector_index_t index)
+world_t::world_t(void)
 {
+	prng.seed(124);
+	perlin.generate(&prng, 32);
+}
+
+void world_t::generate(sector_t *sector, sector_index_t index)
+{
+	sector->bounds.left = index.x * SECTOR_SIZE;
+	sector->bounds.top = index.y * SECTOR_SIZE;
+	sector->bounds.width = SECTOR_SIZE;
+	sector->bounds.height = SECTOR_SIZE;
+	
 	std::cout << "generating (" << index.x << ", " << index.y << ")\n";
 
 	for (ssize_t ly = 0; ly < SECTOR_SIZE; ly++)
 	for (ssize_t lx = 0; lx < SECTOR_SIZE; lx++) {
 		ssize_t x, y;
+		float noise;
 
 		x = index.x * SECTOR_SIZE + lx;
 		y = index.y * SECTOR_SIZE + ly;
 
-		tiles[ly * SECTOR_SIZE + lx].type = (x ^ y) * 151;
+		noise = perlin.get(x, y, 30.0f) * 0.6f +
+		        perlin.get(x, y, 15.0f) * 0.25f +
+		        perlin.get(x, y, 7.0f) * 0.1f +
+		        perlin.get(x, y, 3.0f) * 0.05f;
+
+		sector->tiles[ly * SECTOR_SIZE + lx].type =
+		(noise + 1) * 100;
 	}
 
-	empty = false;
+	sector->empty = false;
 }
 
 sector_t *world_t::get_sector(sector_index_t index)
@@ -47,40 +65,36 @@ sector_t *world_t::get_sector(sector_index_t index)
 	sector = &sectors[index];
 
 	if (sector->empty)
-		sector->generate(index);
+		generate(sector, index);
 
 	return sector;
 }
 
-// divide and round to minus infinity
-static ssize_t divide_rmi(ssize_t x, ssize_t y, size_t *rem)
-{
-	ssize_t rv;
-
-	if (x >= 0) {
-		*rem = x % y;
-		return x / y;
-	}
-
-	rv = (x + 1) / y - 1;
-	*rem = x - rv * y;
-	return rv;
-}
-
 tile_t *world_t::get_tile(ssize_t x, ssize_t y)
 {
 	sector_index_t index;
 	sector_t *sector;
-	size_t tx, ty;
+	ssize_t tx, ty;
 
-	index.x = divide_rmi(x, SECTOR_SIZE, &tx);
-	index.y = divide_rmi(y, SECTOR_SIZE, &ty);
-	printf("get_tile(%zd, %zd)\n", x, y);
-	printf("\tsector is (%zd, %zd)\n", index.x, index.y);
+	index.x = divide_rmi(x, (ssize_t)SECTOR_SIZE, &tx);
+	index.y = divide_rmi(y, (ssize_t)SECTOR_SIZE, &ty);
 	sector = get_sector(index);
 
-	printf("\ttile is (%zd, %zd)\n", tx, ty);
 	return sector->tiles + ty * SECTOR_SIZE + tx;
 }
 
+void entity_t::link(world_t *world)
+{
+	// TODO
+}
+
+void entity_t::unlink(void)
+{
+	for (sector_t *sector : parents)
+		sector->ents.erase(sector->ents.find(this));
+
+	parents.clear();
+	parent_world = nullptr;
 }
+
+} // namespace world