# Dynamic Worlds - Persistence, Chunkloading

- Developed as both a standalone backend for procedurally generated worlds, as well as something used by overmaps to load its worlds without relying on static loads which run into prior issues.

## Basics
- Byond is kind of a limited game engine (understatement) and we can't really have huge maps because memory will kill us, even if we optimize the shit out of lighting and atmospherics
- Things like procedural generation are great but what do we do with stuff we need to "leave behind"?
- We can limit number of things loaded and optimize enough to give most rounds content.
- We will never have a system with this that'll last for an arbitrary amount of time without depleting its content
- This system, if fully developed and determined to be fast enough (with needed optimizations) to work on live for up to ~100 players, would solve everything *permanently.*

## Dynamic Worlds - /datum/overmap_world
- Represents a dynamically loaded world
- Consists of:
- World metadata - seed, maxwidth, maxheight, mode (representing an overmap object, represents the overmap itself, or standalone), generator parameters (what ruins to spawn, calculations for ruin spawns, etc), persistent ID if persistent
- Chunks - /datum/world_chunk
- Tracks what players are on them, what chunks are loaded, etc
- Handles worldgen
- Identified by a GUID() - this is its path on disk or SQL.
- Handles high level access as well as specific tile access
- Coordinates are relative to 0, 0, 0
- Chunks support z values, yes.

### Level Seed
- Level seed is used as the master key for deterministic perlin generation
- Should never be changed - if changed, saved data will remain but everything already saved as 'changed data' will still spawn in the same places - this can be very weird/ugly, but this isn't enforced by the backend.

### Chunk Data
- #define CHUNK_SIZE - Determines size of chunks
- While SQL save backend would theoretically allow for arbitrary loading of any tile, for now, assuming that this is unchangeable in a save - if this is changed, a save with a different size will be automatically tossed.

### UI
- An admin interface can be opened for the Dynamic Worlds subsystem
- Each loaded world can be selected
- Shows chunks in a grid that are loaded
- Allows admins to jump to any chunk
- Allows admins to force-load any chunk

## Chunks - /datum/world_chunk
- Collections of 32x32 tiles
- Loaded and unloaded dynamically in designated chunkloading zlevels
- Utilizes map serialization (Separate module, outlined below) to save unloaded chunks.

## Chunkloading
- Chunkloading is a little complicated (duh!)
- On **first load**, generation is performed
- Subsequent loads load data from disk
- Optimally, as much information as possible should be **deterministic** based on the level seed
- **Only changed data is saved,** if and only if something can be deterministically accessed using **pure math functions**, with good performance, in constant time per tile.
- For everything else, all data is saved (generation takes care of all "don't knows" or "unsures" in the process)
- Players
- We only care about players. Simplemobs, etc, are glitzed over where appropriate because *we simply do not give a shit due to limited computational resources.*
- Each player loads a 3x3 around themselves.
- When the server is idle, up to a 5x5 is loaded around each player
- **Observers**, that don't have a "load allowance override" toggled by an admin, are second class citizens. If resources are strained, they will suffer from very slow load times (players get priority), flat out be unable to load new chunks, and if they're in an unloading chunk, they'll be kicked into an adjacent chunk, or ejected to the observer spawnpoint if none exist.
- Machinery
- Certain machinery that processes (and we actually care about, say, mining drills, etc) will register with a chunk when moving into it. They'll prevent unloads as long as they're active (but may have a variable that determines if they're "absolute chunkloaders" or "keep this alive but allow unload if server is highly loaded")
- Pipes, and power cables will keep chunks loaded as long as their previous chunk is loaded.
- Unloading
- When a player leaves a chunk, and it isn't chunkloaded by something "anchoring" it, a 5 minute timer is started.
- If no player or chunkloading object exists within that 5 minutes (if they leave again it starts again, reset, etc), it'll be serialized to disk and unloaded.

## Static Loading
- Some chunks can be replaced with /datum/chunk/virtual
- These datums below to a /datum/world_linked_area (bad name whatever) - This represents a linked group of chunks linking to a physical zlevel (or perhaps in the future an overmap_location or whatnot)
- This would allow us to link, say, the main station onto an infinite planet. Instead of going into a proper chunk, anyone trying to go into a virtual chunk would just be plopped to whereever it's linked
- On the zlevel it's linked to, transitions would visually display the linked chunks
- Optimally, zlevels would be a multiple of CHUNK_SIZE for this to work perfectly.

## Lookup, Z Management
- Chunkloading loads into a set of managed zlevels
- Real global vars used to lookup
- Faster than managed globals
- 1 assoclist lookup to determine if further actions are needed
- If they are, another lookup determines chunk
- Depends on function, more on this later
- List stores z = 1 for fast lookup of "if we are in a chunk area"
- Another list stores the "[x-y]" of the **bottom-leftmost turf a chunk occupies in the physical world**, that **is not** a transition, associated to the chunk datum
- Chunk (NOT TURF) x and y are relative to 0, 0
- **Chunks are aligned.**
- x = 1, y = 1 are going to be all transitions
- After that, it'll be CHUNK_SIZE, then another transition tile, then immediately, another CHUNK_SIZE, so on
- Math to determine if a tile is a transition would just be (x or y % (CHUNK_SIZE + 1) == 1)
- Math to get the lookup value for the bottomleft most turf would just be (FLOOR(x or y, CHUNK_SIZE + 1) - 1) * CHUNK_SIZE + 2
- Chunks can easily calculate their "virtual x/y/z" (yes, they have a z value)
- The worldmap datum would contain a proc to grab either the chunk, or the tile (loading in the chunk if necessary), relative to 0, 0

## Movement, visual transitions
- Chunk borders are special turfs that map get turfs to the next chunk. They don't physically exist, you can't put anything on them
- Chunk borders are shared by two chunks at once
- Movement just does chunk lookup --> get north/south/east/west/up/down --> get offsetted turf
- Visuals do around the same, but the turf **before** the chunk border would hold the visuals, mostly because the chunk border is shared by two chunks, and adding things to vis contents of both sides can get tricky
- Alternatively, borders can be 2 thick, which wouldn't be hard to do but would add some overhead

## BYOND wrappers
- For all of these, one initial lookup determines if it's on a chunkloaded level
- If it is, continue
- If it isn't, use BYOND default

### X, Y, Z
- Lookup chunk using bottomleft turf
- Get chunk offset
- Multiply by chunk size
- Add offset from bottomleft turf as needed

### Hearers/viewers
- Return byond if radius won't touch a chunk border
- If radius just touches chunk border, do it anyways and grab the turfs on the other side of the border
- This is really bad because we can't control things like x-ray vision
- Extremely high overhead
- TBD - overhead from this and range may make the entire project infeasible
- Potentially, if can see chunk border, "manually draw" on the other side using a fast view/hear approximation from the border and include turfs that are within the "range"
- Even this is slow.

### Range
- Manual spiral range outwards, translating onto other chunks/borders as needed
- Can either use a fast approimation, or directly grab turfs one by one
- The latter would be infeasibly inefficient computationally
- Extremely high overhead

### Get dist/Get dir
- Return if on same chunk
- Grab virtual x/y/z and calculate manhattan distance
- Switch statements for dir

### Get step to/towards
- Towards is get_dir combined with get step
- To is still that, unless on same chunk

### Walk to/towards
- Manual implementation, maybe a ticker subsystem for handling this

## Pathfinding
- Hahaaaaaaaa nope
- Best case, ASTAR/JPS the chunks rather than tiles if within 16 chunks
- Still would require reworking to pathfinding entirely because returning a list of turfs won't do much when the turfs can change location mid-move
- Pathfinding to a directly adjacent chunk MAY work if the turf list returned is consistent enough to allow seamless transitions, however, any more than 1-2 adjacent chunks would be far too much overhead to work
- Even then, it'd just be "pathfind to chunk edge, then pathfind from next edge", not actually grabbing every turf which would also be computationally infeasible

## Generation

### Perlin Noise
- Biomes, turfs, etc, would be generated by perlin noise
- Unchanged data is not saved, as long as we can easily get the deterministic flat-reprensetation of a turf (like type + biome value + special stuff)
- If a turf ever changes, immediately save

### Map Template/Submaps
- Ruin seeding can be done with perlin maybe but likely it'd be allow other datums to hook chunk generation
- Store all seeded ruins by chunk
- Hopefully a fast lookup system
- When seeding, allow things to force-load adjacent chunks to not have something "clipped"
- Loading in would require some hilariously complex math for the maploader if it spans more than one chunk.
- TBD, also project-killing in complexity/CPU expensiveness

## Persistence Module

- Inspired by persistencestation
- Some things should be flattened like gasmixtures/etc directly into a list or JSON
- Otherwise, save variables as needed
- Objects should be able to read existing variables on initialization or atleast post initialization
- Two paradigms, either call a OnDeserialize(list/data) to load data, or code objects to read variables on Initialize
- Persistent module on Nebula has some very good serialization, could use it if needed
- Storage
- SQL is unironically the best option at this point, given the hilariously garbage performance of BYOND savefiles
- Ultimately things would need to either be
- Flattened into text (byond string operations, ha, ha...)
- INSERT INTO with duplicate key = values per object
- Which would probably murder our database server :)

### Serialization/Saving
- Changed data is saved
- Any items on a turf/objects/mobs that aren't lighting objects or has AllowPersist() to false
- The turf itself being changed in any way shape or form from the deterministic generation cycle

### Instantiation/Loading
- Changed data is loaded
- Otherwise, perlin generation fills in the turf/anything like that

## Integrations

### Atmospherics
- Auxtools atmos (or ZAS when ported to RP) will hopefully be able to "smartly" handle outdoors chunks and not need to use memory for each turf.
- Atmos adjacency would need to take chunks into account. This is, very, very bad.
- This can potentially work well on tile atmos by just wrapping adjaceny recalculations, but would be absolutely murderous on ZAS without heavy optimizations.
- Perhaps for ZAS chunk borders would just be "natural" zone dividers, and connections would exist across loaded borders.

### Lighting
- Same, for planetary turfs. Planet-subsystem integration will be required (developed separately) to handle lighting. We can save a lot of memory by lazy-initing lighting and dumping out corners/objects when unnecessary.
- Lighting calculations would need to take chunsk into account. This is very, very bad.

### Powernets
- Power cables need to go across borders. This is slightly less awful than atmos/lighting.

## What's going to kill this project?
- No efficient cross-chunk pathfinding = mobs get fucked
- Potentially can work if we pathfind to edge of chunk but the overhead would be massive
- The maploader works on contiuous space. We're segmenting space.
- Mathing out the things necessary to have the maploader, say, load a ruin across multiple chunks?
- Outlook not so good
- The **best** case would be detecting this, and immediately segmenting into x loads in series, cropping the map (tg maploader is pretty efficient at reading a pre-parsed map) as we go to load in the segments.
- Wrapper overhead
- Even the fastest wrappers, get x/y/z, are going to involve multiple lookups instead of one
- **range, view, hearers, etc** - Outlook not so good. Even a rough simulation/approximation of these would be exorbitant in cost, not to mention hilariously hard to implement
- Instantiation/load overhead
- Most of this, minus the actual instantiation + initialization of objects, can be rust/auxtools'd away if truly need be
- If the rest are too high in cost, this project is sunk
- To sustain a single player moving at 6.66 tiles per second across 32x32 chunks in a straight line we would need a **sustained map loading speed of 1200 tiles per second.**
- Fuck.
- Multiple players clustered together don't load chunks separately (duh) so if everyone is in small groups and don't run top speed, this could work.
- Vis contents
- Dear fucking lord
- The turf transitions are an "all or nothing see everything on the other side or see nothing on the other side"
- This means you can see past walls and everything will be awful.
- All of these problems would be mitigated with larger chunks
- Continuous zlevels with transitions, right now, are basically chunks
- However doing a chunkloading system with this would be hilariously ridiculous at a size of 200x200 even, because of how long it'd take to load and unload a full zlevel instead of a small chunk
- Everything else is semi feasible including the calculations, they're just mildly difficult to actually make because this project is basically trying to make a game engine in a game engine, consisting of dynamic chunkloading and only sending data from things around a player, in an existing, slow, outdated game engine that uses predefined levels instead of a chunkloaded system.
- Why am I like this?

### Something-Something
- If chunks are loaded contiguously in relative positions to each other all the wrapper overhead but "get real x/y/z/get dir/get dist/pathfinding" are gone, and those are ironically, while called the most, the easiest/cheapest to do in computation
- The worst case for this would be one zlevel, per player, if everyone goes in different directions
- If we use small-ish zlevels like 128x128 and optimize the shit out of the server's memory usage and turn on LAA this could work, even 100 players would, perhaps, use the same amount of memory as like, 25 "normal" tgstation zlevels
- :joy: Project not dead I guess but even more ridiculous to put into implementation.