Devlog #3: black holes, supernovas, and O(N log N)

a lot has happened since the tunneling fix.

last time i said the next few updates would focus on cutting time complexity. that’s done now. the big one is Barnes-Hut. instead of checking every body against every other body for gravity, you build a quadtree that recursively splits space into four quadrants. when computing the gravitational pull on a body, if a whole cluster of bodies is far enough away, you just treat it as a single point mass. “far enough” is a ratio called θ; i used 0.5. gravity goes from O(N²) to O(N log N). at ten bodies you won’t feel it. at two hundred you really will.

collision detection got the same treatment. spatial hashing: bodies are bucketed into grid cells by position and you only check pairs that share a cell. O(N) average case. there was a subtle bug where i had a fixed cell size of 100px, which completely broke for large merged bodies since their combined radius could exceed 100 and the system just never detected them. fixed with cellSize = max(100, maxR * 2).

also switched trails from vector::erase(begin()) to a deque so pop_front() is O(1) instead of O(N) every frame. small thing but it was just sitting there being wasteful.

then the actually fun stuff.

i added a body type system. asteroids are jagged 7-sided polygons with a faint white outline. planets get an atmospheric halo and an equatorial band. stars have layered corona glows and eight slowly rotating rays. bodies auto-upgrade when they absorb enough mass, past 20 you become a planet, past 200 a star. it all just happens from collisions.

black holes (H key) are fixed in space. i zero their acceleration and velocity every substep so gravity from other bodies does nothing to them. visually they’re a black void ringed by a spinning orange accretion disk. they eat everything that enters their radius unconditionally, regardless of whether collision mode is on. they grow as they feed.

white holes (W key) are also fixed. the Barnes-Hut tree naturally computes attraction toward everything including white holes. after the tree pass i run a correction that subtracts 2× each white hole’s gravitational contribution from every other body, cancels the attraction, and flips it to repulsion. in merge mode they also kick anything that gets too close instead of absorbing it.

and then supernovas. when a star hits 2000 mass, it explodes. 22 asteroid fragments fly out in a ring, every nearby body gets an outward shockwave kick proportional to how close they were, and a visual ring expands and fades over about 1.5 seconds. if the star was over 3000 mass it collapses into a black hole instead of disappearing.

the thing i didn’t plan was the emergent sequence: binary stars spiral inward from mutual gravity, merge into one massive star, cross the supernova threshold, explode, and leave a black hole sitting in the middle of the debris field. i didn’t script that. it just happens.

next i want nebulas: regions that apply drag to passing bodies. and probably a follow-cam that locks onto a selected body.

thanks for reading :)