[HN Gopher] Determinism in League of Legends: Implementation (2017)
___________________________________________________________________
Determinism in League of Legends: Implementation (2017)
Author : highfrequency
Score : 88 points
Date : 2024-09-30 18:46 UTC (3 days ago)
(HTM) web link (technology.riotgames.com)
(TXT) w3m dump (technology.riotgames.com)
| ryanmcbride wrote:
| Just wanna make those aware who may not be, the SAG-AFTRA called
| a strike against League of Legends on behalf of video game actors
| last week. For those of you who may not want to cross the digital
| picket line.
| double051 wrote:
| Where can we learn more about this? The strike calls for
| players to boycott the game?
| ryanmcbride wrote:
| Here's a few links. I don't believe the union officially
| calls for players to boycott or anything, just for union
| members to strike. Either way I haven't played since the
| strike became official, primarily because I always try to
| support striking unions when possible, and secondarily
| because it's pretty easy to just not play a game while
| they're negotiating.
|
| https://apnews.com/article/sagaftra-formosa-interactive-
| leag...
|
| https://en.wikipedia.org/wiki/2024_SAG-
| AFTRA_video_game_stri...
| tourist2d wrote:
| > "League of Legends" is caught in the middle of a dispute
| between Hollywood's actors union and an audio company that
| provides voiceover services
|
| How is that related to this engineering post? I wish HN took
| action against people commenting wildy unrelated topics.
| Nullabillity wrote:
| How is it _not_ relevant to a post _by_ Riot /LoL?
| bradley13 wrote:
| Good info, and fair enough for people to support the strike, if
| they want to.
|
| FWIW, my view is that the use of AI-generated figures, voices
| etc. in video games is inevitable. As a gamer, I genuinely
| don't care who is behind a particular voice. I cannot imagine
| that many gamers do. All the strike is going to do, is hasten
| the shift to AI.
| Nullabillity wrote:
| This kind of defeatism is the only thing that could make it
| "inevitable" in the first place.
| whatshisface wrote:
| Unless you're excited to live in a world where creative
| personality and art history has been replaced by public or
| private utilities, the (maybe not) inevitable deserves at
| least a little resistance.
| phito wrote:
| A lot of the mainstream "creative" media has been just that
| for a while now. It did not need AI to lose its soul.
| whatshisface wrote:
| The cost of acting as a percentage of budget or revenue
| is highest for indie studios because it's done at fixed
| union rates without the variability in the number of
| hours that can be spent on it you get for art and polish
| coding. It is likely to take over the stuff we actually
| like first, because, among other things, small studios
| are more willing to take risks and accept quality
| compromises in new technology acquisition.
| delusional wrote:
| A lot of the non-mainstream stuff only exists because the
| creatives in the mainstream take the capital they earn
| there and shovel it into niche stuff.
|
| Excluding artists from the mainstream wont just hurt the
| mainstream. It will starve the niche too.
| ryanmcbride wrote:
| I care, I understand not everyone does though
| repeekad wrote:
| They want to ban generative AI in video games? Why would a
| company ever agree to that?
|
| The writers strike eventually resolved, but with big layoffs
| and wiped $2B from the LA economy
| jayd16 wrote:
| The fully organic push might just be a bargaining tactic.
| There's other big wins like ensuring your likeness won't be
| replicated, your work used to train AI without compensation,
| or your work replaced with an AI sound-alike when it's
| cheaper.
| cevn wrote:
| I guess I'm unintentionally supporting them, because Riot
| removed Arena last week. That was the only game type I had the
| stomach to play, I'm tired of whacking minions.
| stonethrowaway wrote:
| "Digital picket line"? Over "AI"? For heavens sake, grow up.
| What are you protesting, the use of technology and mankind's
| advancement?
| delusional wrote:
| Towards what? artist-less art? Higher returns?
| Iridescent_ wrote:
| Except the strike is not really against LoL as a game, but as
| one of the largest clients of the actually targeted company.
| The strike is purely an industry strike and does not have much
| to do with players, as it originates in the VA company trying
| to pull a scummy move to bypass an union. The strike's goal was
| to force Riot to take position and disavow the company, which
| has been successful.
| SeanAnderson wrote:
| "After consulting with several other Rioters, our team settled on
| developing a new PRNG implementation based on XOR-SHIFT."
|
| I wonder why?
| bob1029 wrote:
| Likely performance. You can do xor and shift operations
| essentially for free on a modern pipelined CPU.
|
| Other techniques, such as linear congruential generators,
| require multiplication and division.
| Joker_vD wrote:
| "It's simple, fast, and has a great distribution, which means
| it's more than good enough for gameplay."
|
| Its distribution is not flawless, but I would agree that it's
| good enough for gameplay.
| DarthBatman wrote:
| This! We don't use it for mission-critical crypto or the
| like. It's there to figure out whether a bot goes left or
| right. Given the enormous complexity of the League game state
| and input surface area, it likely won't be a concern unless
| someone devises a way to exploit it for RNG manipulation
| (this seems unlikely.)
|
| The reason we didn't use crand was just code ergonomics.
| C-style rand has global state (by default) and we wanted our
| own interface to be explicit in the code so you knew when you
| were using a gameplay-impacting random number.
| underscoresunde wrote:
| underscores
| o11c wrote:
| The xorshift family is one of the top two RNGs in the modern
| day (the other being PCG). Unfortunately, "choosing the ideal
| member of the family" is nontrivial if you're trying to eke out
| every bit of performance.
|
| The problem with the xorshift family is that it doesn't
| implement the nice auto-scaling (and thus auto-testing) that
| PCG has. Re-parameterizing it means inventing whole new numbers
| from scratch and hoping you plug them in correctly. Xorshift
| also has a rare-but-severe "stuck near zero" problem.
|
| The problem with the PCG family is that its trusted way of
| scaling (nobody likes the `_k` variants) relies on 128-bit
| multiplication (a modern member of the family at least reduces
| that to a mixed 128x64 multiply), which remains notably slow,
| unlike xorshift which only uses small integers.
|
| (But I must emphasize: _all_ RNGs from other families either
| have worse variants of these problems, or give up on
| performance entirely. These concerns should be used only to
| select your preferred tradeoff between the two, there is no
| excuse for _ever_ using any other RNG family unless you need
| cryptographic security)
| nightowl_games wrote:
| > League of Legends does not use a fixed-step server clock, but
| rather a measured frame delta time which we throttle to a target
| frame rate. This makes the server more resilient to system-wide
| performance spikes, but this pattern definitely complicated
| determinism.
|
| This could use some elaboration. I don't even know how it's
| possible to have determinism without a fixed-step. I must
| misunderstand what this means. Every simulation tick in league of
| legends has gotta be the same duration, right? ie: 1.0 / 60.0?
| tylerhou wrote:
| You can still achieve determinism by treating the measured
| delta-time as an input, and resimulating the game with recorded
| delta-time. This may not be feasible on public servers, but is
| definitely feasible for professional play where determinism is
| important to rewind games due to bugs which affect competitive
| integrity.
| maest wrote:
| They have so many bugs that there's a procedure for rewinding
| the game during comp plays? Did I misunderstand?
| pohuing wrote:
| This is not unusual. Bugs happen and when there's a lot of
| money on the line you need a rollback system.
| maest wrote:
| Interesting. I don't think I've seen this in any other
| competitive game, which is why I'm surprised. But maybe
| I'm just lacking information
| mackman wrote:
| I implemented a debug replay system for an American
| Football game when I worked at Sony. The AI hierarchy and
| all animation and physics state was recorded and game
| could be rewound to figure out why an NPC made a poor
| decision. Only needed to track state for the duration of
| a single play. This was on PS2 which I think had 32MB of
| memory but the dev systems had an extra 96MB which we
| could use for this sort of thing.
| chowells wrote:
| Hell. Replay review in American Football and other sports
| _is_ a form of rewinding and fixing bugs in officiating.
|
| So it's certainly done in real life when money's on the
| line.
| nightowl_games wrote:
| Starcraft 2 lets you resume a game from a replay.
| tylerhou wrote:
| In StarCraft II you can resume from replay (and maybe in
| previous games as well), but I don't know if this has
| ever actually been used due to bugs in the game engine
| during competitive play.
| IanGabes wrote:
| They do! Its called Chronobreak. They have used it many
| times in professional matches successfully, but it doesn't
| work in 100% of scenarios.
| nightowl_games wrote:
| Yeah you _could_ but I fail to see why you would ever do
| this. It's also not feasible to synchronize the client with
| the server in real time with this input.
| tylerhou wrote:
| You don't need to synchronize the server and the client.
| The point of determinism is to be able to reproduce game
| states deterministically, not to have people play the video
| game deterministically. Again, this is to "undo" bugs in
| pro play (Chronobreak).
| DarthBatman wrote:
| Thought I heard my ears ringing... Blast from the past here.
|
| That's the beauty part of recording server state and playing it
| back -- we included a recording of whatever accurate integer-
| based OS time I could get on each platform. On Windows, for
| example, I record the raw values of QPC ticks and the tick rate
| into the recording. Then on playback, I play back the clocks
| themselves as if the hardware has that tick rate and tick count
| are from the recorded computer. So if frame 10 took 33.3ms and
| frame 11 took 66.7ms, we'd play them back that way.
|
| Note that playbacks are almost never in real-time. The reason a
| typical server frame takes 33ms is that we might be processing
| for 5ms and then yielding the thread (sleeping) for the
| remaining time during real-time gameplay. On playback, we don't
| yield the thread, so we play back faster than real-time when
| doing something like a live Chronobreak (disaster recovery.)
|
| Strictly speaking, you are right. Let's say we had a game with
| no player inputs (like a bots-only game.) It's possible that
| the outcomes might vary between two games with the same random
| seeds if they run different numbers of frames over the same
| time period. That said, we've actually tried this a few times,
| and our game code is surprisingly resilient to this -- only in
| a few instances have we found issues where subtle variations in
| frame time could impact player outcomes (and those are
| generally corrected when we find them -- this is an esports
| game after all.)
|
| A lot of this comes down to tradeoffs. Yes we might have those
| subtle issues, but if we fixed our timestep, then we'd have the
| other problem of the game potentially going into slow-motion
| during (the admittedly rare) periods of long frame times. In
| practice, we decided time dilation is more negative for player
| performance than loss of interactive resolution; humans are
| great predictors of motion with limited information, but
| they're not so great when the rules of localized reality bend.
|
| Edit: typo
| nightowl_games wrote:
| > It's possible that the outcomes might vary between two
| games
|
| So just to clarify: in League, the 'dt' passed into each
| 'simulation step' is NOT constant? Isnt this kinda crazy? In
| your later articles, floating point imprecision is talked
| about. Couldnt this variance in dt create odd behaviour and
| ultimate contribute to weird things like 'character movement
| speed' being not _exactly_ the same between games? (like
| really small, but still...)
|
| And beyond that, how does the client and the server
| synchronize with each other if the frame #s represent
| different positions in time? My mind is blown right now...
|
| Note: I've worked on many networked games, and have written
| rollback/resimulate/replay code. I don't really understand
| _why_ League wouldnt use a fixed time step. Whats the
| advantage? In our games, the rendering of course uses the
| real dt passed in from the OS, but the simulation step is
| always fixed. This means in our games during a replay, your
| computer could render the outcome differently if your frame
| rate is different, but the raw simulation is always the same.
|
| For context, to show I at least have some idea what I'm
| talking about, I made this replay system (and the game has
| rollback multiplayer):
|
| https://gooberdash.winterpixel.io/?play=5b74f7c0-8591-40dc-b.
| ..
|
| I havent played a lot of League, but I always assumed it
| would use deterministic lock step networking (like it's
| predecessor, Warcraft 3)
| DarthBatman wrote:
| We're recording the integer clocks though, and those don't
| change between runs. While game code converts things like
| (QPC ticks over tick-rate) to floating point, we don't sum
| those numbers directly. Instead, we internally store times
| as the raw integers then convert them to floats on-demand
| (typically when an Update function is asking for
| "elapsedTime" or a timer is asking for a "timeSpan" (like
| time since the start of the game.))
|
| LoL and TFT don't use a synchronized-simulation (lockstep,
| sometimes called peer-to-peer) networking model. LoL is
| Client-Server, meaning the replication is explicit and not
| based purely on playing back client inputs. This gives us
| more control over things like network visibility, LODs, and
| latency compensation at a feature-by-feature level at the
| cost of increased complexity. Most of the games I've built
| over the years use this model and the LoL team is super
| comfortable with it.
|
| The GameClients are not deterministic in the way that the
| GameServer is, though they're naturally closer to that
| ideal since the GameServer itself is typically predictable.
|
| Don't get me wrong, there's a time and place for lockstep
| replication, and LoL probably could have gone that way. I
| wasn't there when that direction was picked, but I would
| have likely made the same choice as my predecessors,
| knowing what I do about our approach to competitive
| integrity.
| doctorpangloss wrote:
| All this stuff predates ECS and a fully specified
| definition of what a live service continent spanning MOBA
| is. All the tradeoffs make sense to me. The real question
| is, would it have been possible to define an engine
| solution that looks more like Overwatch, in the absence
| of a fully specified game? I feel like that is ECS's
| greatest weakness.
| mackman wrote:
| The physics game sim step had to be hardcoded but you could
| vary the graphics rendering independently. That did mean you
| needed to use a different RNG for sim objects and graphics-only
| particle effects.
|
| I worked on the deterministic instant-replay system for a
| racing sim on PS3. The most interesting thing was that on PS3
| we had main processor cores (PPU) and helper cores (SPU) which
| had their own instruction set. Our physics sim could distribute
| work across both, but the thread assignment had to be
| deterministic because PPU and SPU got marginally different
| floating point results for the same instructuion and inputs.
| That was a fun one to figure out!
___________________________________________________________________
(page generated 2024-10-03 23:01 UTC)