Simulation Parallelization | Steam Revolution Game Devlog #9

Рет қаралды 3,709

Күн бұрын

In this video I talk about how I parallelized the simulation code in my game Steam Revolution. I measured accumulated times after running 1M simulation ticks. This makes the math nice so that the number of seconds taken equals the number of microseconds per simulation tick. In the world map with 214 trains, parallelizing my code made the time go from 43.2 s to 17.7 s on my computer, a 2.4x speedup.
Speeding up the simulation via multi-threading is challenging for a few reasons.
1. The duration of each simulation step is very short, so the overhead of parallelization is difficult to overcome. Each simulation step is also composed of multiple interdependent stages that further reduce the time per parallel section. There are 6 parallel steps per tick, in 43 us (7 us per step).
2. The simulation is not trivially parallelizable, because trains interact with each other and with shared resources such as sections of track and industries.
3. Results of the simulation must be deterministic and identical between serial and parallel versions. Re-running a simulation should give the same score every time to make playing the game fun. Also, server verification of results requires the server and client results to match.
I will give an in-depth description of the challenges to making each part of the simulation parallel and the strategies I used to overcome them. Although I’m specifically describing my solutions to my problems, they may provide inspiration for parallelizing your own code.
My game is a blend of OpenTTD and Zachtronics games like SpaceChem or Infinifactory. Compared to other train games, my game's focus is more on optimizing static levels for good scores rather than showing how a transportation empire progresses over time. In this series I document my progress developing a game from scratch with no pre-made engine; one could call it handmade.
Timestamps:
00:00 - Intro
03:10 - Overview of game
03:48 - Benchmark hardware
05:20 - Benchmark times
09:10 - Simulation overview
11:40 - Benchmark simulation steps
13:35 - Overhead sources
21:38 - Update track occupancy
23:12 - Propose location
28:55 - Wait and cargo
39:30 - Commit movement
42:45 - Collision detection
44:38 - Add cars and trains
45:16 - Update industries
45:48 - Cargo loaders
47:32 - Remove smoke
47:55 - Update game state
48:35 - Revisit timings
50:55 - Conclusion

Пікірлер: 20

@NongBenz 22 күн бұрын

Good video, interesting how multi track train networks and signals are a convenient analogy for code parallelization and concurrency

@vectorlua8081 23 күн бұрын

Hooray! More really informative content, stuff that makes sense and is actually useful!

@IstasPumaNevada 17 күн бұрын

Interesting programming information and a train game. I'm going to subscribe to follow along with. :)

@krystofjakubek9376 19 күн бұрын

Nice technical video! Always a pleasure learning about how you overcome challenges

@braspatta 23 күн бұрын

Pretty cool content!

@Kanonenwind 21 күн бұрын

I do have a question: Have you tried batching modifications of shared state? Especially cases like spawning puffs of smoke and noises seem like they should be trivially changeable to storing them in a local list in the thread first, then locking the global list if any were created and just shoving either the list object or each element of the local list into it. It may be benefitial because it means you only need to lock/atomically insert at most once per worker, or totally worse because of the extra code and copies, so I'd love to hear if you have benchmarked this!

@josiahmanson 21 күн бұрын

Good question. I think I mentioned in the video, but the sounds actually are already batched per train over several simulation ticks and are consumed by the main thread during the render update. So, sounds have no locks during the simulation. For smoke puffs I could have done the same thing, but it doesn't cost much performance as it is since the puffs aren't generated all that often (like maybe 1 in 10 frames and only if a train is moving). So, it barely shows up in profiling, a quick test just now showed 0.143 s out of a total 18.344 s run time was spent acquiring the smoke lock. But you are right, that I could probably avoid that overhead. Thanks for the suggestion. Maybe I will implement that.

@josiahmanson 20 күн бұрын

I gave smoke puffs the same treatment as sounds. I store them only in the train now, and there is no reason to have a global array to collect the smoke in, because the renderer can directly use the train arrays. I also removed the per-tick stage of the simulation where I remove smoke, because this only needs to happen once per rendered frame. At the fastest rate that is once per 1000 ticks, which also reduces overhead some. I also made my benchmarking code (that doesn't render) match that to remove finished smoke every 1000 ticks. Rough timings of the best run over like 5: 17.68 before 17.13 after train smoke optimization There is a variance of up to a second between timings, so it is hard to know precisely how much it helped, but it is clearly somewhat better by on the order of half a second. I could in theory do similar for the cargo loaders, but since those affect the sim I will still need to touch them once per tick so the benefits won't be as large. I might try that next.

@Kanonenwind 20 күн бұрын

Nice to hear back the results! Yeah, I didn't expect a big benefit out of the smoke spawning because it didn't seem like something that would happen too often, so I'm pretty amazed if it really is half a second in the end. I mainly mentioned it because this is a common technique in entity component systems to allow multithreaded systems to spawn new entities. You could probably use it in other steps of your simulation, but once one needs more than "many threads create values for one accumulation without order" you may need to add a serial fixup step or something like that, so the smoke seemed like low hanging fruit! And on the audio, you may have mentioned it, I mainly listened to the video over two days when I ate or was on break so I don't remember all the details 😅.

@josiahmanson 20 күн бұрын

@@Kanonenwind Ya, I wouldn't expect you to remember every detail. I think the main benefit from the smoke change was not about the locking, but about my being able to skip the step in most sim ticks and do a big batch update every 1000 ticks. Most ticks there is no change in state for the smoke puffs, so repeatedly processing them was wasteful. Also there is no harm in letting smoke remain in the array past its expiration so skipping the tick it should be removed is safe. These things aren't true for cargo loaders, so I don't expect anywhere near the same benefit.

@michaeljackson1147 16 күн бұрын

<a href="#" class="seekto" data-time="190">3:10</a> The logo has a typo "Steam Revloution" lol

@josiahmanson 16 күн бұрын

lol. oops. thanks for catching that!

@delphicdescant 14 күн бұрын

Typos increase engagement!

@lynnwilliam 23 күн бұрын

Ireland!!!!!

@lynnwilliam 23 күн бұрын

What game is this ?

@josiahmanson 23 күн бұрын

It is a game I am working on as my hobby, called Steam Revolution.

@lynnwilliam 23 күн бұрын

@@josiahmanson I love how you have a deep understanding a parallel processing and parallel programming and simulation. I have the same it is so hard to teach in a YT video. but you did a great job. Where can.I download your software?

@josiahmanson 23 күн бұрын

@@lynnwilliam Thanks for the compliment and your interest. The game hasn't been released, so isn't available for download yet.

@lynnwilliam 23 күн бұрын

@@josiahmanson can you setup maybe a reddit subreddit and link that in all the YT videos about this? Would love to hear what other programmers think. What you are doing is amazing by the way,

@josiahmanson 23 күн бұрын

@@lynnwilliam That is a good suggestion. I'll have to consider it.