From a22bf34ccdb9ba063438f27a8f9bdb6d5bffb28c Mon Sep 17 00:00:00 2001 From: Nic Gaffney Date: Sun, 12 Oct 2025 19:18:04 -0500 Subject: Quadtree optimization complete --- build.zig | 11 ++ src/config.zig | 9 +- src/imgui.zig | 10 +- src/main.zig | 55 +++++--- src/particle.zig | 117 ++++++++--------- src/quad.zig | 379 ++++++++++++++++++++++++++++++++++++++++--------------- src/rules.zig | 28 +++- 7 files changed, 409 insertions(+), 200 deletions(-) diff --git a/build.zig b/build.zig index bc4905a..ac39671 100644 --- a/build.zig +++ b/build.zig @@ -53,4 +53,15 @@ pub fn build(b: *std.Build) !void { } const run_step = b.step("run", "Run the app"); run_step.dependOn(&run_cmd.step); + + const exe_unit_tests = b.addTest(.{ + .root_source_file = b.path("src/quad.zig"), + .target = target, + .optimize = optimize, + }); + + const run_exe_unit_tests = b.addRunArtifact(exe_unit_tests); + + const test_step = b.step("test", "Run unit tests"); + test_step.dependOn(&run_exe_unit_tests.step); } diff --git a/src/config.zig b/src/config.zig index fd088ea..793fde7 100644 --- a/src/config.zig +++ b/src/config.zig @@ -4,15 +4,16 @@ const part = @import("particle.zig"); pub const screenWidth = 1920; pub const screenHeight = 1080; -pub const particleMax = 10000; +pub const particleMax = 100000; pub const initialParticles = 2000; pub const colorAmnt = colors.len; pub const numThreads = 16; - +pub const minQuadSize = 1; +pub const quadSplitLimit = 64; pub var particleCount: i32 = initialParticles; -pub var minDistance: f32 = 20.0; +pub var minDistance: i32 = 20; pub var friction: f32 = 0.95; -pub var radius: [colorAmnt]f32 = undefined; +pub var radius: [colorAmnt]i32 = undefined; pub var speed: [colorAmnt]i32 = undefined; pub var rules: [colorAmnt][colorAmnt]f32 = undefined; pub var colors = [_]rl.Color{ diff --git a/src/imgui.zig b/src/imgui.zig index bcc6b32..688e935 100644 --- a/src/imgui.zig +++ b/src/imgui.zig @@ -26,17 +26,17 @@ pub fn update(alloc: std.mem.Allocator, buf: [:0]u8) !void { _ = z.sliderInt("Particles", .{ .v = &cfg.particleCount, .min = 1, .max = cfg.particleMax }); _ = z.sliderFloat("Friction", .{ .v = &cfg.friction, .min = 0, .max = 1 }); // _ = z.sliderFloat("Radius", .{ .v = &cfg.radius, .min = cfg.minDistance, .max = 500 }); - _ = z.sliderFloat("Minimum Distance", .{ .v = &cfg.minDistance, .min = 1.0, .max = 500 }); + _ = z.sliderInt("Minimum Distance", .{ .v = &cfg.minDistance, .min = 1.0, .max = 500 }); } if (z.collapsingHeader("Radius", .{ .default_open = true })) { for (&cfg.radius, 0..) |*r, i| { - const str = try std.fmt.allocPrintZ(alloc, "{s} Radius", .{rul.colorToString(i)}); - _ = z.sliderFloat(str, .{ .v = r, .min = cfg.minDistance, .max = 500 }); + const str = rul.colorToStringZ(i); + _ = z.sliderInt(str, .{ .v = r, .min = cfg.minDistance, .max = 500 }); } } if (z.collapsingHeader("Speed", .{ .default_open = true })) { for (&cfg.speed, 0..) |*s, i| { - const str = try std.fmt.allocPrintZ(alloc, "{s} Speed", .{rul.colorToString(i)}); + const str = rul.colorToStringZ(i); _ = z.sliderInt(str, .{ .v = s, .min = 1, .max = 1000 }); } } @@ -72,7 +72,7 @@ pub fn update(alloc: std.mem.Allocator, buf: [:0]u8) !void { } z.endTable(); if (z.button("Randomize", .{})) - cfg.rules = rul.ruleMatrix(); + cfg.rules = rul.ruleMatrix(false, false); } if (z.collapsingHeader("Load / Save", .{ .default_open = true })) { _ = z.inputText("Save Path", .{ .buf = buf }); diff --git a/src/main.zig b/src/main.zig index 00dd477..f7ec0a0 100644 --- a/src/main.zig +++ b/src/main.zig @@ -5,6 +5,7 @@ const part = @import("particle.zig"); const cfg = @import("config.zig"); const img = @import("imgui.zig"); const rules = @import("rules.zig"); +const quad = @import("quad.zig"); const c = @cImport({ @cDefine("NO_FONT_AWESOME", "1"); @@ -13,11 +14,21 @@ const c = @cImport({ pub fn main() !void { cfg.colors = cfg.customColors(); - cfg.rules = rules.ruleMatrix(); + cfg.rules = rules.ruleMatrix(true, true); rules.printRules(cfg.rules); - var gpa = std.heap.GeneralPurposeAllocator(.{}){}; - defer _ = gpa.deinit(); + var gpa = std.heap.GeneralPurposeAllocator(.{ + // .safety = true, + // .thread_safe = true, + // .verbose_log = false, + }){}; + defer { + const leaked = gpa.deinit(); + if (leaked == .leak) { + std.debug.print("LEAKY PROGRAM\n", .{}); + } + } + const allocator = gpa.allocator(); rl.initWindow(cfg.screenWidth, cfg.screenHeight, "Particle Simulator"); defer rl.closeWindow(); @@ -28,49 +39,57 @@ pub fn main() !void { c.rlImGuiSetup(true); defer c.rlImGuiShutdown(); - z.initNoContext(gpa.allocator()); + z.initNoContext(allocator); defer z.deinitNoContext(); const imgui_width: f32 = cfg.screenWidth / 2; const imgui_height: f32 = cfg.screenHeight / 3; z.setNextWindowPos(.{ .x = 0, .y = 0 }); z.setNextWindowSize(.{ .w = imgui_width, .h = imgui_height }); - var particles = try part.initParticles(gpa.allocator(), cfg.initialParticles); - defer particles.deinit(gpa.allocator()); + var particles = try part.initParticles(allocator, cfg.initialParticles); + defer particles.deinit(); + var quadTree: quad.Quad(part.particle, cfg.quadSplitLimit) = undefined; - const buf = try gpa.allocator().allocSentinel(u8, 128, 0); + const buf = try allocator.allocSentinel(u8, 128, 0); std.mem.copyForwards(u8, buf, "Absolute File Path" ++ .{0}); - defer gpa.allocator().free(buf); - const pool = try gpa.allocator().alloc(std.Thread, cfg.numThreads); - defer gpa.allocator().free(pool); + defer allocator.free(buf); + const pool = try allocator.alloc(std.Thread, cfg.numThreads); + defer allocator.free(pool); + var frameCounter: u32 = 0; while (!rl.windowShouldClose()) { - if (particles.items(.x).len < cfg.particleCount) { - for (0..@intCast(cfg.particleCount - @as(i32, @intCast(particles.items(.x).len)))) |_| { + if (particles.items.len < cfg.particleCount) { + for (0..@intCast(cfg.particleCount - @as(i32, @intCast(particles.items.len)))) |_| { //std.debug.print("without this print statement it breaks on arm idk why {d}\n", .{cfg.particleCount}); _ = cfg.particleCount; - try particles.append(gpa.allocator(), part.createParticle()); + try particles.append(part.createParticle()); } } - if (particles.items(.x).len > cfg.particleCount) { + if (particles.items.len > cfg.particleCount) { particles.shrinkRetainingCapacity(@intCast(cfg.particleCount)); } + quadTree = quad.Quad(part.particle, cfg.quadSplitLimit).init(allocator, + .{ .x = 0, .y = 0 }, .{ .x = rl.getScreenWidth(), .y = rl.getScreenHeight()}); + defer quadTree.deinit(); + for (particles.items) |p| try quadTree.insert(.{ .pos = p.pos, .data = p}); + rl.beginDrawing(); defer rl.endDrawing(); if (rl.isKeyPressed(rl.KeyboardKey.key_q)) break; rl.clearBackground(rl.getColor(0x1E1E2EFF)); for (pool, 0..) |*thread, i| - thread.* = try std.Thread.spawn(.{}, part.updateVelocities, .{ &particles, i }); + thread.* = try std.Thread.spawn(.{}, part.updateVelocities, .{ particles, quadTree, i }); for (pool) |thread| thread.join(); + frameCounter += 1; + - // part.updateVelocities(particles, cfg.rules); - part.updatePosition(particles); + part.updatePosition(&particles); part.draw(particles); - try img.update(gpa.allocator(), buf); + try img.update(allocator, buf); } } diff --git a/src/particle.zig b/src/particle.zig index 6768869..d33e7ce 100644 --- a/src/particle.zig +++ b/src/particle.zig @@ -1,102 +1,83 @@ const cfg = @import("config.zig"); const std = @import("std"); const rl = @import("raylib"); +const quad = @import("quad.zig"); pub const particle = struct { colorId: u32, - x: i32, - y: i32, + pos: quad.Point, xvel: f32, yvel: f32, }; /// Initialize a MultiArrayList of size amnt with particles created by createParticle -pub fn initParticles(allocator: std.mem.Allocator, amnt: u32) !std.MultiArrayList(particle) { - var particles = std.MultiArrayList(particle){}; - try particles.setCapacity(allocator, cfg.particleMax); +pub fn initParticles(allocator: std.mem.Allocator, amnt: u32) !std.ArrayList(particle) { + var particles = std.ArrayList(particle).init(allocator); + try particles.ensureTotalCapacity(cfg.particleMax); for (0..amnt) |_| - try particles.append(allocator, createParticle()); + try particles.append(createParticle()); return particles; } /// Applies forces from the ruleset to each particle pub fn updateVelocities( - particles: *std.MultiArrayList(particle), + particles: std.ArrayList(particle), + qtree: quad.Quad(particle, cfg.quadSplitLimit), threadidx: u64, -) void { +) !void { const rules = cfg.rules; - const colorList = particles.items(.colorId); - var xvel = particles.items(.xvel); - var yvel = particles.items(.yvel); - var i: usize = threadidx; - while (i < particles.len) : (i += cfg.numThreads) { - const p = particles.get(i); + var particlesInRange = std.ArrayList(particle).init(qtree.allocator); + defer particlesInRange.deinit(); + var i = threadidx; + while (i < particles.items.len) : (i += cfg.numThreads) { + var p: *particle = &(particles.items[i]); + defer particlesInRange.clearRetainingCapacity(); const radius = cfg.radius[p.colorId]; + try qtree.radiusSearchWrapping(p.pos, @intCast(radius), &particlesInRange, rl.getScreenWidth(), rl.getScreenHeight()); var forceX: f32 = 0.0; var forceY: f32 = 0.0; - - var j: usize = threadidx; - while (j < particles.len) : (j += 1) { - const p2 = particles.get(j); - if (i == j) continue; - var check2x = p.x - rl.getScreenWidth(); - var check2y = p.y - rl.getScreenHeight(); - if (p.x < @divExact(rl.getScreenWidth(), 2)) check2x = p.x + rl.getScreenWidth(); - if (p.y < @divExact(rl.getScreenHeight(), 2)) check2y = p.y + rl.getScreenHeight(); - - var distance_x: f32 = @floatFromInt(p.x - p2.x); - var distance_y: f32 = @floatFromInt(p.y - p2.y); - const check2rx: f32 = @floatFromInt(check2x - p2.x); - const check2ry: f32 = @floatFromInt(check2y - p2.y); - - if (@abs(distance_x) > @abs(check2rx)) distance_x = check2rx; - if (@abs(distance_y) > @abs(check2ry)) distance_y = check2ry; - - if (distance_x > radius or distance_y > radius) continue; - + const floatRadius = @as(f32, @floatFromInt(radius)); + const floattMinDistance = @as(f32, @floatFromInt(cfg.minDistance)); + for (particlesInRange.items) |p2| { + if (p.pos.x == p2.pos.x and p.pos.y == p2.pos.y) continue; + const distance_x: f32 = @floatFromInt(p.pos.x - p2.pos.x); + const distance_y: f32 = @floatFromInt(p.pos.y - p2.pos.y); var distance = @sqrt(distance_x * distance_x + distance_y * distance_y); - - if (distance == 0) distance = 0.0001; - if (distance > 0 and distance < radius) { - const f = -force(distance, radius, rules[colorList[i]][colorList[j]]); - forceX += (distance_x / distance) * f; - forceY += (distance_y / distance) * f; - } + if (distance == 0) distance = 0.01; + const f = -force(distance, floatRadius, rules[p.colorId][p2.colorId]); + forceX += (distance_x / distance) * f; + forceY += (distance_y / distance) * f; } - - forceX = forceX * cfg.minDistance / radius; - forceY = forceY * cfg.minDistance / radius; - - xvel[i] = xvel[i] * cfg.friction + forceX; - yvel[i] = yvel[i] * cfg.friction + forceY; + forceX = forceX * floattMinDistance / floatRadius; + // forceX = std.math.clamp(forceX, -10.0, 10.0); + forceY = forceY * floattMinDistance / floatRadius; + // forceY = std.math.clamp(forceY, -10.0, 10.0); + p.xvel *= cfg.friction ; + p.xvel += forceX; + p.yvel *= cfg.friction; + p.yvel += forceY; } } /// Applies the particles velocity and updates position -pub fn updatePosition(particles: std.MultiArrayList(particle)) void { - for ( - particles.items(.colorId), - particles.items(.y), - particles.items(.yvel), - ) |col, *y, yvel| // (y + yvel) % screenHeight - y.* = @intFromFloat(@round(@as(f32, @floatFromInt(@mod(@as(i32, @intFromFloat(@round((@as(f32, @floatFromInt(y.*)) + (@as(f32, @floatFromInt(cfg.speed[col])) / 1000.0) * yvel)))), rl.getScreenHeight()))))); - - for ( - particles.items(.colorId), - particles.items(.x), - particles.items(.xvel), - ) |col, *x, xvel| // (y + yvel) % screenHeight - x.* = @intFromFloat(@round(@as(f32, @floatFromInt(@mod(@as(i32, @intFromFloat(@round((@as(f32, @floatFromInt(x.*)) + (@as(f32, @floatFromInt(cfg.speed[col])) / 1000.0) * xvel)))), rl.getScreenWidth()))))); +pub fn updatePosition(particles: *std.ArrayList(particle)) void { + for (particles.items) |*p| { + const maxVel: f32 = 4096.0; + const posYplusVel: f32 = @as(f32, @floatFromInt(p.pos.y)) + std.math.clamp(p.yvel, -maxVel, maxVel); + const posXplusVel: f32 = @as(f32, @floatFromInt(p.pos.x)) + std.math.clamp(p.xvel, -maxVel, maxVel); + p.pos.y = @mod(@as(i32, @intFromFloat(posYplusVel)), rl.getScreenHeight()); + p.pos.x = @mod(@as(i32, @intFromFloat(posXplusVel)), rl.getScreenWidth()); + } } /// Draw the particles onto the screen using raylib -pub fn draw(particles: std.MultiArrayList(particle)) void { - for (particles.items(.y), particles.items(.x), particles.items(.colorId)) |*y, *x, colorId| - rl.drawRectangle(x.*, y.*, 5, 5, cfg.colors[colorId]); +pub fn draw(particles: std.ArrayList(particle)) void { + for (particles.items) |p| + rl.drawRectangle(p.pos.x, p.pos.y, 5, 5, cfg.colors[p.colorId]); } fn force(distance: f32, radius: f32, attraction: f32) f32 { - const beta = cfg.minDistance / radius; + const beta = @as(f32, @floatFromInt(cfg.minDistance)) / radius; const r: f32 = distance / radius; if (r < beta) return ((beta - r) / (beta - 1.0)); @@ -113,8 +94,10 @@ pub fn createParticle() particle { const color = prng.random().uintLessThan(u32, cfg.colorAmnt); return particle{ .colorId = color, - .x = @intCast(x), - .y = @intCast(y), + .pos = .{ + .x = @intCast(x), + .y = @intCast(y), + }, .xvel = 0, .yvel = 0, }; diff --git a/src/quad.zig b/src/quad.zig index 92e345c..0d4174e 100644 --- a/src/quad.zig +++ b/src/quad.zig @@ -1,6 +1,7 @@ const std = @import("std"); +const cfg = @import("config.zig"); -const Point = struct { +pub const Point = struct { x: i32, y: i32, }; @@ -12,135 +13,313 @@ pub fn Node(T: type) type { }; } -pub fn Quad(T: type) type { +pub fn Quad(T: type, comptime splitLimit: usize) type { return struct { allocator: std.mem.Allocator, - node: ?*Node(T), + nodes: ?std.BoundedArray(Node(T), splitLimit), topLeft: Point, bottomRight: Point, - children: [4]?*Quad(T), + children: [4]?*Quad(T, splitLimit), - pub fn init(allocator: std.mem.Allocator, tl: Point, br: Point) Quad(T) { - return Quad(T){ + const Self = @This(); + + pub fn init(allocator: std.mem.Allocator, tl: Point, br: Point) Quad(T, splitLimit) { + return Quad(T, splitLimit){ .allocator = allocator, - .node = null, + .nodes = std.BoundedArray(Node(T), splitLimit).init(0) catch unreachable, .topLeft = tl, .bottomRight = br, - .children = [4]?*Quad(T){ null, null, null, null }, + .children = [4]?*Quad(T, splitLimit){ null, null, null, null }, }; } - inline fn inBoundry(self: Quad(T), pos: Point) bool { - return pos.x >= self.topLeft.x and pos.x <= self.bottomRight.x and pos.y >= self.topLeft.y and pos.y <= self.bottomRight.y; + inline fn inBoundry(self: Self, pos: Point) bool { + return pos.x >= self.topLeft.x and pos.x <= self.bottomRight.x and + pos.y >= self.topLeft.y and pos.y <= self.bottomRight.y; } - pub fn search(self: Quad(T), p: Point) ?*Node(T) { - if (!self.inBoundry(p)) return null; - if (self.node) |n| return n; - if (@divTrunc((self.topLeft.x + self.bottomRight.x), 2) >= p.x) { - if (@divTrunc((self.topLeft.y + self.bottomRight.y), 2) >= p.y) { - if (self.children[0] == null) - return null; - return self.children[0].?.search(p); + fn isLeaf(self: Self) bool { + return self.children[0] == null and self.children[1] == null and + self.children[2] == null and self.children[3] == null; + } + + fn shouldSplit(self: Self) bool { + if (@abs(self.topLeft.x - self.bottomRight.x) <= 8 and + @abs(self.topLeft.y - self.bottomRight.y) <= 8) { + return false; + } + if (self.nodes) |nodes| + return nodes.len >= cfg.quadSplitLimit; + return false; + } + + fn getQuadrant(self: Self, pos: Point) usize { + const midX = @divTrunc(self.topLeft.x + self.bottomRight.x, 2); + const midY = @divTrunc(self.topLeft.y + self.bottomRight.y, 2); + + if (pos.x <= midX) { + if (pos.y <= midY) { + return 0; // Top-left } else { - if (self.children[2] == null) - return null; - return self.children[2].?.search(p); + return 2; // Bottom-left } } else { - if (@divTrunc((self.topLeft.y + self.bottomRight.y), 2) >= p.y) { - if (self.children[1] == null) - return null; - return self.children[1].?.search(p); + if (pos.y <= midY) { + return 1; // Top-right } else { - if (self.children[3] == null) - return null; - return self.children[3].?.search(p); + return 3; // Bottom-right } } } - pub fn insert(self: *Quad(T), data: T, pos: Point) !void { - const node: ?*Node(T) = try self.allocator.create(Node(T)); - node.* = Node(T){ .data = data, .pos = pos }; - const nNode = node.?; - if (!self.inBoundry(nNode.pos)) return; - if (@abs(self.topLeft.x - self.bottomRight.x) <= 1 and @abs(self.topLeft.y - self.bottomRight.y) <= 1) { - self.node = if (self.node == null) node else self.node; + fn createChild(self: *Self, quadrant: usize) std.mem.Allocator.Error!void { + const midX = @divTrunc(self.topLeft.x + self.bottomRight.x, 2); + const midY = @divTrunc(self.topLeft.y + self.bottomRight.y, 2); + const tl: Point = switch (quadrant) { + 0 => self.topLeft, + 1 => .{ .x = midX, .y = self.topLeft.y }, + 2 => .{ .x = self.topLeft.x, .y = midY }, + 3 => .{ .x = midX, .y = midY }, + else => unreachable, + }; + const br: Point = switch (quadrant) { + 0 => .{ .x = midX, .y = midY }, + 1 => .{ .x = self.bottomRight.x, .y = midY }, + 2 => .{ .x = midX, .y = self.bottomRight.y }, + 3 => self.bottomRight, + else => unreachable, + }; + self.children[quadrant] = try self.allocator.create(Quad(T, splitLimit)); + self.children[quadrant].?.* = Quad(T, splitLimit).init(self.allocator, tl, br); + } + + fn split(self: *Quad(T, splitLimit)) !void { + if (self.nodes == null) return; + for (0..4) |i| + if (self.children[i] == null) + try self.createChild(i); + const nodesToRedistribute = self.nodes.?.slice(); + for (nodesToRedistribute) |node| { + const quadrant = self.getQuadrant(node.pos); + try self.children[quadrant].?.insert(node); + } + self.nodes = null; + } + + pub fn insert(self: *Quad(T, splitLimit), node: Node(T)) std.mem.Allocator.Error!void { + if (!self.inBoundry(node.pos)) return; + if (!self.isLeaf()) { + const quadrant = self.getQuadrant(node.pos); + if (self.children[quadrant] == null) + try self.createChild(quadrant); + try self.children[quadrant].?.insert(node); return; } - if (@divTrunc((self.topLeft.x + self.bottomRight.x), 2) >= nNode.pos.x) { - if (@divTrunc((self.topLeft.y + self.bottomRight.y), 2) >= nNode.pos.y) { - if (self.children[0] == null) { - self.children[0] = try self.allocator.create(Quad(T)); - self.children[0].?.* = Quad(T).init( - self.allocator, - self.topLeft, - .{ - .x = @divTrunc((self.topLeft.x + self.bottomRight.x), 2), - .y = @divTrunc((self.topLeft.y + self.bottomRight.y), 2), - }, - ); - } - try self.children[0].?.insert(node); - } else { - if (self.children[2] == null) { - self.children[2] = try self.allocator.create(Quad(T)); - self.children[2].?.* = Quad(T).init( - self.allocator, - .{ - .x = self.topLeft.x, - .y = @divTrunc(self.topLeft.y + self.bottomRight.y, 2), - }, - .{ - .x = @divTrunc((self.topLeft.x + self.bottomRight.x), 2), - .y = self.bottomRight.y, - }, - ); - } - try self.children[2].?.insert(node); - } - } else { - if (@divTrunc((self.topLeft.y + self.bottomRight.y), 2) >= nNode.pos.y) { - if (self.children[1] == null) { - self.children[1] = try self.allocator.create(Quad(T)); - self.children[1].?.* = Quad(T).init( - self.allocator, - .{ - .x = @divTrunc(self.topLeft.x + self.bottomRight.x, 2), - .y = self.topLeft.y, - }, - .{ - .x = self.bottomRight.x, - .y = @divTrunc((self.topLeft.y + self.bottomRight.y), 2), - }, - ); - } - try self.children[1].?.insert(node); - } else { - if (self.children[3] == null) { - self.children[3] = try self.allocator.create(Quad(T)); - self.children[3].?.* = Quad(T).init( - self.allocator, - .{ - .x = @divTrunc((self.topLeft.x + self.bottomRight.x), 2), - .y = @divTrunc((self.topLeft.y + self.bottomRight.y), 2), - }, - self.bottomRight, - ); - } - try self.children[3].?.insert(node); - } + if (self.nodes) |*nodes| { + nodes.append(node) catch { + try self.split(); + const quadrant = self.getQuadrant(node.pos); + try self.children[quadrant].?.insert(node); + }; } } - pub fn deinit(self: *Quad(T)) void { - if (self.node) |n| self.allocator.destroy(n); + pub fn search(self: Self, p: Point) ?Node(T) { + if (!self.inBoundry(p)) return null; + + if (self.nodes) |nodes| { + for (nodes.slice()) |node| + if (node.pos.x == p.x and node.pos.y == p.y) + return node; + return null; + } + + const quadrant = self.getQuadrant(p); + if (self.children[quadrant]) |child| + return child.search(p); + return null; + } + + pub fn radiusSearch(self: Self, center: Point, radius: u32, results: *std.ArrayList(T)) !void { + if (!self.intersectsCircle(center, radius)) return; + + if (self.nodes) |nodes| { + for (nodes.slice()) |node| + if (locationInRadius(center, node.pos, radius)) { + try results.append(node.data); + }; + return; + } + for (self.children) |child| + if (child) |c| try c.radiusSearch(center, radius, results); + + } + + pub fn radiusSearchWrapping( + self: Self, + center: Point, + radius: u32, + results: *std.ArrayList(T), + worldWidth: i32, + worldHeight: i32, + ) !void { + try self.radiusSearch(center, radius, results); + + const radiusInt: i32 = @intCast(radius); + + const nearLeft = center.x - radiusInt < 0; + const nearRight = center.x + radiusInt > worldWidth; + const nearTop = center.y - radiusInt < 0; + const nearBottom = center.y + radiusInt > worldHeight; + + if (nearLeft) { + const wrappedCenter = Point{ .x = center.x + worldWidth, .y = center.y }; + try self.radiusSearch(wrappedCenter, radius, results); + } + if (nearRight) { + const wrappedCenter = Point{ .x = center.x - worldWidth, .y = center.y }; + try self.radiusSearch(wrappedCenter, radius, results); + } + if (nearTop) { + const wrappedCenter = Point{ .x = center.x, .y = center.y + worldHeight }; + try self.radiusSearch(wrappedCenter, radius, results); + } + if (nearBottom) { + const wrappedCenter = Point{ .x = center.x, .y = center.y - worldHeight }; + try self.radiusSearch(wrappedCenter, radius, results); + } + + if (nearLeft and nearTop) { + const wrappedCenter = Point{ .x = center.x + worldWidth, .y = center.y + worldHeight }; + try self.radiusSearch(wrappedCenter, radius, results); + } + if (nearLeft and nearBottom) { + const wrappedCenter = Point{ .x = center.x + worldWidth, .y = center.y - worldHeight }; + try self.radiusSearch(wrappedCenter, radius, results); + } + if (nearRight and nearTop) { + const wrappedCenter = Point{ .x = center.x - worldWidth, .y = center.y + worldHeight }; + try self.radiusSearch(wrappedCenter, radius, results); + } + if (nearRight and nearBottom) { + const wrappedCenter = Point{ .x = center.x - worldWidth, .y = center.y - worldHeight }; + try self.radiusSearch(wrappedCenter, radius, results); + } + } + + fn intersectsCircle(self: Self, center: Point, radius: u32) bool { + const closestX = std.math.clamp(center.x, self.topLeft.x, self.bottomRight.x); + const closestY = std.math.clamp(center.y, self.topLeft.y, self.bottomRight.y); + + const dx = center.x - closestX; + const dy = center.y - closestY; + const distSq = dx * dx + dy * dy; + const radiusInt: i32 = @intCast(radius); + + return distSq <= (radiusInt * radiusInt); + } + + fn locationInRadius(center: Point, loc: Point, radius: u32) bool { + const dx = loc.x - center.x; + const dy = loc.y - center.y; + const dSquared = dx * dx + dy * dy; + const radiusInt: i32 = @intCast(radius); + return dSquared <= radiusInt * radiusInt; + } + + fn inRadius(self: Self, center: Point, radius: u32) bool { + const points: [4]Point = .{ + self.topLeft, + Point{ .x = self.topLeft.x, .y = self.bottomRight.y }, // Bottom-left + Point{ .x = self.bottomRight.x, .y = self.topLeft.y }, // Top-right + self.bottomRight, + }; + for (points) |p| + if (locationInRadius(center, p, radius)) return true; + + return false; + } + + fn checkRegion(self: Self, center: Point, radius: u32) bool { + return self.inRadius(center, radius) or self.inBoundry(center); + } + + pub fn deinit(self: *Quad(T, splitLimit)) void { + for (self.children) |child| { if (child) |c| { c.deinit(); self.allocator.destroy(c); - }; + } + } } }; } + +test "radius search" { + const alloc = std.testing.allocator; + const topleft: Point = .{ .x=0, .y=0 }; + const bottomright: Point = .{ .x=2560, .y=1440 }; + var quad = Quad(i32, 8).init(alloc, topleft, bottomright); + defer quad.deinit(); + + const arr: [17]i32 = .{ 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 }; + const points: [17]Point = .{ + .{ .x=50, .y=50, }, + .{ .x=70, .y=70, }, + .{ .x=71, .y=71, }, + .{ .x=30, .y=30, }, + .{ .x=29, .y=29, }, + .{ .x=30, .y=70, }, + .{ .x=70, .y=30 }, + .{ .x=70, .y=29, }, + .{ .x=71, .y=30, }, + .{ .x=30, .y=70 }, + .{ .x=29, .y=70 }, + .{ .x=30, .y=71, }, + .{ .x=100, .y=100, }, + .{ .x=51, .y=31, }, + .{ .x=50, .y=70 }, + .{ .x=38, .y=52 }, + .{ .x=50, .y=30 } }; + var expected: [5]i32 = .{ 16, 13, 15, 0, 14 }; + for (arr, points) |n, p| try quad.insert(.{.data= n, .pos=p}); + var out = std.ArrayList(i32).init(alloc); + defer out.deinit(); + try quad.radiusSearch(points[0], 20, &out); + std.mem.sort(i32, &expected, {}, comptime std.sort.asc(i32)); + std.mem.sort(i32, out.items, {}, comptime std.sort.asc(i32)); + try std.testing.expect(std.mem.eql(i32, &expected, out.items)); +} + +test "insertion" { + const alloc = std.testing.allocator; + const topleft: Point = .{ .x=0, .y=0 }; + const bottomright: Point = .{ .x=2560, .y=1440 }; + var quad = Quad(i32, 8).init(alloc, topleft, bottomright); + defer quad.deinit(); + + var arr: [15]i32 = .{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }; + const points: [15]Point = .{ + .{ .x=10, .y=1, }, + .{ .x=22, .y=235, }, + .{ .x=1233, .y=1323, }, + .{ .x=4, .y=423, }, + .{ .x=53, .y=645, }, + .{ .x=6, .y=6, }, + .{ .x=7, .y=70, }, + .{ .x=8, .y=88, }, + .{ .x=129, .y=9, }, + .{ .x=102, .y=10 }, + .{ .x=121, .y=161 }, + .{ .x=12, .y=125, }, + .{ .x=132, .y=135, }, + .{ .x=142, .y=514, }, + .{ .x=215, .y=515 } }; + for (arr, points) |n, p| try quad.insert(.{.data= n, .pos=p}); + var arr_out: [15]i32 = undefined; + for (points, 0..) |p, i| arr_out[i]=quad.search(p).?.data; + std.mem.sort(i32, &arr, {}, comptime std.sort.asc(i32)); + std.mem.sort(i32, &arr_out, {}, comptime std.sort.asc(i32)); + try std.testing.expect(std.mem.eql(i32, &arr_out, &arr)); +} diff --git a/src/rules.zig b/src/rules.zig index fa3d5cb..4e513eb 100644 --- a/src/rules.zig +++ b/src/rules.zig @@ -2,7 +2,7 @@ const cfg = @import("config.zig"); const std = @import("std"); /// Generate the set of rules the particles will abide by -pub fn ruleMatrix() [cfg.colorAmnt][cfg.colorAmnt]f32 { +pub fn ruleMatrix(radius: bool, speed: bool) [cfg.colorAmnt][cfg.colorAmnt]f32 { const seed = @as(u64, @truncate(@as(u128, @bitCast(std.time.nanoTimestamp())))); var prng = std.rand.DefaultPrng.init(seed); var rules: [cfg.colorAmnt][cfg.colorAmnt]f32 = undefined; @@ -13,8 +13,10 @@ pub fn ruleMatrix() [cfg.colorAmnt][cfg.colorAmnt]f32 { if (isNeg == 1) val = 0 - val; rules[i][j] = val; } - cfg.radius[i] = prng.random().float(f32) * 500; - cfg.speed[i] = prng.random().intRangeAtMost(i32, 1, 1000); + if (radius) + cfg.radius[i] = @intCast(@abs(prng.random().intRangeAtMost(i32, cfg.minDistance+1, 100))); + if (speed) + cfg.speed[i] = prng.random().intRangeAtMost(i32, 1, 1000); } return rules; } @@ -57,13 +59,13 @@ pub fn loadRules(allocator: std.mem.Allocator, absolutePath: [:0]u8) !void { for (&cfg.radius) |*r| { const buf = try reader.readUntilDelimiterAlloc(allocator, ',', 16); defer allocator.free(buf); - r.* = try std.fmt.parseFloat(f32, buf); + r.* = try std.fmt.parseInt(i32, buf, 10); } try reader.skipBytes(1, .{}); { const buf = try reader.readUntilDelimiterAlloc(allocator, ',', 16); defer allocator.free(buf); - cfg.minDistance = try std.fmt.parseFloat(f32, buf); + cfg.minDistance = try std.fmt.parseInt(i32, buf, 10); } { const buf = try reader.readUntilDelimiterAlloc(allocator, ',', 16); @@ -96,7 +98,21 @@ pub fn saveRules(absolutePath: [:0]u8) !void { } /// Convert the color index to a string -pub fn colorToString(c: usize) []const u8 { +pub inline fn colorToString(c: usize) []const u8 { + return switch (c) { + 0 => "Red", + 1 => "Green", + 2 => "Blue", + 3 => "Yellow", + 4 => "Magenta", + 5 => "Brown", + 6 => "Orange", + 7 => "Gray", + else => " ", + }; +} + +pub inline fn colorToStringZ(c: usize) [:0]const u8 { return switch (c) { 0 => "Red", 1 => "Green", -- cgit v1.2.3