Super Mario 64 HD

The camera in Crash was on a rail. It could rotate left, right, up, and down (in Crash 2 and beyond, at least), but could not translate except by moving forward/backward on the rail. This motivates a key insight: if you're only rotating the camera, the sort order of the polygons in the scene cannot change.

This allowed us to sample points on the rail and render the frame at each sample point ahead of time, as a batch job, on the SGI using a Z-buffer. (We may have done the Z-buffer with software; I don't remember.) Then we could recover the polygon order of each frame by looking at the Z-buffer. And, even better, at run-time we could simply not render at all those polygons that weren't ultimately visible in the pre-rendered scene. This solved both the sorting and clipping problem nicely, and made the look of the game closer to 3K polygons/frame vs. the 1K polygons we were actually rendering in real time. (Many polygons were occluded by other polygons.)

The trick, though, was what exactly to do with this sort/occlusion information. In a nutshell, what I did was write a custom delta-compression algorithm tailored to the purpose of maintaining the sorted polygon list from frame to frame, in R3000 assembly language. Miraculously, this ended up being quite feasible because the delta between frames was in practice very small -- a hundred bytes or so was typical. And if a transition was too heavyweight (i.e., the delta was too big) we'd either sample more finely in that area or tell the artists to take stuff out. :)

One thing nobody talks about but which is obvious in retrospect is that without a Z-buffer you're pretty screwed: sorting polygons is not O(N lg N) -- it's O(N^2). This is because polygons don't obey the transitivity property, because you can have cyclic overlap. (I.e., A > B and B > C does not imply A > C). This is why virtually every game from that era has flickery polygons -- they were using bucket sorting, which has the advantage of being linear time complexity, but the disadvantage of being wrong, and producing this flickery effect as polygons jump from bucket to bucket between frames.

I'll leave the matter of weaving the foreground characters -- Crash himself and the other creatures -- into the pre-sorted background for another day.

Crash also benefited from the (at the time) novel rendering model that Andy, Mark (Cerny) and Jason developed. This basically allowed any vertex of crash to move anywhere in the animation sequences -- which was huge, because it allowed Jason to approximate traditional squash-and-stretch even on that limited hardware.

However, on the primary copyright issue of the APIs, the court ruled that "So long as the specific code used to implement a method is different, anyone is free under the Copyright Act to write his or her own code to carry out exactly the same function or specification of any methods used in the Java API. It does not matter that the declaration or method header lines are identical." The ruling found that the structure Oracle was claiming was not copyrightable under section 102(b) of the Copyright Act because it was a "system or method of operation."

This actually happened quite often in early generations of computer games and consoles. Super Mario Bros had quite a few clones where all that changed were the visual assets.

More recently, there are many examples of this happening on the iOS App Store and other venues with a low barrier to entry.

Edit: and :)

This is long settled in US law. Things like art and text are copyrightable. The game itself is not.

The patent in question, http://www.google.co.uk/patents/US6410835. Espacenet has it too of course, http://worldwide.espacenet.com/publicationDetails/claims?CC=..., but Google is better is it gives the B2 published form of the claims as opposed to the A1 first submitted form. Major fail there for the EPO's ESPACENET in my opinion.

Claims 1, priority date is 24 July 1998:

>"1. A dance game apparatus comprising: music output means for outputting one piece of music from at least one stored piece of music; a floor panel having a step-on base section; said step-on base section comprising a top panel and a support member which supports the panel; detection means for detecting a stepping operation on said step-on base section; said detection means comprising stepping sensors interposed between said panel and said support member at mutually opposing positions of said panel; said stepping sensors comprising longitudinally extending conductive sections having a longitudinal length, one of said conductive sections being moveable laterally relative to another of said conductive sections at any one of a plurality of positions along the longitudinal length of said one conductive section to effect contact with said other conductive sections at any one of a plurality of corresponding contact positions such that said stepping sensors detect stepping on said step-on base sections at plural locations corresponding to said plurality of corresponding contact positions, guidance means for performing a stepping operation instruction to said step-on base section in time with said music; measurement means for measuring a time deviation between the timing of a stepping operation instruction and the time at which the fact that said step-on base section is stepped on is detected by said detection means; and evaluation means for providing a higher score the smaller the measurement result." //

FWIW the Mario Kart patent you cite refers to methods of controlling NPC in order to provide strong rivals, avoid bunching of NPC in racing games and provide variation in race orders despite relatively fixed characteristics (acceleration and top-speed). None of that prevents you having cars with the same styles, having the same tracks, having the same end goals, having the same range of pickups and such - it only relates to specific algorithms for providing competing computer controlled cars/NPC.