[dreamingincode]

Thanks for the explanation! I happened to be thinking of similar multithreading ideas (chunks and ping-ponging states) recently, but was stuck on what happens when computation happens across chunks in multiple threads. e.g. an object move across chunk border, or an object interaction affecting two objects in different chunks. Could you elavorate on your approach about these? I'm really curious

[ItsFirefly]

Good follow-up question! As for the read state, you're already golden in the sense that you only read data and don't update it. If a chunk needs world or entity data from a neighboring chunk—or even halfway across the world—you can just follow pointers there and you know the data is available and accurate.

For the write state, you're absolutely right that entities will need to transition between chunks. The server looks up the destination in the "active chunk set" I mentioned and then uses per-chunk std::vector<>s guarded by a mutex to push "migrating" entities. This requires a mutex since multiple CPUs/cores/threads/chunks can be pushing entities to the same destination chunk. These mutexes largely have zero to little contention.

Does that answer your question in an acceptable way?

[dreamingincode]

Thanks! The idea of having a list of migrating entities per chunk is good, and it avoids locking on the list of all entities in a chunk. But I still have some confusion about it:

> The server looks up the destination in the "active chunk set" I mentioned

but what if the entity teleports to an inactive chunk?

> and then uses per-chunk std::vector<>s guarded by a mutex to push "migrating" entities.

Will these migrating entities participate in later calculation within the same tick, or are they excluded? If excluded, what happens when there are two mechanisms that mutates that entity, but the first one put it into the migrating list of another chunk? If included, the thread of which chunk will continue this calculation?

And when some kind of mechanism mutates two entities in different chunks, which thread is chosen to run this mutation? And how does it mutate the state for an entity in the other chunk?

Meanwhile since you mentioned ticks, (just to be sure) are you using a barrier per tick to wait for all threads to finish the same tick? When are the migrating entities merged into the main list, and are you using another barrier for that?

[ItsFirefly]

Really getting into the nitty-gritty here. If an entity migrates to an inactive chunk, I keep the entity "on hold" and add a "chunk set mutation" to the active chunk set so that the set is expanded in the next tick. The processing thread for this newly added chunk sees that no data exists yet and synchronizes the state from the backend during the subsequent tick. On this tick the entity gets added to the new chunk write state and disappears quietly from the old chunk in the next tick since it isn't "on hold" or copied anymore.

As for the processing per tick: the entire active chunk set gets semi-randomly processed by threads. You'd be absolutely right that the order of operations isn't always deterministic. An entity not being processed for a tick doesn't happen since the old chunk will still process entities that are "on hold", but only perform a subset of operations. Double-processing does occur and this is sometimes visible while playing with a chat message being duplicated. This happens pretty rarely and I took care to make sure occasional double-processing doesn't interfere with gameplay mechanics.

As for synchronization: yes, each tick all processing threads join together and the server performs minor central processing and scheduling. Then the next tick begins and all threads are started again.

[dreamingincode]

I see. It seems sometimes we do have to live with non-deterministic behaviors or even small errors.

I'm still unsure about the following question from your answers: > when some kind of mechanism mutates two entities in different chunks, which thread is chosen to run this mutation? And how does it mutate the state for the entity in the other chunk? My initial thought was this would require adding locking on every entity, since it might be accessed from another chunk/thread. But that's clearly not ideal. Maybe have a separate list for outside-chunk changes, and merge them with internal changes later?

And regarding having two states: How/when are you sending world state to clients? My thought was to clone the current state periodically and send it to clients (can sending takes less than one tick? I don't have an idea). Sending state to clients seems to be needed if the game needs client side predication, hence this question.

[ItsFirefly]

I think your first question is actually supposed to be: what if a single (not two) entity is modified from multiple chunks?

All external effects that can happen to an entity are written to an atomic integer that tracks healing points, damage points and effects like poison and stunning. Angeldust currently runs on CPUs supporting atomic integers everywhere, so this doesn't have to fall back to mutexes. On platforms/compilers without atomic integers I have a software-fallback that uses mutexes for this, but currently it's not used anywhere.

Most world state is compiled into flat byte arrays each tick to save processing time, since many clients can be in the same area at once. The server bundles these world state byte arrays for chunks near a client together and sends them over the network. The client interpolates from these updates. What you see on screen lags behind subtly to make sure animations are smooth. I think this happens in most online games since you don't really want to extrapolate.

Angeldust's game pace and mechanics are designed so that the interpolation doesn't affect your aiming accuracy or game experience too much.

[dreamingincode]

Thank you again for all the explanations!