hi all. I study randomization stuff, reverse engineering, statistics, and similar. This thread is based on some work I've been doing for RTP.
I've been working on refining the selection algorithm and I'd like to share how it works
I realized my old archimedean spiral design wasn't just banding "a little", it was effectively downsampling to about half the available land, which wasn't necessarily a bad thing to be spacing by 1 chunk, it only put a bit of a lower bound on likely selection distance, but it's not memory efficient to have half the points on the curve hit duplicate 2d coordinates and did not let me configure the distance factor.
so simple concept, instead of polar to cartesian I'll just stay in cartesian and reuse the square variant of an archimedean spiral at a variable scaling factor using chained hilbert curves at each point on the curve to optimize the run length encoding for 2d locality without sacrificing the center-out expansion.
Every hilbert curve is a bin. That allows (A) cpu cache locality for the indexing table, (B) whole bin exclusion from memory for all-good or all-bad bins, (C) working in a capability to offload bins to disk if the scope in-memory grows too large.
Using this model also meant the number of runs needed to describe an ocean dropped from a few hundred to a few dozen.
I borrowed roaring bitmaps as an idea from another project to further cut the run length encoding by about 30-50% depending on the land (a run was at least 64 bits in the table but a few sparse rejections is 1 bit per chunk).
In some contexts, merging run lengths is much more trivial with hilbert curves due to proximity factors like selecting a location within 1 chunk of a requested biome, so a little lossy encoding pulled the memory usage down by 10-30% and generally overlapped with some beaches/ I'm maximizing for % land from a selection point, so it seems good to let go of beaches as opposed to inland rivers.
I put the model through some tests for memory efficiency and selection cost using a non-repeating pseudorandom number generator (modified Feistel PRP), and I got it down to tens of nanoseconds per unique selection at about a 60-70% memory reduction in my tests. Dropping 1MiB to a few hundred KiB was not significant to the server as a whole but it made me happy. The design did open up something else though...
I saw in one test I accidentally created a pattern on the map. I realized it was because of sampling in powers of 4 in a curve designed to recurse in powers of 4, and that would let me start deliberately downsampling for selection distance purposes. I introduced offsets (0, 128, 64, 192, ..., 0) and produced a new nearest neighbor statistic (4096 samples, r=4096) with a median distance scaling with the downsampling rate. I measured a minimum distance of 70 blocks in my latest runs. Corners are likely to have an exception every now and then, idk how to fix that other than exclusion after use.
I also found this model to be incredibly fast for scanning pregenerated region files, from start to finish I was able to scan every chunk at 10k cps on my threadripper bench, thanks to caching one regionfile at a time to scan the entirety of the file before moving on. That pulled my `scan` command down to about 10 seconds to scan a 4k radius, or 10 minutes for a 16k radius, which I think is pretty good for reading data from a pregen'd world.
I also found that palletizing biome memory on the same curve (location -> biome index -> biome name) makes the compression algorithm more efficient for distinct "colors" than the latest image compression algorithms (that I know of) on top of the power-of-4 pixel scaling allowing LOD samples by bin, which allowed me to stream map data rather efficiently through the extremely limited bandwidth i get by routing an editor through lucko's stuff.
Next I'm going to try storing a contour map similarly to biomes so I can derive both slopes and elevations from memory before I load anything.
Progress here - https://github.com/DailyStruggle/RTP
Architecture decisions here - https://github.com/DailyStruggle/RTP/tree/V3/docs/adr
charts here - https://github.com/DailyStruggle/RTP/tree/V3/docs/architecture
some pictures here - https://github.com/DailyStruggle/RTP/tree/V3/docs/assets/img
I've also been working on setting up unit tests, coverage gates, mutation tests, static analysis tools (PMD, sonarqube, qodana), an evolutionary fuzz tester (confirmed against a known memory leak in BetterRTP), and docker compose dev stack setup. I'm using gitar as an AST-based review tool since I don't otherwise have code reviews (gitar sponsored it for me via their open source program). I'm fiddling with my process to do less commit-to-main and more pull request based stuff, currently I do too much in a PR but that's something I accept as a solo dev. I'm not too worried about nonexistent reviewers atm.
As for performance benchmarks, I'm nearing 250 teleports per second (max) on folia with no thread exceptions or obvious race conditions, which tells me I'm going in the right direction with compute efficiency and scheduling practices.