Friday, March 27, 2015

Crash Bandicoot Dev on rendering techniques

As seen on Hacker News:


Maybe Andy forgot to mention it; it's been a while since I've read the whole series.
The code was C and lisp so it didn't really require any effort to port other than replacing the rendering pipeline. And we used the SGIs to pre-render every frame anyway, to precompute the polygon sort order. (The PS1 had no Z-buffer, so you were stuck sorting polygons at run-time if you didn't do something clever.)
So we already had the rendering pipeline ported. Obviously you couldn't save your game to the memory card, etc. -- some stuff didn't work. But the game was playable (albeit very frustrating with keyboard controls).

That blows my mind, I always assumed it did have a z buffer. So what did you guys do to remedy 'z fighting' triangles? My interest is; I wrote a 3d renderer in Java using fillPolygon() many years ago, and used polygon sorting in place of a z buffer. Z fighting was of course a problem.

Some day I will write this up for real, but without going into detail, here's a summary.
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.

Thursday, February 12, 2015

Run a Minecraft Server on OSX Boot2Docker

Run a Minecraft Server on OSX Boot2Docker

Here's how I did it. I hope you find it useful!

One-time Setup

Do these steps once, to initialize Boot2Docker:

Step 1: Install Docker for OS X

Step 2: Create a directory to hold your Minecraft files. This needs to be under the /Users part of your file system because boot2docker automatically mounts /Users to the boot2docker-vm.

  mkdir /Users/yourname/minecraft/data

Step 3: Initialize boot2docker

  boot2docker init

Step 4: Forward the TCP port Minecraft uses from the Mac to the boot2docker-vm.


  VBoxManage modifyvm "boot2docker-vm" --natpf1 "tcp-port25565,tcp,,25565,,25565";

Start Minecraft

Do these steps every time you want to start your Minecraft server.

Step 1: Start boot2docker.

 boot2docker start

Step 2: Set up the shell variables so you can use the docker command.

 $(boot2docker shellinit)

Step 3: Run the minecraft container.

 CONTAINER=$(docker run -v /Users/yourname/minecraft/data:/data -d -e EULA=TRUE -e VERSION=LATEST -p 25565:25565 itzg/minecraft-server)

The first time your run this it will take a few minutes to download and install minecraft. After that it should be much faster

View the Minecraft Server Log

  docker logs $CONTAINER

This prints out the logs from the container (you set the CONTAINER variable as part of the docker run command above.)

If you've lost track of your container, you can list all currently running containers.

  docker ps

If you don't see any containers, you container may have already exited. The Minecraft server will exit if it encounters an error while running.

Shut Down

You can shut down all running containers and quit boot2Docker by using the stop command:

  boot2docker stop

Note that the Minecraft Server files will be stored in /Users/yourname/minecraft/data, and when you've stopped the server you can edit the files using your mac. (You might want to edit the files in order to modify the server settings.)

Sunday, February 8, 2015

"Masters of Doom"

I've been reading the book Masters of Doom about the careers of John Carmack and John Romero. I have ported their games Doom and Quake to many different platforms. It was interesting to read about their lives and game business.

The book brought back memories of development in the '80's, and '90s. Things were simpler (and worse) then.

Some other John & John links:

The Rise and Fall of Ion Storm
Stormy Weather

Carmack QuakeCon Keynotes


Sunday, January 11, 2015

Reverse engineering my own game

I've long-since misplaced the source code to my Atari 800 game Dandy Dungeon. But thanks to the Atari800MacX emulator and the emulation scene, I've been able to play an emulated version of my original game. That's been helpful for remembering all the little details of gameplay.




For example, I was able to determine that the original game animated the arrows at 15 Hz and the players and monsters at 7.5 Hz.

FWIW I think the emulator may be slightly incorrect about the HBLANK processing emulation. I'm pretty sure that the color background for the 4th line of text should be a different color from the color background of the 3rd line of text.

The iOS version of the game is progressing -- the dual thumbstick virtual controls work well.

The next step (and it's a big one) is going to be multiplayer support. GameKit here I come.

Sunday, January 4, 2015

Fun with shaders

There are a total of 3 draw calls and 2 textures in this scene:


The whole tile map is rendered as a single draw call: a single 2-triangle tile that's instanced Row x Column times, using a 3D texture as a texture atlas. I originally used point sprites, but switched to instanced triangles because I wanted to use non-square tiles.

The virtual joystick is rendered as two coarse triangle strip rings, using a 1D radial texture. Note the anti aliasing. (I could have used quads, but wanted to minimize overdraw.)

So far Metal has been fairly straightforward to use, at least for someone like me coming from a DirectX 9 / Xbox 360 / Android OpenGL ES 2.0 background.

Friday, January 2, 2015

3*(N+1) Devices for N People

At my house we are trending towards having N+1 laptops for N people, because (a) I need to keep my work laptop separate from my home laptop, and (b) frequently everyone in the family wants to use their laptops at the same time.

The same goes for tablets, and when the kids are old enough to have phones I expect it will be the same for phones.

I tried using multi-user accounts on shared family tablets and laptops, but ended up assigning each kid their own devices. It was simpler from an account management point of view, and the kids like personalizing their devices with stickers and cases.

Having assigned devices also makes it easier to give different Internet and gaming privileges to different kids, depending on age and maturity.

A downside of assigned devices is that not all the devices have the same features. People complain about hand-me-down devices, as well as the perverse incentive created when an accidentally broken device is replaced by a brand new, better device.


Letting go of the Web and Embracing Mobile

When I started working on Android in 2007, I had never owned a mobile phone. When Andy Rubin heard this, he looked at me, grinned, and said "man, you're on the wrong project!"

But actually, being late to mobile worked out well. In the early days of Android the daily build was rough. Our Sooner and G1 prototypes often wouldn't work reliably as phones, and that drove the other Android developers crazy. But since I was not yet relying on a mobile phone, it didn't bother me much.

Seven years later, mobile's eaten the world. But I still haven't internalized what that means. I think I'm still too personal-computer-centric in my thinking and my planning.

Here's some recent changes that I'm still trying to come to grips with:

  • Android and iOS are the important client operating systems. The web is now a legacy system.
  • Containerized Linux is the important server operating system. Everything else is legacy.
  • OS X is the important programmer's desktop OS (because it's required for iOS development, and adequate for Android and containerized Linux development.)
  • The phone is the most important form factor, with tablet in second place.
  • Media has moved from local storage to streaming.
  • Programming cultural discussion has moved from blogs & mailing lists to Hacker News, Reddit & Twitter. (To be fair, these new forums mostly link back to blog posts for the actual content.)

In reaction, I've stopped working on the following projects:

  • Terminal Emulator for Android. When I started this project, all Android devices had hardware keyboards. But those days are long gone. And unfortunately for most people there isn't a compelling use case for an on-the-device terminal emulator. The compelling command-line use cases for mobile are SSH-ing from the mobile device to another machine, and adb-ing into the Android device from a desktop.
  • BitTorrent clients. My clients were written just for fun, to learn how to use the Golang and node.js networking libraries. With the fun/learning task accomplished, and with BitTorrent usage in decline, there isn't much point in working on these clients. (Plus I didn't like dealing with bug reports related to sketchy torrent sites.)
  • New languages. For the platforms I'm interested in, the practical languages are C/C++, Java, Objective C, and Swift. (And Golang for server-side work.)
    • I spent much of the past seven years experimenting with dynamic languages, but a year of using Python and JavaScript in production was discouraging. The brevity was great, but the loss of control was not.
Personal Projects for 2015

First, I'm going to port my ancient game Dandy to mobile. It needs a lot of work to "work" on mobile, but it's a simple enough game that the port should be possible to do on a hobby time budget. I'm probably going to go closed-source on this project, but I may blog the progress, because the process of writing down my thoughts should be helpful.

After that, we'll see how it goes!