7 ms·

This looks impressive. Can you go into how you implemented the immutable world state each tick a bit more? I'm developing a game myself, and figuring out a goo

by suby 7y ago

This looks impressive. Can you go into how you implemented the immutable world state each tick a bit more? I'm developing a game myself, and figuring out a good method of multithreading it took a lot of work. While I am content with the results, I wouldn't say I arrived at a good solution. It sounds like you went with a purely functional approach? Did you rebuild the entire gamestate each tick, or keep a list of changes you needed to make to the relevant data?

ItsFirefly 7y ago
I'll reply more in depth after my livestream, but it's a very good question. You can hop on YouTube right now to discuss it if you want. There's a bit of banter going on, but I might be able to squeeze in some useful replies in between.
sxp 7y ago
https://youtu.be/1PhArSujR_A?t=988 https://youtu.be/1PhArSujR_A?t=988 was Carmack's presentation on an immutable Haskell game engine. Unfortunately, he doesn't go into too much detail. https://news.ycombinator.com/item?id=15036591 https://news.ycombinator.com/item?id=15036591 was the previous HN thread about it.
ItsFirefly 7y ago
This question was the most asked one during my livestream. It's a good one! Even though it's 01:33 right now after a 7 hour livestream, I'll try to answer it as clearly as possible, building from the foundation up to the high level. The Angeldust game world is tracked in an "active chunk set". A chunk is a 2D part of the world, 32x32x64 in-game blocks (meters). The active chunk set tracks only the chunks that contain, or are near, players. This chunk set is processed in parallel on any number of threads/cores configured in the server settings file. Angeldust tracks two states for the data contained in each chunk, kind of like an array of size 2. Each tick, one state in the array is the immutable "read"-state and the other is the mutable "write"-state. Every tick these states ping-pong between the roles. During processing the server processes the read state and copies over unchanged entity/world data by simply pushing pointers to that data into std::vector<>s in the write state. For things that did change I push a new pointer into the write state and clear up the old pointer in the next tick. Pushing pointers saves memory bandwidth since you don't have to copy all entity data for every tick. And still you can guarantee that the "read"-state will be unmodified so that other CPUs/cores/threads can freely access all of the data and pointers. On the livestream I discussed a few cases where I do use (largely uncontested) mutexes for data synchronization: for friend chat and private chat I do a lookup of destination hero pointers in the "hero map" and then lock/unlock the hero's mutex for pushing chat messages into a vector. Does this make sense? Let me know if I should elaborate. I will probably take a nap now, but I'll answer you (and others) tomorrow. I'll also do another livestream tomorrow, because I feel everyone on HN has very useful questions, feedback and ideas.
- suby 7y ago
  Thanks for the explanation. It makes perfect sense. I did something very similar, except your system sounds better in that you only copy data that has been changed. I have a double buffer system where I'm copying almost all of the data each tick, and swapping the stacks when the next tick is due.
- dreamingincode 7y ago
  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 7y ago
    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 7y ago
      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?

by suby 7y ago

ItsFirefly 7y ago

I'll reply more in depth after my livestream, but it's a very good question. You can hop on YouTube right now to discuss it if you want. There's a bit of banter going on, but I might be able to squeeze in some useful replies in between.

sxp 7y ago

https://youtu.be/1PhArSujR_A?t=988 https://youtu.be/1PhArSujR_A?t=988 was Carmack's presentation on an immutable Haskell game engine. Unfortunately, he doesn't go into too much detail. https://news.ycombinator.com/item?id=15036591 https://news.ycombinator.com/item?id=15036591 was the previous HN thread about it.

ItsFirefly 7y ago

This question was the most asked one during my livestream. It's a good one! Even though it's 01:33 right now after a 7 hour livestream, I'll try to answer it as clearly as possible, building from the foundation up to the high level. The Angeldust game world is tracked in an "active chunk set". A chunk is a 2D part of the world, 32x32x64 in-game blocks (meters). The active chunk set tracks only the chunks that contain, or are near, players. This chunk set is processed in parallel on any number of threads/cores configured in the server settings file. Angeldust tracks two states for the data contained in each chunk, kind of like an array of size 2. Each tick, one state in the array is the immutable "read"-state and the other is the mutable "write"-state. Every tick these states ping-pong between the roles. During processing the server processes the read state and copies over unchanged entity/world data by simply pushing pointers to that data into std::vector<>s in the write state. For things that did change I push a new pointer into the write state and clear up the old pointer in the next tick. Pushing pointers saves memory bandwidth since you don't have to copy all entity data for every tick. And still you can guarantee that the "read"-state will be unmodified so that other CPUs/cores/threads can freely access all of the data and pointers. On the livestream I discussed a few cases where I do use (largely uncontested) mutexes for data synchronization: for friend chat and private chat I do a lookup of destination hero pointers in the "hero map" and then lock/unlock the hero's mutex for pushing chat messages into a vector. Does this make sense? Let me know if I should elaborate. I will probably take a nap now, but I'll answer you (and others) tomorrow. I'll also do another livestream tomorrow, because I feel everyone on HN has very useful questions, feedback and ideas.

suby 7y ago
Thanks for the explanation. It makes perfect sense. I did something very similar, except your system sounds better in that you only copy data that has been changed. I have a double buffer system where I'm copying almost all of the data each tick, and swapping the stacks when the next tick is due.
dreamingincode 7y ago
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 7y ago
  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 7y ago
    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?