Simulation Parallelization | Steam Revolution Game Devlog #9

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