Street Fighter II paper trails – allocating sprite space by hand(fabiensanglard.net)
fabiensanglard.net
Street Fighter II paper trails – allocating sprite space by hand
https://fabiensanglard.net/sf2_sheets/index.html
80 comments
I absolutely love learning about the clever tricks and their long-tail effects that came out of dealing with incredibly resource constrained computing environments and/or where some quirk of hardware ended up inspiring a lot of fabulous creative misuse.
This is a fantastic article!
This is a fantastic article!
I was one of the developers on this game in the 90s:
https://www.youtube.com/watch?v=lubyi79e6SY
It was meant to be 100% 2D, and the programming and art went down that path for a few months before it was realized that there just wasn't enough RAM on PCs of the time to store all the possible sprites for the characters in every rotation. The numbers get out of hand very quickly when you have four main characters, each of which can walk in 8 or 16 directions, can also run, walk up stairs, climb ladders, crawl, fire one of 20 different guns etc. The isometric backgrounds are all sheets of 2D tiles, laid out just like in Street Fighter and every other sprite based game.
So, several months into development it was decided to change all the characters to 3D to save RAM. I switched the entire game over in two weeks, including creating all the tooling to convert from 3D Studio to.. whatever the fuck, because there were no rules in those days. When that game was started there were almost no 3D accelerators, and I don't remember if you needed specific SDK for them. I seem to remember our game couldn't use them, perhaps because of the way the 3D and 2D were composited in the frame, which was very unusual - most games were either 2D or 3D, not a combination.
Are there any easter eggs hidden in the sprites for SFII? There were various ones in Abomination, mainly written in the graffiti around the cities.
And then there are ones like this (TFT) that we can't talk about: https://www.reddit.com/r/gaming/comments/3ylmm4/a_staggering...
https://www.youtube.com/watch?v=lubyi79e6SY
It was meant to be 100% 2D, and the programming and art went down that path for a few months before it was realized that there just wasn't enough RAM on PCs of the time to store all the possible sprites for the characters in every rotation. The numbers get out of hand very quickly when you have four main characters, each of which can walk in 8 or 16 directions, can also run, walk up stairs, climb ladders, crawl, fire one of 20 different guns etc. The isometric backgrounds are all sheets of 2D tiles, laid out just like in Street Fighter and every other sprite based game.
So, several months into development it was decided to change all the characters to 3D to save RAM. I switched the entire game over in two weeks, including creating all the tooling to convert from 3D Studio to.. whatever the fuck, because there were no rules in those days. When that game was started there were almost no 3D accelerators, and I don't remember if you needed specific SDK for them. I seem to remember our game couldn't use them, perhaps because of the way the 3D and 2D were composited in the frame, which was very unusual - most games were either 2D or 3D, not a combination.
Are there any easter eggs hidden in the sprites for SFII? There were various ones in Abomination, mainly written in the graffiti around the cities.
And then there are ones like this (TFT) that we can't talk about: https://www.reddit.com/r/gaming/comments/3ylmm4/a_staggering...
In case you missed the last paragraph of the blog post, it says: "I have made several attempts to talk with developers who worked on CPS-1/CPS-2 systems. All of them have failed so far."
Feel free to contact him for the legacy of your great work and the greater good of humanity :)
Glide for 3Dfx cards maybe? https://en.wikipedia.org/wiki/Glide_(API)
When writing a DMG emulator I thought about how these tiny sprites are often similar. A sprite will be a series of bytes with an address to the beginning.
It got me thinking about a kind of compression algorithm could find byte overlaps and re-pack the sprites, and then adjust the addresses.
This got me thinking: are there any compression algorithms that do not require decompression? You pack them once and then just point at slices.
Then this got me thinking: is that just what unzipping is doing, just eagerly?
It got me thinking about a kind of compression algorithm could find byte overlaps and re-pack the sprites, and then adjust the addresses.
This got me thinking: are there any compression algorithms that do not require decompression? You pack them once and then just point at slices.
Then this got me thinking: is that just what unzipping is doing, just eagerly?
That is how basic Lempel-Ziv compression works, which is one of the two fundamental techniques used in data compression. You keep a history of what you've already decompressed, and if you find something you already have, you instead encode a pointer to it. Variants of this (LZW, LZ77, LZSS, and a bajillion custom variants, because game developers like to reinvent their own compression) have been used in many, many games.
The other is entropy coding, which means re-writing bytes and pointer codes into variable length values that are optimized by frequency: fewer bits for common codes, more bits for uncommon ones. The most basic approach for this is Huffman coding, which is kind of like variable length binary phone numbers.
Together, these two techniques are how DEFLATE compression works, which is the algorithm used by zip, gzip, and zlib. zlib is then used in many, many formats, like PNG and PDF.
Trivial "look for dupes and subsets and just change pointers" compression is already standard when building C code. If your program has two strings, "foobar" and "bar", the linker will just store "foobar" in the strings section and point 3 bytes into it for "bar", assuming the right compilation/linking options to make it work.
The other is entropy coding, which means re-writing bytes and pointer codes into variable length values that are optimized by frequency: fewer bits for common codes, more bits for uncommon ones. The most basic approach for this is Huffman coding, which is kind of like variable length binary phone numbers.
Together, these two techniques are how DEFLATE compression works, which is the algorithm used by zip, gzip, and zlib. zlib is then used in many, many formats, like PNG and PDF.
Trivial "look for dupes and subsets and just change pointers" compression is already standard when building C code. If your program has two strings, "foobar" and "bar", the linker will just store "foobar" in the strings section and point 3 bytes into it for "bar", assuming the right compilation/linking options to make it work.
There was a similar trick used for compressing game backgrounds in Commodore 64 games.
The compressor would create a special font (C64 "charsets" are 8x8 pixels), and slice the picture into 8x8 tiles where each block corresponds to an ASCII character. Although C64's hires resolution was 320x200 (160x200 in multicolor mode), because of repeating blocks it would usually end up using less than 256 characters. The actual background would then be drawn using those characters with the special font. There is no eager decompression involved.
The compressor would create a special font (C64 "charsets" are 8x8 pixels), and slice the picture into 8x8 tiles where each block corresponds to an ASCII character. Although C64's hires resolution was 320x200 (160x200 in multicolor mode), because of repeating blocks it would usually end up using less than 256 characters. The actual background would then be drawn using those characters with the special font. There is no eager decompression involved.
Many years ago, I implemented an N64 ROM compressor that could work out a rough family tree for variations of a game. It worked something like this:
Brute force compare all the ROMs to each other and find "ancestor" with the least amount of changes as compared to any other.
Pick that as an ancestor, re-brute force check every remaining ROM against that one for changes.
It was silly and wasteful computationally but you could store 40 variations of a cart in 50MB instead of 1GB.
Brute force compare all the ROMs to each other and find "ancestor" with the least amount of changes as compared to any other.
Pick that as an ancestor, re-brute force check every remaining ROM against that one for changes.
It was silly and wasteful computationally but you could store 40 variations of a cart in 50MB instead of 1GB.
Do you remember what you determined the "ancestor" to be?
For the n+1 cart, it was always the smallest diff between n and any remaining carts.
Picking the first n, was more difficult. A strong hint was if the ROM name contained a variant of the word Japan. Otherwise, imagine you had 4 images, you could diff them 16 ways, but half of those ways are mirror images of each other ie. a diff of ROM 2->4 is the inverse of of a diff of ROM 4->2.
So ideally, the first ancestor would be the image with the most amount of the smallest children.
Picking the first n, was more difficult. A strong hint was if the ROM name contained a variant of the word Japan. Otherwise, imagine you had 4 images, you could diff them 16 ways, but half of those ways are mirror images of each other ie. a diff of ROM 2->4 is the inverse of of a diff of ROM 4->2.
So ideally, the first ancestor would be the image with the most amount of the smallest children.
Iwata famously implemented RLE in Pokemon Gold/Silver. That gains an easy 50% from all the whitespace.
Huffman coding would be the simplest algorithm to compress the repeated patterns in sprites, but I think even loading up the dictionary to decompress would run into memory limitations on these old systems. If nothing else it would cause hitching.
Huffman coding would be the simplest algorithm to compress the repeated patterns in sprites, but I think even loading up the dictionary to decompress would run into memory limitations on these old systems. If nothing else it would cause hitching.
Apparently DNA is compressed in this way, it makes studying it very difficult.
https://www.news-medical.net/health/What-is-an-Overlapping-G...
https://www.news-medical.net/health/What-is-an-Overlapping-G...
Yes. Check out succinct data structures. They are closely related to compression algorithms. The above mentioned compression algorithms (incl. Entropy and all LZ variants) need a decompression step. They might try to improve the decompression speed by chunking and sacrifice storage space, but decompression is needed. This is unrelated to how they remove redundant information from the data (e.g. using pointers). Succinct data structures try to avoid decompression at all. Again, at the cost of storage space but some operations can be done on the succinct data directly as it is on disk.
Vector quantization, for example. Sound scary, but compression is basically k-means and decompression a table lookup.
I remember another article where the main developer set aside a big chunk of memory right when they started coding. When they had issues fitting everything in memory shortly before the deadline, he deleted this chunk and had no issue to deliver the project.
I think this is something we should do more today. Defining a memory budget, and staying inside.
I think this is something we should do more today. Defining a memory budget, and staying inside.
There was a story about a year ago of someone mentioning something similar, where they recommend always having a 10 GB blank file on their server.
This save them multiple times when issues arose later relating to space availability, even for updating things, etc.
This save them multiple times when issues arose later relating to space availability, even for updating things, etc.
I remember it as being for "disk full" conditions when everything came to a crawl, because log files could no longer be written either.
> I think this is something we should do more today. Defining a memory budget, and staying inside.
It's fun to think about, but I am not sure if it's the right tradeoff for most projects?
It's fun to think about, but I am not sure if it's the right tradeoff for most projects?
Maybe this is the article you're thinking of (pretty sure it was first published by Gamasutra): https://www.gamedeveloper.com/programming/dirty-coding-trick... (see The Programming Antihero)
Gamasutra IS Game Developer now, they rebranded recently.
https://www.gamasutra.com/view/news/387227/Gamasutra_is_beco...
https://www.gamasutra.com/view/news/387227/Gamasutra_is_beco...
>The enemy of art is the absence of limitations.
—Attributed to Orson Welles (<https://quoteinvestigator.com/2014/05/24/art-limit/>)
—Attributed to Orson Welles (<https://quoteinvestigator.com/2014/05/24/art-limit/>)
I love that we can dig into rom images from 30 years ago and recreate sprite sheets that were originally hand drawn for something that was an important part of our culture. What more I love that Fabien actually does it and shows us how it's done.
The fact that later titles are encrypted, so he doesn’t have access to them made me a bit sad. The DRM mentality strikes again.
Capcom had a hell of a time fighting knock-off SF2 boards. I can understand why they went the DRM route, as sad as it is for preservation. That said, haven't all those roms been decrypted?
The graphics on CPS-2 were not encrypted, just shuffled. The code encryption has long been defeated as well.
Loved this article. SFII was so huge when I was about 13-20... that game had such a long tail. I remember seeing it for the first time and being blown away, it was rather amazing when all you'd seen up to that point was NES and PC games on a 286 or so.
Funny thing is I'm pretty darn sure I have no desire to work in commercial game development these days, but would have loved to back then. The creativity around limitations was amazing back then and it seemed like so much care was put into making games fun. These days it seems like addiction mechanisms, getting people to spend more money, obsessiveness with graphics over gameplay, etc.. are ruining everything.
Funny thing is I'm pretty darn sure I have no desire to work in commercial game development these days, but would have loved to back then. The creativity around limitations was amazing back then and it seemed like so much care was put into making games fun. These days it seems like addiction mechanisms, getting people to spend more money, obsessiveness with graphics over gameplay, etc.. are ruining everything.
>These days it seems like addiction mechanisms, getting people to spend more money, obsessiveness with graphics over gameplay, etc.. are ruining everything.
Couldn't be further from the truth, especially when it comes to Street Fighter... People complain about microtransactions today and don't even think to consider that the original microtransaction was the arcade machine. Games back then were specifically designed to extract a certain amount of money per hour from players and their difficulties were adjusted to maintain that rate.
It's never been better to be a game developer then today. The number of platforms available to you, distribution options, variety of studios/publishers are much greater today than ever before.
Couldn't be further from the truth, especially when it comes to Street Fighter... People complain about microtransactions today and don't even think to consider that the original microtransaction was the arcade machine. Games back then were specifically designed to extract a certain amount of money per hour from players and their difficulties were adjusted to maintain that rate.
It's never been better to be a game developer then today. The number of platforms available to you, distribution options, variety of studios/publishers are much greater today than ever before.
> People complain about microtransactions today and don't even think to consider that the original microtransaction was the arcade machine
I couldn't disagree more. The arcade machine did not feel like a microtransaction at the time. We were glad to spend the coins on them. Now, even with presumably much more funds than when we were kids, the microtransactions feels very exploitative!
If people "dont even think to consider" then that means there isn't much of a similarity
I couldn't disagree more. The arcade machine did not feel like a microtransaction at the time. We were glad to spend the coins on them. Now, even with presumably much more funds than when we were kids, the microtransactions feels very exploitative!
If people "dont even think to consider" then that means there isn't much of a similarity
would be truly amazing if Fabien can pull it off.
there is so much secrecy surrounding video game development in japan. especially the 8 and 16-bit era. i was very interested in how they did pixel art back then. they supposedly drew them using special keyboards and CRT monitors.
there is one page on the whole internet that briefly mentioned the process.
there is so much secrecy surrounding video game development in japan. especially the 8 and 16-bit era. i was very interested in how they did pixel art back then. they supposedly drew them using special keyboards and CRT monitors.
there is one page on the whole internet that briefly mentioned the process.
From what I gathered on Akiman Twitter, they drew on 16x16 rectangular grid paper and then manually translated that to pixels with a keyboard using arrows keys and 0-F keys.
That's it.
That's it.
You can see Nintendo's process for SMB here:
https://www.youtube.com/watch?v=DLoRd6_a1CI
https://www.youtube.com/watch?v=DLoRd6_a1CI
There is also some footage about digitization/level design in this SMB3 documentary (they might be using the same sources though): https://youtu.be/MxT6IwUtLSU?t=671
The mouse with the crosshair is a nice idea!
The mouse with the crosshair is a nice idea!
They still make digitizing tablets, don't they?
Wacom has a mouse with a cursor on it.
Another excellent article by Fabien :)
One thing that surprises me is that in such a ROM-constrained context, the artists weren't asked to save some more. There's some tiles that are empty except for a handful of corner or side pixels; I could imagine going to the artists and asking them to tweak the pose a tiny bit to save a tile.
Or maybe what we're seeing in these sheets is the result of doing that just enough to fit their game into the available ROM, at which point they didn't need to free any more tiles?
One thing that surprises me is that in such a ROM-constrained context, the artists weren't asked to save some more. There's some tiles that are empty except for a handful of corner or side pixels; I could imagine going to the artists and asking them to tweak the pose a tiny bit to save a tile.
Or maybe what we're seeing in these sheets is the result of doing that just enough to fit their game into the available ROM, at which point they didn't need to free any more tiles?
My guess is that they preferred bigger optimizations first, such as the given examples of reusing Ryu's body tiles for Ken and mirroring Sagat's legs. If those hit the target, there's no need to go around trying to pick up a tile here and there around the edges.
Also, any given saved tile might not have packed well in the overall sprite sheet, given that they were organizing the ROM by hand.
Also, any given saved tile might not have packed well in the overall sprite sheet, given that they were organizing the ROM by hand.
[deleted]
>> Notice how Ruy's top hair for 0x69/0x6A was placed at 0x6F/0x9F in order to not disturb the layout. Why the hair of the top left pose is offsetted is unknown. Could it be that GFX ROM address 0x0000 could not be used? Analyzing other games also showed that tile 0x0000 was never used.
My guess is that it was easier to encode and use a blank tile than to specify those strange shapes where sprites are non-rectangular. Just tell the hardware the size in tiles and then offer a set of tiles that includes blanks. This could be confirmed or refuted once they find the area in ROM that specifies how to put the tiles together to form a sprite.
It sounds like a complete sprite had to be entirely on one page, so there must be a list of tile numbers to compose a sprite and they would be 1 byte each. since they know the tile layout for some of the poses, they should be able to write down that sequence of bytes and look for it in the ROM, then check if there are zero tiles in there. Or just check the MAME source code since that level of detail was probably all figured out a long time ago for that project :-)
My guess is that it was easier to encode and use a blank tile than to specify those strange shapes where sprites are non-rectangular. Just tell the hardware the size in tiles and then offer a set of tiles that includes blanks. This could be confirmed or refuted once they find the area in ROM that specifies how to put the tiles together to form a sprite.
It sounds like a complete sprite had to be entirely on one page, so there must be a list of tile numbers to compose a sprite and they would be 1 byte each. since they know the tile layout for some of the poses, they should be able to write down that sequence of bytes and look for it in the ROM, then check if there are zero tiles in there. Or just check the MAME source code since that level of detail was probably all figured out a long time ago for that project :-)
> It sounds like a complete sprite had to be entirely on one page
That doesn't seem to be the case. There are pieces of Chun-Li and Blanka on the Dhalsim sheet.
That doesn't seem to be the case. There are pieces of Chun-Li and Blanka on the Dhalsim sheet.
I'm currently writing a tool to package up sprite tiles for the Neo Geo[1], which handles graphics in a very similar manner as the CPS1. I can't imagine composing these tiles manually, what a monumental task.
The Neo Geo's hardware offers a few graphical features that work by assuming the tiles are ordered in a certain way. It's an interesting challenge to meet those requirements.
[1] https://github.com/city41/sromcrom
The Neo Geo's hardware offers a few graphical features that work by assuming the tiles are ordered in a certain way. It's an interesting challenge to meet those requirements.
[1] https://github.com/city41/sromcrom
After I am done with the CPS-1, I am considering documenting the Neo-Geo. I have no found really good documentation so far but maybe you can recommend me some?
Email me at [email protected]
Email me at [email protected]
Fascinating read, one question though:
If they can split an image into multiple tiles at different addresses (as they did in some examples shown in the article), shouldn't they only need to care about the total tile number? Why did they bother to try to fit these postures (more or less) as whole on sheet, or making these sheets at all?
If they can split an image into multiple tiles at different addresses (as they did in some examples shown in the article), shouldn't they only need to care about the total tile number? Why did they bother to try to fit these postures (more or less) as whole on sheet, or making these sheets at all?
Because they were manually drawing and designing the sheet layouts. If this was an automated process, as shown for the CPS-2 titles, then they could (and did) automate it.
Steet Fighter II, the game I mostly played in my childhood. Always been a big fan of this amazing game.
It has had such a cultural impact to those of us who grew up with it. I was a teenager when SFII came out and have very fond memories of playing it at arcades and convenience stores with friends. I started learning how to code back then and a lot of my early code was attempts at making a Street Fighter game. (They were usually just attempts at recreating the art and animation in QBasic.)
Yeah SF2, hyper and turbo were a huge part of my youth too. What an era! I miss playing it
I could be mistaken, if it was SF II or some other similar game, but for PC (back in the DOS game, the sprites for these were not stored rectangular (with transparency) but rather a run-length of here is a line of pixels that starts from here to here. Hence your code can just "movsb" instead of checking (expensive) for transparency).
... Could've been another game, but it was fun trying to decode the images :)
(I think it also makes pixel to pixel collision easier to tackle, but don't remember the details - this might've been Star Control II thing, another game we used (as kids) to decode images/mods)
... Could've been another game, but it was fun trying to decode the images :)
(I think it also makes pixel to pixel collision easier to tackle, but don't remember the details - this might've been Star Control II thing, another game we used (as kids) to decode images/mods)
This reminds me: the Allegro library has a way to compile bitmaps into series of mov instructions to make blitting faster. This was somehow the fastest method on early x86 processors. Loops were expensive back then.
See https://liballeg.org/stabledocs/en/alleg016.html
See https://liballeg.org/stabledocs/en/alleg016.html
Perhaps you were thinking of SFIBM/SF2IBM, aka SFLIU [1], a homebrew version of SF2 for PCs written by a Korean dev. There were specs of the file formats used out on the internet at the time and I remember the image files were stored as run-length encoding.
[1] http://cwcyrix.nsupdate.info/archives/SFLIU/sfliu.html
[1] http://cwcyrix.nsupdate.info/archives/SFLIU/sfliu.html
You might be right (for my case). It could've been that is what I've played (!!!) it was around 1991-1996 (?) and it's when I've started digging into the format (along with other games, like SC2). Might've been even later, but it was an older game. Never knew it was a homebrew version :)
Reminds me of doing unwrapping of custom models for Quake. After a bit of practice I realized it came out much better if I made the face, head, and front parts larger so they contained more details. Then other bits could be squeezed in or mirrored to maximize those 256x256 pixel skins.
Reminded me of this link - https://www.criticalhit.net/gaming/street-fighter-iii-will-a...
What a game they made out of those 6MiB. Constraints foster creativity rather than limiting it.
The sheer amount of sprites caused it to be the biggest ROM at the time on the Super NES. 16 megabits! That also caused the game to be priced at something ridiculous like $75 US
I wonder if they used this same method on the SNES or not.
I wonder if they used this same method on the SNES or not.
I just wanted to note this website is very well-presented. It mimics the simplicity of a sheet produced by an old typewriter.
Eye pleasing and no distraction from the text, as a web page should be.
Eye pleasing and no distraction from the text, as a web page should be.
No website should use text-align justify and I will die on this hill.
You have a point there. It is less noticeable on mobile, but desktop has no call for it.
Though were we in a universe where every choice is a cruel dichotomy, I'd pick understated text-align justify over JavaScript bombardments.
Though were we in a universe where every choice is a cruel dichotomy, I'd pick understated text-align justify over JavaScript bombardments.
It is really nice. The only thing I’d change is the text justification.
I recall seeing a video of their software setup, where they would use the console controllers instead of a mouse to draw the sprites.
[deleted]
Topically, some of these would make for extrmely geeky wrapping paper.
Street Fighter is one of the the only game that I ever bought... Kali was another one (game related app).
This is really great stuff and I think important as "developer archaeology". The 80s and 90s don't seem that long ago (to those of us who were around), but it's easy to forget people back then didn't have the sophisticated tools we have today. That said, people did have tools, so it's awesome to be able to get a glimpse into the workflow of folks back then.