1000 Players - One Game of Doom

if Doom runs on everything and I mean it even has its own subreddit for what it runs on why not have one instance of Doom run on everything and while I'm at it why not just let twitch control the Doom guy this actually sounds pretty easy right just have twitch show doom and then everyone can run around using twitch chat right well it turns out that the average twitch experience is over 5 seconds behind but I tried it anyways and it took twitch over 1 minute to open this door obviously the whole asky Doom thing was probably a little bit weird but hey hear me out I've been exploring this idea of a realtime game engine but it's all asking so I thought using Doom as like a test bed would be a great idea because I wanted everyone to be able to see the same game at the same time and be able to play it together on Twitch like a happy family a very degenerate family but a happy family nonetheless technically mind sweeper was the first game that I ever did and yes it is being displayed in neovim and yes twitch is not that great at mind sweeper therefore I'm going to have to create my own packet formula my own network compression and my own web display to be able to have Doom displayed everywhere not because I need to but because I can therefore I just have to build a couple pieces first I just need to be able to build a program that can spawn the asky program parse out all the data frame it and send it up to a server now this server is going to have to be able to take in a bunch of connections from all the clients coming in and be able to send down all of that P packetized frame ised whatever ised data so that the clients can happily see it on their computer and of course in life there's two things that are unavoidable one death two Engineers that chronically underestimate how difficult things will be this is the first frame of Doom displayed in asy this is that same frame but this is the ansy codes that actually are required to display Doom in those colors ansy always starts off with an escape code followed by an Open Bracket followed by a command one colon one moves the cursor to the top left of the screen 2J clears the screen colon H is Shand for move the cursor to the top left of the screen 1 M makes any succeeding characters bold 38 colon 2 colon 116 colon 001 colon 001m will color any text dark red then finally we're followed by two L's which is almost as many L's as the average Twitter post and that's how you get two dark red L's every color has its own escape sequence so now to parse out the frame I had to look for SLR slns or as I like to call them a registered nurse and of course the semicolon H to denote the end of a frame and boom there we go we're done we've parsed out all the data now I can easily send it up to my relay server which will relay it out to all the clients like that was actually it that's pretty easy right well this is where things took a little bit of a dramatic turn instead of being done with the project I really just started the project so let's think about it this way every single frame contains a bunch of characters and a bunch of colors right so that means I'm going to have to store the characters I want to send plus the color of those characters by the way this is the American spelling of colors the proper way okay no CS around here now if each color takes three bites to store one bite for red one for blue and one for green green of course being in the middle and then one bite for the ansy character because an is really a seven bit but you know you typically store it an eight that means it's four bites per little character now there wasn't that many characters there was 212 characters by 66 so that's probably not that many right well if you happen to multiply that by four you get about 56,000 bytes per frame there's 30 frames a second there's going to be a th000 users that'd be 1 Gigabyte per second or anywhere between 2 to 12 cents per second if I were to run this on fly iio you know I like you guys but I don't really want to spend something like $150 an hour to have Doom run so that means I'm going to have to create my own compression algorithms because again I just want to do it okay I just want to I want to go and explore something I've never built before because honestly that's what makes engineering fun is just Reinventing the wheel and seeing how well you can do so first I had to create a baseline test so I actually let Doom just run and I'd let it run for 10,000 frames and then I would determine how much data would I have to send up to the relay server to see am I making my encoding better or am I making it worse so just doing nothing would be about five 545 megabytes worth of data sent for 10,000 frames of data I think I could probably do a lot better than that you know I think I'm a pretty smart fell so I figured if I could just look I just look at the asy maybe something will stand out how about you look at the asky does anything stand out to you here I'll zoom in does anything stand out here if you look closely you'll see that each character duplicated that means I can take out half the data and then reproduce it on the client side and with that one little change we are now down to 272 megabytes for 10,000 frames okay better not good better though all right so I want to do this again now look at this if you look at the screen carefully you will notice something White characters are always dollar signs W's tend to be really light colors dark colors tend to be really small characters and of course looking at the Doom code it did turn out they generate the ASI based on the brightness of the color so that means I could drop every single character and on the other side I could just generate the character based on the brightness of each cell this change took us from 272 mbes to 204 mbes this was a big Improvement so my next idea a bit controversial I took the red the green and the blue and instead of having a bite for each I projected each one into a single bite so red would would take the first three bits of a bite green would take the next two bits and blue would take the final three bits which led to this definitely not an Abomination code and of course that change brought us from 204 to 68 megabytes for 10,000 frames okay now we're cooking now we're making some actual progress here then there's another thing I noticed look at this load screen did you notice that it didn't change a whole bunch well why send duplicate frames I bet you there's a bunch of duplicate frames yep there was we went from 68 to 35 megabytes for 10,000 frames now these changes have all been good but I haven't really actually compressed the data I'm really just taking stuff out and implicitly hydrating it again on the client or in the case of colors just making it kind of look ugly so now it's time to actually start doing some compression so at this point I knew I probably need to start pursuing maybe some more sophisticated techniques the first technique I pursued was actually called Rite I've used this once in the past I didn't know its name but effectively it just means run length en coding so let's pretend you had the following string wwwww d d Mega do R if I were to compress this with run length en coding what I do is I look at the first character then at the next character if they're the same I keep going and I keep going and I keep going until I encounter a character that's not the same and then go 5 W so I took five bytes and compressed it into two bytes so if there's a nice run length of the same items you can really compress well so this D becomes 2D and then this R becomes one R and as you can see with the r it actually encoded it worse because it took up two characters instead of one the D was the exact same but the w we really won on and when I look at the data like you'll notice that there's like a whole bunch of L's in a row there's a whole bunch of in a row right there so I figured this has to produce some sort of win right yes it did we're down to 28.9 megabytes okay we're winning but we could actually make this even better I don't know if you know anything about exor exor is a bitwise operation but something that's unique about exor is that it actually has memory let me show you what I mean by that let's say that you have a and it equals 1 1 0 0 and you have b equal 1 0 1 0 if you were to exor these two together or exclusive or them together which means that if there's one one then it's a one if there's two ones it's a zero or two zeros it's a zero we would produce the following so I'm going to set a to the results of this so that'd be 0 0 0 0 1 1 1 0 one one one again that's not exclusively or zero now with this value right here I can recreate either of these values using the opposite let me show you what I mean by this I'm going to assign B the xor of these two so 0 0 0 1 1 0 0 1 1 1 0 1 notice now that b is the value of a we just swapped B and A a so if I were to redo this one last time with a I could actually now have a equal B by doing 0 1 0 1 a is now equal to b b is now equal to a we swap the values without ever having a temporary variable this is actually one of the fundamental basis of Ford error correction in web RTC what it does it takes all of your packets and then adds one more packet at the end that is the exor of all the previous ones because if you only miss one packet it can actually restore that by xoring any of those together remember web RTC uses UDP which is an unreliable program and it doesn't even come in order so let's actually apply this to our frames that means we could take frame zero and we could exort with frame one this is going to produce a frame exort that means if we have frame zero that has almost the exact same image as frame one we're going to largely produce a frame that will be just a bunch of zeros and then the place that it's not will have some ones and if we use the previous frame we can generate the next frame because remember exor has memory that means if we combine exor plus rle we could potentially get a whole bunch of zeros in a row and then just get really nice run length encoding and it does turn out that is the case we are now down to 21.8 megabytes for 10,000 frames we are now better but we need more so let's talk about the next thing we're going to do we're going to bring in Huffman and coding if you've never done Huffman and cating like I never did up until this thing I've never even tried to build it it was tons of fun to try to build but how Huffman encoding works is really simple let's say we have the following string a b c a b d a what Huffman does is first takes the frequency of every single character so there's three A's 2 B's 1 c 1 D we're going to take these four values and we're going to put them into a Min heap if you're not familiar with the Min Heap it's pretty dang simple it just takes the smallest values and will pop them first there's no other guarantee in order other than removing the smallest elements so what we're going to do is remove two elements at a time and combine them so we'll start off with these two we have a c on one side and we have a d on the other side then we're going to add those two numbers together and put it back into the priority Q so now we're going to remove the next two minimum ones right here which is going to be this kind of amalgamation of c and d and 2B which is going to create the following tree we're going to have B on one side and then we're going to have our C and D on the other side now we have a weight of four 2b + 21 1 put that back into our Min Heap pop up the next two and we're going to get the following we're going to have a on one side and then we're going to have B on the other side now we take this tree and we actually give it some binary values we put a zero on the left hand side a one on the right hand side and you just keep on doing this all the way down now we actually have our encoding for a b c and d so originally a b c and d is actually stored with seven bytes but using Huffman and coding we can actually store it with only two bytes so check this out a is just a zero okay zero B is 1 0 C is 1 1 0 a is just zero B is 1 0 D is 1 1 1 and the final a is a zero that means we still have three bits left in which we're just going to put little X's right here because we don't need those but this is now our Huffman encoded bits and you can see something unique about this you can never run into a situation in which you have an ambiguous result when I parse out the first bit it's a zero it goes to a definite character within the tree you can never have one bit potentially go two different directions so it's always unique you just simply need to know how many bits were encoded because you could run into the situation where you have some extra junk at the end which would thus cause potentially bad encoding now adding in Huffman we are down to 15.99 megabytes okay this is looking good for 10,000 frames and of course if I take all the strategies and combine them together it actually gets us all the way down to 13 megabytes that is looking so good that means approximately every 5 minutes and 30 seconds it will cost me about 1.3 1.4 1.5 GB now we're talking okay I don't mind spending $5 to $10 on your degenerates per hour of course per hour lastly I just had to figure out how to get twitch to control now this was actually a pretty fun little exercise size so twitch chat just like floods in with all the characters and what I decided is that I will measure for 250 milliseconds and then take out the most occurring value say this W and then for the next 250 milliseconds do the exact same thing and what I'll do is during this measurement period I will play out the W every 16 milliseconds to simulate it being held and this is it and that's all I had to do is just feed those keys back into the game and then I should be able to play this I do want to make a shout out to steuart he actually gave me a server for me to run this for free with really high bandwidth and actually made this a success so hey thanks Stuart appreciate that stut Dev let's go and we did all of that work just to watch Twitch chat be defeated by some stairs yes oh oh oh and again failing on stairs and again failing on stairs and again failing on stairs oh wait oh wait no and of course this ultimately ended with us actually winning it was a clencher maybe I set the difficulty to the lowest difficulty but we got it okay we got it yeah that's right me from the past we were so pumped and then all they had to do is walk through this door of course which was just so painful to watch also if you'll notice that twitch chat would like freeze and then we couldn't move move because we are sending too many characters we are hitting the limit of twitch and boom beat the level let's go high five me yeah yeah and there you go that's what it looks like when a thousand people beat Doom together the pure raw athleticism that was missing the staircase repetitively but nonetheless they did it so hey give this video a like hey you subscribed name your child after me give me your Twitch blue crap subscribe to my vs code only fans where I do some real dirty JavaScript coding the name is the primagen

Channel: ThePrimeagen

Views: 201,765

Keywords: software, vim, programming, javascript, typescript, software engineering, web developing, web developer, software developer, developer, cpp, programmer humor, humor, reactjs, js, ecmascript, tc39, Netflix, Engineering, Engineer, Facebook, Amazon, Interviews, Software Interviews, vimrc, neovim, spacevim, vim c++, vim editor, text editor, vscode, vscode vim, vim plugins, autocomplete, vim autocomplete, nodejs, twitch, developer productivity, spacemacs, algorithms, datastructures, Data Structures, python, bash

Id: 3f9tbqSIm-E

Length: 15min 41sec (941 seconds)

Published: Thu Jun 13 2024