What... You only understand half of what a video is about and thoroughly explains? That's like reading a well written recipe and still not understanding how to make the dish. That's some deep idiocy, good on you for daring to share that.
I bet the Nintendo employee(s) who coded the decompression behavior never would have guessed anyone would’ve made a video on their work, let alone even be noticed. I bet they would be pretty happy to know their work is being praised :)
Technically, it was Game Freak employees, Nintendo is just the publisher and didn't have any direct hand in the development of the gen 1 Pokemon games.
I dreaded this video, but it turns out this compression algorithm isn't nearly as complicated as I expected! This is finally a video of yours that I understand again! The method of efficiently encoding numbers of arbitrary magnitude in bitstreams by splitting them into their length, encoded in unary, and themselves, encoded in binary without the leading 1, has a name. If I recall correctly, it is called "Gamma coding" (as in the Greek letter that looks like an upside-down capital L).
"Elias" gamma coding is the only encoding method I could find that is similar, but it's slightly different than what's used here. But perhaps it would be correct to call it an alternate kind of gamma coding!
Good luck if you ever study LZ compression, and more advanced encoding schemes... RLE and delta coding is simple in comparison. some people build compressors from reverse engineered decompressors that are significantly more complex than poke
You explain these algorithms better than any college lecture I've seen so far. Could you make a video about Iwata's compression algorithm that was used to fit Kanto into Gold and Silver? I think it was found in the recent leaks.
That's would be so amazing to see. It's always talked about how he saved the post game by squeezing everything in, but I haven't seen anyone explain how.
the compression iwata/HAL contributed to gen 2 isn't as space efficient as gen 1's - it was used because it was much faster to decompress, and the gen 2 prototypes ran very slowly without it. it wasn't about fitting another region in, game freak had more than enough space to spare.
It's so rare to see so much effort put in to a video. You didn't have to go so far as to actually animate the decompression but you did. You didn't have to make that web app but you did.
He didn't have to do the animations but If he didn't I probably would've been lost. I can understand some fairly complex topics but when I just read a description without visual aids I often find myself struggling with otherwise simple enough concepts (Generally speaking I'm primarily a hands on learner with visual learning a close second).
Yes, he did. If he didn't do that he wouldn't stand out much. He is not the only reverse engineer on UA-cam, so if he wants to impress anyone, he has to do those things.
So is this the main cause of the long delay when you encounter a Missingno? That is, the sprite decompression algorithm spending several seconds spewing junk bits all over the game ram. Are there any other causes?
Retro Game Mechanics Explained I noticed when performing the glitch in Pokémon Stadium that loading the sprite causes the game to save. Do you know what could be causing that, and do you think that could contribute to the loading time?
@@albertnortononymous9020 The Game Boy (and many other cartridge based systems) have extra RAM on the cartridge. Some or all of this extra RAM has a battery to keep it powered even if the cartridge is removed, allowing the game to save. However, you can still use that cartridge RAM for anything you want, since you know it will be present when running the game. That includes storing the Pokemon sprites during decompression. I'd imagine the way Pokemon Stadium works to tell you the game is saving when using the GB Tower is it watches the parts of RAM that the game saves to (such as the Hall of Fame, that gets corrupted when encountering Missingno). Normally this is only written to when saving the game, so Stadium shows a saving indicator. When Missingno is encountered, the decompression algorithm breaks out of the space it normally occupies, and overflows into the Hall of Fame data, corrupting it and rendering it unusable. Since the game is writing to the save "file", Stadium thinks the game is saving.
As a professional Architect of large scale systems and an avid lover of retro systems (even made my own Atari 2600 game).... DAMN. That's some serious software engineering going on there! Fantastic explanation, BTW!
The fact that a team of only FIVE programmers had a hand in making a graphics system this complex, yet effective, for a Game Boy game (while leaving in SO MANY glitches elsewhere in that game) is insane!
I've worked on decompression algorithms for a couple of games on the Nintendo DS, both using RLE techniques and JPG. But the method used by Pokemon is another level of RLE, much more advanced than what I used back in the day! Also, outstanding video and explanation, thank you very much for sharing!
17:15 that moment when the previous 5 minutes actually made sense. I kept forgetting that despite reading individual bits we we're reading them to write PAIRS of '00' which is how the compression was actually able to be efficient.
I remember hearing from GameHut about RLE encoding, but the way he explained it left me wondering "Yeah, but how do you actually do that?" *This* video truly explains how the game does what it does, and that is why I love this channel. Keep up the great work, and I'll look forward to whatever's next!
Yeah, GameHut explains how he has programmed stuff, and Retro Game Mechanics Explained explains how the functions themselves work. They explain on two different levels. Because of the depth that RGME goes into, he needs more videos for just one topic.
@@ThatGamerBlue Automated Teller Machine Machine, Ramen (Noodle Soup) Noodle Soup. Love GameHut's explanations as well but he definitely keeps things more surface level (which is still great).
I've been wondering this for some time now. I've heard everything from Gamefreak ran out of space and Iwata compressed the data better, to Gamefreak had plenty of space but it didn't run fast enough. Unfortunately, it seems like the topic only picked up interest after Iwata's passing.
@@danimalforlife I find the former more likely. If it's already not running fast enough then compressing it isn't going to help at all, especially on as slow of a CPU as the Game Boy and Color have. Conceivably you could address the problem with bigger ROM chips and just more bank switching but that relatively small cost for one cartridge adds up spectacularly. Pennies matter in quantities of millions.
@@sedrosken831 I ended up looking into this more. Still up in the air what exactly Game Freak's thought process was, but performance seems to be the determining factor as Gen 1's RLE compressed better. They sacrificed a little bit of space, but the final product does seem to run faster than in the Spaceworld 97 demo. www.reddit.com/r/Games/comments/hwlylf/while_it_is_true_that_iwata_did_write_a_new/
I come away from these videos with three emotions. One is being overwhelmed by the torrent of information I get during the vid. The second is awe at the work that goes into memory management and streamlining for games. The third is just an incredible respect to RGME for not only being able to understand what's going on under the hood, but also to reverse engineer and present said understanding to people who have never encountered such techniques. Love this channel.
Very likely that Iwata had a hand in the compression code. Man was an ABSOLUTE UNIT, he managed to squish GSC enough to find room for Kanto. His apprentice managed to squish Smash Ultimate like crazy.
Unlikely, Iwata ported the battle system from rby over to stadium from scratch, which implies he wasn't familiar with the code. He also was employed by HAL laboratories at the time and not game freak.
It's understandable people miss Iwata, but I cannot help but get the feeling at this point, people are just finding excuses to bring him up in conversations... Iwata had a hand in the compression algorithm for Gen 2. I don't even know if he ever worked on the mainline games before or since.
@@shadowmanwkp that doesn't imply he wasn't familiar though? Gameboy and n64 games were totally different. They ran different architectures, and n64 games were mostly developed in C. It makes total sense for him to make it from scratch regardless of if he was familiar or not
Knee Snap or he could,ve just compile the gameboy’s Z80 code into the N64’s risc code instead to save time , the compilor will automatically put a flag on unsupported features of that target processor,the only thing iwata had to do was debug & alter the compilet code to make it work. Am mean why would you ever want to do everything from scratch because of a different type processor if a compilor does exist???
I can't say anything about Iwata's involvement in this, but those techniques are common knowledge in this field, and were even more widely known and used back then. This is clever but at least something along those lines is to be expected of such a game. I can't say I would have managed to optimize it that far but at least I'd use a technique at 6:05 which would give a decent compression for the system. If bit-planes are split anyway it would come more or less naturally to delta-code them, and then XOR modes would probably come after a bit more thinking. This, working in unison, is still clever though.
I have so much respect for the people who coded this game. no matter how "broken" it seems, it's still incredibly impressive to me that they managed to do all this.
amazing video, i am at loss of words at how good your explanations are and how much effort you put into every video (i mean, i absolutely did not expect a web app to be made just for this, but you did it any way) and the fact that this kind of video only attracts a niche audience shows how big your passion is on these topics. again, kudos
@@Smileyrat it probably was, the problem is they optimised their compression algorithm using their knowledge of sprites, but did not optimize this bit using the same knowledge
Yeah, it seems plausible that they just didn't know if they were going to need non-square sprites when they decided on the data format. And since they obviously didn't end up needing the extra storage, why bother changing it.
This was one of my absolute favorite videos! I always appreciated the level of detail you put in. It inspired my to write my own version of the decompression algorithm in python and scrape all the sprites from the game cartridge. I had such a fun learning experience working with exciting computer science principles with old nostalgic subject material. Thanks for making this information easily available! If your ever looking for nightmare fuel, the delta encoded first bit plane of Pikachu in Pokemon Blue (US) has some strong Five Nights at Freddie's Vibes XD
18:00 One fun further optimization you can do is to just immediately write the terminating 00 of the data block to the output when you read it, and then just _not_ add that extra 1 to the length of the next rle block since you already just wrote the 00 from the data block.
What I find mind-blowing about all this, is how quick it happens despite the Game Boy CPU not really giving you the tools to do this effectively. Coding the unpacking routine seems more difficult than coming up with the compression scheme itself.
Great video! Something that would be neat to see, at least on the website, is an animation showing off how a finished image is compressed into a small number of bits.
I think I'm gonna have to watch a few times to fully grasp everything, it's pretty complex for someone who knows close to nothing about the subject, and yet I want to understand
The webapp made for this is one of the best that i've ever seen, and i really, truly, genuinely mean it. Far too many websites these days are bloated, overcomplicated crap (and the W3C is in part to blame for allowing that, mind you), yet this is a refreshing bit of simplicity. Thank you.
It's so interesting to see how similar this decompressing method works compared to genetics. Not exactly the same, ofc, but the overall "grammar" is quite alike
This 30 minute video took me about an hour and a half to watch because of the immense amount of time I spent with the video paused and going back a minute or so to listen to something again before finally understanding it lol. Thanks for everything you do, dots!
@@ctb3335 Not exactly, Color data was not added to the original cartridges, they had no way of knowing in the og GameBoy days that a Color system would come out with backwards compatibility (because even Nintendo didn't know until they started getting request by devs to make a Color GameBoy). GameBoy Colors actually had a lookup table in their firmware that was used to add color to all og GameBoy games created before the Color came out. Later/transition games had additional data for color just as some transitional games between the Color and Advanced had additional features that took advantage of the Advanced hardware (like wider screen and extra button support).
0:36 That's an interesting point you make there, Mr. RGME! You should tell it to my teammate from senior design, who wrote some compression code but refused to write a decompressor because "we're not testing for that!"
(13:50) My initial idea was to use 00 as the terminator here as well, and use a form of counting that does not include 00 in the middle of it. So that is: 1, 10, 11, 100, 101, 110, 111, 1010, 1011, 1100, ... and a series of zeros at the end means all zeros except for the last two belongs to the number. Then 45 would be encoded as 111110(00), 8 bits instead of 10. But covering this non-standard number to an actual binary number might be too time consuming, and might not be worth it. Plus my system requires more bits for 1,2,4-6, is the same length for 3, 8-14, 27-30 and only saves 1 bit for numbers 7, 15-26, and starts saving 2 bits from 31 and up. So my method isn't that good now that I've looked at it.
1:46 [sees the Charmander sprite split into two images] "but there's four colors displayable on a Game Boy, the lightest is nothing so that makes seOOOOHHHHHHH the overlap between the two is the darkest color, gotcha gotcha gotcha. I feel smart now. OK keep talking."
Decompression rules: 1. Check the first binary digit. If 0, it's a RLE packet. If 1, it's a data packet. 2. In a data packet: Copy every string of two bytes to the decompressed string until a string of 00 is reached, then start a RLE packet. Go to step 3. 3. In a RLE packet: Follow steps 4-8. 4. Start reading binary digits until you get into a 0. Count the number of binary digits you read, including the 0. 5. Read that same number of digits after the 0. 6. Add the digits that you read before the 0 to the digits that you read after the 0, in binary. For example, if 0110101000101110..., after the original 0 saying that it starts with an RLE packet, you read 2 1s and a 0 (110), saying that you need to read 3 digits after (101). Add the 110 (6) to the 101 (5) to get 1011 (11). 7. Then, add 1 to the sum. (For example, 1011, or 11, +1 is 1100, or 12.) 8. Copy that number of 00 pairs to the decompressed string, then start a data packet. Go back to step 2.
I'm not an especially smart person, but nonetheless your videos make me feel like I'm watching a university lecture. I'm just thankful I can pause, rewind, turn on or off subtitles, and watch it again before the exam!
Whomever came up with these bit packing tricks was a bloody genius. Adding the number to its own length, using a terminator for the data packets, binary delta coding... So many excellent ideas.
Dude, You really are exceptional .. Not only knowing and understanding the content, but how to display it, all the animations and scripts to make these videos.. You should be proud of yourself.. Cheers from Regina Canada.
I know its old, but this is the kind of stuff i was fascinated by when the only things i had to program were a ti-85 and Palm Pilot in middle school. Definitely earned a sub from me!
Having an insanely complicated algorithm to compress data in the most efficient way and then using a look up table to flip a number is the epitome of rby
Ty for this video! I've used what I've learned here for a bitmap font storage function, getting decent compression and increasing the display speed by a lot.
Regarding the web app: you don't actually need to have the upload button; you can use the change event on the input (e.g. `$("#binFile").change(uploadBinary)`). That would probably also avoid confusion with it being an upload to a server vs local processing.
This is a great video. The encoding method is pretty intuitive - I mean, knitting patterns use RLE - but I never knew the actual mechanics, or why it caused glitch pokemon to look like that. I was wondering if you could talk about GSC's sprite compression? Gen II sprites have a distinctive amount of dithering, which doesn't compress very well with these methods (tested with your web tool!) so I imagine they used another method to encode that efficiently...?
Excellent video as usual! Even with these Pokémon graphics videos getting pretty beefy, they remain super interesting. I've been thinking lately about how Satoru Iwata supposedly helped improve on the image compression in Gold and Silver. I haven't really seen anyone get into it more substantially, though, so I'm curious: are there any major differences in how Gold and Silver compress graphics, or were Iwata's contributions most likely just in the realm of more consistently making the most of the existing algorithms?
Love your videos! Both for the technical details, and the ease at which you describe. I noticed something with your RLE explanation around 14:00. The encoding of N is actually rather inefficient for large N. The example you give, 63282 represented with 30 bits is inefficient compared to the 16 bits to represent the original number. Perhaps they could have used 4 bits to specify the length of N as 1-16 in every case. This gives a Best case of 5 bits or worst case of 20 bits. However, their way is likely more efficient if they are expecting less than 32 packets in a row to be a common case. This is because 31 in RLE is 1110 1111 which is just as efficient as 0011 1111. Given the size of the sprites and sprite data, I would bet theirs is more efficient since the chance for N
Of course 16 bits to write the number in plain binary is more efficient, but you have to know the size of the number beforehand! If you don't, you have to encode that information as well. Simply encoding the length in unary and appending the original number would take 32 bits, but the method shown in the video does it in 30. The issue with using a constant number of bits is that it becomes very inefficient for groups of just one or two 00 pairs (which are fairly common). Using 4 bits to write 2 bits is the opposite of compression!
I love these videos and this channel.. It would be very nice if you cover some 3d games also, like explaining how StarFox uses FX chip or how some 3d games works using the co-processors to help handle the 3d rendered (or to render all the 3d at all and pass to the console)..
Heck yeah A new video I can't wait to learn more about how Pokémon was programed Seriously For some reason this stuff always interested me Especially the glitches and how they even work So Thank you Thank you so much for making these videos
5:45 Ah yes, RLE: the only compression algorithm I actually understand well enough to implement...although I didn't go quite as far as GameFreak and just used a byte for each value. No "data packets" either, just basic RLE. It is a good algorithm to understand, though; fairly quick and very simple, yet very effective for a lot of different data used in sprite-based games.
Me: "Is it using RLE? I bet it's RLE. Is it RLE?" 5:42 - "A method known as RLE" Me: "Yesssssss" The use of delta encoding was something I didn't expect. But it makes perfect sense. They really tried everything they could to minimize the sprite data size. Thanks for making this video! It was very interesting.
man, retro game designers were clever, xor'ing is such a simple concept to make it a stream of 0's (only recording when a bit changes) but id have never thought of that
28:33 This feels like the big reveal at the climax of a story. That the big secret you were looking for all along was right with you the entire time. The payoff of learning that Sheik is delta encoded Zelda.
Great video! I love these sorts of deep dives into algorithms. It's cool how the limitations of the time motivated such a complex and clever algorithm. I wonder how often that happens today, given that we have more computing power, so there're fewer incentives. QQ: - How much space did this method actually save (on average) compared to just storing the sprites naively? - Did you glean all of this info from reverse-engineering the game, or were you able to track someone down to ask questions of?
Watching the decompression animations is like playing "Who's That Pokemon" only actually somewhat difficult.
It's PIKACHUUU!
ua-cam.com/video/IfQumd_o0Gk/v-deo.html
Pretty sure it was actually Mew.
it's the food i had for breakfast
and then the entirety of the raw decompressed data is impossible mode
its like playing whos that pokemon but you forgot the names of most of the pokemon
Man.. I still wonder why I am so obsessed with these videos, even though I understand only half of the content
funni pictures go "make"
I was on board until recently, this one (and a few previous) sealed my unsubscribe.
I understand them perfectly and love them because they are something complex which has nothing to do with highschool. They are nice for a break.
What... You only understand half of what a video is about and thoroughly explains? That's like reading a well written recipe and still not understanding how to make the dish. That's some deep idiocy, good on you for daring to share that.
@@MuscarV2 don't be so rude.
I bet the Nintendo employee(s) who coded the decompression behavior never would have guessed anyone would’ve made a video on their work, let alone even be noticed. I bet they would be pretty happy to know their work is being praised :)
Didn’t saturo iwata make the compression system?
i believe he made that for g&s's map data
@@Spunney ohhh alright
Japan's view on the internet has been very not good,but I agree that they'd be impressed with people decoding how this works.
Technically, it was Game Freak employees, Nintendo is just the publisher and didn't have any direct hand in the development of the gen 1 Pokemon games.
I dreaded this video, but it turns out this compression algorithm isn't nearly as complicated as I expected! This is finally a video of yours that I understand again!
The method of efficiently encoding numbers of arbitrary magnitude in bitstreams by splitting them into their length, encoded in unary, and themselves, encoded in binary without the leading 1, has a name. If I recall correctly, it is called "Gamma coding" (as in the Greek letter that looks like an upside-down capital L).
Γ
"Elias" gamma coding is the only encoding method I could find that is similar, but it's slightly different than what's used here. But perhaps it would be correct to call it an alternate kind of gamma coding!
My prof may have simplified it when he just called it Gamma coding then.
Good luck if you ever study LZ compression, and more advanced encoding schemes... RLE and delta coding is simple in comparison. some people build compressors from reverse engineered decompressors that are significantly more complex than poke
@@zxbryc Lempel-Ziv-Storer-Szymanski is not only hard to pronounce correctly, it's also a nightmare to implement it yourself
“We’ll look at the data format in a bit” yes but how MANY bits
It varies, depending on the size of the look.
don't make me bite you
Stop being so CRUMBy, you two!
I'm going to have an aneurysm
gringoes' must-see videos I’m NIBBLING at the Bit to see where this goes.
You explain these algorithms better than any college lecture I've seen so far. Could you make a video about Iwata's compression algorithm that was used to fit Kanto into Gold and Silver? I think it was found in the recent leaks.
That's would be so amazing to see. It's always talked about how he saved the post game by squeezing everything in, but I haven't seen anyone explain how.
the compression iwata/HAL contributed to gen 2 isn't as space efficient as gen 1's - it was used because it was much faster to decompress, and the gen 2 prototypes ran very slowly without it. it wasn't about fitting another region in, game freak had more than enough space to spare.
@@monkybros yeah I feel like this story has been shared around and exaggerated quite a bit.
@@LewisBavin yeah it's a combination of "how did they fit two regions in?" And the growing legend of iwata
@@monkybros Even if that's true, Iwata's skill shouldn't be understated. The man knew his stuff.
It's so rare to see so much effort put in to a video. You didn't have to go so far as to actually animate the decompression but you did. You didn't have to make that web app but you did.
He's incredibly talented. I can tell his channel will get bigger, it's very high quality and deserves every subscriber and more.
He didn't have to do the animations but If he didn't I probably would've been lost. I can understand some fairly complex topics but when I just read a description without visual aids I often find myself struggling with otherwise simple enough concepts (Generally speaking I'm primarily a hands on learner with visual learning a close second).
Yes, he did. If he didn't do that he wouldn't stand out much. He is not the only reverse engineer on UA-cam, so if he wants to impress anyone, he has to do those things.
h
@@grn1 Agreed. the visuals help show (literally, show) you what the algorithm is doing, or what the encoding achieves. It becomes very intuitive
So is this the main cause of the long delay when you encounter a Missingno? That is, the sprite decompression algorithm spending several seconds spewing junk bits all over the game ram. Are there any other causes?
That is correct! It's pretty much the only thing that takes so long.
Retro Game Mechanics Explained I noticed when performing the glitch in Pokémon Stadium that loading the sprite causes the game to save. Do you know what could be causing that, and do you think that could contribute to the loading time?
*sram
@@Nottinertv its *just* an overflow. and *anything* can be a negative value. and yes cgb has the same 8 bit limit... i mean, GS also runs on DMG
@@albertnortononymous9020 The Game Boy (and many other cartridge based systems) have extra RAM on the cartridge. Some or all of this extra RAM has a battery to keep it powered even if the cartridge is removed, allowing the game to save. However, you can still use that cartridge RAM for anything you want, since you know it will be present when running the game. That includes storing the Pokemon sprites during decompression.
I'd imagine the way Pokemon Stadium works to tell you the game is saving when using the GB Tower is it watches the parts of RAM that the game saves to (such as the Hall of Fame, that gets corrupted when encountering Missingno). Normally this is only written to when saving the game, so Stadium shows a saving indicator.
When Missingno is encountered, the decompression algorithm breaks out of the space it normally occupies, and overflows into the Hall of Fame data, corrupting it and rendering it unusable. Since the game is writing to the save "file", Stadium thinks the game is saving.
As a professional Architect of large scale systems and an avid lover of retro systems (even made my own Atari 2600 game).... DAMN. That's some serious software engineering going on there! Fantastic explanation, BTW!
The fact that a team of only FIVE programmers had a hand in making a graphics system this complex, yet effective, for a Game Boy game (while leaving in SO MANY glitches elsewhere in that game) is insane!
7x7 BP0 in C is my favourite piece of classical music
By Venusaur
David Velasco encountered by red
no its 69x420 BP0 in B is the most popular and you should favourite this too
@@skitten4671 and red is sus
@@thesizzles1337 .funny not found
"it's gonna get a little more complicated"
I already barely understand, I just really love these videos for some reason
I've worked on decompression algorithms for a couple of games on the Nintendo DS, both using RLE techniques and JPG. But the method used by Pokemon is another level of RLE, much more advanced than what I used back in the day! Also, outstanding video and explanation, thank you very much for sharing!
17:15 that moment when the previous 5 minutes actually made sense. I kept forgetting that despite reading individual bits we we're reading them to write PAIRS of '00' which is how the compression was actually able to be efficient.
“Pokémon Sprite Decompression Explained” Or; “How the MissingNo. got its stripes”
“Pokémon Stripe Decompression Explained” Or; “How the MissingNo. got its sprites”
This is a good one
@@ras662 i had a stroke
spell [REDACTED] backwards must be fun at parties.
@@ras662 He had a Video on that. Because Missigno. and every Glitchmon doesn't only have "issues" with the decompression.
I remember hearing from GameHut about RLE encoding, but the way he explained it left me wondering "Yeah, but how do you actually do that?" *This* video truly explains how the game does what it does, and that is why I love this channel. Keep up the great work, and I'll look forward to whatever's next!
Yeah, GameHut explains how he has programmed stuff, and Retro Game Mechanics Explained explains how the functions themselves work. They explain on two different levels. Because of the depth that RGME goes into, he needs more videos for just one topic.
Which of GameHut's videos was that? Now that I understand how RLE works, I kind of want to go back and see what he did with it.
@@supernunb3128 ua-cam.com/video/YV9x1KY_XWI/v-deo.html he doesn't go in depth on exactly how it works
run length encoding encoding
@@ThatGamerBlue Automated Teller Machine Machine, Ramen (Noodle Soup) Noodle Soup.
Love GameHut's explanations as well but he definitely keeps things more surface level (which is still great).
I just wanted to say that your editing is absolutely phenomenal. I'm always blown away by the quality of your videos.
Everyone always mentions Iwata’s compression in Gold/Silver. I would be interested to learn about what changed.
I've been wondering this for some time now. I've heard everything from Gamefreak ran out of space and Iwata compressed the data better, to Gamefreak had plenty of space but it didn't run fast enough. Unfortunately, it seems like the topic only picked up interest after Iwata's passing.
@@danimalforlife I find the former more likely. If it's already not running fast enough then compressing it isn't going to help at all, especially on as slow of a CPU as the Game Boy and Color have.
Conceivably you could address the problem with bigger ROM chips and just more bank switching but that relatively small cost for one cartridge adds up spectacularly. Pennies matter in quantities of millions.
@@sedrosken831 I ended up looking into this more. Still up in the air what exactly Game Freak's thought process was, but performance seems to be the determining factor as Gen 1's RLE compressed better. They sacrificed a little bit of space, but the final product does seem to run faster than in the Spaceworld 97 demo.
www.reddit.com/r/Games/comments/hwlylf/while_it_is_true_that_iwata_did_write_a_new/
I saw your channel at the end of a Technology Connections video and I'm not disappointed in the slightest with your content.
I come away from these videos with three emotions. One is being overwhelmed by the torrent of information I get during the vid. The second is awe at the work that goes into memory management and streamlining for games. The third is just an incredible respect to RGME for not only being able to understand what's going on under the hood, but also to reverse engineer and present said understanding to people who have never encountered such techniques.
Love this channel.
Very likely that Iwata had a hand in the compression code. Man was an ABSOLUTE UNIT, he managed to squish GSC enough to find room for Kanto. His apprentice managed to squish Smash Ultimate like crazy.
Unlikely, Iwata ported the battle system from rby over to stadium from scratch, which implies he wasn't familiar with the code.
He also was employed by HAL laboratories at the time and not game freak.
It's understandable people miss Iwata, but I cannot help but get the feeling at this point, people are just finding excuses to bring him up in conversations...
Iwata had a hand in the compression algorithm for Gen 2. I don't even know if he ever worked on the mainline games before or since.
@@shadowmanwkp that doesn't imply he wasn't familiar though? Gameboy and n64 games were totally different. They ran different architectures, and n64 games were mostly developed in C. It makes total sense for him to make it from scratch regardless of if he was familiar or not
Knee Snap or he could,ve just compile the gameboy’s Z80 code into the N64’s risc code instead to save time , the compilor will automatically put a flag on unsupported features of that target processor,the only thing iwata had to do was debug & alter the compilet code to make it work.
Am mean why would you ever want to do everything from scratch because of a different type processor if a compilor does exist???
I can't say anything about Iwata's involvement in this, but those techniques are common knowledge in this field, and were even more widely known and used back then. This is clever but at least something along those lines is to be expected of such a game. I can't say I would have managed to optimize it that far but at least I'd use a technique at 6:05 which would give a decent compression for the system. If bit-planes are split anyway it would come more or less naturally to delta-code them, and then XOR modes would probably come after a bit more thinking. This, working in unison, is still clever though.
You went above and beyond with the web app. You, sir are an excellent teacher.
20:30 You’ve now explained how mechanical hard drives work.
And CDs
5:00 one of black bits in upper right corner has 0 instead of 1. Idk how i spotted that :D
Dear LORD this means that he must've done this graphic manually! 😱
The dedication of this man.
Ha, I just wondering the same thing. How did I noticed that.
IN the 4th row, right? The white bit next to it has a 1 instead of a 0 too.
Intentional Easter egg?
I have so much respect for the people who coded this game. no matter how "broken" it seems, it's still incredibly impressive to me that they managed to do all this.
This guy's like the Bob Ross of video game mechanics. My cup of tea.
i was literally looking for something to help me fall asleep thank you so much its 9:42 AM
haha yes, I'm a fucking idiot and can't sleep right too
@@TehVulpez Same
Bruh, what in the world is your sleep schedule like? Usually if I'm still up by 9am I just give up on sleeping that night.
His voice and style of video is very easy to just close your eyes and drift off too
@@petemagnuson7357 honestly I was like that a while ago, but they might be a night shift
Lemme guess, the 5x5 was Mew?
the 5x5 is charmander i believe
edit: nvm
Underrated comment
amazing video, i am at loss of words at how good your explanations are and how much effort you put into every video (i mean, i absolutely did not expect a web app to be made just for this, but you did it any way) and the fact that this kind of video only attracts a niche audience shows how big your passion is on these topics. again, kudos
Holy crap that explanation is so good! That you included the tool to play with ourselves is even more amazing! Dude what you do is absolutely gold!
Now imagine he was a teacher and this was every lesson? I would have loved such a school/collage/...
(3:00) So they could have saved 4×151 bits if they ignored specifying width and height separately? That's 604 b, 75 B data saved.
Imagine optimizing the hell out of sprite while ignoring such an easy optimisation
I wonder if it was coded that was so they could use non square sprites if they wanted to, while still using this compression method.
@@Smileyrat it probably was, the problem is they optimised their compression algorithm using their knowledge of sprites, but did not optimize this bit using the same knowledge
Yeah, it seems plausible that they just didn't know if they were going to need non-square sprites when they decided on the data format. And since they obviously didn't end up needing the extra storage, why bother changing it.
@@simonthelen5910 This, they probably created this algorithm before having all pokemon sprites, so they had to accomplish for every posibility.
This was one of my absolute favorite videos! I always appreciated the level of detail you put in. It inspired my to write my own version of the decompression algorithm in python and scrape all the sprites from the game cartridge. I had such a fun learning experience working with exciting computer science principles with old nostalgic subject material. Thanks for making this information easily available!
If your ever looking for nightmare fuel, the delta encoded first bit plane of Pikachu in Pokemon Blue (US) has some strong Five Nights at Freddie's Vibes XD
"We'll look at the data format in a bit..."
Nice pun there
@@squidwardsquad um... you're welcome???
Thank you
It's so well explained that it's not complicated anymore...
18:00 One fun further optimization you can do is to just immediately write the terminating 00 of the data block to the output when you read it, and then just _not_ add that extra 1 to the length of the next rle block since you already just wrote the 00 from the data block.
What I find mind-blowing about all this, is how quick it happens despite the Game Boy CPU not really giving you the tools to do this effectively. Coding the unpacking routine seems more difficult than coming up with the compression scheme itself.
I'd love to see how you explain the compression methods they developed for secret of Evermore!
Being a programmer and a long-time Pokémon fan makes me more and more fascinated by the history behind the game.
I love your video. I almost felt every bit of data streamed into my computer amazed me.
We definitely need more videos like this, with such detailed explanation and such great illustration of various algorithms
wtf this editing is amazing.I can just feel the effort put into this
I don’t know why I love videos like this so much. It’s just so fascinating to me. ❤️
Great video! Something that would be neat to see, at least on the website, is an animation showing off how a finished image is compressed into a small number of bits.
This is absolutely awesome. You explain things very well and the graphics are as clear as they can possibly get.
I think I'm gonna have to watch a few times to fully grasp everything, it's pretty complex for someone who knows close to nothing about the subject, and yet I want to understand
"Just as a warning, things are about to get a bit more technical and complex..."
*Looks at length of video
*I don't need sleep, I need answers!*
The webapp made for this is one of the best that i've ever seen, and i really, truly, genuinely mean it. Far too many websites these days are bloated, overcomplicated crap (and the W3C is in part to blame for allowing that, mind you), yet this is a refreshing bit of simplicity. Thank you.
I've been waiting for the sequel for months without even realizing
It's so interesting to see how similar this decompressing method works compared to genetics. Not exactly the same, ofc, but the overall "grammar" is quite alike
Very comprehensive video. Although I would describe XOR as "if the bits are different, return 1"
This 30 minute video took me about an hour and a half to watch because of the immense amount of time I spent with the video paused and going back a minute or so to listen to something again before finally understanding it lol. Thanks for everything you do, dots!
Never thought I'd be learning so much. This channel is freaking awesome
0:10 Wait, MORE complex than the last two?!
Can you talk about how the Gameboy color added colors to Gameboy games?
Color data was added to the game cartridge, but was ignored by a normal game boy.
@@user2C47 oh. That's less exciting than was imagined by both me and Half-Baked, could still be a bit of an interesting vid.
@@ctb3335 Not exactly, Color data was not added to the original cartridges, they had no way of knowing in the og GameBoy days that a Color system would come out with backwards compatibility (because even Nintendo didn't know until they started getting request by devs to make a Color GameBoy).
GameBoy Colors actually had a lookup table in their firmware that was used to add color to all og GameBoy games created before the Color came out. Later/transition games had additional data for color just as some transitional games between the Color and Advanced had additional features that took advantage of the Advanced hardware (like wider screen and extra button support).
@@grn1 so a similar thing to the super game Boy?
@@grn1 While I know and own some of the GB/GBC transition titles, I've never heard of GBC/GBA transition titles, do you have any examples?
This is beautiful. I also like how the encoding mode 1 sort of works as an edge detector
0:36 That's an interesting point you make there, Mr. RGME! You should tell it to my teammate from senior design, who wrote some compression code but refused to write a decompressor because "we're not testing for that!"
(13:50) My initial idea was to use 00 as the terminator here as well, and use a form of counting that does not include 00 in the middle of it. So that is: 1, 10, 11, 100, 101, 110, 111, 1010, 1011, 1100, ... and a series of zeros at the end means all zeros except for the last two belongs to the number. Then 45 would be encoded as 111110(00), 8 bits instead of 10. But covering this non-standard number to an actual binary number might be too time consuming, and might not be worth it. Plus my system requires more bits for 1,2,4-6, is the same length for 3, 8-14, 27-30 and only saves 1 bit for numbers 7, 15-26, and starts saving 2 bits from 31 and up. So my method isn't that good now that I've looked at it.
Here's the full list from 1 to 221, showing what the order of the binary numbers will be if they aren't allowed to contain "00" except for the end. You can compare it to the way Pokémon does inside the parentheses, and you can see that my idea is more memory efficient from values 31 and beyond; but I have no idea about decompression speed. But as most sprites will use values below 31, my method isn't good for this.
1: 100 (00)
2: 1000 (01)
3: 1100 (1000)
4: 10000 (1001)
5: 10100 (1010)
6: 11000 (1011)
7: 11100 (110000)
8: 100000 (110001)
9: 101000 (110010)
10: 101100 (110011)
11: 110000 (110100)
12: 110100 (110101)
13: 111000 (110110)
14: 111100 (110111)
15: 1000000 (11100000)
16: 1010000 (11100001)
17: 1010100 (11100010)
18: 1011000 (11100011)
19: 1011100 (11100100)
20: 1100000 (11100101)
21: 1101000 (11100110)
22: 1101100 (11100111)
23: 1110000 (11101000)
24: 1110100 (11101001)
25: 1111000 (11101010)
26: 1111100 (11101011)
27: 10000000 (11101100)
28: 10100000 (11101101)
29: 10101000 (11101110)
30: 10101100 (11101111)
31: 10110000 (1111000000)
32: 10110100 (1111000001)
33: 10111000 (1111000010)
34: 10111100 (1111000011)
35: 11000000 (1111000100)
36: 11010000 (1111000101)
37: 11010100 (1111000110)
38: 11011000 (1111000111)
39: 11011100 (1111001000)
40: 11100000 (1111001001)
41: 11101000 (1111001010)
42: 11101100 (1111001011)
43: 11110000 (1111001100)
44: 11110100 (1111001101)
45: 11111000 (1111001110)
46: 11111100 (1111001111)
47: 100000000 (1111010000)
48: 101000000 (1111010001)
49: 101010000 (1111010010)
50: 101010100 (1111010011)
51: 101011000 (1111010100)
52: 101011100 (1111010101)
53: 101100000 (1111010110)
54: 101101000 (1111010111)
55: 101101100 (1111011000)
56: 101110000 (1111011001)
57: 101110100 (1111011010)
58: 101111000 (1111011011)
59: 101111100 (1111011100)
60: 110000000 (1111011101)
61: 110100000 (1111011110)
62: 110101000 (1111011111)
63: 110101100 (111110000000)
64: 110110000 (111110000001)
65: 110110100 (111110000010)
66: 110111000 (111110000011)
67: 110111100 (111110000100)
68: 111000000 (111110000101)
69: 111010000 (111110000110)
70: 111010100 (111110000111)
71: 111011000 (111110001000)
72: 111011100 (111110001001)
73: 111100000 (111110001010)
74: 111101000 (111110001011)
75: 111101100 (111110001100)
76: 111110000 (111110001101)
77: 111110100 (111110001110)
78: 111111000 (111110001111)
79: 111111100 (111110010000)
80: 1000000000 (111110010001)
81: 1010000000 (111110010010)
82: 1010100000 (111110010011)
83: 1010101000 (111110010100)
84: 1010101100 (111110010101)
85: 1010110000 (111110010110)
86: 1010110100 (111110010111)
87: 1010111000 (111110011000)
88: 1010111100 (111110011001)
89: 1011000000 (111110011010)
90: 1011010000 (111110011011)
91: 1011010100 (111110011100)
92: 1011011000 (111110011101)
93: 1011011100 (111110011110)
94: 1011100000 (111110011111)
95: 1011101000 (111110100000)
96: 1011101100 (111110100001)
97: 1011110000 (111110100010)
98: 1011110100 (111110100011)
99: 1011111000 (111110100100)
100: 1011111100 (111110100101)
101: 1100000000 (111110100110)
102: 1101000000 (111110100111)
103: 1101010000 (111110101000)
104: 1101010100 (111110101001)
105: 1101011000 (111110101010)
106: 1101011100 (111110101011)
107: 1101100000 (111110101100)
108: 1101101000 (111110101101)
109: 1101101100 (111110101110)
110: 1101110000 (111110101111)
111: 1101110100 (111110110000)
112: 1101111000 (111110110001)
113: 1101111100 (111110110010)
114: 1110000000 (111110110011)
115: 1110100000 (111110110100)
116: 1110101000 (111110110101)
117: 1110101100 (111110110110)
118: 1110110000 (111110110111)
119: 1110110100 (111110111000)
120: 1110111000 (111110111001)
121: 1110111100 (111110111010)
122: 1111000000 (111110111011)
123: 1111010000 (111110111100)
124: 1111010100 (111110111101)
125: 1111011000 (111110111110)
126: 1111011100 (111110111111)
127: 1111100000 (11111100000000)
128: 1111101000 (11111100000001)
129: 1111101100 (11111100000010)
130: 1111110000 (11111100000011)
131: 1111110100 (11111100000100)
132: 1111111000 (11111100000101)
133: 1111111100 (11111100000110)
134: 10000000000 (11111100000111)
135: 10100000000 (11111100001000)
136: 10101000000 (11111100001001)
137: 10101010000 (11111100001010)
138: 10101010100 (11111100001011)
139: 10101011000 (11111100001100)
140: 10101011100 (11111100001101)
141: 10101100000 (11111100001110)
142: 10101101000 (11111100001111)
143: 10101101100 (11111100010000)
144: 10101110000 (11111100010001)
145: 10101110100 (11111100010010)
146: 10101111000 (11111100010011)
147: 10101111100 (11111100010100)
148: 10110000000 (11111100010101)
149: 10110100000 (11111100010110)
150: 10110101000 (11111100010111)
151: 10110101100 (11111100011000)
152: 10110110000 (11111100011001)
153: 10110110100 (11111100011010)
154: 10110111000 (11111100011011)
155: 10110111100 (11111100011100)
156: 10111000000 (11111100011101)
157: 10111010000 (11111100011110)
158: 10111010100 (11111100011111)
159: 10111011000 (11111100100000)
160: 10111011100 (11111100100001)
161: 10111100000 (11111100100010)
162: 10111101000 (11111100100011)
163: 10111101100 (11111100100100)
164: 10111110000 (11111100100101)
165: 10111110100 (11111100100110)
166: 10111111000 (11111100100111)
167: 10111111100 (11111100101000)
168: 11000000000 (11111100101001)
169: 11010000000 (11111100101010)
170: 11010100000 (11111100101011)
171: 11010101000 (11111100101100)
172: 11010101100 (11111100101101)
173: 11010110000 (11111100101110)
174: 11010110100 (11111100101111)
175: 11010111000 (11111100110000)
176: 11010111100 (11111100110001)
177: 11011000000 (11111100110010)
178: 11011010000 (11111100110011)
179: 11011010100 (11111100110100)
180: 11011011000 (11111100110101)
181: 11011011100 (11111100110110)
182: 11011100000 (11111100110111)
183: 11011101000 (11111100111000)
184: 11011101100 (11111100111001)
185: 11011110000 (11111100111010)
186: 11011110100 (11111100111011)
187: 11011111000 (11111100111100)
188: 11011111100 (11111100111101)
189: 11100000000 (11111100111110)
190: 11101000000 (11111100111111)
191: 11101010000 (11111101000000)
192: 11101010100 (11111101000001)
193: 11101011000 (11111101000010)
194: 11101011100 (11111101000011)
195: 11101100000 (11111101000100)
196: 11101101000 (11111101000101)
197: 11101101100 (11111101000110)
198: 11101110000 (11111101000111)
199: 11101110100 (11111101001000)
200: 11101111000 (11111101001001)
201: 11101111100 (11111101001010)
202: 11110000000 (11111101001011)
203: 11110100000 (11111101001100)
204: 11110101000 (11111101001101)
205: 11110101100 (11111101001110)
206: 11110110000 (11111101001111)
207: 11110110100 (11111101010000)
208: 11110111000 (11111101010001)
209: 11110111100 (11111101010010)
210: 11111000000 (11111101010011)
211: 11111010000 (11111101010100)
212: 11111010100 (11111101010101)
213: 11111011000 (11111101010110)
214: 11111011100 (11111101010111)
215: 11111100000 (11111101011000)
216: 11111101000 (11111101011001)
217: 11111101100 (11111101011010)
218: 11111110000 (11111101011011)
219: 11111110100 (11111101011100)
220: 11111111000 (11111101011101)
221: 11111111100 (11111101011110)
1:46 [sees the Charmander sprite split into two images] "but there's four colors displayable on a Game Boy, the lightest is nothing so that makes seOOOOHHHHHHH the overlap between the two is the darkest color, gotcha gotcha gotcha. I feel smart now. OK keep talking."
Decompression rules:
1. Check the first binary digit. If 0, it's a RLE packet. If 1, it's a data packet.
2. In a data packet: Copy every string of two bytes to the decompressed string until a string of 00 is reached, then start a RLE packet. Go to step 3.
3. In a RLE packet: Follow steps 4-8.
4. Start reading binary digits until you get into a 0. Count the number of binary digits you read, including the 0.
5. Read that same number of digits after the 0.
6. Add the digits that you read before the 0 to the digits that you read after the 0, in binary.
For example, if 0110101000101110..., after the original 0 saying that it starts with an RLE packet, you read 2 1s and a 0 (110), saying that you need to read 3 digits after (101). Add the 110 (6) to the 101 (5) to get 1011 (11).
7. Then, add 1 to the sum. (For example, 1011, or 11, +1 is 1100, or 12.)
8. Copy that number of 00 pairs to the decompressed string, then start a data packet. Go back to step 2.
I'm not an especially smart person, but nonetheless your videos make me feel like I'm watching a university lecture. I'm just thankful I can pause, rewind, turn on or off subtitles, and watch it again before the exam!
Whomever came up with these bit packing tricks was a bloody genius. Adding the number to its own length, using a terminator for the data packets, binary delta coding... So many excellent ideas.
I was expecting this explanation. Thank you!! I'm actually surprised of all the work they put into this games.
Dude, You really are exceptional .. Not only knowing and understanding the content, but how to display it, all the animations and scripts to make these videos.. You should be proud of yourself.. Cheers from Regina Canada.
Quite interesting! I like how calm & peaceful your voice is, & the lack of music makes this more enjoyable!
I know its old, but this is the kind of stuff i was fascinated by when the only things i had to program were a ti-85 and Palm Pilot in middle school. Definitely earned a sub from me!
Thanks for the video.
This makes compression (well, compression adapted to this kind of images) easy to grasp and understand.
Having an insanely complicated algorithm to compress data in the most efficient way and then using a look up table to flip a number is the epitome of rby
Ty for this video!
I've used what I've learned here for a bitmap font storage function, getting decent compression and increasing the display speed by a lot.
This helped me to realize why some glitch pokemon load longer when you battle them, they need more time to load and i think you know why
Honestly you are my new favorite channel...
This is exactly the interesting shit they dont teach you in uni
"Ugly Javascript..." lolz
I think XOR is my favorite math operation.
It's made it into my list of top 10 binary operators for sure ;)
What's the difference between XOR and standard OR?
@@clockworkpotato98921 OR 1 is 1.
1 XOR 1 is 0.
32'26 In the subtitles, "thjis" should be "this"
Regarding the web app: you don't actually need to have the upload button; you can use the change event on the input (e.g. `$("#binFile").change(uploadBinary)`). That would probably also avoid confusion with it being an upload to a server vs local processing.
i love counting in binary, this video was incredible from start to finish
This is a great video. The encoding method is pretty intuitive - I mean, knitting patterns use RLE - but I never knew the actual mechanics, or why it caused glitch pokemon to look like that.
I was wondering if you could talk about GSC's sprite compression? Gen II sprites have a distinctive amount of dithering, which doesn't compress very well with these methods (tested with your web tool!) so I imagine they used another method to encode that efficiently...?
33:20 I came back to this video to rewatch today and god damn, I just have to remind you how beautifully that is written.
Excellent video as usual! Even with these Pokémon graphics videos getting pretty beefy, they remain super interesting.
I've been thinking lately about how Satoru Iwata supposedly helped improve on the image compression in Gold and Silver. I haven't really seen anyone get into it more substantially, though, so I'm curious: are there any major differences in how Gold and Silver compress graphics, or were Iwata's contributions most likely just in the realm of more consistently making the most of the existing algorithms?
Love your videos! Both for the technical details, and the ease at which you describe.
I noticed something with your RLE explanation around 14:00. The encoding of N is actually rather inefficient for large N. The example you give, 63282 represented with 30 bits is inefficient compared to the 16 bits to represent the original number.
Perhaps they could have used 4 bits to specify the length of N as 1-16 in every case. This gives a Best case of 5 bits or worst case of 20 bits.
However, their way is likely more efficient if they are expecting less than 32 packets in a row to be a common case. This is because 31 in RLE is 1110 1111 which is just as efficient as 0011 1111.
Given the size of the sprites and sprite data, I would bet theirs is more efficient since the chance for N
Of course 16 bits to write the number in plain binary is more efficient, but you have to know the size of the number beforehand! If you don't, you have to encode that information as well. Simply encoding the length in unary and appending the original number would take 32 bits, but the method shown in the video does it in 30.
The issue with using a constant number of bits is that it becomes very inefficient for groups of just one or two 00 pairs (which are fairly common). Using 4 bits to write 2 bits is the opposite of compression!
I love these videos and this channel.. It would be very nice if you cover some 3d games also, like explaining how StarFox uses FX chip or how some 3d games works using the co-processors to help handle the 3d rendered (or to render all the 3d at all and pass to the console)..
can someone make or show a website with missingno's file that works with the website, as well as showing what the settings for him are?
YESS!!! Thank you for this video! I waited for it!
Heck yeah
A new video
I can't wait to learn more about how Pokémon was programed
Seriously
For some reason this stuff always interested me
Especially the glitches and how they even work
So
Thank you
Thank you so much for making these videos
...half a "bite" is called a nibble? omfg I love that
Man this is hard... I haved to rewatch the video a lot of times to fully comprehend
5:45 Ah yes, RLE: the only compression algorithm I actually understand well enough to implement...although I didn't go quite as far as GameFreak and just used a byte for each value. No "data packets" either, just basic RLE.
It is a good algorithm to understand, though; fairly quick and very simple, yet very effective for a lot of different data used in sprite-based games.
Ah, yes. My favourite classical music piece. 5x5 BP0 in C
5x5 BP0 in C, by Mew
my favorite way to explain the XOR is 'three way light switch'.
Me: "Is it using RLE? I bet it's RLE. Is it RLE?"
5:42 - "A method known as RLE"
Me: "Yesssssss"
The use of delta encoding was something I didn't expect. But it makes perfect sense. They really tried everything they could to minimize the sprite data size.
Thanks for making this video! It was very interesting.
It's amazing to see what great lengths they ran in order to save a few KB and stuff more contents into the game.
man, retro game designers were clever, xor'ing is such a simple concept to make it a stream of 0's (only recording when a bit changes) but id have never thought of that
10 minutes in and this stopped being about pokemon a while ago. Its now a thoroughly interesting explanation of game coding
I got hyped up for this video and missed it by a day, very nice
We take those for granted today, but man this sure gave people headaches back then
Those videos look like so much work. Very impressive!
28:33 This feels like the big reveal at the climax of a story. That the big secret you were looking for all along was right with you the entire time. The payoff of learning that Sheik is delta encoded Zelda.
25:24 The in-progress Venusaur in buffer B looks like it's screaming in pain, its eyes bloodshot.
Your video editing skills are insane
these videos are just so relaxing and interesting :) I love to just listen and learn about these complex coding techniques :)
Got big flashbacks to my discrete computational analysis class, though i was a hell of a lot more focused on this!
Great video! I love these sorts of deep dives into algorithms. It's cool how the limitations of the time motivated such a complex and clever algorithm. I wonder how often that happens today, given that we have more computing power, so there're fewer incentives.
QQ:
- How much space did this method actually save (on average) compared to just storing the sprites naively?
- Did you glean all of this info from reverse-engineering the game, or were you able to track someone down to ask questions of?