We prove NP-hardness results for five of Nintendo’s largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokemon. Our results apply to Super Mario Bros. 1, 3, Lost Levels, and Super Mario World; Donkey Kong Country 1-3; all Legend of Zelda games except Zelda II: The Adventure of Link; all Metroid games; and all Pokemon role-playing games. For Mario and Donkey Kong, we show NP-completeness. In addition, we observe that several games in the Zelda series are PSPACE-complete.
Translation: video games might provide interesting fodder for complexity theory, and possibly provide a model for novel ways of looking at difficult decision problems. In any case, I just like seeing Metroid mentioned on the arXiv.
I was very happy to have gotten this far. I had the Kid, the Prince of Persia, running and jumping on my screen. I was able to control it and perform all the normal actions. And it felt right. Timing, speed, animations. Of course it was spot on, it was using the original code written by Jordan Mechner, lifted from its Apple II grave and brought back to life, with a new purpose.
At this point I was sure I could do this. It would only be a matter of months. Oh boy, was I wrong.
From the Prince of Persia C64 Development Blog, in which the author writes with excellent detail about his recent hobby attempt to reverse engineer and port the classic computer game to the Commodore64 (warning: lots of posts about pixels, sprites and assembly language debugging – your entertainment value may vary). The original Apple ][ source code for PoP had long ago been lost, but the game’s creator coincidentally posted a handy excerpt of the game’s design documentation as a PDF on his blog, and many other ports existed, so…why not try recreate the original code?
Bonus: Prince of Persia creator Jordan Mechner has collated his original design notes and journals into a nice 300-page ebook. Neat! I’d love to have a whole series of these for classic games.
If you love the old Lucasfilm games and want a peek into how their venerable game engine worked from a very technical perspective, you should read this article that walks through a disassembled Maniac Mansion. Extra bonus: Ron Gilbert, the creator of the SCUMM scripting language, drops a lengthy note in the comments section with insider info:
One of the goals I had for the SCUMM system was that non-programers could use it. I wanted SCUMM scripts to look more like movies scripts, so the language got a little too wordy. This goal was never really reached, you always needed to be a programmer. 🙁
actor sandy walk-to 67,8
This is the command that walked an actor to a spot.
actor sandy face-right actor sandy do-animation reach walk-actor razor to-object microwave-oven start-script watch-edna stop-script stop-script watch-edna say-line dave “Don’t be a tuna head.” say-line selected-kid “I don’t want to use that right now.”
I think it’s amazing that they managed to build a script interpreter with preemptive multitasking (game events could happen simultaneously, allowing for multiple ‘actors’ to occupy the same room, the clock in the hallway to function correctly, etc.), clever sprite and scrolling screen management, and fairly non-linear set of puzzles into software originally written for the 8-bit C64 and Apple II era of computers.
Mechanical engineering student Terry Garret plays through a few levels of Bit.Trip.Runner, one of my favorite games of the past year. It’s a very challenging game, with simple actions but difficult timings that are set to fun 8-music and sound effects.
The handsome logo for Segagaga, one of my absolute favorite video game concepts: you run a fantasy RPG version of Sega, the ailing game console company, fending off rival electronics behemoth SonyDOGMA (at the time, the Sega Dreamcast was facing its untimely demise). A surrealist, sarcastic, postmodern metafiction of the Japanese game industry from the inside, satire on a shoestring budget with a bit of loving apology for what was about to happen with Sega and the business in general.
“The Japanese bubble burst in 1993 – that was the start of the recession and the economic downturn. At the very same time, the gaming industry was keeping going just as if it was the boom time. In 1999, it was becoming clear that the boom was fading fast for the industry. Coincidentally, we were making SGGG at this very turning point. Near the end of the game, the hero is fired because his company closes, and he finds refuge in a game store near Sega that actually existed! The store manager is Alex Kidd – he was also fired from Sega, when Sonic arrived. The message to the hero is that no matter how bad things look, there is no point in crying over the industry. You have to carry on – just like Alex Kidd, who is working hard.“
In the same way a painting allows us to gaze upon the faces and souls of people from another age, or a book permits us to linger on the thoughts of great figures from history and fiction, videogames can expand our awareness of the world as it is, was, or might be.
It’s interesting to look back at the hype and spectacle of the early CD-ROM games (with novelties like Myst flying off the shelf the medium was hailed as the savior of declining video game sales) as a parallel to the hype and spectacle of the real 18th Century phantasmagoria and magic lantern parlor theater. From classic gaming site GOG.com’s short editorial piece commemorating their recent addition of Roberta William’s popular 1995 FMV horror game Phantasmagoria:
In the mid-1700s, long before horror pioneers like Alfred Hitchcock, films such as Dracula and Frankenstein, and even cinema itself, the predecessor to horror cinema was born in a tiny coffee shop in Leipzig, Germany. The proprietor of the shop, Johann Schropfer, welcomed patrons with a warm beverage and an invitation to shoot the breeze and some stick in his adjoining billiards room. But the extra attraction of running a table after a long workday didn’t do much to boost Schropfer’s steadily declining patronage. In an effort to drum up business, Schropfer cast out pool tables and converted the billiards parlor into a séance chamber. […]
By the late 1760s, Schropfer’s once-deserted shop had evolved into a hotspot where patrons gasped in awe at ghostly images projected onto smoke, chilling music, ambient sounds, and burning incenses whose aromas were evocative of malevolent forces. The masterful performance put on by Schropfer proved so lucrative that the coffee-shop-owner-turned-showman took his show on the road throughout Europe until 1774, at which time Schropfer, perhaps haunted by the specters he alleged to call forth from the afterlife, took his own life.
From a recent interview with legendary game designers Jordan Mechner (the original Prince of Persia) and Eric Chahi (Another World) on being an auteur in the modern game development environment. Jordan Mechner’s advice to the young designer:
A good friend in another field gave me this piece of advice recently. He said that most people approach things “1-2-3.”
One is the first inspiration, the vision, the excitement. One is gold. One is touched with magic; everyone wants a piece of it.
Two is all the reasons it won’t work, or won’t sell, or could get screwed up; all the difficulties – technical, financial, logistical – that need to be solved.
Three is doing it.
Most people get stuck on two. My friend’s advice was to go in a different order: “1-3-2”. Skip two and go straight to three. I’d never heard it phrased quite this way before, but looking back, the things I’ve done in my life that I’m most glad of, I did them 1-3-2. So that’s my advice too.
[I]t raises the question of how this particular nonsense word came into wide use at MIT. It seems reasonable to pursue this question, and reasonable that there would be some discernable answer. After all, there’s a whole official document, RFC 3092, explaining the etymology of “foobar.” It could be interesting to know what sort of nonsense word “zork” is, since it’s quite a different thing, with very different resonances, to borrow a “nonsense” term from Edward Lear or Lewis Carroll as opposed to Hugo Ball or Tristan Tzara. “Zork,” of course, doesn’t seem to derive from either humorous English nonsense poetry or Dada; the possibilities for its origins are more complex.
From Post Position’s “A Note on the Word ‘Zork’”, investigating the nonsense term that would in the late 70’s would become synonymous with interactive fiction and the birth of popular computer gaming. Maybe Get Lamp will soon clear up some of this for us.
The proprietary 8-bit processors that powered Atari’s home consoles are being resurrected by the Atari History Museum’s Curt Vendel. He’s rebuilding each chip from the fabrication specification data detailed in the original tape-outs he has in his possession, and hopes to be able to crank out brand new replacement chips (the originals have been unavailable to the enthusiast market for years). This looks to my non-engineer eyes like an impressive feat of reverse engineering and history gathering! If nothing else, one can appreciate the high-res circuit scans he’s posted in the discussion thread.
Katie Couric goes all regulators on some FMV villains in this circa 1990 clip about arcade laserdisc sensation (well, maybe not so much) Mad Dog McCree. It’s kind of sad to see early 90’s tv – the production values on the crummy video game look far more polished than the Today Show’s.
One of the best games of all time, now running experimentally in your browser, demonstrating that the future could be very bright for non-proprietary interactive content on the web. It’s only the first part of the 2nd level (or whatever you want to call the cage-swinging, alien-buddy-meeting scene) and it’s glitchy, but still looks beautiful and smoothly animated (maybe a bit too smooth, due to the <canvas> polygons being all anti-aliased and filtered out of the box). If you’ve never played the original game, an amazing high-res WinXP-compatible remake came out a couple of years back in honor of the 15th anniversary of its original release.
Pressure Cooker was an ambitious exception among its contemporaries. In 1980, most home computer music remained limited to single-voice melodies and lacked dynamic range. Robert “Bob” Yannes, a self-described “electronic music hobbyist,” saw the sound hardware in first-generation microcomputers as “primitive” and suggested that they had been “designed by people who knew nothing about music” (Yannes 1996). In 1981, he began to design a new audio chip for MOS Technology called the SID (Sound Interface Device). In contrast to the kludgy Atari TIA, Yannes intended the SID to be as useful in professional synthesizers as it would be in microcomputers. Later that year, Commodore decided to include MOS Technology’s new SID alongside a dedicated graphics chip in its next microcomputer, the Commodore 64. Unlike the Atari architecture, in which a single piece of hardware controlled both audio and video output, the Commodore machine afforded programmers greater flexibility in their implementation of graphics and sound […]
When I saw this headline linked by Waxy I took it to be an overview of the recent (late 90’s to now) chiptune music craze, but it’s actually a nice little overview of the nearly 30 years old history of writing music on game hardware. Even includes sections on cracktros, the demoscene, and the early advent of trackers, along with some good videos of the relevant technology.
We did manage to fox Psygnosis now and then, and I can lay claim that it took John White an hour to figure out “Its hero time”. When ever psygnosis did some testing, we’d get back a fax with the level name, time taken to complete, and some comments and a difficulty rating. These were usually aound 3-6 minutes, and some general coments on how they found it.
Every now and again though, the fax would be covered in scribbles with the time and comment’s crossed out again and again; this is what we were striving for while we were designing the levels, and it gave us all a warm fuzzy feeling inside.
Early 1990’s gamers all surely remember the schlocky FMV games like Sewer Shark (sadly directed by VFX legend John Dykstra!), Night Trap (widely attacked in the U.S. Senate by Joe Lieberman!!), and Double Switch (starring Corey Haim and Debbie Harry!!!), and probably even get a cold chill whenever the name Digital Pictures comes up. Turgid, not much fun, and costing in the millions to produce, they were supposed to revolutionize the home entertainment business (anyone remember the $700 Philips CD-i?).
The side of the story that I hadn’t heard until now is that those were actually ports by the time the Sega CD and 3DO came around. Originally those games were created for a late 1980’s Nolan Bushnell-produced VHS (!!!) system called the Control-Vision, aka the NEMO (short for “Never Ever Mention Outside”, an appropriate moniker). Special circuitry in the system would allow games to be encoded onto multi-track VHS tape, jumping quickly (?) between segments as players push the control buttons.
Going up against the then-$100 NES, and with a competing video tape game system that already failed on the market (World of Wonder’s Action Max), Hasbro wisely pulled the plug on the NEMO. All of the expensive FMV footage that was shot would only make the light of day a few years later, squeezed down to a resolution of 256×224 pixels, mercilessly dithered down to 64 colors at a time.
Taito’s new Cho Chabudai Gaeshi, a game based on a literal interpretation of the Japanese idiom “flip the table” (chabudai gaeshi). It gladdens my heart to see new weird games being made for the arcade. At least it’s easier to relate to than Boong-Ga Boong-Ga.
As one commenter on Kotaku notes, “If they localized this in the US it’d have to be called ‘F*ck This’”
From The Women of Leisure Suit Larry. I don’t think I could sum it up any better than the post’s author: “there is a seriously ugly and amazing coffee table art book dying to be made out of this”. Hopefully such a coffee table book would include a portion dedicated to the even-more-awkward non-Sierra attempts at smut like Rex Nebular and the Cosmic Gender Bender.
NewForestar’s NESynth, bringing 8-bit style waveforms to an iPhone app. It supports P2P collaboration with other iPhones, but it if it had a full tracker built into it it’d be killer. The accelerometer-tilt pitch-bending and “Famicom controller mode” are neat additions.
First localized video from the upcoming Phoenix Wright spinoff, “Miles Edgeworth: Turnabout Prosecutor”. Notable for the series is the move to adventure game-style sprites for the character interaction / investigation scenes. Watching this I realized what must be done: we need a hacked ROM of “Streets of Rage” with these sprites of Edgeworth, Gumshoe, and new “sidekick girl” character Kay replacing Alex, Adam, and Blaze! </videogame nerdery>