aboutsummaryrefslogtreecommitdiffstats
path: root/src/game/build_graph.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/game/build_graph.cpp')
-rw-r--r--src/game/build_graph.cpp487
1 files changed, 487 insertions, 0 deletions
diff --git a/src/game/build_graph.cpp b/src/game/build_graph.cpp
new file mode 100644
index 0000000..032bbf5
--- /dev/null
+++ b/src/game/build_graph.cpp
@@ -0,0 +1,487 @@
+#include "game/build_graph.hpp"
+#include <cmath>
+#include <cstdio>
+#include <algorithm>
+
+namespace {
+constexpr float PI = 3.14159265358979323846f;
+uint64_t edge_key(int a, int b) {
+ if (a > b) std::swap(a, b);
+ return (uint64_t)(uint32_t)a << 32 | (uint32_t)b;
+}
+float wrap_angle(float d) {
+ while (d > PI) d -= 2.0f * PI;
+ while (d < -PI) d += 2.0f * PI;
+ return d;
+}
+}
+
+// =============================================================================
+// Construction
+// =============================================================================
+
+int BuildGraph::add_node(float x, float y, bool foundation) {
+ nodes.push_back({x, y, 0.0f, 0.0f, MIN_NODE_MASS, foundation});
+ return (int)nodes.size() - 1;
+}
+
+int BuildGraph::add_edge(int na, int nb, int mat) {
+ if (na < 0 || na >= (int)nodes.size()) return -1;
+ if (nb < 0 || nb >= (int)nodes.size()) return -1;
+ if (na == nb || edge_exists(na, nb)) return -1;
+ if (materials.empty()) return -1;
+ if (mat < 0 || mat >= (int)materials.size()) mat = 0;
+
+ const BuildNode& A = nodes[na];
+ const BuildNode& B = nodes[nb];
+ float dx = B.x - A.x, dy = B.y - A.y;
+ const MaterialDef& m = materials[mat];
+
+ BuildEdge e{};
+ e.node_a = na;
+ e.node_b = nb;
+ e.mat = mat;
+ e.rest_length = std::sqrt(dx*dx + dy*dy);
+ e.rest_angle = std::atan2(dy, dx);
+ e.stress = 0.0f;
+ e.hp = e.max_hp = m.hit_points;
+ e.burning = false;
+ e.burn = 0.0f;
+ e.settle = m.tension_only ? 0.0f : SETTLE_TIME; // ropes are floppy by nature
+ e.half_width = m.half_width;
+ e.r = m.r; e.g = m.g; e.b = m.b; e.a = m.a;
+ edges.push_back(e);
+
+ rebuild_topology();
+ return (int)edges.size() - 1;
+}
+
+int BuildGraph::add_link(int na, int nb, int mat) {
+ if (na < 0 || na >= (int)nodes.size()) return 0;
+ if (nb < 0 || nb >= (int)nodes.size()) return 0;
+ if (na == nb || materials.empty()) return 0;
+ if (mat < 0 || mat >= (int)materials.size()) mat = 0;
+ const MaterialDef& m = materials[mat];
+
+ float ax = nodes[na].x, ay = nodes[na].y;
+ float bx = nodes[nb].x, by = nodes[nb].y;
+ float dist = std::hypot(bx - ax, by - ay);
+ if (dist < m.min_length || dist > m.max_link_length) return 0;
+
+ int segs = (m.max_length > 0.0f) ? (int)std::ceil(dist / m.max_length) : 1;
+ if (segs < 1) segs = 1;
+ if (segs == 1) return add_edge(na, nb, mat) >= 0 ? 1 : 0;
+
+ // Subdivide into a chain of intermediate nodes so no segment exceeds max_length.
+ int created = 0, prev = na;
+ for (int i = 1; i < segs; i++) {
+ float t = (float)i / segs;
+ float px = ax + (bx - ax) * t, py = ay + (by - ay) * t;
+ int mid = add_node(px, py, is_on_ground(py));
+ if (add_edge(prev, mid, mat) >= 0) created++;
+ prev = mid;
+ }
+ if (add_edge(prev, nb, mat) >= 0) created++;
+ return created;
+}
+
+void BuildGraph::extrude_edge(int edge_id, float off_x, float off_y) {
+ if (edge_id < 0 || edge_id >= (int)edges.size()) return;
+
+ int mat0 = edges[edge_id].mat;
+ if (mat0 >= 0 && mat0 < (int)materials.size()) {
+ // Keep box sides single (braceable) edges: clamp the drag to max_length.
+ float ol = std::sqrt(off_x*off_x + off_y*off_y);
+ float maxlen = materials[mat0].max_length;
+ if (ol > maxlen && ol > 1e-6f) { off_x *= maxlen / ol; off_y *= maxlen / ol; }
+ }
+ if (std::sqrt(off_x*off_x + off_y*off_y) < 0.1f) return;
+
+ const BuildEdge e = edges[edge_id]; // snapshot before vectors move
+ const int ea = e.node_a, eb = e.node_b, mat = e.mat;
+ const float ax = nodes[ea].x, ay = nodes[ea].y;
+ const float bx = nodes[eb].x, by = nodes[eb].y;
+
+ float cx = ax + off_x, cy = ay + off_y; // slanted parallelogram is fine
+ float dx = bx + off_x, dy = by + off_y;
+
+ // Node merging: reuse a nearby existing node so the box grafts into the graph.
+ int nc = find_nearest_node(cx, cy, SNAP_RADIUS);
+ if (nc < 0 || nc == ea || nc == eb) nc = add_node(cx, cy, is_on_ground(cy));
+ int nd = find_nearest_node(dx, dy, SNAP_RADIUS);
+ if (nd < 0 || nd == ea || nd == eb || nd == nc) nd = add_node(dx, dy, is_on_ground(dy));
+
+ add_edge(nc, nd, mat); // three new sides (original edge is the fourth)
+ add_edge(ea, nc, mat);
+ add_edge(eb, nd, mat);
+
+ // Auto diagonal brace (longer diagonal) so the box is rigid on creation.
+ if (!materials[mat].tension_only) {
+ float l1 = std::hypot(nodes[nd].x - nodes[ea].x, nodes[nd].y - nodes[ea].y);
+ float l2 = std::hypot(nodes[nc].x - nodes[eb].x, nodes[nc].y - nodes[eb].y);
+ if (l1 >= l2) { if (l1 >= MIN_BRACE_LENGTH) add_edge(ea, nd, mat); }
+ else { if (l2 >= MIN_BRACE_LENGTH) add_edge(eb, nc, mat); }
+ }
+}
+
+// =============================================================================
+// Topology — adjacency, edge lookup, faces, triangulation, node mass O(E.deg)
+// =============================================================================
+
+void BuildGraph::rebuild_topology() {
+ adj_.assign(nodes.size(), {});
+ edge_set_.clear();
+ for (int ei = 0; ei < (int)edges.size(); ei++) {
+ const auto& e = edges[ei];
+ adj_[e.node_a].push_back({e.node_b, ei});
+ adj_[e.node_b].push_back({e.node_a, ei});
+ edge_set_.insert(edge_key(e.node_a, e.node_b));
+ }
+
+ // Faces + per-edge triangulated flag (common neighbour of both endpoints).
+ faces.clear();
+ for (auto& e : edges) {
+ int a = std::min(e.node_a, e.node_b);
+ int b = std::max(e.node_a, e.node_b);
+ bool tri = false;
+ for (auto [c, _] : adj_[a]) {
+ if (c == b) continue;
+ if (edge_set_.count(edge_key(b, c))) {
+ tri = true;
+ if (c > b) faces.push_back({a, b, c}); // emit each triangle once
+ }
+ }
+ e.triangulated = tri;
+ }
+
+ // Node mass = half of each incident strut's mass, floored.
+ for (auto& n : nodes) n.mass = 0.0f;
+ for (const auto& e : edges) {
+ float half = materials[e.mat].mass * 0.5f;
+ nodes[e.node_a].mass += half;
+ nodes[e.node_b].mass += half;
+ }
+ for (auto& n : nodes) if (n.mass < MIN_NODE_MASS) n.mass = MIN_NODE_MASS;
+}
+
+bool BuildGraph::edge_exists(int a, int b) const {
+ return edge_set_.count(edge_key(a, b)) != 0;
+}
+
+// =============================================================================
+// Simulation — stiff damped mass-spring, integrated with oversampling
+// =============================================================================
+
+void BuildGraph::step(float dt) {
+ const int n = (int)nodes.size();
+ const float h = dt / OVERSAMPLES;
+ float dampf = 1.0f - air_drag * h;
+ if (dampf < 0.0f) dampf = 0.0f;
+
+ // Fresh struts are held rigid during their build grace: freeze their nodes.
+ held_.assign(n, 0);
+ for (const auto& e : edges) {
+ if (e.settle <= 0.0f) continue;
+ if (!nodes[e.node_a].is_foundation) held_[e.node_a] = 1;
+ if (!nodes[e.node_b].is_foundation) held_[e.node_b] = 1;
+ }
+
+ for (int s = 0; s < OVERSAMPLES; s++) {
+ fx_.assign(n, 0.0f);
+ fy_.assign(n, 0.0f);
+
+ // gravity (held/pinned nodes don't move, so skip)
+ for (int i = 0; i < n; i++)
+ if (!nodes[i].is_foundation && !held_[i])
+ fy_[i] = -gravity * nodes[i].mass;
+
+ // spring forces: F = k*stretch + c*(relative velocity along axis)
+ for (const auto& e : edges) {
+ BuildNode& A = nodes[e.node_a];
+ BuildNode& B = nodes[e.node_b];
+ float dx = B.x - A.x, dy = B.y - A.y;
+ float dist = std::sqrt(dx*dx + dy*dy);
+ if (dist < 1e-6f) continue;
+ float nx = dx / dist, ny = dy / dist;
+ float stretch = dist - e.rest_length;
+ const MaterialDef& m = materials[e.mat];
+ if (m.tension_only && stretch < 0.0f) continue; // rope slack
+
+ float relv = (B.vx - A.vx) * nx + (B.vy - A.vy) * ny;
+ float f = m.stiffness * stretch + m.damping * relv;
+ fx_[e.node_a] += f * nx; fy_[e.node_a] += f * ny;
+ fx_[e.node_b] -= f * nx; fy_[e.node_b] -= f * ny;
+ }
+
+ // semi-implicit Euler integration
+ for (int i = 0; i < n; i++) {
+ BuildNode& p = nodes[i];
+ if (p.is_foundation || held_[i]) { p.vx = p.vy = 0.0f; continue; }
+ p.vx = (p.vx + fx_[i] / p.mass * h) * dampf;
+ p.vy = (p.vy + fy_[i] / p.mass * h) * dampf;
+ p.x += p.vx * h;
+ p.y += p.vy * h;
+ }
+ }
+
+ // Record signed axial deformation for stress colouring.
+ for (auto& e : edges) {
+ float dx = nodes[e.node_b].x - nodes[e.node_a].x;
+ float dy = nodes[e.node_b].y - nodes[e.node_a].y;
+ float dist = std::sqrt(dx*dx + dy*dy);
+ e.stress = (e.rest_length > 1e-6f) ? (dist - e.rest_length) / e.rest_length : 0.0f;
+ }
+}
+
+int BuildGraph::check_strain() {
+ std::vector<int> brk;
+ for (int ei = 0; ei < (int)edges.size(); ei++) {
+ const BuildEdge& e = edges[ei];
+ const MaterialDef& m = materials[e.mat];
+ const BuildNode& A = nodes[e.node_a];
+ const BuildNode& B = nodes[e.node_b];
+ float dx = B.x - A.x, dy = B.y - A.y;
+ float dist = std::sqrt(dx*dx + dy*dy);
+ float ratio = (e.rest_length > 1e-6f) ? dist / e.rest_length : 1.0f;
+
+ bool fail = false;
+ if (m.tension_only) {
+ fail = ratio > m.max_expansion; // rope: over-stretch only
+ } else {
+ fail = ratio < m.max_compression || ratio > m.max_expansion;
+ // Angle stress: a loose (un-triangulated) strut past its grace snaps
+ // once it rotates too far from the angle it was built at.
+ if (!fail && !e.triangulated && e.settle <= 0.0f) {
+ float dev = std::fabs(wrap_angle(std::atan2(dy, dx) - e.rest_angle));
+ if (dev > m.angle_threshold) fail = true;
+ }
+ }
+ if (fail) brk.push_back(ei);
+ }
+ if (brk.empty()) return 0;
+
+ for (auto it = brk.rbegin(); it != brk.rend(); ++it) // descending: indices stay valid
+ edges.erase(edges.begin() + *it);
+ rebuild_topology();
+ printf("Build: %zu strut(s) snapped\n", brk.size());
+ return (int)brk.size();
+}
+
+void BuildGraph::update_timers(float dt) {
+ for (auto& e : edges)
+ if (e.settle > 0.0f)
+ e.settle = e.triangulated ? 0.0f : std::max(0.0f, e.settle - dt);
+}
+
+int BuildGraph::kill_grounded() {
+ int killed = 0;
+ for (;;) {
+ int hit = -1;
+ for (int i = 0; i < (int)nodes.size(); i++)
+ if (!nodes[i].is_foundation && nodes[i].y < ground_level) { hit = i; break; }
+ if (hit < 0) break;
+ destroyed_events.push_back({nodes[hit].x, nodes[hit].y});
+ break_node(hit);
+ killed++;
+ }
+ return killed;
+}
+
+// =============================================================================
+// Destruction
+// =============================================================================
+
+void BuildGraph::apply_splash(float x, float y, float radius, float damage,
+ float knockback) {
+ if (radius <= 0.0f) return;
+
+ // Knockback: shove nearby free nodes away from the blast (linear falloff).
+ for (auto& n : nodes) {
+ if (n.is_foundation) continue;
+ float dx = n.x - x, dy = n.y - y;
+ float d = std::sqrt(dx*dx + dy*dy);
+ if (d >= radius) continue;
+ float f = 1.0f - d / radius;
+ if (d > 1e-4f) { n.vx += (dx/d) * knockback * f; n.vy += (dy/d) * knockback * f; }
+ }
+
+ // Damage struts by their midpoint distance; collect those that hit 0 HP.
+ std::vector<int> brk;
+ for (int ei = 0; ei < (int)edges.size(); ei++) {
+ auto& e = edges[ei];
+ float mx = (nodes[e.node_a].x + nodes[e.node_b].x) * 0.5f;
+ float my = (nodes[e.node_a].y + nodes[e.node_b].y) * 0.5f;
+ float d = std::sqrt((mx-x)*(mx-x) + (my-y)*(my-y));
+ if (d >= radius) continue;
+ e.hp -= damage * (1.0f - d / radius);
+ if (e.hp <= 0.0f) brk.push_back(ei);
+ }
+ if (brk.empty()) return;
+ for (auto it = brk.rbegin(); it != brk.rend(); ++it)
+ edges.erase(edges.begin() + *it);
+ rebuild_topology();
+}
+
+int BuildGraph::find_blocking_edge(float x, float y, float radius) const {
+ int best = -1; float best_d = radius;
+ for (int i = 0; i < (int)edges.size(); i++) {
+ if (!materials[edges[i].mat].blocks_projectiles) continue;
+ const BuildNode& A = nodes[edges[i].node_a];
+ const BuildNode& B = nodes[edges[i].node_b];
+ float ex = B.x - A.x, ey = B.y - A.y;
+ float len2 = ex*ex + ey*ey;
+ if (len2 < 1e-6f) continue;
+ float t = std::clamp(((x-A.x)*ex + (y-A.y)*ey) / len2, 0.0f, 1.0f);
+ float d = std::hypot(x - (A.x + t*ex), y - (A.y + t*ey));
+ if (d < best_d) { best_d = d; best = i; }
+ }
+ return best;
+}
+
+float BuildGraph::beam_fire(float ox, float oy, float dx, float dy, float range,
+ float damage, bool ignite, float& hit_x, float& hit_y) {
+ float dl = std::hypot(dx, dy);
+ if (dl < 1e-6f) { hit_x = ox; hit_y = oy; return 0.0f; }
+ dx /= dl; dy /= dl;
+
+ // Gather every strut the ray crosses (of any material), sorted by distance.
+ struct Cross { float t; int edge; };
+ std::vector<Cross> crosses;
+ for (int i = 0; i < (int)edges.size(); i++) {
+ const BuildNode& A = nodes[edges[i].node_a];
+ const BuildNode& B = nodes[edges[i].node_b];
+ float ex = B.x - A.x, ey = B.y - A.y;
+ float denom = dx * ey - dy * ex;
+ if (std::fabs(denom) < 1e-6f) continue; // parallel
+ float t = ((A.x - ox) * ey - (A.y - oy) * ex) / denom; // dist along ray
+ float u = ((A.x - ox) * dy - (A.y - oy) * dx) / denom; // param along segment
+ if (t >= 0.0f && t <= range && u >= 0.0f && u <= 1.0f) crosses.push_back({t, i});
+ }
+ std::sort(crosses.begin(), crosses.end(),
+ [](const Cross& a, const Cross& b){ return a.t < b.t; });
+
+ // Damage/ignite each crossed strut; pass through transparent ones; stop at wood.
+ float stop = range;
+ std::vector<int> brk;
+ for (const auto& c : crosses) {
+ BuildEdge& e = edges[c.edge];
+ e.hp -= damage;
+ if (ignite && materials[e.mat].flammable) e.burning = true;
+ if (e.hp <= 0.0f) brk.push_back(c.edge);
+ if (materials[e.mat].blocks_beam) { stop = c.t; break; } // wood halts the beam
+ }
+ hit_x = ox + dx * stop;
+ hit_y = oy + dy * stop;
+
+ if (!brk.empty()) {
+ std::sort(brk.begin(), brk.end());
+ brk.erase(std::unique(brk.begin(), brk.end()), brk.end());
+ for (auto it = brk.rbegin(); it != brk.rend(); ++it)
+ edges.erase(edges.begin() + *it);
+ rebuild_topology();
+ }
+ return stop;
+}
+
+void BuildGraph::ignite_edge(int edge_id) {
+ if (edge_id < 0 || edge_id >= (int)edges.size()) return;
+ if (materials[edges[edge_id].mat].flammable) edges[edge_id].burning = true;
+}
+
+void BuildGraph::ignite_area(float x, float y, float radius) {
+ for (int i = 0; i < (int)edges.size(); i++) {
+ float mx = (nodes[edges[i].node_a].x + nodes[edges[i].node_b].x) * 0.5f;
+ float my = (nodes[edges[i].node_a].y + nodes[edges[i].node_b].y) * 0.5f;
+ if (std::hypot(mx - x, my - y) < radius) ignite_edge(i);
+ }
+}
+
+void BuildGraph::update_fire(float dt) {
+ // Burn: DoT + advance spread timer; ignite flammable neighbours; destroy at 0.
+ std::vector<int> newly_lit;
+ std::vector<int> brk;
+ for (int i = 0; i < (int)edges.size(); i++) {
+ auto& e = edges[i];
+ if (!e.burning) continue;
+ const MaterialDef& m = materials[e.mat];
+ e.hp -= m.burn_rate * dt;
+ e.burn += dt;
+ if (e.burn >= m.spread_time) {
+ e.burn = 0.0f; // spread again after each interval
+ for (int end : { e.node_a, e.node_b })
+ for (auto [nb, ei] : adj_[end])
+ if (!edges[ei].burning && materials[edges[ei].mat].flammable)
+ newly_lit.push_back(ei);
+ }
+ if (e.hp <= 0.0f) brk.push_back(i);
+ }
+ for (int ei : newly_lit)
+ if (ei >= 0 && ei < (int)edges.size()) edges[ei].burning = true;
+ if (!brk.empty()) {
+ std::sort(brk.begin(), brk.end());
+ brk.erase(std::unique(brk.begin(), brk.end()), brk.end());
+ for (auto it = brk.rbegin(); it != brk.rend(); ++it)
+ edges.erase(edges.begin() + *it);
+ rebuild_topology();
+ }
+}
+
+void BuildGraph::break_edge(int edge_id) {
+ if (edge_id < 0 || edge_id >= (int)edges.size()) return;
+ edges.erase(edges.begin() + edge_id);
+ rebuild_topology();
+}
+
+void BuildGraph::break_node(int node_id) {
+ if (node_id < 0 || node_id >= (int)nodes.size()) return;
+
+ edges.erase(std::remove_if(edges.begin(), edges.end(),
+ [node_id](const BuildEdge& e) {
+ return e.node_a == node_id || e.node_b == node_id;
+ }), edges.end());
+
+ nodes.erase(nodes.begin() + node_id);
+ for (auto& e : edges) {
+ if (e.node_a > node_id) e.node_a--;
+ if (e.node_b > node_id) e.node_b--;
+ }
+ rebuild_topology();
+}
+
+// =============================================================================
+// Queries
+// =============================================================================
+
+int BuildGraph::find_nearest_node(float x, float y, float radius) const {
+ int best = -1;
+ float best_d2 = radius * radius;
+ for (int i = 0; i < (int)nodes.size(); i++) {
+ float dx = nodes[i].x - x, dy = nodes[i].y - y;
+ float d2 = dx*dx + dy*dy;
+ if (d2 < best_d2) { best_d2 = d2; best = i; }
+ }
+ return best;
+}
+
+int BuildGraph::find_nearest_edge(float x, float y, float radius) const {
+ int best = -1;
+ float best_d = radius;
+ for (int i = 0; i < (int)edges.size(); i++) {
+ const BuildNode& A = nodes[edges[i].node_a];
+ const BuildNode& B = nodes[edges[i].node_b];
+ float ex = B.x - A.x, ey = B.y - A.y;
+ float len2 = ex*ex + ey*ey;
+ if (len2 < 0.0001f) continue;
+ float t = ((x - A.x)*ex + (y - A.y)*ey) / len2;
+ t = std::clamp(t, 0.0f, 1.0f);
+ float px = A.x + t*ex, py = A.y + t*ey;
+ float d = std::hypot(x - px, y - py);
+ if (d < best_d) { best_d = d; best = i; }
+ }
+ return best;
+}
+
+BuildEdge* BuildGraph::mutable_edge(int id) {
+ if (id < 0 || id >= (int)edges.size()) return nullptr;
+ return &edges[id];
+}
generated by cgit v1.3 (git 2.53.0) at 2026-10-09 10:15:08 +0000