Tracing rays through the world.

5 files changed, 142 insertions, 7 deletions

diff --git a/src/common.hpp b/src/common.hpp
index 81d79e3..259c458 100644
--- a/src/common.hpp
+++ b/src/common.hpp
@@ -88,6 +88,12 @@ namespace world {
 		rectf_t bounds;
 	} cmodel_t;
 
+	typedef struct {
+		bool hit;
+		v2f_t end;
+		float frac;
+	} trace_t;
+
 	class world_t {
 		procgen::prng_t prng;
 		procgen::perlin_noise_t perlin;
@@ -113,6 +119,7 @@ namespace world {
 		std::list<entity_t*> get_render_entities(rectf_t rect);
 
 		bool test_rect(const cmodel_t *cmodel, const entity_t *ignore);
+		trace_t trace(v2f_t start, v2f_t end, cflags_t cflags);
 
 		void debug_point(sf::Vector2f point);
 	};
@@ -276,11 +283,14 @@ namespace render {
 
 		void render_text(v2f_t x, float height, const wchar_t *wstr, text_align_t align, sf::Color color);
 		void render_hlrect(rectf_t rect, sf::Color color);
+		void render_arrow(v2f_t x0, v2f_t x1, sf::Color color);
 
 		void debug_path(std::list<v2f_t> *path);
 	};
 }
 
+extern render::state_t *debug_render;
+
 namespace assets {
 	typedef struct {
 		render::oriented_sprite_4M_t head_idle, body_idle;
diff --git a/src/game.cpp b/src/game.cpp
index 8daa7d0..fd119f8 100644
--- a/src/game.cpp
+++ b/src/game.cpp
@@ -9,6 +9,7 @@ enum {
 };
 
 class unit_t : public world::entity_t {
+protected:
 	world::world_t *world;
 
 	world::cmodel_t make_cmodel(v2f_t at)
@@ -182,6 +183,19 @@ public:
 		render->render(&assets::human.body_idle, render_bounds, move.angle);
 		render->render(&assets::human.head_idle, render_bounds, move.angle);
 
+		{
+			v2f_t x1;
+			static float t = 0;
+			world::trace_t trace;
+
+			t += 0.02f;
+
+			x1[0] = x[0] + cos(t) * 5;
+			x1[1] = x[1] + sin(t) * 5;
+			trace = world->trace(x, x1, 1);
+			render->render_arrow(x, trace.end, sf::Color::Green);
+		}
+
 		if (move.moving && debug_draw_paths)
 			render->debug_path(&move.path);
 
@@ -200,13 +214,11 @@ public:
 
 void state_t::start(void)
 {
-	for (size_t i = 0; i < 10; i++) {
-		human_t *human;
+	human_t *human;
 
-		human = new human_t;
-		human->place(&world, v2f_t(0.5, 0.5) + i * v2f_t(0.2, -1.2f));
-		units.insert(human);
-	}
+	human = new human_t;
+	human->place(&world, v2f_t(0.5, 0.5));
+	units.insert(human);
 }
 
 void state_t::stop(void)
diff --git a/src/main.cpp b/src/main.cpp
index f6a2de5..f4b1105 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -4,6 +4,7 @@
 bool debug_draw_cmodels = false;
 bool debug_draw_paths = false;
 bool debug_draw_tile_coords = false;
+render::state_t *debug_render;
 
 uint64_t nano_clock(void)
 {
@@ -23,7 +24,8 @@ int main()
 	size_t frame = 0;
 	double before = NAN;
 
-	window.setVerticalSyncEnabled(false);
+	debug_render = &render;
+	window.setVerticalSyncEnabled(true);
 
 	text::load_strings("pl");
 	assets::load();
diff --git a/src/render.cpp b/src/render.cpp
index 943ffcf..7e90190 100644
--- a/src/render.cpp
+++ b/src/render.cpp
@@ -222,6 +222,16 @@ void state_t::render_hlrect(rectf_t rect, sf::Color color)
 	wot_rect.setOutlineColor(sf::Color::Transparent);
 }
 
+void state_t::render_arrow(v2f_t x0, v2f_t x1, sf::Color color)
+{
+	sf::Vertex line[2] = {
+		sf::Vertex(x0, color),
+		sf::Vertex(x1, color)
+	};
+
+	window->draw(line, 2, sf::Lines);
+}
+
 void state_t::debug_path(std::list<v2f_t> *path)
 {
 	bool first = true;
diff --git a/src/world.cpp b/src/world.cpp
index 3d21789..dc35f46 100644
--- a/src/world.cpp
+++ b/src/world.cpp
@@ -277,6 +277,107 @@ bool world_t::test_rect(const cmodel_t *cmodel, const entity_t *ignore)
 	return false;
 }
 
+static const v2f_t transforms[4] = {
+	{+1, +1}, {-1, +1}, {-1, -1}, {+1, -1}
+};
+
+static const tile_index_t transforms_index[4] = {
+	{+1, +1}, {-1, +1}, {-1, -1}, {+1, -1}
+};
+
+static const tile_index_t offsets_index[4] = {
+	{0, 0}, {-1, 0}, {-1, -1}, {0, -1}
+};
+
+static inline size_t quadrant(v2f_t dx)
+{
+	if (dx[0] == 0.0f && dx[1] == 0.0f)
+		return 4;
+
+	if (dx[1] >= 0.0f) {
+		if (dx[0] >= 0.0f)
+			return 0;
+		else
+			return 1;
+	} else {
+		if (dx[0] >= 0.0f)
+			return 3;
+		else
+			return 2;
+	}
+}
+
+trace_t world_t::trace(v2f_t start, v2f_t end, cflags_t cflags)
+{
+	v2f_t x, dx;
+	size_t quad;
+	trace_t res;
+
+	dx = end - start;
+
+	quad = quadrant(dx);
+	if (quad == 4) {
+		res.hit = false;
+		res.end = end;
+		res.frac = 1.0f;
+		return res;
+	}
+
+	start ^= transforms[quad];
+	dx ^= transforms[quad];
+	end ^= transforms[quad];
+
+	x = start;
+
+	while (1) {
+		v2f_t mod, P;
+		tile_index_t index;
+
+		if (x[0] >= end[0] && x[1] >= end[1]) {
+			res.hit = false;
+			res.end = end ^ transforms[quad];
+			res.frac = 1.0f;
+			return res;
+		}
+
+		index = (tile_index_t(x.floor()) ^ transforms_index[quad]) +
+		        offsets_index[quad];
+		//rectf_t tile(index, (v2f_t)index + v2f_t(1, 1));
+
+		if (get_tile(index, false)->type > cflags) { // FIXME
+			//debug_render->render_hlrect(tile, sf::Color::Red);
+			res.hit = true;
+			res.end = x ^ transforms[quad];
+			res.frac = (x - start).len() / (end - start).len();
+			return res;
+		}
+
+		mod = x - x.floor();
+		//debug_render->render_hlrect(tile, sf::Color::Green);
+
+		// Project onto x = const.
+		P[0] = 1.0f - mod[0];
+		P[1] = P[0] / dx[0] * dx[1];
+		if (mod[1] + P[1] >= 0.0f && mod[1] + P[1] <= 1.0f)
+		{
+			x += P;
+			x[0] = std::round(x[0]);
+			continue;
+		}
+
+		// Project onto y = const.
+		P[1] = 1.0f - mod[1];
+		P[0] = P[1] / dx[1] * dx[0];
+		x += P;
+		x[1] = std::round(x[1]);
+	}
+}
+
+trace_t trace_cmodel(v2f_t start, v2f_t end, const cmodel_t *cmodel)
+{
+	// TODO
+}
+
 void world_t::debug_point(sf::Vector2f point)
 {
 	sector_index_t index = sector_index_at(point);