Design New conceptual layer: sector (plus musings on multi-world/node)

[Cervator]

And now for something completely different!

While the focus on v1.0.0 right now is good I wanted to spend a moment looking to the time beyond. I picked a topic close to my heart that has come up again and again and might make up one of the big features of v2.0.0. Let me start with a simple scope progression:

Block - Chunk - Sector (simulation) - Cluster (multi-node) - World - Universe (multi-world) - Metaverse (inter-server)

Right now we just have the three in bold: blocks, the chunks that contain them, and the world that contains chunks. I think but am not sure if @msteiger started something sector-like for placing cities, please chime in if that's the case, I vaguely recall it coming up.

Currently we have no collection type object between the world and the chunks in it. We can store world and chunk level entities (I think) and deal with "bigger" stuff than plain blocks that way, but we don't have a good way to handle multi-chunk objects or things that need to simulate something without being attached to live chunks. If Cities does sector-level stuff I'm guessing it would use a world entity of some sort?

Over time we've discussed concepts that need something more, and even have had independent code for a few, like a climate simulator @Nym Traveel built ages ago. PlaTec is another similar example. Both just produce disconnected artifacts like height maps we'd then import into the game as a one-time event, their output remain static forever.

I'd like to see (and correct me if I'm way off-based architecturally here) us expand the setup to support sectors or something like it (different name?). Goal would be to have a place to store and process sector-local data without needing a single chunk loaded, along with some more stuff I'll cover further down.

A simple example would be cities that grow and connect to each other via trade routes. Better and more trade routes lead to faster growth, that happens even with no players around. On a new server/world creation you'd initialize a 3x3x3 grid of sectors, but for ease I'll pretend we're 2D and just imagine a flat 3x3 area. In a new phase of world gen that could be tied to @msteiger's new world preview in the UI you would:

1. Create the sector storage and add the minimal amount of needed sectors
2. Run some basic noise-based placement of the "city eggs" we've talked of in the past - each a single entity that lives in the sector storage with some basic generated information about the cities (location, name, size, etc)
3. Run another basic step downstream of that (like how current facets can be chained) to let each city connect to a set/random number of neighbors. Cities already has roads like that.
   1. If a city is in an outlying sector near enough to the void outside, our normal approach with chunks would be to create the neighbors enough to start generating stuff, In this case we don't have much actual concrete content so can probably just say city x has y connections to void sector z and when that generates make the connections formal.
4. Optionally simulate city development and trade routes in an accelerated way before starting the game (think Dwarf Fortress' world generation step with visual progress)
   1. Sector-level features would get the same per-game-loop chance to do whatever they want, although probably more rarely (every minute? Every 5? Every hour?) and they'd normally only have access to sector-level data on themselves and neighbors (and world if needed). During accelerated simulation it would run as fast as allowed to speed up progress.
5. After the game starts you begin to generate appropriate chunks including turning the city eggs into actual cities made of plots, buildings, etc. The actual city generation will attach to the earlier sector-level data to check for needed stats like size of city.
   1. If you opted for an accelerated start the cities will have grown while in the egg state. The original starting state of city eggs was based on pure noise but now we've added a small layer of augmented data on top.
6. As the game starts running normally the simulation of city growth continues to run in the sector layer, applying changes at the chunk and block layer (spawning new buildings when appropriate, sending out caravans) only if those chunks are loaded. If they're not the change is just done in sector data and queued for block-rasterization next time a player gets near
7. When a player gets near enough to a sector void you:
   1. Create it in storage
   2. Do initial city egg placement based on original noise
   3. Hook up trade routes, checking with neighbor sectors that already said they expected x routes to the new sector
   4. Run the accelerated simulation based on world age, taking into account any queued events in neighbor sections (city x sent y caravans via trade route z with a large amount of red-dye based goods so those could be particularly common in the new city)

Similar examples could be made for climate simulation - how does the temperature vary and impact crop growth through the seasons in some location? What if the player builds a giant mountain that blocks the warm wind from the equator? You can't have simulations take the changing world into account without somewhere to store that level of data. River simulation and weather are two more.

But wait - we pretty much could do that already with world entities! We totally could. I think. It is just code and some storage somewhere above chunks. So why sectors?

Long-term for aging servers and larger player counts we're going to hit performance issues from the sheer number of entities and things to track. Storing stuff at the world level is like global variables - use them sparingly!

The real reason for sectors is helping split apart entity storage to where we can have entirely independent areas. If two players are 200 kilometers apart there's no reason they need to know about each other for local data. Just chat and some other limited stuff like that. Heck they might as well be in different worlds. Oh!

I expect this would be a stepping stone to both multi-world and multi-node (wondered about those above in the scope statement?) as well as a new use of @Florian's Context architecture tweaks. I don't know how large sectors should be, but most likely they shouldn't all be independent from their neighbors. We might actually want to make that determination dynamically based on active player population and location.

EVE Online does something similar with their server nodes. How many solar systems one node serves changes dynamically based on player population. If a large battle commences the affected node can throw off outlying systems that aren't involved to a different node and focus all resources on the battle. Our sectors could be akin to their solar systems, which admittedly are better isolated from each other (connected by stargates) than our large pieces of contiguous world. Maybe more accurately we'd group sectors together in clusters, like EVE has solar systems in constellations, and one of our nodes would run one or more clusters.

Another theorized need I figure is that sectors wouldn't be adjacent with no overlap like chunks are currently, they would likely have a border a few chunks thick that both neighbor sectors would contain. That eases processing when entities (like players or creatures) are right on the edge between borders. Rather than switching what sector data is available each time a player crosses the line you'd stay in the one sector until you've walked a few chunks in. The system would need to be able to figure out what side is primary for some related entities.

I'm less sure about that though, since a fight between a few players and/or creatures right on an edge might not need sector data. Not sure what would. But if you are on a cluster edge where two different server nodes are serving each side there might be some need to have all the intense data/processing happen primarily on just one node. But in that case maybe you would've just kept track of the sectors better and not split them between nodes in the first place?

In any case we won't need multiple server nodes for quite some time. But I wanted to bring it up for future planning anyway since we still haven't split out gestalt-entity and could keep this in mind on that journey.

Multi-world is maybe more interesting and less complicated. There you'd have a truer comparison to EVE as two whole worlds would have a nice separation like two solar systems in EVE. With some form of travel you'd be able to move between them, but you don't need both in the same entity store / Context. Something as simple as splitting two entity stores might be a huge win for taking advantage of threading on many-core servers.

So in summary:

• Sectors would contain chunks, multiple sectors per world. Sectors can be used for data storage beyond chunks without making excessive world-level "globals" to allow for better world gen and simulation. Sector level data could be processed without any chunks live/loaded
  • Sectors would likely be of a set size like 32x16x32 chunks (to take chunk height into account), but maybe other options are worthwhile for optimization reasons (even 2D sectors if you just care about the main world surface for one particular simulation type?). Maybe you don't need a lot of layers high up in the sky etc. Unsure here.
• World simulation could occur in an accelerated fashion during world setup/preview plus when a new sector is needed (it can catch up to current world time). Large scale systems like climate simulation would have a home independent of chunks and could be consulted by local systems for details as the world changes. Although in some cases like a finite world (flat "planet") you might want a climate sim at world level, then deal with impacts on biome at the sector level.
• A Cluster would be a dynamic selection of sectors that could be isolated from other clusters as far as entity storage / other storage / Context is concerned. They could run in parallel as long as they stay in time sync. Keeps down storage sizes and allows for better multi-threading on a single server. On saving / exiting you'd probably still "just" write stuff at a sector or even chunk level.
• A Node would be a single server machine that can be part of a multi-node game server. A node can run one or more clusters independently of other nodes, excepting some minimal overhead like staying in time sync, handling chat, logins, etc. You'd likely have a single master node or even a controller node of some sort.
• A World is simply all the sectors making up a planet, a dimension, or some other geographically separated concept. You could still have infinite worlds that keep growing forever as each would have its own coordinate system, chunk storage, etc. Current "global" scope, nothing bigger exists at the moment.
• A Universe would be the next "global" up from world in a future where we support multi-world. Could probably have more layers like solar system, but that doesn't seem important yet.
• A Metaverse is just silly, but if somebody really wanted inter-server teleportation they could probably make it work this way. It came up at some point.

Forgive me for my almost certain architectural missteps or poor memory above. I'm sure I got some details wrong, so please help me correct them!

At current I'm only really thinking about getting started brainstorming and maybe working on the sectors and simulation over the coming months (may make this another GSOC candidate). Something else to fill in those boring idle moments between working hard on v1.0.0 issues and opening presents!

 

[Cervator]

Addendum: Surfaces Zones

A missing piece in the above is what to do about things that care specifically about one layer (like sea level), but not so much about other layers.

At present IIRC sea level is the only "surface" we declare and refer to, although I think we theoretically could declare other surfaces like a major cave level or flying islands. But sea level and any such other surface would be global if my thinking is right (and you don't use math tricks to cover a checkerboard pattern or something). With sectors you could declare a surface local to one or more sectors. So rather than a cave level being *everywhere* you could base its presence on noise or whatever applied to sectors.

A global surface still would likely make sense for some things like a climate simulator for the main sea level surface. And maybe you'd want a magma sea at a certain level underground for the whole world. You could choose between global and local. Not that a global layer of sky islands would necessarily be thick, they could be super sparse and not appear to be connected, but they'd likely still either be at one layer or generated generically all the way up. Instead you could just define multiple local sky island layers if you so chose to mix it up a bit.

I figure that would have some beneficial potential for pathfinding. I think @synopia already has a concept of floors in block-based pathfinding, it would probably be nice to cache known paths to get from one surface to another.

 

[chessandgo]

Chunk size - if chunks are smaller:

• less data is sent until its needed. This can help the networking aspect, and works as a simple anti-cheat for xray. You can xray if we haven't even sent you the blocks!
• easier, and more verbose metadata. fewer blocks means that its easier to analyze chunks in the background to obtain metadata. Become even more useful when all grouped together. (which may be useful for stuff like if the server should or should not send this chunk, or it should be sent to the rendering engine.)
• Maybe help new terrain generation. Less choppy loading as chunks are smaller, chunks are delivered to you faster, and in staller bursts of computing power.
• Might help with chunk recall? (more metadata/structured data to go off of)
• Maybe increase storage and undo optimization

 

[manu3d]

Chunk size is tied to performance. Current chunks are 32 x 64 x 32 blocks = 65,356 blocks or 2^16 blocks, the length of a short int. This is used for fast indexing, to quickly jump from the memory address of one chunk to another. Making them the length of a char (2^8 = 256 blocks) is likely too fine-grained for performance and going the next level up (2^32 = 4'294'967'296 blocks, the length of a long int) is likely to be too big for current hardware. At least some of the issues you are describing @chessandgo can be addressed by this proposal. I.e. the stuttered loading you report is likely a fairly constant-speed loading of chunks that are out of sight.

 

[Cervator]

So I noticed an update to Improbable's SpatialOS which had them launch their service into public Alpha via collaboration with Google. So think massive elastic cloud availability, maybe interesting hooks with AI, and so on, including machine learning.

In short: SpatialOS is the server side stuff for an MMO. They handle the multi-node hosting for massive worlds and you just code against their API to process workloads (players connecting and doing stuff in a world). Several notable games are already being based on it and with Google throwing their weight behind it (after some 20 million of earlier VC money) that's saying something.

What made it stick out and got me to post this here is a few striking similarities

• SpatialOS uses an entity-component system. Huh! Looks oddly familiar. Entities, Components, Component Updates (Events) and Workers (Systems). Interesting!
• Their architecture primer (scroll down on the front page till you hit "Architecture") looks exactly like how I would visualize Sectors, complete with some degree of overlap possible
• They have a Java API which again looks weirdly familiar. Sure the class names differ and you're doing callbacks instead of catching events, but conceptually the resemblance is remarkable to me
• One of the game snippets shown in their primer looks like the exact same kind of space arcade shooter as Destination Sol

Should we totes get onboard and build Terasology the MMO real quick? Well, no. It'll eventually be a commercial service (not open source, at least not yet) and there are still plenty of differences with them looking to be targeting Unity so far with more work to support other stuff coming. But it looks incredibly interesting to me at a nerdy level, like the kind of thing I would dive into and learn about if I actually had such a thing as free time. It could be a very cool thing to examine and get ideas from.

And hey, who knows. Maybe at some point in the future when they progress into Beta and beyond, and we've gotten Gestalt extracted and polished some more ... maybe somebody nerdy could find some time to think about how stuff might link together

(Edit: There are even EntityTemplates - prefabs! And some JSON. Okokok I'm stopping, more important stuff to do right now)

 

[Skaldarnar]

We get it, we should work on sectors

The scope of SpatialOS is way broader than what we are aiming at, using the same fundamentals in form of the ES. We are doing something right if there is that much potential in terms of scalability. The implementation of sectors could very well become a potential GSOC task for the summer - we have lots of ideas and concepts floating around, and a skilled student can definitely come up with a good design here.
In the far future, hooking up different Terasology worlds to a single universe where players can move between them sounds awesome. But let's start with our very own multi-worlds

 

[Cervator]

Here's a chat log from IRC of me trying to explain some ideas a bit deeper:

4:41:12 PM - Cervator: so to start a little higher up with the architecture
4:41:33 PM - Cervator: right now we just have chunks and some entities that can be marked as global, which is effectively "world" level since that's the largest thing that exists right now
4:42:25 PM - Cervator: i'm not actually sure exactly when a chunk gets unloaded - at least at some point it didn't necessarily unload just because the player can't see it (outside of view distance), chunks would tend to hang out maybe for easy reloading later
4:43:08 PM - Cervator: we have some challenges there even in the current system and at least a couple bugs like duplicate chunk loading in multiplayer (a request to load the same chunk gets issued twice)
4:43:23 PM - Cervator: so a good intro to a proposal like that would probably be digging into chunk sorting/ordering
4:43:44 PM - oniatus: interest yes but heading to bed the next time :) i'll stalk the logs tomorrow
4:43:50 PM - Cervator: righto :)
4:43:54 PM - Vizaxo: Yep, that makes sense
4:44:02 PM - Cervator: the idea i had with the sectors themselves were actually more about being able to keep multiple independent *entity* stores
4:44:07 PM - Cervator: less so about chunks directly
4:45:06 PM - Cervator: to begin with you might actually only have one sector in a world, no matter how much the player explores - although that's more of an experimental phase just to be able to start on the architecture
4:45:26 PM - Cervator: so sectors aren't of a set x,y,z size
4:45:47 PM - Cervator: and honestly i'm not even sure if a full multiple entity stores / multi-world is possible quiiiite yet
4:46:24 PM - Cervator: in large part since gestalt-entity is a thing now (Terasology's entity system, extracted into an external lib)
4:46:34 PM - Cervator: so if we do any huge overhauls in engine they should probably be together
4:46:50 PM - Cervator: that's partly why just having a single sector might actually be enough for the GSOC work period
4:47:22 PM - Cervator: but conceptually the idea would be to have something be on top of chunk organizing enough to where it can spot two entirely separate areas, like the two different continents i think i used in an example somewhere :)
4:47:38 PM - Cervator: then at *that* point it intelligently cuts the world entity store in two
4:48:38 PM - Cervator: but moving from plain chunk sorting/ordering to an "affinity" system to figure out when two large parts of the world should sub-divide as far as entities goes is probably quite a challenge on its own - thus may just aim for one sector for gsoc along with a bunch of preparations, like improving sort/order stuff
4:48:50 PM - Cervator: as far as chunks go
4:49:01 PM - Vizaxo: Ok, cool
4:49:06 PM - Cervator: i'm not sure how big the impact would actually be - sectors aren't really for "storing" chunks
4:49:18 PM - Cervator: i don't think it'll impact existing world gen much if at all, for instance
4:49:28 PM - oniatus: Sounds like a quad-tree like data approach :)
4:49:41 PM - Cervator: could be, i'm a design guy not an architect, hehe
4:50:11 PM - Cervator: i think it'll come down more to contributors defining entities at a more exact scope
4:50:19 PM - Vizaxo: So what exactly do entites do in the game? I haven't really touched them yet
4:50:23 PM - Cervator: like block entities vs chunk entities vs sector vs world vs universe
4:50:39 PM - Cervator: so entities is a huge concept, hit the engine wiki sometime there are a few pages there :)
4:50:57 PM - oniatus: For a simple understanding: It's like a class but without hard wiring
4:50:58 PM - Vizaxo: There's an engine wiki? Is that on GH?
4:51:10 PM - oniatus: https://github.com/MovingBlocks/Terasology/wiki/Entity-System-Architecture
4:51:15 PM - Cervator: yep :D
4:51:27 PM - Vizaxo: Ooh, this seems like something I should have already read :p
4:51:32 PM - Cervator: so a chest is backed by an entity, and would count as a block entity
4:51:33 PM - Cervator: hehe
4:51:40 PM - Cervator: it is a little important yes :D
4:51:54 PM - Cervator: that entity is in theory only needed if the player is within range of that block
4:52:14 PM - Cervator: if that block isn't loaded (its containing chunk isn't loaded) then nobody really cares
4:52:20 PM - oniatus: It's not that hard though :) instead of writing a car class with a position variable and a storage for the passengers you create and entity and add a locationComponent and a PassengerRoomComponent to it :)
4:52:31 PM - oniatus: If you need 4 tires, then add a tireComponent to it
4:52:36 PM - Cervator: unless you go smart-ass and start playing with quantum tunneling and connect the chest with some other chest far away
4:53:09 PM - Vizaxo: But currently the chest is stored globally, is it?
4:53:16 PM - Cervator: at *that* point you wouldn't be able to just keep that chest's entity at the chunk scope - you might need it even if that chunk isn't loaded
4:53:29 PM - Cervator: there's only one entity store right now
4:53:29 PM - oniatus: so basically the entity system decouples data structure and makes it re-usable. It also adds blueprinting with prefabs and persistence via the librabry
4:53:51 PM - Cervator: but i think a chest's entity would only load if you load its chunk from disk
4:53:53 PM - Vizaxo: Ok, that makes sense, thanks :)
4:54:05 PM - oniatus: Should be per-chunk unless it is not alwaysRelevant
4:54:16 PM - Cervator: a true "world" entity at current is marked as, yep, alwaysRelevant
4:54:27 PM - Cervator: see? oniatus should totally mentor this or something!
4:54:39 PM - Cervator: so even on just loading the world you'd get those entities
4:54:58 PM - Cervator: so that's a chest - currently chunk scope
4:55:10 PM - Cervator: the magic dome in Light & Shadow? alwaysRelevant, so world scope
4:55:14 PM - Cervator: there are no other scopes at present
4:55:19 PM - Vizaxo: Ah, ok
4:55:33 PM - Cervator: sector scope would be something that's above chunks, but (eventually) below world
4:56:45 PM - Cervator: so much like if you didn't have the chest's chunk loaded you don't need that entity, you might not care to have a particular sector-scoped entity loaded if it is only relevant to continent A yet nobody is on continent A
4:58:07 PM - Vizaxo: Yep, and I can now better see how that relates to possibly leading to multi-node and multi-server
4:58:09 PM - Cervator: Vizaxo: so does that help give some new enlightenment on the concept? :)
4:58:11 PM - Cervator: yup
4:58:18 PM - Vizaxo: Yeah, definitely, thanks
4:58:24 PM - oniatus: maybe one example for sectors could be towns. As long as some chunks of a town are active you may want to keep a town-managing entity alive that keeps track of town like stats (happyness etc)
4:58:31 PM - Cervator: multi-world may actually come before multi-sector-per-world
4:58:51 PM - oniatus: But if the entire town is unloaded the entity may be persisted and removed from memory
4:58:53 PM - Cervator: because you can much more easily split apart the entity store when you have two distinct entirely unconnected worlds
4:59:03 PM - Vizaxo: I was imagining something different, but you could plobably implmeent the thing I described with the entities
4:59:12 PM - Cervator: yep for the town example
4:59:35 PM - Cervator: you don't want to tie the "town entity" to a given chunk/block, yet you don't want it to be loaded if its whole continent is offline
5:00:06 PM - Cervator: so as far as the proposal goes it is a fair bit more about that sort of architecture and world setup than outright biome generation or climate simulation and such
5:00:13 PM - Cervator: i would suggest:
5:00:56 PM - Cervator: 1) Examine and improve the current chunk loading/unloading/sorting/ordering/etc in part to make it easier later to spot when there are completely independent groups of chunks with no connection points between them (if so: candidate for sector split)
5:01:26 PM - Cervator: 2) Implement minimal Sector logic that just offers a new entity scope, but only maintains one sector per world (maybe multi-world could be a stretch goal)
5:02:03 PM - oniatus: LocalChunkProvider is a great class to keep one busy for some days =)
5:02:36 PM - Cervator: 3) Improve world setup in the first place: allow for more phases during world setup and generation, like generating a world map then starting to prep sector scoped entities like "town entities" that are tied to a location on the big map, but have no chunks at all until a player gets near
5:02:50 PM - Cervator: yeah i think just those three items could make a full GSOC item
5:02:53 PM - Vizaxo: oniatus: I'll have a trawl through it :p I did have a look through some of the low-level engine code, so I've got a bit of an idea where it fits in
5:03:17 PM - Vizaxo: Great, that all makes sense
5:03:52 PM - Cervator: stretch goal for 1st item could be simply logging when the condition seems present for "Oh hey, current world state would support splitting into two sectors, here's a bunch of useful info, just not actually doing anything yet"
5:04:38 PM - Cervator: item 3 we could go into some more detail later, but check out the world preview functionality for some initial inspiration (and its related issues/bugs/challenges)
5:05:01 PM - Vizaxo: Ok, will do
5:05:04 PM - Cervator: in short, current state goes something like:
5:05:18 PM - Cervator: 1) Create world -> customize modules if desired -> preview world if desired -> play!
5:05:29 PM - Cervator: when the new way could be something like
5:07:05 PM - Cervator: 2) Create game screen -> customize modules if desired -> customize world parameters (finite size? round? donut? cubic planet? halo? number of worlds?) -> pre-generate a world map (of some size) showing continents and such -> allow player to customize more specific world config like frequency of cities then regen world map -> accept config and start generation, but wait for player -> click "enter world" when ready
5:07:50 PM - Vizaxo: Ok, that sounds pretty awesome
5:07:52 PM - Cervator: could even have a stage where you've accepted world config/map but then want to explicitly name some of the cities, or place some extras by hand
5:08:03 PM - Cervator: check out a video of the Dwarf Fortress world generation :)
5:08:09 PM - Cervator: it is a whole process
5:08:19 PM - Vizaxo: I need to try DF; I tried it once and swiftly rage quit
5:08:28 PM - Cervator: another fun part: during world gen in DF *it simulates multiple centuries of world history*
5:08:35 PM - Cervator: while showing you things changing on the map
5:08:48 PM - Cervator: we don't need to bother with chunks for that kind of simulation at all
5:09:04 PM - Cervator: and we wouldn't store any of it as chunk/block entities
5:09:26 PM - Cervator: player could also pick an actual spot on the world map where they want to spawn
5:10:17 PM - Cervator: i think a bunch of that is probably more valuable in the short term than really digging deep with the sectors themselves - we can start preparing the support for that but maybe not hit the trigger until gestalt-entity is ready for integrating back in the game, replacing the internal version
5:12:58 PM - Cervator: oh, and all that didn't even touch on surfaces/layers
5:13:22 PM - Cervator: that's another sort of layer above chunks - i'm sure it is useful for something but i'm not entirely sure about a lot of deeper details yet
5:14:27 PM - Vizaxo: Is that to do with having thigs like a surface layer, cave layer, sky-island layer, etc.?
5:15:00 PM - Cervator: yeah, since you could easily imagine things that would be specific to a layer
5:15:16 PM - Cervator: so they're very similar to Sectors, but more static since a surface doesn't change nearly as much
5:15:28 PM - Cervator: a layer could have its own map
5:15:43 PM - Cervator: so there's one map for the sky islands, one for the main overworld, one for a mega-cave layer etc
5:16:30 PM - Cervator: Vel0city mentioned something similar was being used for the Realistic Terrain Generation thing, something i'd be curious to learn more about sometime
5:17:19 PM - Vizaxo: Ok, so they would come into play in the preview stage, and can be seen/modified in the same way
5:18:47 PM - Cervator: yeah that could be another config option. Want a sky layer? Sure, here you go. View each major layer in its own tab
5:19:35 PM - Vizaxo: Yep. And I guess you could view multiple worlds in a similar way?
5:19:58 PM - Cervator: yeah probably
5:20:08 PM - Cervator: it is almost like a surface is a sub-world
5:20:23 PM - Cervator: but one you could travel to via regular means
5:20:32 PM - Cervator: good for long distance AI pathfinding
5:21:13 PM - Cervator: only way to get from point A on the surface is walking to the sky-port at point B then taking an air ship to the landing pad on the sky island for point C then walking again to get to point D
5:22:24 PM - Cervator: unless you have wings, anyway
5:22:45 PM - Cervator: then if your stamina allows you to cover the distance then you can consider it an option to fly direct yourself

 

[Vizaxo]

This is an update on my GSoC project, which includes implementing the sectors concept. This thread will be quite long, but it contains over a month worth of work. I'll be doing posts weekly from now on, which should be in more digestible chunks. For an introduction to my project, feel free to check out my blog post on the subject (you can scroll down to "What is my project?" for an introduction to the project).

Since that blog post, caches have been renamed to pools. The name 'cache,' especially when used in a context relating to computing, implies some form of local saving against a master store, but that isn't what they're doing here. 'Pool' is a better term, because they are splitting the whole selection of entities into smaller discrete groups to be stored/processed separately.

Issues/PRs

There's an issue on GitHub ([Discussion] Sectors Implementation/API #2976) where discussion of the API and features of sectors are being discussed, so feedback on the architecture/API is appreciated over there.

Also feel free to check out the pull requests, and submit any feedback (whether it's about the project in particular, or coding style/fixes, etc.). Soon I'll be cleaning up and re-applying these pull requests against a v2.0 branch, so they might go out of date (I'll try to update this thread when that happens).

[WIP] Sectors #2975
Rename cache to pool #1
Bug fixes and method cleanup #2

Progress so far

The first thing I did was implement the EntityPool, which involved taking lots of the logic for creation and storage of entities out of the EntityManager and putting it into its own class. The pool API is mostly about creation and retrieval of entities, and the pool implementation also needs to store the EntityRefs and components associated with those entities.

Most of the EntityManager's methods, such as the creation methods, have been made to work on the global-scope pool by default. Specific methods to interact with sector-scope entities have been added, such as createSectorEntity, which creates an entity in sector-scope.

Pools can be made up of other pools. The SectorManager is a pool, but it doesn't directly hold entities, it holds multiple pools for sector-scope entities (each of these sub-pools is a sector). The EntityManager is another pool, which holds a pool for the global entities and also holds the aforementioned sector manager.

This is easier to illustrate in a diagram:

Spoiler

I couldn't find an easy way to create ellipses in GIMP, so I hope my hand-drawn potato-shapes suffice:

The EntityManager used to have quite a lot of code duplication in its methods for creating entities, as there are over 10 different methods used to create entities (e.g. creating an entity with a list of components, a prefab, or in a certain position). There were also several different methods to retrieve the EntityRef associated with an entity ID, despite all of them doing the same thing. This meant that there were lots of different places where entities and EntityRefs were created, so it was hard to update all of them when code was changed. This led to bugs such as the entities not being properly assigned to pools, which meant they weren't stored properly, and fetching the entities didn't always retrieve them all.

I have refactored this code to only have a single function that retrieves the EntityRef associated with a given entity (getEntity). There is also an EntityBuilder available, which can be used to build up an entity by adding a prefab and/or components one-by-one. The creation methods have been refactored to use this builder, which also helps to reduce code reuse.

The iteration functions (getAllEntities to get all entities, and getEntitiesWith to get all entities with the given components) were present in the previous EntityManager, but they had to be changed to aggregate the iterables from each pool within the EntityManager. The Iterables.concat method from Guava was very useful for this, as I could just concatenate the iterables returned by each pool contained within that parent pool.

I also changed the implementation of the EntityPool's getEntitiesWith from an imperative style with nested loops to a more declarative stream-based implementation. This new implementation is much more concise, and, in my opinion, is much easier to understand.

Here is a comparison of the code:

Spoiler

The original imperative code (link):

  @SafeVarargs
  @Override
  public final Iterable<EntityRef> getEntitiesWith(Class<? extends Component>... componentClasses) {
      if (componentClasses.length == 0) {
          return getAllEntities();
      }
      if (componentClasses.length == 1) {
          return iterateEntities(componentClasses[0]);
      }
      TLongList idList = new TLongArrayList();
      TLongObjectIterator<? extends Component> primeIterator = store.componentIterator(componentClasses[0]);
      if (primeIterator == null) {
          return Collections.emptyList();
      }

      while (primeIterator.hasNext()) {
          primeIterator.advance();
          long id = primeIterator.key();
          boolean discard = false;
          for (int i = 1; i < componentClasses.length; ++i) {
              if (store.get(id, componentClasses[i]) == null) {
                  discard = true;
                  break;
              }
          }
          if (!discard) {
              idList.add(primeIterator.key());
          }
      }
      return new EntityIterable(idList);
  }

The updated declarative stream-based code (link):

  @SafeVarargs
  @Override
  public final Iterable<EntityRef> getEntitiesWith(Class<? extends Component>... componentClasses) {
      return () -> entityStore.keySet().stream()
              //Keep entities which have all of the required components
              .filter(id -> Arrays.stream(componentClasses)
                      .allMatch(component -> componentStore.get(id, component) != null))
              .map(id -> getEntity(id))
              .iterator();
  }

One of the most difficult tasks so far was making sure proper information on the entity scope is serialised, so that they are saved properly. When saving the game, the only information that is stored is whether the entity is in the global scope or the sector scope. Specific details about which pool the entity is in aren't stored, which allows the SectorManager to reallocate the entities between pools as it sees fit when they are loaded into the game.

I had to modify the protobuf information about the entity to include a scope field, and ensure that filed was properly applied to the EntityRef, and also properly taken into account when loading/unloading the entity.

Next steps

The main implementation of sectors is done now, but there are still a few things to do (such as allowing entities to move to other sectors). As mentioned earlier, a v2.0 branch will be created, so pull requests can be made against that branch. I'll be rebasing and squashing the commits down to keep a nice git history and make them easier to review.

Some features of sectors, such as allowing the SectorManager to split its pool into multiple different pools depending on the game load, are probably not going to be implemented in this GSoC project. The underlying architecture is there, but I don't think there would be much benefit to doing it now, so waiting until performance becomes an issue and being able to profile and plan around the actual circumstances will be more effective.

The next step is to actually implement sectors so that they can be seen in action. I am going to explore the Dynamic Cities module, which was created for last year's GSoC project, to see if the cities can be moved into sector-scope, allowing simulation of the cities while the player is far away and the chunks aren't loaded.

 

[Vizaxo]

Sectors

This week has involved more fixes and cleanup, including bug fixes, code quality improvement, and more documentation.

I've also added the moveToPool method to the EntityManager, which allows entities to be moved between different pools. This can be used in changing the scope of the entity, by moving it between the global- and sector-pools, or by the sector manager to rearrange entities in the sectors. The setScope method of EntityRef uses moveToPool to move the entity into the appropriate pool when the entity's scope is changed.

I've also added some unit tests for moveToPool and setScope. These were useful to implement, helping to find a bug: the EntityRef was destroyed and a new one had to be created when moveToPool was called, which I hadn't considered a problem, but seemed obvious whenn I wrote the test. The tests were definitely useful, so I'll continue to write more in the future.

I updated getEntityPool (now renamed to getPool, which I think is just as clear but more concise) to return an Optional<EngineEntityPool>, rather than just an EngineEntityPool. This allows for much cleaner handling of values that could otherwise be null, such as when an entity doesn't have a pool, or when an invalid id is passed in.

Here's the PR that contains the above: https://github.com/Vizaxo/Terasology/pull/3

DynamicCities

One of the goals of the sectors project is to implement sectors in a module, to show them working in practice. The DynamicCities module, created during GSoC last year, was chosen as a good candidate for this, as secotrs can be used to allow the cities to simulate while the player is away, ideally with a minimal performance penalty.

I've been testing DynamicCities and reading through the code to find out how the simulation works, and how it can be improved with sectors. I found out that the DynamicCities settlement entities are marked as alwaysRelevant, which means they won't unload when the chunk they're in unloads, so they still do simulation while the player is away. I need to do more testing and logging to check how much simulation is done (I think extra blocks stop being added to the queue after hitting a threshold, so there might be a limit to the amount a city can grow while it is unloaded), and to find out if it can be adapted to use sectors.

I have experienced a crash multiple times where entering a city after being away for a long time will cause the game to exceed the GC threshold and crash, so perhaps altering the way the simulation is done can fix this. This is also worth investigating further, in case it's unrelated or not caused by the city loading; finding out steps to reproduce would be useful.

The ideal situation is one where unloaded cities can continue to simulate at the same rate, so they keep evolving as if the player was standing next to them. However, this could cause performance problems, especially in large worlds where lots of cities have been discovered. One solution is to delay all of the computations until the city is reloaded, but that might cause huge lag spikes when the city is reloaded. Another solution is to run designated sector-simulations on their own threads, but that might require big changes to systems/events, and it's hard to know how much of an improvement that would give at the moment.

I'm going to do more testing and add logging info to DynamicCities to try to figure out where the bottlenecks and possible improvements are.

 

[Vizaxo]

v2.0.0 branch

I've rebased my changes onto the develop HEAD, and squashed the commits down into a few meaningful stages to keep the history clean.

v2.0.0 branch PR: https://github.com/MovingBlocks/Terasology/pull/3009

Sector simulation

I've added a SectorSimulationSystem, which allows sector-scope entities to perform simulations depending on whether the chunk they're in is loaded or not. It's still got some work to be done on it, but this first implementation is working so far.

Simulation PR: https://github.com/Vizaxo/Terasology/pull/5

Dynamic Cities

I've started updating DynamicCities to use the sector simulation outlined above. This makes the settlement and region entities sector-scope, and moves the simulation code from the update loop into simulation events. This allows the city growth to be simulated when the chunks aren't loaded, but the actual block updates only occur when the relevant chunks are loaded. Again, it's still a WIP, and and will be updated alongside the simulation system.

PR: https://github.com/Vizaxo/DynamicCities/pull/1

 

[Vizaxo]

SectorRegionComponent

The SectorRegionComponent allows sector-scope entities to watch multiple chunks, stored as a set inside the component. This means that whenever any of these chunks is loaded, the entity will be counted as loaded and sent a LoadedSectorUpdateEvent at regular intervals, allowing it to update things that rely on the world (blocks, entities in the world (e.g. animals, NPCs), etc.). The set of watched chunks can be added to and changed as it simulates,
allowing for, for example, a city to grow, or a herd of deer to move around.

PR: https://github.com/MovingBlocks/Terasology/pull/3022

Dynamic Cities

I've further updated DC, with sector simulation and implementing the SectorRegionComponent, so the whole city zone counts as part of the city (this means that the city will update if any chunk is loaded, not just the central chunk).

PR: https://github.com/Terasology/DynamicCities/pull/30

I also started reducing use of the region entities which are created during world generation in favour of directly accessing the generation information from the facets. This is a WIP though, so I haven't made a PR for it yet.

 

[Vizaxo]

Allowing a different simulation rate depending on whether the entity is loaded or not

Previously, sector entities had a constant simulation rate, which meant that the maximum time between simulation events was the same regardless of the state of the sector entity or the chunks it had loaded. This meant that the rate had to be set assuming it was loaded, because otherwise the player could be near the entity and not see any effects from it for a long time. However, this meant that it would have to simulate too often when the player was far away, and too many entities doing this might cause performance problems. As entities will likely not have any watched chunks most of the time (depending on which sector entities are in action, and how the players are spread through the world), to maximise performance the entities should be able to simulate at the minimum possible rate when unloaded.

To do this, I've split up the maxDelta into unloadedMaxDelta and loadedMaxDelta, so there are 2 different values for the simulation rate depending on whether the entity is loaded or not.

PR: https://github.com/MovingBlocks/Terasology/pull/3041

Removing alwaysRelevant, and instead using the sector scope

This change replaces the entity's alwaysRelevant property by putting that data onto the EntityScope. There are currently 3 scopes: gloabl, sector, and chunk. Global- and sector-scope are alwaysRelevant, but chunk-scope is not. The default scope for a new entity is chunk-scope, so it is not alwaysRelevant by default.

PR: https://github.com/MovingBlocks/Terasology/pull/3037

Preparing for surfaces and updating the world preview

The next part of the project will involve surfaces (mentioned above in this thread) and updating the world preview.

Changes to the world preview will likely involve allowing sector-scope entities to pre-simulate before the world starts (so, for example, cities can start growing in the world preview phase) and have those changes displayed on the preview, as well as being able to adjust the simulation time and see how that changes the world.

Surfaces will also be shown on the world preview, probably with a button to switch between which surface is shown (so, for example, you can toggle between showing the surface layer and the cave layer, with each surface detailing how it is shown on the world preview).

 

[Cervator]

In other news we brainstormed terminology a bit and thought "Zone" would work better than "Surface" for that concept.

"Surface" might too easily call to mind the entire surface of, say, a planet, or get confused with simply referencing the surface of a world. But the concept actually calls for the possibility of even sub-dividing the primary world surface as well as other things you might consider layers (sky islands, massive cave levels, etc). Imagine an infinitely generated flat world: the primary surface is going to keep growing forever, and whenever a player provokes more world gen along the edge that's more stuff getting added. If you want to have discrete maps (as in, showing a specific major continent) you need to be able to say "Hey within these bounds this is continent A" - or a zone.

Zone in MMO terms have long been used for smaller separate areas where the game would be able to only load up game assets needed within that area. This is kinda like that but with way larger zones and without necessarily having any sort of loading screen when traveling between them. It may also help since a "Surface" wasn't meant to just contain the top layer of blocks along some conceptual part of the world - more like a large slice of world you could declare - think a three layered cake, top fluffy layer is a band of sky islands, middle is some nice vanilla and the bottom is delicious chocolate ...

Anyway. Enough about cake. Zone could perhaps also help clarify you could just as well have a limited size underground, said sky island layer, another continent, and so on. Although defining "zone" to mean that may still sound pretty artificial, maybe more so than surface, but with less terminology clash.

Finally we also came up with the concept of Zone Connectors which would be a world gen concept meant to connect zones. Without one you just have space of whatever is the most prominent material - air between an overworld and sky islands, water between two distant continents, and plain old ground between an overworld and a major cave layer far below. There is still "stuff" in that space (birds in the air, fish in the water, minerals in the ground) but that's generic between the edges of zones.

An explicit zone connector example would be a giant beanstalk that connects the overworld to sky islands, or a bridging staircase of floating islands a la Avatar. You could have a massive planet scarring chasm that leaves a hole between the overworld and a cave layer. And so on. Keep in mind there are two distinct types of caves we talk about here: regular old random caves that are just sunk into the ground within a zone, and a whole other map-based cave world layer that would go far below (for example the Inferno world layer @Isaac made for GCI). You even could have regular caves working as a connector between zones, but IMHO you should set that explicitly. Then in other cases you can happily define new zones and let the world slot them into appropriate height layers so they don't bump into each other. Or if we get really crazy maybe we can come up with creative ways to let them mildly overlap anyway ...

On a side note "zone" does appear in DynamicCities as well as a city zoning concept, within districts. That's not really a major term clash but the usage in DC could possibly be tweaked a bit for clarity (like always referring to "zoning" of an area rather than ever refer to a "zone")

 

[Cervator]

Just randomly digging around in the forum reminded me I posted this other thread about 2D mapping possibly using Tiled. Dunno if that might relate here as an option to help work on surfaces/zones in a more static world. Wanted to post the link here to have it handy.

 

[Sarthak Khandelwal]

Hello everyone, I've written my Google Summer of Code Proposal on Multi World (#3146). I would appreciate feedback of any kind on it!
The full proposal can be found here.
Thank you!

 

[Cervator]

Bumping this for GSOC 2018 as we have multiple related proposals floating around, like multiworld by @Sarthak Khandelwal (TheFlash) - I just reviewed that one again but really need some more volunteers with some exposure to the area to chime in

We also came up with a nice diagram for a new "Create Game" UI flow that would also support world shape, infinity vs finite, static worlds instead of generated, etc:

 

[Cervator]

Another new concept. More will come and some will deserve their own threads, but for now I figure keep going here with some related concepts until somebody feels ready to bite off a chunk and go work on it in a focused way elsewhere. For instance the cubic planet / finite world and multi-world GSOC stuff will surely introduce a bunch of new things like local world entity pools and world faces for defining how a single world acts along the various axes of our 3D coordinate system. We also have ways to expand on the save game system to better ship predefined worlds and such.

Dynamically Seeded Content

A concept that has come up from time to time is the idea of seeding content in ways not directly related to which modules you initially create a world with, even content that doesn't live in a module in the first place. Some games do a kind of alternative form of multiplayer in which everybody plays single player (or in some cases limited multiplayer) but can encounter content from games played by others. This naturally has some risks and would ideally contain some curating of the shared content.

What reminded me about this topic and finally made me write about it here in the forum was an article on massivelyop.com about Worlds Adrift adding 300 brand-new player-made islands - an example of such content. The game author made an island making tool available and allowed players to submit their designs, then picked 300 good ones and added them to the primary world.

This somewhat gets into content created during play time, much like some Minecraft worlds become elaborate settings where many players have created content in the world. Example: Wynncraft. I don't know if that content is solely used in that single world, but imagine if each quest, each dungeon, each piece of content could be packaged up and inserted dynamically in other worlds in some appropriate location, without being explicitly configured during initial world creation or a later update stage.

There are two sides to this concept: packaging up the content and seeding it elsewhere. It could go something like this:

1. Encourage players to make repackage-friendly content - we have that to a degree already with StructureTemplates, but they're relatively smallish. Imagine small scenarios or quests as other bits of similar content, as well as larger world features (coincidentally more distinct world features and how to place them is another GSOC item)
2. Dynamically scrape or manually mark out compatible content (where an author has opted in / is doing the marking) from actual games (not just brand new modules) and gather it in some repository. Not necessarily a regular module repo, think more of a central live database
3. Dynamically seed such content into other worlds, as a sort of foreign / imported content that isn't module based (gets loaded out of central DB). Smaller features could be added during regular chunk gen or even be triggered a la GooeysQuests style. Larger features could be placed during a new phase of world gen where a higher-than-chunks pass tries to organize a sizable new part of the world, possibly even a new Surface/Zone (say a player arrives at a new continent or breaks through to a new cave layer)
4. Over time expand what can be processed that way to more types of content, like larger floating islands. Whole continents / surfaces / zones might be too big since that's practically a sub-world situation probably from worldgen moreso than in-game player-built content. Those could still be seeded but probably would be created more normally as modules and just registered for such a special secondary purpose ("surprise" layers in the world that you didn't explicitly select/configure)

Suddenly you have the ability to both support larger player groups in creating something like Wynncraft, as well as harvesting content across many worlds like it to re-seed it in new worlds. Over time you could as a server admin opt into new sources for such dynamic content, curate it to a higher degree to fit a target theme you have in mind, and share your own content later on.

If the players have explored most the available content add a new world, a new layer, or a new faction, to help liven things up again. Maybe you could even orchestrate it in such a way that you can trigger an invasion of content (like a powerful and aggressive NPC empire - hello Riftwar Cycle!) being introduced at an existing location, where it would envelop a larger area and bring with it new quests, challenges, structures, creatures, and so on.

To be clear: This is not in the slightest meant to be considered for any sort of work this GSOC. But it could be built on in the future, after further maturation of areas like multi-world, structure templates, quests, surfaces/zones, and even the server facade to where you could maintain an existing game universe and add new stuff with a button press.

 

[Cervator]

On another related note LaysDragon (on Discord, no forum account yet?) made a nice diagram after some sector / sector entity scope talk:



Although I think there's an error on the middle right side where "16 pies" should be "16 muffins" ?

It is nice to see a diagram like that and it has the interesting case of a partially unloaded system feeding coarse grained simulated work from sector scope into fine grained simulation in a loaded chunk.

Made me think of other potential issues, like what if some completely other system made a goddess of apples angry every time an apple is consumed? Normally you'd listen for the event processing the apple, but if that logic is short-circuited, what do you listen for?

I wonder if we could have fine grained event handlers automatically also consider a coarse grained single event doing processing in bulk. So instead of catching 6 AppleEaten events you'd catch 1 BulkAppleEaten event thrown with a count = 6 by the coarse grain simulation. That could perhaps even be used without sector scope being involved as large machines bulk up in quantity processed.

We have a somewhat similar example of how to deal with block change events in bulk, which was raised as a performance issue in the past and led to some activity on GitHub. But then the higher performance bulk handler turned out to be missing something (that might be another thing linked from that PR). Wonder if we could somehow use the granular event handling to project an appropriate response in a single action?

Another similar situation: catching up with some types of simulation that just pause and tracks time elapsed, then if needed (player enters range) attempts to fast-forwarded the needed activity.