dmbaggett

In the same era (age 7-12) I went to school on an airbase in Germany and at some point “they” (no idea who) decided I should not do normal math, but should instead spend time with the Airmen who ran the computers. They had an Interdata-something-16 minicomputer which had both punched tape and teletype I/O. I played Oregon Trail on the teletype and always died of dysintery. I once asked the wise and aged Airman (he was probably 25), “can I punch my own holes in the tape and make the computer do cool things?” To which he responded “Yes. No.”

I had “Microsoft Adventure” on the H89, which I played for a million hours and was why I dug up the original (probably not really; it’s complicated) Don Ekman Colossal Cave FORTRAN code and ported to TADS, which then led to Graham Nelson’s Inform port.

WUT, I had no idea. That’s cool!

I remember reading Byte Magazine when I was 7 and not understanding why I couldn’t plug one of those cool S-100 bus graphics cards into my Heathkit H89.

So I made space invaders out of box drawing characters.

BASIC was slow so I tried using C. (Yes, there was a minimal C compiler for the H89!) But then C was too fast and “for (i=0; i<10000; i++);” didn’t seem to slow things down like it did in BASIC so then I was stumped. “C is too fast for games!” — me

The H89 had a built-in monitor and a 5 1/4” floppy drive. Its precursor, the H8, was much like this emulated S100/Altair, with LEDs and switches as your only I/O.

I don’t know how much time Andy spent building the “poor man’s VM” system, but I know it was a significant effort that underpinned the rest of the game. The packer was something I probably put a few days into in the beginning (greedy and other trivial heuristics) and then kept improving in my “spare time” over the next year or so.

The packer was the final step after a level was pre-sorted and otherwise processed. It was quite fast, so it added only a little bit of extra time to the primary work of pre-rendering every frame of the level to recover the sort order (which typically took around an hour).

I did experiment with solver algorithms but they were so obviously going to be too slow that I abandoned the idea.

Thank you. Too many startups ago. :)

Sort of. While it was helpful to have the delta-compressed polygon list for each part of the level in its own 64KB chunk, the minor miracle of fitting >10MB levels into 2MB of RAM (half of which was VRAM as I recall) was down to two things: 1) Andy wrote this insane dynamic layout/loader thing that optimized the CD’s bandwidth (which was of course pathetic by today’s standards, as you point out); 2) I wrote a tool that packed the chunks into pages so that we never needed too many active at any given point in the level. This is an NP-Complete problem and we didn’t have solvers back then so the tool just tried a bunch of heuristics, including a stochastic one (think early simulated annealing). The problem with the latter was that if you “got lucky” you might never achieve the required packing again after the artist changed a turtle or something…

Exactly right! I had been working on a prototype for a Doom-style game in the summer of 1994 for the 3DO and built out the beginnings of the “sort polygons AOT” concept. While the idea was conceptually simple, the details were a bear. I guessed that using keyframes with the entire polygon list plus deltas would “just work out” and fit in the limited storage and computational budget of the PS1… and I was very relived when it was clear my intuition was right. (Otherwise we would have needed to redo the entire game engine.)

Another challenge was dealing with foreground objects: you have to somehow sort these into the pre-sorted background polygons. This mostly worked with bucket sorting but we had to use the gross hack of allowing each foreground object to have tunable “push-back” to fix sorting glitches. This required manual work for each level.

Finally, while precomputing the per-frame sort order for a game like Crash would be trivial now, in 1995 we had to build our own Beowulf cluster thingy and farm the level precompute out in pieces to the artists’ SGI workstations, and levels typically took an hour to process. The artists LOVED that. :)

Insomniac was down the hall from us when we wrote Crash 1 and yes, the Hastings brothers definitely wrote some very tight assembly code!

I don’t know about other developers at the time, but we had quite a lot of hand-written assembly code in the Crash games. The background and foreground renderers were all written in assembly by hand, as was the octree-based collision detection system. (Source: me; I wrote them.)

And this thread comes full circle: Mark Cerny actually significantly improved the performance of my original version of the Crash collision detection R3000 code. His work on this code finally made it fast enough, so it’s a really good thing he was around to help out. Getting the collision detection code correct and fast enough took over 9 months —- it was very difficult on the PS1 hardware, and ended up requiring use of the weird 2K static RAM scratchpad Sony including in place of the (removed) floating point unit.

GOOL was mainly used for creature control logic and other stuff that didn’t have to be optimized so much to be feasible. Being able to use a lisp dialect for a bunch of the code in the game saved us a ton of time. The modern analogue would be writing most of the code in Python but incorporating C extensions when necessary for performance.

Andy made GOAL (the successor lisp to GOOL) much more low-level, and it indeed allowed coding essentially at the assembly level (albeit with lispy syntax). But GOOL wasn’t like this.

Many years ago (circa 1993) I ported the original Colossal Cave adventure by Crowther and Woods to TADS, a language created by Mike Roberts specifically for authoring text adventures. (Colossal Cave just came up recently here.)

https://ifdb.org/viewgame?id=c896g2rtsope497w

Graham Nelson ported my port to his Inform language, and Inform is probably your best choice if what you actually want to do is write a (plain text) adventure game.

If you want to learn C programming, writing a text adventure in C would be a fun learning project! But aside from pedagogy there’s no real reason to write a text adventure in anything other than Inform, TADS, etc. Not only is it much easier to use one of these purpose-built languages, with Inform you get multi-platform compatibility going back to the 8-bit era for free!

Personally if I had any free time, I’d be more interested in looking at how to use a frontier LLM like llama as an integral part of a text adventure. There was something like this using GPT-2 circulating on here a while back, but it was pretty rough.

However, it’s clear that if you figured out how to precisely control the LLM so it didn’t produce crazy stuff, you could realize the dream of truly realistic NPCs in these games. Text adventures would seem to be a perfect laboratory for experimenting with this.

It depends on when you do the query. Years ago (mid 2000s) at ITA, Carl wrote code to find the longest possible shortest route between any two airports with scheduled flights. At the time the winner was Wasu, New Guinea to Peawanuck, Ontario, which took a minimum of 90 hours and many flights. There are airports you can only get to at the end of a long line of stops; this drives the number of stops way up.

We used these to make Crash Bandicoot and we even had a mode where you could run on the game on the SGI. It was ... sort of ... playable.

They were once required to do so (and may still be; I’m not sure at this point), at least if they want to offer flights to or from the US:

https://en.wikipedia.org/wiki/ATPCO

However, interpreting this data properly is decidedly nontrivial (>1M LoC).

Pricing does not imply booking is OK, though. And even circa 1999, Southwest hassled us (ITA Software) about even showing their fares, without us offering any way to book any flights on any carrier.

For inference you could use a maxed-out Mac Ultra; the RAM is shared between the CPU and GPU.

Full disclosure: I worked with Andy on Crash and am an angel investor. If you’re interested in AI and gaming I recommend you reach out. This is an extraordinary team and opportunity.

Hopefully you’ve read the Polygon article and seen the videos with Andy Gavin talking about the underlying tech. I was going to do part two of the video series but COVID killed it. Maybe we’ll revive that; it would be fun.

Yes, for Crash Bandicoot we had to entirely skip the C SDK for everything performance-critical; pushing arguments onto the stack and the SDK popping them off for each function call used more cycles than the underlying operation in many of these SDK calls.

Sony explicitly forbade this, presumably because they envisioned the API established by the C SDK as a way to ensure future backward-compatibility. We just ignored the rules and hoped the superior performance we could achieve would overcome any bureaucratic obstacles.

We also had to reverse engineer some of the PS1’s really nice capabilities. I only learned the hardware supported vector pipelining for strip rendering by noticing the coordinate values move from one register set to the next in the debugger.

Seeing that was a revelation: when rendering a polygonal mesh, you naively have to project three coordinates for each triangle. But if you convert your mesh into sequences of polygonal strips where each triangle shares an edge with the next triangle in the mesh, you only need to project a single additional vertex for each additional polygon in the strip. Observing the behavior in the debugger, it was obvious to me that the Sony hardware had in fact been optimized for this approach. But not only were we not given any documentation on this, we were instead told to use the C SDK, which didn’t expose this capability at all.

The PS1 also had 2KB of “scratchpad” that was slower than registers but much faster than RAM. Hearsay was this was a way for the CPU designers to make use of the physical space on the die meant for floating point instructions which the MIPS CPU in the PS1 didn’t have.

I used the scratchpad to store projected 2D “stamps” of the 3D world (stored in an octree) and Crash: a kind of low-res Crash Flatland. I could then check for X/Y collisions between Crash and the world very rapidly by inspecting the flatland bitmap stored in the 2K scratchpad. This was Mark Cerny’s idea; he was our producer on the Crash games and has also been responsible for PS2 through PS5 hardware.

One of the best teams on the planet!

An authoritative source on this Inventing the Alphabet by Johnanna Drucker. She covers not only the modern evidence but also attempts to classify alphabets throughout history, with particular focus on the Middle Ages. The first half is a bit dry -- how much do we really care what various scholars in the 16th Century made up about the history of the alphabet? -- (a lot was made up), but the second half looks at the modern archaeological contribution to the study of alphabetic origins and is very interesting.

There are also lots of scans of really interesting Medieval manuscripts cataloging alphabets in the book.

Unfortunately it's not perfectly supported. If you set up a private registry on gitlab and try to push packages with epoch versions, gitlab will normalize the ! to _ so everything breaks. (We found this out the hard way recently.)

Another Python versioning gotcha I've never see discussed is use of instructions like AVX2 in C extensions. There seems to be no way in Python versioning to say "this version is for CPUs with AVX2 instructions" so I guess public C extensions have to be compiled for the least common denominator instruction set. Does anyone know otherwise? How do other packaging systems like cargo deal with this?

I distinctly remember buying a 1GB hard drive in 1992 for $1300 via an ad in Computer Shopper. And that was a really good price!

At age 15 I wrote a pacman clone for the Atari ST and was both impressed by and jealous of Minter's Llamatron for the same platform. My game was 30Hz only rarely, usually degrading to 15Hz, and you could really feel it in the gameplay. Llamatron was always fast (always 60hz?) -- because that's just how Jeff rolls. Respect.

On the plus side, my crappy pacman clone was good enough to convince Andy Gavin to (years later) bring me on as the first developer hire at Naughty Dog. The system works! (I guess?)

We didn’t use BSP trees for Crash 1-3; instead we pre-rendered frames of the game on our SGI workstations and recovered the sort order from the (software) Z buffer. Then we stored the sorted list of polygons, using differential compression between key frames to reduce the space required. It was a total brute force hack.

What I think you’re seeing in Warped is what we did with Crash 1 and 2 as well: I had to sort the foreground object polygons into the pre-sorted background polygons. That was modified bucket sorting, but there were manually tuned adjustments to make it work and stable between frames.

I honestly don’t know, but I’m guessing an expert 2022 3D game developer is around here somewhere. :)

Interesting — TIL. Thanks for commenting.

Your intuition is correct. However, in the context of an O(N^2) comparison sort you can implement a tie-breaker check that at least ensures order stability between frames.

Occlusion culling is still relevant and of course BSP trees help with that as well. What I meant is there is no value in sorting polygons any longer. (As far as I know; the last time I worked on a game was 1997.)

As someone working at the same time as him on similar problems, I honestly and sincerely disagree. At the time my reaction was "this is space cadet stuff". 486 hardware was really slow, and the idea of doing any kind of real computational geometry back then was incredibly far-fetched. Until he showed it wasn't.

Amazingly brilliant work, especially given the CPU capabilities at the time. Carmack's use of BSP trees inspired my own work on the Crash Bandicoot renderer. I was also really intrigued by Seth Teller's Ph.D. thesis on Precomputed Visibility Sets though I knew that would never run on home console hardware.

None of these techniques is relevant anymore given that all the hardware has Z buffers, obviating the need to explicitly order the polygons during the rendering process. But at the time (mid 90s) it was arguably the key problem 3D game developers needed to solve. (The other was camera control; for Crash Andy Gavin did that.)

A key insight is that sorting polygons correctly is inherently O(N^2), not O(N lg N) as most would initially assume. This is because polygon overlap is not a transitive property (A in front of B and B in front of C does NOT imply A in front of C, due to cyclic overlap.) This means you can't use O(N lg N) sorting, which in turn means sorting 1000 polygons requires a million comparisons -- infeasible for hardware at the time.

This is why many games from that era (3DO, PS1, etc) suffer from polygons that flicker back and forth, in front of and behind each other: most games used bucket sorting, which is O(N) but only approximate, and not stable frame to frame.

The handful of games that did something more clever to enable correct polygon sorting (Doom, Crash and I'm sure a few others) looked much better as a result.

Finally, just to screw with other developers, I generated a giant file of random data to fill up the Crash 1 CD and labeled it "bsptree.dat". I feel a bit guilty about that given that everyone has to download it when installing the game from the internet, even though it is completely useless to the game.