LeafRTP | Random Teleport

<!-- Markdown mirror of FRONT_PAGE_LITE.bbcode (free LeafRTP front page). Kept in sync with the BBCode source by hand; update both when changing copy.

Marketplace listing metadata (current, for SEO reference): Title: "LeafRTP" Tagline: "Deterministic Random Teleportation engine" -->

Purpose

LeafRTP is a /rtp command. It teleports a player to a random, safe spot in the world, in the most cpu-efficient way it can.

Origin

We were all players once, and we've all complained about "lag" on servers. Many of us tried to pinpoint where it came from and tbh in my studies it took days of work just to find out that a random teleport plugin was triggering performance issues. The biggest cost in any profiling tool was never labeled based on who called the api - that part is obscured, so the source of the thousands of extra chunks in memory is misattributed. I went through the "blame the users" phase and wised up to realize that it's better to fix the tool than to tell people not to use it.

In 2021, this project started as a demonstration of mathematical principles and as a high-difficulty optimization puzzle. I wanted to make something for the community to reference and create a new performance standard, make a name for myself as an obsessive developer. It was received instead as a product and a bunch of features were requested, so I worked on the design elegance so that a few design details resulted in an exponential number of possible configurations. As a result it's a little off-meta but not difficult to fully understand. Measure in chunks, define some regions, and access them via command or api, and anything in between is server design nuance.

"Chunks" were selected as the measurement because the cost to the server is chunk-based rather than block-based and checking adjacent blocks is "optimal" if it doesn't leave a chunk boundary.

I don't like regulating how to use it nor what to use it with, so in V2 I refactored to use more swappable suppliers and consumers, making it easy to programmatically swap safety checks, biome checks, shapes, etc.. There wasn't much optimization to do, so I studied coding practices. Frankly "clean code" is a regret as it increased input latency but the structure gave me a pretty good launch point for reorganization.

For v3 I needed to update for modern game versions and modern web platforms. I got some bright ideas about cache locality optimizations, data access optimizations, cross-platform support via SPI (service provider interface) concepts, and active tracking to catch any "memory leak" that I heard about but could never seem to reproduce on my rig.

Following the V3 update and micro optimizing the selection process, I've created a test bench plugin to assist with testing throughput up to 1 rtp call per gametick (20/s) which has demonstrated performance falloff in the pure reroll model, in every implementation I tested, except this one. I was also able to verify that a common optimization to "use loaded chunks" tends towards placing users in each others' bases to exacerbate either griefing or rerolling depending on claim integration.

What makes it different

Most /rtp plugins are designed around a script: "pick a spot, check it, try, try again" + "add x feature". This creates non-deterministic compute costs around "try again". LeafRTP is a reconstruction for engineering rigor in the foundations, prioritizing stability under load.

I have documented design details more precisely here, denoting design/feature decisions, superseding decisions, and alternatives considered.

Spatial mapping and memory

Measurements show me about 35-65% of a world is "unsafe" for placement, based on oceans, lava, void.

Selections come off a space-filling Archimedean spiral curve, an indexed mapping from 1D to 2D. The math, with distribution plots: Why LeafRTP exists.

The spatial mapping enables storing and recalling information about prior selections, including biome and invalidity cause, using segments rather than image compression, as this enables a specific optimization - offset selections. The location selection phase is a constant-time lookup with occasional table rebuilding that excludes invalid locations, e.g. oceans, lava, void.

Anvil pre-filter

An Anvil (.mca) pre-filter reads biome and block data straight from the region files on disk, so batches of locations can be filtered if a world is generated and those locations are unloaded. It also helps with reading what the world actually contains, rather than what the generator predicts. The common shortcuts (getBiome, getHighestBlockAt) answer from the generation noise map, which can disagree with the real terrain once a spot has been edited or carried across a Minecraft version. Architecture.

Pre-verified cache

Safe destinations are prepared at-rate and a number of them are kept ready in a cache per defined region, so serving /rtp is handing back a coordinate that's already checked. The numbers are in the Performance section below.

Features