▲ 398 points
back
180 comments
Seeing stuff like this on here fills me with nostalgia.
I basically learned to code thanks to a few helpful and extremely patient IRC members in the Spring RTS engine[1] community (some of whom I spot in these comment sections on occasion - hi!), and deterministic lockstep simulation for online play was one of the first ideas that totally blew my mind when I learned about it ("b-but that means all the "random" numbers on every computer need to be the same! and so do all the floating point calculations across different hardware!"). Of course, to me at the time, that was deep magic that I thought I'd never be able to fully understand.
[1] see https://springrts.com/ - or check out http://zero-k.info/ and https://www.beyondallreason.info/ for games on the engine that are still pretty active
Yup. That’s how networking basically worked for Army of Two. We only sent controller input over the network. Everything else was deterministic.
If the randomness is deterministic doesn't that mean players could peek into the future?
Hedgewars also uses deterministic lockstep. But due to the floating point problem, the main developer elected to write custom fixed point math instead. It works since the game doesn't use a lot of physics.
Oh man I discovered Spring about 15 years ago. Never dug into the engine but wrote a couple Lia scripts. Great engine. Good times.
The random numbers I understand, because I’ve used a similar principle to make tests deterministic. The trick is to make the same number of calls to the generator and use the same seed. The floats are really thorny though, differing subtly across CPUs. Did they just rely strategically on rounding? Make heavier use of integers?
Lots and lots of great things in here, thank you for sharing.
> At first take it might seem that getting two pieces of identical code to run the same should be fairly easy and straightforward
I found that a little funny. I would certainly not assume that. Synchronization problems are one of the scariest areas of programming in my opinion.
IRL it was not simple. The game usually worked, but occasionally things would go out of sync.
The biggest downside is mentioned in the article: If one person lags, everyone lags. In an 8-player game, the chance that at least one person lags was pretty high. I used to play on the Mac version of GameRanger, a small community. That was 2008, when reliable internet wasn't as common. Players had personal reputations, and those who lagged too much were often excluded from games.
I think this is a “must-read” for anyone, even if you aren’t in game dev or doing networking stuff. There’s just so many mini “eureka!” nuggets to enjoy.
I think that internet multiplayer is possibly one of the hardest things in game dev (use an engine that gives it to you!!!) despite feeling like some little sideshow.
I imagine Blizzard and Westwood have similar stories from the 90s.
https://www.codeofhonor.com/blog/the-making-of-warcraft-part...
there's this for Warcraft 1 development
> Cheating to reveal information locally was still possible, but these few leaks were relatively easy to secure in subsequent patches and revisions.
I don't understand this. Running the whole simulation locally on both ends means that a modified client would have access to the whole game state, and I don't really see how you could patch that out.
Anyone have any idea what they actually did? Try to detect modified clients? Obfuscate the game state to make it harder to interpret?
In age II, it was CRC checks of game state that prevented cheating! Games would get out of sync if there was a mismatch, which could happen for various reasons.
I worked at MacSoft during the Age2 and Age3 days. The ports were faithful to the windows versions, but cross platform hadn’t been solved at the time because of this problem.
It also made long game play sessions longer because the calculated state kept getting more complicated.
There was one particular Mac OS X update that broke math interoperability for multiplayer because they changed how math worked on the OS. This meant we had to bundle a common math library to ensure the game the game states would line up, preventing unnecessary CRC checks.
One of the unofficial solutions used in Warcraft 3 was to spawn an illegal 3D model object in the corner of the map by a trigger as soon as the map begins, or during random spot checks during the map gameplay.
The model would crash the game (and world editor, that's why we have to spawn it during runtime) when displayed, but it wouldn't get displayed when under fog of war, so you'd put it in a place that is impossible to be seen by a player under normal circumstances. But if someone uses a fog of war cheat or a maphack, it'd crash for them.
Of course it won't prevent you from more advanced hacks which e.g. modify the client and display an overlay of the enemy units rather than just revealing the fog of war.
As long as users are running the game on their own computers, preventing that type of read-only cheating is not possible. "Solutions" to this problem come in the form of invasive spyware, such as Warden (Blizzard), Easy Anti-Cheat (Epic), Vanguard (Riot), etc. These are programs that run with the highest possible priviledge, inspect all memory/storage/devices/input, and report what they find to a server.
As someone who grew up playing Age of Empires II and still consider it among the best games ever made, reading this is nothing short of amazing.
I still regularly have dreams about it 20 years later.
I take it as a sign that I'm in a good healthy place mentally when the most stressful and anxiety inducing thing my brain can conjure up is me being rushed by 3 units in the dark age.
I still play it (the definitive edition) with my wife. Best game ever in my opinion.
What I find interesting about the lockstep approach described here is it seems a lot of modern RTS games still use the same approach, even though the bandwidth calculations have changed radically. When developing my own RTS game I was able to fairly straightforwardly get 1000 units in combat to live stream using about 50 KiB/s bandwidth, which is nothing these days: https://www.construct.net/en/blogs/ashleys-blog-2/rts-devlog...
So as much as this is a fascinating piece of history and an impressive technical solution to the constraints of the time, I think modern games ought to move past it.
> So as much as this is a fascinating piece of history and an impressive technical solution to the constraints of the time, I think modern games ought to move past it.
But why? As far as I know mega-hits like Warcraft III and it's new, updated, version, "Warcraft III: Reforged" which came out 20 years later still use that technique.
The benefits do go well beyond being able to "send" hundreds of units across the wire: a deterministic game engine allows to create tiny replay files and, very importantly, allows to find and smash bugs way quicker.
Having the next game state being a deterministic function of the current game state + player inputs is great.
What would RTS games win by "moving past" that? To do what instead? How would you then implement the replay functionality? You'd also invariably run into a class of bugs which would be hard to reproduce but which would be trivial to reproduce using a deterministic engine.
From a latency point of view you're not gaining anything either: you need to receive the other player's units position anyway. So what's the difference between receiving the hundreds of unit's position or receiving the player input that created these unit's position? Just compute them, deterministically, as soon as you get the player's input.
Did those units shoot? What happens when there is a few thousand projectiles in the air, fired by those 1000 units? What about map deformations? What about map wide physic simulations, like springs tsunami water sim or the lava flows of a volcano, changing directions?
IIRC, and I've got nearly all my emails since the nineties until now so I could find out, I sent an email to the author of that article back when I read it, I think, still IIRC, on the Gamasutra website. And he answered me: we chit-chatted about deterministic game engines, for I wrote one in... 1991! (not for a networked-game though).
The subject already came up here on HN and some posted about games using deterministic engines before AoE.
The reason I did it is I had a bug which happened ultra-rarely and couldn't figure it out so I thought a long time about this and realized a could make the game deterministic and that would maybe allow me to record the bug happening and then be able to replay it. I found that by myself: back in 1991 I had never heard of anyone writing a deterministic engine back then. So I took a few days and rewrote the engine to be fully deterministic. Sure enough it eventually caught the bug: some case where the hero would clear a level after having fired two shots at once, which was an extra (by default it only had one shot at any time). The shot still on the previous level would continue to "live", invisible, in the following level, and would corrupt the memory. Classic.
Oh the memories to see that article again!
This site used to be Gamasutra didn't it?
Yup, this post is how I found out that they changed their name.
> Game Developer was first founded in 1997 as Gamasutra and has strived since its inception to be a leading resource and reference for game development and industry knowledge. Following the shift from Gamasutra to Game Developer in August 2021, the site has maintained that mission while embracing the in-depth content its namesake Game Developer magazine is known for.
They renamed it because they decided being a pun on "Kama Sutra" was just weird and unprofessional.
(Same for the NIPS conference. But oddly not for the science journal PNAS.)
It's interesting how the online gameplay has changed between the different versions of the game as network latency has improved.
For example, being able to micro manage archers to dodge other archers, and time their shots is something that wasn't possible previously.
That sounds terrible. I'm pretty sure the next game in the series, Age of Mythology, didn't permit missed shots.
Has network latency improved much since this article's date? Bandwidth definitely, but latency?
As someone who fixes up old games in my spare time, and Age of Empires II being one of them, I'll provide a bit of trivia about the game's internals:
- The AI system is not part of the deterministic simulation. This was surprising to me, and after contacting one of the original programmers it was explained that it was due to a desynchronization bug that the "AI and network programmers weren't able to fix it in time".
A consequence of this design regression is that, due to the AI now being authoritatively run by the designated host player, network congestion issues arose which lead to a clear series of progressively more aggressive optimizations to reduce egress traffic. This primarily consisted of a very simple filter (mentioned in the article) which dropped duplicate commands in the common submission path, meaning it applied to both local user and AI commands, along with batching of AI-submitted commands which would be flushed at rather arbitrary times.
I'll note that I've restored AI being deterministic in my project.
- A rather obscure determinism bug resulted from their compiler's implementation of a few CRT routines, namely fsin/fcos and a few others, which leveraged the specialized ISA instructions of the same name. The problem being that these transcendental functions are beyond the scope of the IEEE 754 spec. and ergo are hardware implementation-dependent. In practice, contemporary Intel/AMD chip families produce bitwise the same result, however those around the time of AoE are known to diverge on results to some small margin (as confirmed by an Intel engineer on a thread I came across while researching).
- The game employs a dirty-update system for rendering, not only that it's at a scanline granularity. This was something I was very pleased to see, as it's a exceedingly rare to see such an important optimization in games of this era (although common in earlier eras)
- There's some "interesting" naming conventions, one being prefixing member variables names with "value" -- there's even a "valueValue". Very little consistency in general in this regard, a reflection of independence between teams working on different components.
- While there are attempts at validation of input into the simulation (albeit woefully inadequate), it relies on ad hoc inclusion of PID (player ID) fields within commands. This is entirely useless, as this information is not authoritative and controlled by the players, permitting them to "spoof" the contextual information required for validation.
This is one of the more perplexing aspects of the engine, especially given the necessary information about the origin of a command is ofcourse available.
(As this information was later publicly published by other individuals I don't see a problem with elaborating on it here as I have)
- An example of missing the wood for the trees: session information goes through an ad hoc compression for its wire form (just bitpacks fields) to conserve bandwidth, however the architectural choice is to synchronize this session state by just having the host broadcast the state --dirty or not-- every 200ms, flooding the network pointlessly (atleast in the 18.8k days)
- While Age of Empires is somewhat notorious for its poor multiplayer performance (notably when contrasted with say, the recent "Definitive Edition"), and while its implementation of this synchronization model is certainly rather juvenile, it should be understood that the final MP gameplay issues are primarily due to the choice of a peer-to-peer topology over the public internet, which at the time was the most reasonable.
While superficially P2P may seem like it should achieve the lowest latencies for instance, the reality is that the primary determinant is the characteristics --jitter, delays and packet-loss, reordering, ect-- of the path between two hosts and a P2P architecture means there's n*n paths (network egress/ingress paths are typically asymmetric). In contrast, a server/client model you not only have far fewer routes, but datacenters are located at critical points in the network, roughly analogous to comparing travelling A->B along a freeway versus via the maze of residential streets.
- The state checksum "algorithms" involved are bordering on useless, atleast for state-tracing (such as when debugging desync. bugs.). They appear to have been devised by way of believing doing "a bunch of random bitwise ops" constitutes sufficient mixing -- a quick test demonstrated that csum collisions were not just possible, but occured sometimes for over 80% of inputs.
--
There's a lot more that could be said but I feel that's enough for now.
Sending state updates every 200ms made my spidey sense tingle. Most industrial control systems of the 90s would work on continuous 200ms polling through the network. Mostly RS485 links at 9600 baud.
The thing is that this is perfectly reasonable if your network infrastructure is known. If you have fixed bandwidth and deterministic packet sizes, then you can do math and know what the behavior will be. Determinism is good! Also this assumes the network is single purpose. Which it was! For games in the 90s it was! This isn’t bad design, it was good design for the network infrastructure people would have had at the time!
Absolute left field question. Have you touched the other RTS contemporary of the time, Red Alert 2 in any detail?
I've been told the source code for it leaked some long time ago and has floated around for the past two decades or so. While most people contend that EA had lost the source code to the Command & Conquer series games many years ago when the studio was closed down and assets were shipped to "DICE" in Stockholm
I remember using some kind of resource explorer, looking into the scripts powering the AIs. If I remember correctly, it didn't get "smarter" at higher levels, it just cheated and gave itself more resources every minute, lol.
> I'll note that I've restored AI being deterministic in my project.
Are you the OpenAge author, or maybe Voobly? I've never read such detailed info on AoE's internals online. Thanks for the post.
> In practice, contemporary Intel/AMD chip families produce bitwise the same result, however those around the time of AoE are known to diverge on results to some small margin
That little bit of validation I needed for why I avoid AMD CPUs. (not entirely serious)
> There's some "interesting" naming conventions, one being prefixing member variables names with "value" -- there's even a "valueValue". Very little consistency in general in this regard, a reflection of independence between teams working on different components.
Actually suffixing! i.e. objectsValue.
How are you able to work on the game? Are you employed to do so? Do you reverse engineer? Or has the source leaked?
I enjoyed reading how they solved synch problem: schedule this moments commands for 2 turns from now, and the turn length is dynamic to smooth out experience.
Maybe a 2001 in the title would help?
The 28.8 was more than enough for me to place the article in time.
We've 10/100mbps in 2001 and I think 1500 archers on 28.8k hayes is a great challenge no matter what the year.
I love seeing the inside of the game development cycle from a technical perspective, thanks for sharing.
That's crazy I see this post. Haven't read it yet, but I just played a 3v3 game out of nostalgia. People still play this game years later, and it works great.
An RTS we developed just recently (Iron Harvest) is still based on the same basic principle. But instead of peer to peer we use a "smart" proxy server that receives the commands of all clients and sends the entire sequence back to the client. That way if one client has a high ping the other players latency isn't affected.
(2001)
For those who don’t want to suffer from eye-bleeds due to ads, interstitial scrolling ads, more ads, and awful formatting, Googling the title yields this PDF:
https://zoo.cs.yale.edu/classes/cs538/readings/papers/terran...
Maybe the link can be replaced? Also can (2001) be added to the title?
You see ads? Is your computer broken?
>>sarcasm overload
Install uBlock Origin yo
Who remembers tourneys for Age of Empires at Sunnyvale Fry's.