Commander Keen's adaptive tile refresh
fabiensanglard.net
fabiensanglard.net
[1] No relation to the more famous Carmack, but IMO the unsung master of the 16-color palette.
“Our memory is slow, so let’s redraw only things that changed” is kind of a given nowadays.
Still the optimization in 4-6 is fun. Did the whole thing in 1-3 just because of an assumption that the buffer would not wrap around, and then it did and all that work became obsolete.
[1]: https://learn.microsoft.com/en-us/windows/win32/gdi/clipping
I think it is more interesting that the pipeline was invalidaterect/region => getevent => event was a draw event => draw region (or part of it). The getevent would only generate draw events if nothing more important was going (keyboard/mouse input, timer, message from other app/desktop accessory). It would also prioritize top windows first so you would only get a draw event for a window at the bottom once the windows above had no more dirty areas.
If you really knew what you were doing, you could short circuit this a bit and draw in your windows outside of draw event handling.
On the other hand, of course, CPUs do have a complex system of several levels of caches, but that's not primarily because of (lack of) memory bandwidth but memory latency.
For Win32 and X11 at least the damaged region (or "invalid region") approach is still there and AFAIK recently (as in a few months ago) the modesetting driver for Xorg added the ability to use the damage regions when "TearFree" is enabled (this does server-side composition to avoid tearing - it is disabled by default) to only update the of the screen that changed instead of the entire screen.
Also i remember reading some time ago about some monitors being able to use partial frame data (the monitor "shadows" the frame) so that they can support faster updates.
I think the concept can also help with slow display tech like e-ink devices.
Some also implement partial redraw into the tiles to handle things like cursors blinking to avoid having to redraw the entire tile.
However it is still an issue if one wants to achive maximum performance, and it is done by only sending the vertices and textures to the GPU that are actually going to be visible.
Yes, it's you and your vaulted position of standing on the shoulders of those to whom these developments actually were ‘revolutional’. I equate the level of accomplishments from Id to be at the level of cavemen throwing rocks at the spaceship to cavemen buying insurance on TV levels of achievement.
Carmack and id are responsible for at least 4 or 5, "I had no idea a computer could do that" moments for me.
Tangentially related: Android still doesn't get this. Turn on the screen refresh flashes in the developer menu and then look a your static screen and be amazed who often android draws even though nothing changed.
Energy efficiency is a separate matter.
I'm willing to bet :)
The difference in time spent by GPU between drawing 1000 and 50 sprites is almost 0.
Updating buffers is of course a totally separate thing, and on that side I don't think anyone updates everything every tick, usually there's some sort of scene graph that knows about dirty transforms and their children, so only those get updated..
And the animation framework always just "scrolled" the view (or screen) when it could.
Check out the evolution from the first game: https://en.wikipedia.org/wiki/Commander_Keen_in_Invasion_of_...
To the last game: https://en.wikipedia.org/wiki/Commander_Keen_in_Goodbye,_Gal...
I was playing them at the time, as a young child, and I'd forgotten the pace at which things were apparently happening.
So from software Ray Casting to full 3D acceleration in that time period.
7 years ago from now we had Uncharted 4, it is behind were we are now but not as much as you would think.
It's not that hard when one guy is writing the rendering code, another doing game logic, one doing artwork, one level design, and one doing sound. Nobody is really stepping on anyone's toes.
He talked how they were always working on 2 games and would do a press release with a shipping date before they more or less even started lol
Romero just released a new book 10 days ago... Doom Guy: Life in First Person https://amzn.to/43M0rSg
The crazy part was also working 2 full time jobs essentially, 8 hours at softdisk then they would use those PCs at night for 8 hours to crank out their private games, also borrowing them on the weekends to get more work done.
Talking about these little tile and scrolling tricks. Golden Axe on the Master System had to get around the sprite size limit by having the entirety of the graphics live on the background layer. This meant everything sat and moved in an 8x8 pixel grid. A neat little hack even if it made the whole thing a little chunky.
I think I'd pick Prince Of Persia, not to diminish Commander Keen a single bit but I always found PoP visuals and game dynamics unmatched for its time. I'm also getting biased for two reasons: I played PoP when I believe I was 7 years old and made a magic impression on me when I first played it and is also is my favourite platformer of all times. But of course PoP lacks of the scrolling at all which is Commander Keen's black magic.
I understand that Jordan Mechner put in a ton of hours rotoscoping the movements. (Example: https://www.youtube.com/watch?v=fCy8WqAgPbY)
On a tangent, Mechner is an incredibly talented (and in my opinion, severely underrated) game designer. "The Last Express" is a masterpiece, and wondrous in a different way.
Yes it is very impressive even today. Those tons of hours on rotoscoping paid off immensely. I haven't played "The Last Express" though I've seen some screenshots and looks a very nice game. Somehow the artwork resembles the style of Alphonse Mucha: https://en.wikipedia.org/wiki/Alphonse_Mucha
I ended up ripping out all of that code because when I tried to profile the cost of drawing the whole screen with my RIVA TnT card I literally couldn't measure the tiny amount of time it took.
I am glad I missed the EGA period of PC development, I never would have gotten anything done.
Continuously learning from the scarce resources I had (books from the local library and a floppy disk with txt files).
I was too young (mid teens) / unexperienced to get anything finished but did manage smooth vertical scrolling and almost got the horizontal stuff working, double buffering a rotating 3D cube (z buffering, math, line by line polygon drawing).
Then came DirectX and you lost all touch with the machine, a rotating 3D cube was breeze, I didn't see the fun in that.
Sure it won't compete with the performance of GPUs, but I feel like we should have a category of GPU-less PC graphics for things like the demo scene. Where you strive to deliver interesting results at modern resolutions but hamstrung by CPU-only, incentivizing exploring parallelization techniques, SIMD optimization that strongly resembles assembly coding of yesteryear, and good old fashioned cleverness.
* 'Many'-core CPU (say 8..16 relatively simple cores, eg. RISC-V) * A good, but modest amount of RAM (eg. few dozen... few hundred MB) * Integrated graphics, but of a conceptually simple type, eg. a plain framebuffer + _maybe_ some blitter / DMA / scrolling / hw sprite support. Simple enough that a single programmer can wrap their head around it (vs. complex 3D GPU where hardly anyone knows all its details). * Graphics outputting to common consumer display (HDMI, DisplayPort) * Sound & some other common I/O
Roughly Commodore Amiga level complexity (at most! simpler = better), just modern fabrication tech & faster.
This would be perfect platform for all sorts of homebrew games, hobby / retro style OSes, educational, industrial uses & more.
But doesn't exist afaik. Microcontroller usually don't have built-in graphics, too little RAM, or otherwise aren't quite it.
A step up (small SBC) and you get loooaads of peripherals, 3D GPU, firmware & associated complexity thrown in 'for free'. Nice for running full blown OS like Linux, not so nice for wrapping one's head around that hardware.
There is the Commander X16 [1] but it's "too 8-bit".
On the microcontroller side I was very excited about the STM32U599 [2] but it seems very secretive about how to program the graphics unit.
[1]: https://www.commanderx16.com/
[2]: https://www.st.com/en/microcontrollers-microprocessors/stm32...
Allwinner F133
Bouffalo Lab BL808
GreenWaves GAP8
(no native video hw on this one I think? targeted at IoT edge computing)
And these are often one-off parts. At some point it goes away, and then what to do? As opposed to being sort-of-standard platform offered by multipe vendors that one could code software ecosystem against (like for eg. Raspberry Pi).
You could of course design your own hardware. But then you quickly get into FPGA territory, design-your-own-computer project, lower clock rates, higher cost, etc. Cheap, small, highly integrated SoC much preferred here.
I ended up working on software rendering (ray tracing) for film production for many years. Now I'm working for a hardware vendor, so I get to have fun with the machine way below the DirectX level.
I was trying to do similar things on a 486 with a slow supervga card. Without vga hardware scrolling tricks it couldn't even do 60fps of full redraws at 320x200 8 bit.
Screen resolutions have gotten so high that there's a bit of a reversal again -- even if you can redraw an entire 4K screen at 60 fps, it's not exactly efficient. Games typically still redraw everything, but desktop compositors definitely do some optimizations, including dynamically assigning layers to hardware planes to reduce redrawn area.
Here's one game. Note we did not do the smooth scrolling but the coarse scrolling worked by the second method.
We had the tech to do smooth scrolling, I don't recall why it didn't make it to final game. Maybe compatibility.
So you're not wrong: this invention is perhaps nothing particularly special. What made it special was the combination of novelty, utility, and successful commercialisation.
Then why there were so many 'top tier' scrolling platformers at the time that ran so choppy? While I don't think it's a hard requirement for a fun game, the level of smoothness Keen had (especially on low-end hardware like a <10MHz machine) was eye-opening at the time.
It was a vast leap for PC gaming and it opened an new era of PC gaming.
However, here is what I never quite understood, what was so different about the NES and PC tech that Nintendo had figured out to do sideways scrolling years before the PC?
Here’s a video of the port: https://youtu.be/1YWD6Y9FUuw
My Dad pulled it from the DEC internal file sharing service and brought it home. I long believed that it was a figment of my imagination until I heard that ID had developed a demo for Nintendo that must have gotten leaked
The downside is that that's all it does. That's the whole graphics system. You can't like, paint an individual pixel.
(you can, if you treat each tile as a mini framebuffer, which is how something like the NES port of Elite is possible, but this is expensive and you only have a very small amount of processing time and a limited number of tiles)
PC's have typically had a much more bitmapped graphical regime, where individual pixels are addressable and drawable, which better suits a general purpose computer but means you have to do some trickery if you want to get some of the polish that consoles had, and was typically slower since you didn't have dedicated hardware that spoke in those terms. on the flip side though setting up a windowing system on an NES with its hardware speaking in sprites and tiles would be a nightmare.
PCs staggered on thanks to much faster 32-bit CPUs, but they didn't really pull ahead until 3D cards became the norm towards the late 90s.
But you don't get scrolling for free. You've got to manually copy memory around and as the linked article points out, if you brute-force it you only get around 5fps because of the ISA bus' limited bandwidth.
The NES (and other 8/16bit) game systems are not built to let you draw arbitrary crap. They are built to render tiles. You define a grid of background tiles and provide a scroll offset. Sprites work similarly but they can move independently. You get all this for free at 60fps. The downside is that you can't render arbitrary stuff very easily. You have to jump through some serious hoops to e.g. paint an individual pixel somewhere.
It's not so much that Nintendo "figured it out" before IBM. IBM built a general-purpose computer and created a series of general-purpose graphics systems geared towards static graphics, giving you fine-grained control over every single pixel. If you look at an EGA card it's a beast; lots of silicon on there.
Nintendo on the other hand created a much simpler single-purpose graphics system geared toward sliding tiles around.
https://www.youtube.com/watch?v=I845O57ZSy4
i would also recommend another two of his interviews:
Todd Howard https://www.youtube.com/watch?v=H9AAnV59ddE
Guido van Rossun https://www.youtube.com/watch?v=-DVyjdw4t9I
In hindsight, we were pretty lucky to have computers at that time at school. Even if old ones. Still have not found all of the games again on DOS game archives, that were on these machines.
If anyone knows other classic-gaming blogs, where there is technical depth, please do share. https://nicole.express/ and https://sudden-desu.net/ are my other favorites.
One of these days I’ll make a retro DOS game for fun. Just need to find the time.
> Those poor saps with 2,400 bps modems would spend almost a full half hour doing this.
This was me! Still remember it to this day.
Now that I've thought about it a little more, I realised it's like painting a picture on the side of a cylinder. No matter where you draw the left-hand edge of the image, there's always a way to rotate the cylinder (set the CRTC_START and PEL registers) so you can see the whole thing clearly.
> I took the easy solution of when you finally did run to the edge of the screen I accepted a hitch and just copied the whole screen up.
I remember when Keen started up it would usually mention something about "VGA compatibility mode enabled", and I always wondered what that meant.
BTW. Recommendations how to run this? As a "grown up" I haven't used windows in about... 20 years? How do I play this on Debian?
I see online that there aren't a lot of negative reviews about Commander Keen (like you would find about bad movies), and I suppose it makes sense. I mean, it was still fun. I would put it below Mario 2 though, and Mario 2 was the one I would leave out of a list like the one above.
On the PC, there were a lot of great games too, but side scrolling was definitely something to play on a console.
Anyway, most games are not as good as Mario, it is a genre-defining series. I think it is not a great comparison—what does it tel you that I’m slower than Usain Bolt?
Crystal Caves remains one that captivates people's attention though - it's very unassuming, no particularly strange gimmicks, but it has the right mix of stuff to be surprising and engaging. It even got a remaster on Steam.
PC, 80's/90's home computers: programming bits & pieces Lego style by oneself, exchanging software + knowledge with friends, exploring assembly code, coding straight to the metal & so on, is so much more rewarding + extends creativity / skillset for use later in life.
In comparison, game console is just 'dumb' appliance like a toaster or TV set top box: hit button, watch it do its 1 trick. ;-)
https://github.com/geon/kate/blob/master/src/platform/dos/eg...
I have really enjoyed Jason Schreier's recent books on game dev.
https://www.amazon.com/Once-Upon-Atari-history-industry/dp/0...
I found amusing how David Kushner in Masters of Doom describes him as "the human exclamation mark" :-P
Did figure out the double buffering stuff on my own though ;)
Seems so obvious, learn something new everyday, even if it would have been more useful, say maybe ~30yrs ago ;)
They are actually back up now.
You’re probably aware that the PC itself is an IBM development, but once it because a generic platform they couldn’t turn a profit while having to compete with all the cheap clones (I.e. what we today simply call PCs).
When the early 90's were here, IBM was losing billions of dollars a year, companies like Dell and Compaq were selling more and more PC's while IBM continued to sell less and less. There were spinoffs and re-organizations, IBM still made some things like the MWave soundcard/modem, but they couldn't really compete with all the small startups making new peripherals and components. IBM was still manufacturing things in the USA, they were and old and slow and kludgy company...
I mean to do that on EGA is very neat (well duh!) considering those consoles all have dedicated VPU's for this task. Just wanted to make sure I am understanding it correctly.
Isn't this similar to virtual scrolling?
For single-buffered infinite scrolling, this is exactly what you want, and this is how the BBC Micro's 640 pixel wide bitmap mode scrolls nice and quickly (something you'd never manage otherwise with a 2 MHz CPU), and why there are a fair number of infinite 4-way scrolling games on the platform. It's a shame more platforms didn't have this kind of thing designed in.
Thank you for your writing, it’s been exceptionally enjoyable.
You play a spirit version of a Shiba Inu guiding humans to the exits.