Why 1999 Quake 3 Netcode Belongs in Every CS Degree

0:00It's the late '9s with titles like Doom

0:02and Quake. Its software has changed

0:04gaming forever. Online multiplayer

0:07firsterson shooters are becoming more

0:09and more popular. It software has a

0:11radical idea. What if we dropped the

0:14singleplayer campaign entirely? What if

0:17the next game was only an arena shooter?

0:20But to justify their decision, the

0:22multiplayer had to be flawless. It had

0:25to run on low-spec machines and dial up

0:28connection while at the same time

0:29pushing graphics, physics, and gameplay

0:32to new levels. They wanted to create a

0:34fast-paced arena shooter that felt

0:36smooth on the average PC. So, they had

0:40to beat the limitations of bandwidth,

0:42latency, and relability. Instead of

0:44waiting for the technology to improve,

0:46they decided to challenge it, pushing

0:48the limits of what's possible. What they

0:51built became the foundation of modern

0:54multiplayer networking, pioneering ideas

0:56and concepts that are still used today.

0:59It's not about frameworks or third-party

1:02libraries. It's the evolution of the

1:04engine architecture they had been

1:06shaping since Doom, refined game after

1:09game. And that's why every computer

1:11science student or even experienced

1:14developer should study it. It's a master

1:17class in fundamentals. In my opinion, it

1:20deserves a place in every CS curriculum.

1:23In this video, I'm going to talk about

1:25the snapshot system, delta compression,

1:28Huffman compression, client side

1:30prediction, and why they use UDP instead

1:32of TCP. This is the Quake 3 net code.

1:38Okay, so first let's start with the

1:40problems. This sounds like a description

1:43of a dinner with my family.

1:46Anyways, at that time it was facing what

1:48I call the impossible triangle.

1:50Bandwidth, latency, and reliability.

1:53Bandwidth was low. Keep in mind, most

1:56people were still on dialup. If you're

1:57younger, you probably never heard that

2:00dialup modem. It made this kind of alien

2:03sound and somehow we all just accepted

2:06it as normal. But if you think about it,

2:08nothing ever since has sounded like

2:10that. And also, your phone didn't work.

2:13Okay, so bandwidth was limited. So they

2:16couldn't just push every little game

2:18change across the connection. Then the

2:20latency was high. If the client waited

2:23for the server to confirm every move,

2:26the game would just feel unresponsive

2:28and then there was reliability. You had

2:30to accept the fact that packets were

2:33going to get lost. That's just how

2:35networks operate. And of course for the

2:38guy having a full crash out. Yes sweetie

2:41you could use raw dog TCP to guarantee

2:44delivery. But TCP comes with a lot of

2:47overhead. It resends all packets even if

2:50the information is no longer relevant.

2:52And in a shooter if something happened 5

2:55seconds ago there's no point in

2:58retransmitting it most of the time. This

3:01of course doesn't include all messages

3:03everything. But most gameplay packets

3:06are not worth resending. So they decided

3:09to go with UDP. I'm going to talk about

3:11this in detail. Okay. Now, the most

3:14impactful highlevel decision in the game

3:17design was this. Quake 3 had no

3:20singleplayer campaign. So the

3:22multiplayer had to carry the whole game.

3:24It had to work. And you know why?

3:28because it wasn't 2025 where everyone

3:31ships half assass finished games for the

3:33full price for like $80 and then you got

3:36to buy the DLC and then the premium pack

3:39to have two more missions. I think we're

3:41just collectively accepting too much and

3:45gradually lowering our standards. But

3:47how do you solve something like this

3:49triangle here? The answer is you don't

3:52solve it with one big magic trick. In

3:55fact, it is very rare that you solve all

3:58bottlenecks with one decision. Usually,

4:01you come up with a lot of small ideas,

4:04each one covering one limitation. And

4:06then when you stack them all together,

4:08you can push through this plateau. Now,

4:12to easier understand how they put all of

4:14this together, let's start with the

4:16Quake 3 client server architecture and

4:18the snapshot system on a very high

4:20level. Okay, so if you watched my last

4:23Quake video, you know that the game is

4:25split into two parts. The client and the

4:28server. The client renders the game,

4:30does bunch of other stuff, handles your

4:32input, and then sends that input to the

4:35server. Now, the server holds the

4:38authoritative game state. It holds the

4:41true state of the game. Since after all,

4:44all the players want to play the same

4:46session, the same game. So, the server

4:48receives all inputs from all clients,

4:52updates the game state, and sends the

4:54updated game state to all the clients.

4:56That's the model. Pretty simple on

4:59paper, but making it actually work for a

5:02fast-paced FPS is a whole other story.

5:06Stay with me. Now, under the hood, the

5:08server runs a snapshot system. In

5:11regular time intervals, the server

5:14creates a snapshot of the current game

5:16state containing all new updates from

5:18the clients. Think of a snapshot like as

5:21a photograph of the whole game state at

5:24a specific moment in time. It contains

5:26all the relevant information. Now they

5:29can just take the snapshot and send it

5:32to all clients, right? Yeah, they could

5:34if there wasn't our triangle of

5:36limitations, bandwidth, latency, and

5:38reliability. So, let's address the most

5:41important concepts that made this work.

5:44Okay, if you're dealing with low

5:46bandwidth, your only option is to send

5:49less data. So, first ask yourself, do I

5:53really need to send all of this data all

5:55the time? That's also something you

5:57should ask yourself when sending the

6:0011th reel today to someone who hasn't

6:03even reacted to the previous 36. Anyway,

6:06ask yourself, do I need to send the

6:08whole snapshot? I mean you can but in

6:12reality not everything is changing all

6:14the time. So why not just send the delta

6:18the difference between the last two

6:20states. So in case nothing has changed

6:24for an entity you just send one bit that

6:27indicates nothing has changed for this

6:29entity. That's delta compression. But

6:33how we going to tackle the problem if

6:34one client gets out of sync and the

6:38other one is still in sync? Not to be

6:40confused with an sync. You can't send

6:43the same delta to both since you would

6:46lose information. So for each client,

6:49the server keeps a snapshot buffer that

6:52holds the last 32 snapshots for that

6:56client, a history. So the server creates

6:58a delta for each client based upon the

7:01last snapshot that has been acknowledged

7:03by the client in case you're wondering.

7:06But isn't that a lot more processing on

7:09the server side than sending out

7:10everything all the time? Yes, and this

7:13is a tradeoff. But our bottleneck isn't

7:16the server side processing power. The

7:19bottleneck is the bandwidth. But let's

7:21continue. So when you reduce the full

7:23snapshot to just the delta you have

7:27scoped out information that has to be

7:29communicated to the clients. Now what

7:32you can do is you can try to represent

7:36the data the same data but with fewer

7:40bits and that's where the Huffman

7:42compression comes in. Don't worry I'm

7:44going to talk about this in detail

7:46during the video. Okay. And then we have

7:48latency. When talking about latency, you

7:51can of course wait every time for the

7:53server to approve acknowledge your

7:55action. But what you can also do is act

7:59now and reconcile later in case your

8:02action is not valid. That is client side

8:05prediction and it makes the game feel

8:07more responsive or super responsive

8:10because you're not waiting for the other

8:12side to acknowledge your actions. And

8:14for the reliability, Quake 3 chose UDP

8:18over TCP. UDP is lightweight and fast,

8:21and if a package gets lost, the game

8:24just keeps going. I mean, it's better to

8:27miss a frame, then freeze for 2 seconds

8:30while waiting for all data. For specific

8:32actions, they have built-in reliability

8:35into the UDP frame. For example, for

8:37actions like a client leaving the game

8:40or changing the map. Now if you put all

8:43of that together, snapshots, deltas,

8:46compression, prediction, UDP, you get

8:50the core of the Quake 3 net code. Not

8:53one giant breakthrough, even though many

8:56of these ideas are genius in my opinion,

8:58but as you can see, it's a bunch of

9:00smart decisions working in harmony. Now,

9:04I'm going to go through each of these

9:06concepts in more detail. So, first we're

9:08going to talk about the techniques that

9:10minimize the needed bandwidth. Since

9:12Quake is a FPS game and not chess, you

9:16can see everything all the time, which

9:19when you think about it, is actually

9:21great news for your bandwidth. So, the

9:23first thing you do is ask yourself, why

9:26would you even try to send data about

9:28the stuff the player can't even see? And

9:31this is where the potentially visible

9:34set or PVS comes in. When the map gets

9:37compiled, they do some pre-processing

9:39and figure out from every possible

9:42position in the map what areas you could

9:45potentially see. So, if your map looks

9:48like this, you get information like if

9:51you're in sector A, you can potentially

9:54see sectors B and C, depending on your

9:57orientation, of course, but you will

9:59definitely not be able to see D, E, and

10:03F. All of this information gets cooked

10:06into the map. So at runtime, we don't

10:08have to do any expensive line of sight

10:11calculations. Let's take a look at the

10:14server snapshot code. So we go in code

10:18server server snapshot C. We have this

10:22function called server add entities

10:25visible from point. So it basically

10:28loops through all the entities in the

10:30world.

10:32But before adding the entity to the PVS

10:36pool, it starts by doing all these let's

10:39call them knockout criteria checks. So

10:44for example, if an entity is not active,

10:46there is no point in checking where it

10:48is.

10:49It doesn't make sense doing first a PVS

10:52calculation and then checking if it's

10:55active. And this is how you should

10:59design your code. I know it sounds like

11:02common sense, but it isn't that common

11:05sense in practice. So, the goal is to

11:08filter out everything before you go into

11:10expensive calculations

11:13or even if the calculation per se isn't

11:17expensive, why would you do it if you

11:19can't just drop it entirely? Okay, so it

11:23starts by defining a bunch of stuff. And

11:26this here is the main loop.

11:30So it's basically iterating through

11:32every single entity starting at zero and

11:35then going all the way up and then we

11:38have this cascade of knockout criteria

11:42filtering or whatever you want to call

11:45it which I mentioned.

11:47So all of these are just bit checks or

11:51integer comparisons. So it's very cheap.

11:54And here we have the PVS check or PVS

11:58lookup. This is a chain of bitfise

12:01operations that basically checks if the

12:04entity's cluster is visible from the

12:06client's position. Now, what is a

12:08cluster?

12:10A cluster is a group of nearby map areas

12:14that tend to see the same stuff. So

12:17instead of tracking a tracking thousands

12:20of thousands of tiny small individual

12:23spaces, Quake tree bundles them

12:26together.

12:27So the whole system is way more

12:30efficient by doing it this way. I mean I

12:33could make an own video about u only

12:36talking about clusters and PVS but let's

12:39continue. Okay. So this client PVS is

12:43the premputed bit array where each bit

12:46represents whether a specific cluster

12:48can be seen. So this loop is just asking

12:51can I see any of the clusters this

12:54entity belongs to. And as soon as it

12:57finds one one visible cluster it breaks

12:59out and it adds the entity. This isn't

13:02doing complex 3D rate tracing or

13:05anything crazy. It's just looking up in

13:07that precomputed table that I mentioned.

13:09So by doing it this way the question can

13:12the client in area A see an entity in

13:17cluster D becomes just is the bit for

13:21cluster D set in the premputed

13:24visibility array and boom table lookup

13:27done. Okay so this cluster nums lets you

13:31draw the conclusion that entities can

13:33span across multiple clusters. So the

13:37loop just checks if any cluster the

13:39entity touches is visible. And as soon

13:42as it finds one one visible cluster, it

13:45breaks out and adds the entity. And at

13:49the end of this function, we have this

13:51really cool portal feature. So if the

13:55entity is a portal, it recursively calls

13:58the same function from the portal's

14:01destination, adding basically everything

14:03visible through the portal. So for

14:06example, mirrors or teleporters

14:09automatically show what's on the other

14:11side. Okay. So after this PVS step,

14:15instead of having to deal with hundreds

14:17of entities, you might only have 20 that

14:20the client actually needs to know about

14:23and that's saving enormous amounts of

14:26bandwidth. Okay, that's that about the

14:29potentially visible set. Now let's look

14:32at the delta compression because the

14:34code is surprisingly elegant once you

14:36understand what's happening. So let's

14:39first take a look at the entity state

14:41strct which is located in code game

14:45shared header file. The entity state

14:48struck holds data basically for

14:52everything. And I'm talking about all

14:54the data for all the objects in the game

14:57for the players, rockets, items,

15:00everything. Now the classic

15:03objectoriented

15:04programming class way to handle this

15:06would be to write custom code for each

15:10field like just bomb up everything with

15:14gather and setter functions and then

15:17build in a chain of impossible

15:20inheritance. I don't know why but these

15:23university classes love inheritance more

15:26than I don't know frat boys. So you

15:30would end up like having a gazillion

15:33functions to get and set data and then

15:35do that for each entity type something

15:39like if position changed send position.

15:42If health changed send health and you

15:45you would end up with such an enormous

15:48amount of code that's uh also very

15:53inefficient.

15:54And it's also inefficient in a

15:56maintenance sense because imagine you

15:58want to add something and then you also

16:01need to add code to compare it to encode

16:04it decode it and all that stuff. It's

16:07very errorprone but the it guys did

16:10something way more elegant. So let's

16:13first start with the net field and this

16:15will all make sense when we come to the

16:17right delta entity function if you're

16:20not a prompt engineer of course. So

16:23let's open message C. And here we can

16:26find the net field strct. This is the

16:29strct for each entry in the lookup table

16:32that drives this whole delta system.

16:34It's got the field name, the bite offset

16:37within the strct and the number of bits

16:40to use for network encoding. And then

16:43comes a little bit of pre-processor

16:45magic that makes the table easy to

16:47maintain. But don't get scared. I know

16:49when you first time see something like

16:51this, it looks like

16:54do I really need a job?

16:59But let me break it down. So, so we can

17:02understand what's actually happening in

17:04here. Okay, let's go step by step. So,

17:06the first part is hash x. That hash

17:10symbol is the stringification operator.

17:13It just takes whatever you pass in and

17:15turns it into a string. So if you write

17:18net f position for example

17:22that hash x becomes a string holding

17:26position. Simple enough. It's just a

17:29field name as a string. Okay. The second

17:32part is

17:34where it gets scary if you are a Python

17:37developer.

17:40This is calculating the bite offset of a

17:42field within the strct.

17:47Now let me walk you through this step by

17:50step because there's a really clever

17:52trick happening here. Okay. So first

17:54let's take a look at this. This is a

17:57cast. What this does is it takes the

18:00number zero which is the null pointer

18:03and casts it to a pointer to a entity

18:07statect.

18:09So we are pretending that there's a

18:11entity state strct sitting at memory

18:14address zero.

18:17Obviously there isn't really a strct

18:20there but the compiler doesn't know at

18:22this point. Okay. Next we have this x.

18:27This accesses the field we are

18:30interested in. So if we call net f

18:33position this becomes position. We are

18:37accessing the position field of this

18:40imaginary strct at address zero.

18:44And then comes the end operator. This

18:46takes the address of that field. Now

18:50here's the clever part.

18:54If our strct starts at address zero

18:58and we take the address of a field

19:02inside it,

19:04that address is

19:07the offset of the field from the

19:09beginning of the strct.

19:14If the position field is 12 bytes into

19:17the strct,

19:20its address when this truck is at

19:22address zero is then 12. Okay, does this

19:26make sense?

19:29Probably not, but it's a very elegant

19:32way and you will see why why this is

19:34important. And finally we cast this

19:37whole thing to a integer. So we get a

19:39nice integer offset value. Okay. So the

19:44compiler is doing all this math at

19:46compile time to figure out where each

19:49field lives within the strct. And this

19:52becomes really powerful and you will see

19:54it. Okay. Right below that you see the

19:57actual table with the entity state

20:00fields. And this is where we use this

20:03net f.

20:05Okay. I mean,

20:09look how clean this looks like. Even

20:12though you can't probably understand

20:13what's happening here, it looks really

20:15nice. So each line is just a field name

20:20and wrapped in this netf followed by the

20:23number of bits to use for encoding.

20:27And the compiler

20:29now processes each of these net net f

20:33macros and calculates where that field

20:36actually lives in the entity state

20:39strct.

20:41So each entry ends up with three things.

20:45the field name, the bite offset from the

20:49start of the strct, and the number of

20:52bits to use for encoding

20:54that field over the network.

20:57If you're wondering now, what's this

20:58last bit for? That last bit just tells

21:01the network code how much precision to

21:04use when sending this value.

21:08Okay. So if you scroll up you will see

21:11that uh yeah value of zero means it's a

21:16float and should be encoded

21:19accordingly

21:21while other values for example like 32

21:23specify how many bits to use for these

21:27integers. Okay for I don't know

21:31timestamps or something. Now you may be

21:34thinking or maybe not but Tariq

21:39couldn't we just hardcode these offsets?

21:43Why do we need this

21:46sorcery? And that's actually a really

21:49great question because the answer

21:50reveals why this approach is

21:55genius.

21:56Yeah, I mean you probably wouldn't come

21:59up with this approach to solve this type

22:01of issue. And that's why it's very

22:04important to study these code bases

22:06because this isn't something a

22:07university teacher would necessarily

22:10teach you in his programming class. I

22:13mean, sure, you could write something

22:16like, I don't know, just hardcode all

22:19the offsets and that works fine until

22:22you need to change the strct. And you're

22:25going to have to change the struct a

22:27lot. I mean, game development is very

22:30iterative. You're constantly adding new

22:34fields, removing old ones, reordering

22:36things for performance or changing data

22:40types or something. And uh

22:44let's say you added a new field on top

22:46of this entity state. Now, for

22:52every single offset in your hard-coded

22:55table, you would need to make a change.

22:57And for example, health isn't anymore at

23:01offset 48, and 52 offset is wrong for

23:04the weapons. Position moved, angles

23:07moved, everything shifted.

23:10So now you have to manually go through

23:12your entire table and recalculate every

23:16offset by hand. I mean you could of

23:18course script this part by doing it with

23:21this approach. You just recompile and it

23:24automatically recalculates all the

23:26offsets for you. The compiler knows the

23:29strct layout. So it figures out where

23:32everything is. You add a field to the

23:34strct. You add one line to the table

23:36using the net TF and you're done. No

23:40manual offset calculation. So no chance

23:43of getting anything wrong. Now besides

23:45that we have another advantage when it

23:48comes to struck padding and alignment.

23:50As you know sometimes the compiler adds

23:53invisible padding byes between two

23:55fields to align them properly for

23:57performance. So you might think two

24:00integer fields are eight bytes apart but

24:03the compiler added four bytes of padding

24:06for whatever reason. So now they're

24:09actually 12 bytes apart. But with this

24:12approach, you don't have to think about

24:15any of this. The compiler just

24:17calculates it and you get the offset.

24:20Okay. And there's of course the thing

24:22with the portability. I mean, different

24:25compilers on different platforms might

24:28lay out the trucks differently. They

24:31might use different padding rules or

24:33different alignment requirements. And

24:36with hard-coded offsets, your table

24:38would be wrong on some platforms. So

24:41this isn't about something you couldn't

24:44do otherwise.

24:46It's more about this not having to be

24:48tedious and not having to do this

24:51errorprone manual work every single time

24:53you change something because you put the

24:56responsibility on the compiler to do

24:58this let's call it maintenance stuff.

25:01Okay. Now let's see how this table

25:04actually gets used. If you scroll down

25:07now further in the message.c C file

25:10you'll see this message write delta

25:13entity function. This is where it gets

25:16interesting. So this function takes two

25:19entity states the old one and the new

25:21one and then figures out what has

25:23changed. It starts by defining a bunch

25:26of stuff and then we get to this loop.

25:30So this function has two very important

25:34loops and the first one goes through the

25:37fields and looks for the last changed

25:40field. That's this LC here.

25:44Why is this important?

25:46Well, imagine you have a series of

25:48fields

25:5010

25:52and then a lot of zeros.

25:56Now every bit is a field. One means we

26:02have a change and zero means we have no

26:05changes.

26:07Now this LC variable

26:10marks the spot so to say where the last

26:13change is located in the entity fields

26:18and it tells the rest of the function

26:20then okay here is where the last changed

26:23field is and after that everything is

26:26unchanged. So you can cut this tail off

26:31drop the tail like a lizard. Okay. And

26:35then we have these checks. If nothing

26:37has changed, you can return immediately.

26:39There's no point in comparing fields if

26:42there are no changes. But if there are

26:46changes,

26:47then comes the second loop.

26:50And in this loop, we go through all the

26:52fields and compare all the values and we

26:55write the delta bits. Okay? And

26:59generally speaking, the loop doesn't

27:01really know what it's comparing.

27:04And that's that's elegant about it.

27:08Okay, so the delta compression really

27:10scopes out only the information that

27:13really needs to be sent. In practice, it

27:17looks something like this.

27:20Let's say we have a player entity that

27:22moves slightly and changed weapons.

27:26The old state position is 100 250.

27:31Weapon is 2.

27:34Animation frame is 15.

27:36The new state position is 105, 250.

27:42Weapon is three. And the animation frame

27:44is still 15. Now the delta compression

27:49sees that only the X position and the

27:52changed weapon. So it only sends these

27:55two fields. And now that's maybe 16 bits

27:59instead of hundreds of bits for the full

28:02entity state it would take. But we are

28:05still not done with the bit squeezing.

28:07So if you think about it, the PVS

28:09filtering and the delta compression

28:12scope out the data that we definitely

28:15need to send in the next game state

28:17update. And since we can't filter out

28:20any more unnecessary information, the

28:22only thing that we can do is to try to

28:25represent these update bits with fewer

28:29bits. And that's where Huffman

28:31compression comes in. So after that's

28:34done, we have this stream of bits that

28:36we want to send in the next game update.

28:39So we run it through the Huffman

28:40compression. Now let me explain how the

28:44Huffman compression actually works.

28:46We're going to start with a small

28:47example and then I'm going to take a

28:49look at the code. So, Huffman

28:51compression is basically like creating a

28:53key map for your data. Instead of every

28:56bite taking exactly eight bits, we

28:58represent the most common bite values

29:00with just one or two bits. While very

29:04rare values can take up more than eight

29:06bits. But since the rare stuff is well

29:10not being sent out that frequently, you

29:12end up saving tons of data overall. So

29:16what they've done is they analyzed the

29:18traffic during normal gameplay and found

29:20out that specific values are sent more

29:23frequently than others. They analyze the

29:26bite frequencies and then you get

29:28something like this. For example, zero,

29:31which basically means no change, appears

29:3440% of the time because most things

29:37don't change most of the time. Then one

29:40representing tiny movement deltas appear

29:4325% of the time. A two for example like

29:47a slightly bigger movement shows up 20%

29:49of the time and very big movements like

29:53teleporting appear only 15% of the time.

29:56These are of course not the actual

29:58values from Quake. I'm just giving you

30:00an example. Now in case you're wondering

30:03how do you determine which value gets

30:05which key and how do you avoid

30:07ambiguity? Well, it's kind of simple. In

30:11our imaginary example, we have these

30:13four separate nodes, zero, 1, 2, and FF.

30:19Now, here's where the Huffman algorithm

30:22comes in. The rule is very simple.

30:24Always merge the two nodes with the

30:26lowest frequencies. So, first, we're

30:29going to take FF at 15% and the two at

30:3220% and combine them. Next, we're going

30:36to take the one at 25% and our new node

30:39at 35% which we created in the step

30:42before and combine these two. And now in

30:46the final merge, we combine zero and the

30:50node two to create the full tree. Okay.

30:53Now we assign the codes by following

30:57edge labels. Left edges are zero, right

31:00edges are one. So first let's start with

31:03zero. So we go left. Left is zero. And

31:06we end up in the leaf. So zero is zero.

31:10Now we want the one. So we go right

31:13which is one. And then left which is

31:15zero and end up in the leaf. 1 zero. FF

31:20we're going to go right right left which

31:23is 1 1 0. And then for the two we go

31:27right right one one one. And here's the

31:30beautiful part about why this works

31:32without any ambiguity. Let's try to

31:35decode the bitstream. 0 1 0 1 1 0 1 1.

31:40Okay, we start at the root. We read the

31:43zero. We go left. End up in the leave.

31:47And then we reset to the root. We read

31:49the one. We go right internal node. That

31:52means we continue. We read a zero. We go

31:56left. And we end up in the leaf again.

31:59reset to the root. Now we read a one, go

32:02right, then again one, go right, then

32:05read zero, go left. We end up in the

32:07leaf and we reset to the root again. Now

32:10we continue doing this until we decoded

32:13the whole bit stream. And the result is

32:16a perfectly decoded bitstream with zero

32:20ambiguity. Now to demonstrate how much

32:22compression can we achieve with this

32:24Huffman compression. For example, if you

32:27send five bytes, these five bytes

32:30without Huffman that's 40 bits. With

32:33Huffman, it's only 11 bits. So we end up

32:36saving over 70% of data. Now let's take

32:40a look how Quake tree actually

32:42implements this. So Quake Tree uses two

32:47different approaches. an adaptive

32:50Huffman and a precomputed Huffman. It

32:53uses the adaptive for the initial

32:55connection handshake. It is located in

32:57the Huffman. C file. So for adaptive, it

33:01uses this half compress function. They

33:05used precomputed Huffman trees for

33:08regular gameplay packets. Let's open

33:10code q message. C.

33:15Now in message C we have this premputed

33:20frequency table called message huffman

33:24data.

33:26So when starting the game you call

33:29message in it Huffman

33:32and that builds a Huffman tree from this

33:34frequency table.

33:36But how did they use this in the code?

33:39Well, when the game reads or writes bits

33:42in the message functions, it roots the

33:44data through the Huffman encoder if

33:47compression is enabled. Of course, since

33:50the client in the server use the same

33:52Halfman tree, there is no discrepancy

33:54when the payload needs to be coded or

33:57decoded. All of this works because game

34:00network data is a very predictable

34:03pattern. you have always a lots of zeros

34:05from delta compression and you have

34:07small integers for coordinates. So

34:10certain values appear way more often

34:14than others. I mean if the frequencies

34:16were all the same if you have like a

34:19even distribution of the values. It

34:22wouldn't make sense integrating the

34:24Huffman compression in all of this.

34:26Okay. So that means they integrated this

34:29Huffman compression directly in the read

34:32bits and write bits functions. Now

34:35generally speaking the compression

34:37pipeline is highly efficient. PVS cuts

34:40out maybe 80% of the data you don't

34:42need. Delta compression reduces what's

34:45left from hundreds of bits per entity

34:47down to maybe 20 or 30 bits on average.

34:50And then Halfman squeezes that remaining

34:53data by another 50 or 70% by exploiting

34:56the patterns in game data. You end up

34:59taking what should have been multiple

35:01megabytes per second and turning it into

35:04a few kilobytes per second. And the

35:07crazy part is this isn't just clever

35:11compression. It's compression that's

35:13specifically designed around the

35:15patterns that actually exist in real

35:17game data. They didn't just apply

35:19generic compression algorithms. They

35:22built compression that understands what

35:24Quake tree network traffic actually

35:28looks like. And that's why you got that

35:30much compression. All right. So, we've

35:33solved the bandwidth problem, but now we

35:36add the second fundamental constraint,

35:38latency. And this one's a real

35:42mindbender because the solution involves

35:44something that sounds a bit

35:46counterintuitive.

35:47letting every player live in their own

35:50personal timeline from a firstperson

35:53perspective. Now, before we continue, a

35:56word from our today's sponsor,

35:58Brilliant. Instead of refreshing your

36:00inbox for the daily job rejection email,

36:03since apparently nobody is hiring

36:05anymore, just get Brilliant. It's got

36:07interactive courses on math, data

36:09analysis, and computer science that

36:12actually make your brain feel good. I

36:14use it when I need to recover from

36:16making spaghetti and not the Italian one

36:18or when I want to sound clever around

36:20friends who still think I fix printers

36:23for a living. The best part is you can

36:25start from zero. Brilliant takes you

36:27from the basics and builds up step by

36:30step. Even if your attention span has

36:32been reduced to the length of my last

36:34relationship, it's basically an arm

36:36workout for the brain. To learn for free

36:39on Brilliant, go to

36:40brilliant.org/tariq10x.

36:42Scan the QR code on screen or click on

36:45the link in the description. Brilliant's

36:47also given my viewers 20% off an annual

36:50premium subscription which gives you

36:52unlimited daily access to everything on

36:55Brilliant. Now back to the video. Okay.

36:58Now the problem with latency is when you

37:00press a key the signal has to travel to

37:03the server. The server has to process it

37:06and send back the result. And only then

37:08you can see your character move. That's

37:11what we call a full round trip. And on

37:13the internet from the '9s, we're talking

37:16about delays that make the game feel

37:18like you're controlling your character

37:20via screen sharing. There is just no way

37:23to speed it up with elegant software

37:25tricks to lower the latency. If a train

37:28has a top speed of 50 mph, it doesn't

37:31matter how light the fright is that the

37:34train is carrying, it can't go any

37:36faster. So they had to accept that as a

37:39hard limitation and create something

37:41that will give you the illusion that the

37:43game is super responsive. Now their

37:46solution breaks down into two core

37:49mechanisms that attack different aspects

37:52of the latency problem. First we have

37:55client side prediction which makes your

37:57character feel instantly responsive by

38:00running the game physics locally.

38:03Second, we have interpolation and

38:05extrapolation which make other players

38:08look smooth despite receiving choppy

38:10updates from the server. Together, these

38:13two create the illusion that latency

38:15doesn't exist. Now, I have talked in

38:18another video about the client side

38:19prediction, and I have to mention that

38:21Quake wasn't the first game that

38:23implemented it. Ken Silverman was

38:26actually the first one to implement it.

38:28The creator of the build engine which

38:30powered Duke Nukem 3D. He implemented

38:33clientside prediction in January 96, 7

38:37months before John Carmarmac added it to

38:39the Quake World in August 96. You can

38:43also find it in the Duke Nukem source

38:45code and I might be making few more Duke

38:48videos in the future. In my opinion,

38:50it's genius even though it looks like a

38:53very normal concept nowadays. Okay, so

38:56the core idea is very simple. When you

38:59press a movement key, instead of sending

39:01that input to the server and waiting for

39:04permission to move, your client

39:06immediately runs the exact same movement

39:09physics that the server uses. So you see

39:12yourself move instantly even though the

39:15server hasn't even received your input

39:17yet. Now let's take a look at the code.

39:20If you open code C game CG predict,

39:24there is a function called CG predict

39:28player state that runs every single

39:31frame. This is the heart of the

39:33prediction system. I'm going to walk

39:34through this, but on a very high level.

39:38As you can see, there are many comments

39:40in this part of the code. That's usually

39:42a good indicator that a section is more

39:45complicated than the rest in good

39:48projects, of course. Bad projects are

39:51full of useless comments. Okay, so the

39:55client needs to figure out which

39:56commands it needs to execute, what to

40:00predict. Every time you press a key or

40:02move your mouse, the client creates a

40:04command, a little packet of data that

40:07says at this moment in time, the player

40:09wanted to move forward or turn left or

40:12whatever. The server sends back

40:14snapshots to tell you, I've processed

40:17everything up to command number, let's

40:20say, nine. So when the predict system

40:23runs, it looks at the acknowledgement

40:25and says, "Okay, the last thing that the

40:29server confirmed was command number

40:31nine, but I'm currently at command 14

40:33because I've sent five more commands

40:36since then. So, I need to replay

40:38commands 10, 11, 12, 13, and 14 to

40:42figure out where where I should be right

40:44now. Okay,

40:47I'm not going to dig deep into every

40:49line here. So, I'm obviously skipping

40:51some parts. And then at some point, we

40:54arrive at this loop. This loop is

40:59walking through all those unacknowledged

41:02commands one by one. And for each

41:04command, it calls the trap function. In

41:07my last Quake video, I talked about trap

41:08functions if you remember. Trap get user

41:12command to retrieve the command from the

41:14buffer. And then it calls pove. That's

41:17the physics function. And here's the

41:20beautiful part. Pove is the exact same

41:25code that runs on the server side and

41:28it's located in this pove. C source

41:31file. So both client and server link to

41:36the same file. So when your client runs

41:39pove with the command number I don't

41:41know 11, it gets the same exact result

41:46as the server got when it processed

41:48command number 11. The pove function

41:52takes this pove strct as an input

41:56and this strct contains basically

41:58everything you need to run the physics.

42:01It contains the player state, the

42:04command to execute and everything. And

42:06that's the essence why the prediction is

42:09so accurate. So it's not guessing, it's

42:12not a gamble. It's literally running the

42:15same physics simulation with the same

42:17input so it gets the same output.

42:20And then when the update arrives, the

42:22clan just checks if it's been right. And

42:24if not, it starts a reconciliation

42:26routine to get back on track. Now,

42:29client side prediction solves the

42:31problem for your own character. But what

42:34about everyone else? This is where

42:37interpolation and extraolation come in.

42:39And this is solving a completely

42:42different aspect of the latency problem.

42:45So for example, the server is sending

42:47you snapshots at maybe 20 frames per

42:50second, but your game is running at 50

42:53frames per second. If you just displayed

42:56each snapshot exactly when it arrived,

42:59other players would be like teleporting

43:02around. And that's a 100% valid reason

43:06to smash your keyboard. I mean the

43:08client doesn't display the latest

43:10snapshot immediately. Instead, it

43:12deliberately runs about 100 milliseconds

43:15behind which gives it two snapshots to

43:19work with and then it smoothly

43:21interpolates between them.

43:24You can see in

43:27code came

43:29CG ants. C we have this function

43:32interpolate entity position. Okay, so

43:36this function is pretty straightforward.

43:39It takes two snapshots, the current one

43:41and the next one, and blends between

43:43them.

43:45The function uses this pre-calculated

43:48interpolation factor F and which is

43:51basically a number between 0 and one

43:53that tells you how far along you are

43:57between the two snapshots. Meaning if

44:00it's zero, you're exactly at the first

44:02snapshot. And if it's one, you're at the

44:05second snapshot. If it's 0.5, you're

44:09halfway between them. Now, here's how it

44:11works. First, it evaluates where the

44:16entity should be in both snapshots with

44:19this bg evaluate trajectory.

44:24This takes the trajectory data from each

44:26snapshot which includes position,

44:28velocity, and movement type

44:31and calculates the exact position at

44:34that moment in time. This handles things

44:37like entities that are accelerating or

44:41following curved paths. Then it does a

44:44simple linear interpolation between

44:46those two positions using that

44:49interpolation factor F that I mentioned.

44:52And then it does the same exact thing

44:54for the angles. So basically same idea.

44:58Evaluate the angle trajectory for both

45:00snapshots and then interpolate between

45:02them using the same interpolation

45:05factor. So the client is constantly

45:08sliding entities from where they were to

45:11where they're going and creating this

45:14illusion of continuous movement even

45:16though it's only receiving 20 updates

45:19per second. So, what's brilliant about

45:21this whole system is how it creates this

45:26illusion of instant responsiveness,

45:30smooth gameplay despite the fundamental

45:33constraint of latency.

45:36You get instant response for your own

45:38actions through the client side

45:40prediction.

45:41And you get smooth visuals because of

45:44interpolation and extropolation. And the

45:47price you pay is that everyone is living

45:49in a slightly different timeline. I

45:53mean,

45:54most people never even notice that it

45:58works like this. Okay. All right. So,

46:00we've conquered bandwidth and we've

46:02beaten latency. But there is still one

46:05more fundamental problem with the

46:07internet from the '90s. Reliability. And

46:10this is where Quake 3 made perhaps its

46:13most counterintuitive decision. They

46:16decided to embrace packet loss instead

46:18of fighting it. Now, when most people

46:21think about network reliability, they

46:23think about TCP, the protocol that

46:26guarantees every bite will arrive in the

46:28correct order, no matter what. TCP is

46:32like a perfectionist postal service that

46:35will keep redelivering the same letter

46:37until you confirm you got it. and it

46:40won't deliver letter number two until

46:43leather number one is safely in your

46:45hands. For most applications, this is

46:48exactly what you want. But for a

46:50realtime game, this perfectionist

46:53approach is actually suboptimal. See,

46:56the thing about game data is that it has

46:59an expiration date. If a packet

47:02containing last frames player positions

47:04gets delayed by half a second while TCP

47:07tries to retransmit some earlier packet,

47:10that data isn't just late. It's actively

47:13harmful. You don't want to know where

47:15players were half a second ago. You want

47:19to know closely as possibly where they

47:21are right now. So Quake 3 made a radical

47:25choice. They threw out TCP entirely and

47:29built their reliability on top of UDP.

47:32UDP is like a much more relaxed mail

47:36service that just throws packets at

47:38their destination and hopes for the

47:40best. If a packets gets lost, well,

47:43maybe the next one will make it through.

47:46Now, if you're looking for reliability

47:48logic in the network transmission code,

47:51you're not going to find it there. Let's

47:53open the net channel code and look at

47:55the net channel transmit function. Okay,

47:58this right long takes the message and it

48:01adds a sequence number so you can detect

48:04packet loss and then this net send

48:09packet sends it over UDP and moves on.

48:13So where's the reliability?

48:17Well, it's built in at a higher level in

48:20the message system and both client and

48:23server have their own implementation of

48:25it. So on the server side, if you look

48:29at the code code server server main C,

48:34there's a function called add server

48:37command.

48:41This is where messages that absolutely

48:44must arrive get stored like

48:47player joined, map changed, or I don't

48:50know, server settings updated. These

48:53commands must go into the reliable

48:56queue. So, the server keeps these

48:59commands in a circular buffer and

49:02resends them with every outgoing packet

49:04until the client acknowledges them. On

49:08the client side, it works the same way,

49:10but in reverse. If you look at the code

49:14in code client

49:18clain C, there's this

49:21add reliable command. So this handles

49:26reliable messages from client to server

49:30things like changing your nickname,

49:32sending chat messages or requesting map

49:36downloads. So, we have the same circular

49:40buffer pattern, same same logic. Both

49:43sides keep resending their reliable

49:45commands until the other side says,

49:48"Okay, I've received it." But here's

49:50where it gets really interesting.

49:54How do you make a system work when most

49:56of your data is being sent unreliably?

50:00The answer is one of the most elegant

50:02pieces of engineering in the entire

50:04Quake 3 code base. It's the circular

50:07snapshot buffer.

50:09I mean, the idea is brilliant in its

50:12simplicity. Instead of trying to make

50:13sure every packet arrives, they designed

50:16a system where losing packets doesn't

50:18have a major impact. Both the server and

50:21the client keep just a rolling window of

50:23the last 32 snapshots they dealt with.

50:26So, when the server wants to send you a

50:28new snapshot, it doesn't just delta

50:30against the previous one. It can delta

50:33against any snapshot in your 32 slot

50:36window that it knows you received. Let

50:40me show you how this works. So in the

50:42code, if you open the server snapshot C

50:46file, there's this write snapshot to

50:49client. This is where the server decides

50:53which snapshot to use as the base for

50:55the delta compression. The server tracks

50:58which snapshot the client last

51:00acknowledged in client delta message. So

51:03if the client says I got snapshot 27 but

51:06snapshots 28 29 30 got lost. The server

51:10just delta snapshot 31 against snapshot

51:1327.

51:15In a traditional system this would be a

51:18disaster. You would either have to

51:20retransmit all the missing packets or

51:23send a huge full update. But the with

51:26this quake system, missing packets in

51:28between don't really matter that much.

51:31And the circular buffer is using this

51:34binary mastrix. So no complex buffer

51:38management is needed. On the client

51:40side, we have code client client

51:44parse.c.

51:45We have this client par snapshot

51:47function. The server tells the client

51:50which snapshot to use as the base. The

51:52client looks it up in its own circular

51:54buffer. applies the delta and

51:57reconstructs the current state. If you

52:00have any missing snapshots in between,

52:02it doesn't really matter. So, the end

52:05result is a system that's incredibly

52:06robust against network problems. It's a

52:09system that handles problems gracefully

52:12instead of failing catastrophically.

52:15So by designing around these actual

52:17requirements instead of trying to force

52:20a traditional reliability model, Quake 3

52:23created a network system that's both

52:25more robust and more efficient than

52:27anything based on TCP could ever be. And

52:30that's how they solved the reliability

52:32problem. It's the same kind of paradigm

52:35shift we saw with the bandwidth and the

52:37latency. Instead of fighting the

52:39constraints, they embraced them and

52:42designed around them. conclusion. You

52:45know, I'm sitting here looking at all

52:47this code and I'm thinking how wild this

52:51whole story really is. Like, imagine

52:54everyone's telling you that what you

52:56want to do just can't work. The internet

52:58is too slow, too unreliable, and too

53:02broken for realtime gaming. And

53:04honestly,

53:06they weren't wrong. I mean, the numbers

53:08were pretty brutal. But instead of

53:11giving up, these guys did something that

53:13still makes me smile when I think about

53:16it. It's just like having a drink with

53:18the boys and saying, "Hell yeah, let's

53:19let's do this." I mean, they looked at

53:22every single limitation and basically

53:25said, "Okay, what if we design around

53:29this instead of fighting it? What if we

53:32don't care about packet loss? What if we

53:34don't try to keep everyone perfectly

53:37synchronized all the time? What if we

53:39just embrace the chaos? And that's

53:42exactly what they did. Every technique

53:44we just walked through, the delta

53:46compression, the client prediction,

53:48Huffman, none of it came from having

53:51better hardware or faster connections.

53:54It all came from being clever about

53:57working with what they had. They turned

53:59their constraints into their competitive

54:01advantage. Innovation always comes from

54:05limitations. And the crazy part is how

54:08well it worked. I mean, we're still

54:10using these exact same ideas today. When

54:14you're playing Call of Duty or whatever

54:17game came out for $80 this month, you're

54:20experiencing the direct descendants of

54:22these techniques. 25 years later, and

54:25nobody's really come up with anything

54:29fundamentally better. And that's how you

54:31know something is truly revolutionary.

54:34When it doesn't just solve the immediate

54:36problem, but it becomes the foundation

54:38that everyone else builds on. The best

54:42solutions often come from the worst

54:45situations. When everything's working

54:47against you, when you have no choice but

54:49to think completely differently. Some of

54:52the most elegant code I've ever seen

54:56came from developers who had their backs

54:58against the wall and had to be creative.

55:00Anyone working in embedded knows this.

55:03It's easy to develop when your software

55:05has to run on 16 gigs of RAM. But how

55:09about I give you 4 mgabytes and I also

55:12want you to do a flash over the air with

55:14a AB swap. It makes you wonder what

55:17problems are we just accepting today

55:19because they seem too hard or too

55:21fundamental to change. What assumptions

55:24are we making that maybe we shouldn't

55:26be? Because if there's one thing this

55:28story teaches us is that sometimes the

55:31impossible is just waiting for someone

55:33brave enough to ignore what everyone

55:36else says can't be done. And I'm not

55:38trying to give you a motivational speech

55:40how everything is possible because we as

55:43humanity clearly can't even manufacture

55:46printers that work when we need them.

55:49Okay. Now I want to take the moment and

55:50say a big thank you to my patreons and

55:53YouTube members. Your support over the

55:55past year really helped me. Your

55:56memberships, messages, emails,

55:59everything. As you know, I'm

56:00continuously upgrading my setup, trying

56:02to improve the format, experimenting

56:05content-wise, trying out new ideas, and

56:08also listening to constructive

56:10criticism. Your comments and suggestions

56:13really help me to create better and

56:15better content. If you want to support

56:17the channel, there's a Patreon link in

56:19the description or you can become a

56:21YouTube member or just leave me a

56:24comment. So, that's it for today. If you

56:26like the content, hit like and subscribe

56:28and see you in the next one. Tik T.