The Jason Jones (Bungie Software) interview (pages 199-207) from "Tricks of the Mac Game Programming Gurus" published by Hayden Press 1995 (ISBN# 1-56830-183-9). The book in now out-of-print. Transcript brought to you by M-Class.
Profile: Jason Jones
Jason Jones is the lead programmer at Bungie Software for the very hot game Marathon. In case you are among the few who haven't seen it, Marathon is a first-person, fully 3-D action/adventure/combat game in the tradition of Pathways Into Darkness, Wolfenstein, Doom, and so on.
Q. Could you give me a general idea of Marathon's architecture? Is there a rendering engine and a refresh daemon a l%87 Doom? How exactly is the program structured?
A. No, Marathon doesn't have that type of asychronous operation between the game model and the rendering engine. They're clearly separate in the architecture, but all the game code is executed between frames while we're working on rendering the image. We generate a frame, display it, and we figure what happened in the world while we were generating that frame, update our state of the world, and then draw the next frame.
Q. Basically, the program generates a frame or a screen of animation every so often. In between this, it processes events that occurred, maybe a user interaction.
A. Let me explain that a little better. There are two things that go on. There's a big piece of data sitting in memory somewhere that represents the state of the world at any given time. It tells you where the monsters are, where the projectiles are in the air, and where all the players are. It also indicates if doors are open, if objects are in certain places, and if there's something exploding. The data block has all that information.
Basically, we give that big piece of data to the rendering engine, which turns it into a picture. It [the engine] renders a screen to show to the player, based on where the player is and what he can see from that position. Essentially, the input to the rendering engine is the state of the world, and the output is a bitmap that represents what the player sees. So then we display that bitmap and then, depending on how much time has passed, we may have a lot or a little work to do. If it took a long time to render that frame, we have a lot of work to do. If that frame was rendered in less than a 30th of a second, then we might not have any work to do. In that case, we actually wait until the state of the world changes.
We have thirty updates a second, or, put another way, our world changes every 30th of a second. We monitor the player's keyboard every 30th of a second, and we check the network for other player's commands every 30th of a second. Then, between frames, we handle all the updates that occurred while we were rendering the previous frame. Finally, we render the next frame. It is not like Doom, where things reportedly happen asychronously. However, we do a lot of stuff asychronously. A lot of work on the update happens this way. We have an interrupt that fires every 30th of second and a lot of work happens during that interrupt.
Q. What's the interrupt? is that the frame update or what?
A. No, the frame update is every 1/30th of a second. The state of the world is updated from the interrupt.
Q. So the interrupt handles updating the parameters in the big data block that represents the world?
A. It checks the player's keyboard for keystrokes and checks the network. Stuff like that.
Q. Do you have a really complex event loop that primarily handles updates and everything else is sort of subsidiary of that?
A. Yes. The complex loop has to update everything. It lets the monsters move. It moves all the bullets, and it updates all the explosions. It lets all the players move according to the commands they've given, if any. By complex I mean it does a whole lot of work. Everything that has to do anything in Marathon has to do it every 30 of a second. So we do have a big loop that basically goes out and handles all of that.
Q. Is this your main event loop? Or is there no similarity to a Mac application event loop at all?
A. There is very little similarity. We actually have two loops: a game loop and a Mac event loop. The game loop is a little bit subservient to the Mac event loop. We have a very simple Mac event loop. It basically looks for Command-Q to quit the game, and it really doesn't do much more than that. The main Mac event loop then calls the game loop, which does the updates. It goes through as many iterations as it has to, depending on how long the last frame took to render. The main purpose of our Mac event loop is to avoid giving the operating system any time.
Q. That way, Marathon can have most of the processor's time to get its work done. So you just look for look Command-Q for quit?
A. Honestly, the only things I think we look for from the operating system are Command-Q and Command-W, which both do the same thing. That's probably it.
Q. So most of the user interface processing is handled in the game loops as well?
A. Exactly. It's all game-related stuff like updating the weapons - things like that.
Q. On the user event stuff, like the keyboard, do you use Toolbox calls or do you do some other mechanism to grab a keyboard event?
A. We use the Toolbox call GetKeys(). We do not read the state of the keyboard through the Event Manager.
Q. You use GetKeys() and then look at the low-memory global keymap array and pull the keystroke out of there. Now, can you tell us about the rendering engine?
A. The most difficult part of the rendering engine to write is, given a point in the world and the direction in which the user is looking, how do you find out what surfaces must be drawn and in what order they have to be drawn?
Q. In other words, you're trying to figure out if there are objects in the way. You don't worry about drawing the rest of the wall, because there's something in front of it you have to worry about drawing first.
A. The problem is dealt with this way: Given an entire map of the area, the first thing you do is trivially discard all the stuff that is behind you and to the sides of you. Then, for stuff that you can see, you have to figure out what order you have to draw each object. You need to know where it is, what orientation it's in for proper texture mapping, and then whether there are any objects in front of it, such as monsters or missiles. So, a very large part of the renderer is devoted to simply generating a list of 3-D polygons with enough information for texture mapping.
Q. I've seen the Preferences section of Marathon where you can turn the texture mapping of the floors and ceilings off. Is that to enhance playability on a slower system?
A. You can turn off the ceilings and floors. Right. we have two totally different subroutines: One of them handles floor and ceilings, and the other handles the walls. The technique and texture maps are totally different.
Q. Why do you have the two subroutines anyway? Was there some compelling design reason you did it that way?
A. Absolutely. There are certain mathematical simplications you can exploit for speed. They're totally different in the case of mapping a floor and the case of mapping a wall. So, we wrote two. Instead of writing one slow general-purpose routine, we wrote two specialized ones. And, the simplications are fairly obvious. A wall always moves straight up and down on your screen and is always perpendicular to your viewing direction. When we're doing the texture mapping, we're actually stepping along the floors from left to right on the screen, and we're stepping along the walls from top to bottom.
Q. Because all the walls are perpendicular, all you have to do for the texture map is crunch the pattern down. But because of perspective, with the floors and ceiling textures there's a lot more math computations involved. Is that the idea?
A. Right. The floors are actually more complicated. When we're texture mapping a wall, we can figure out what column in the texture we have the texture map, and then we know that as long as we're within the same column on the screen, we're coming from the same column of the texture. So all we have to do is worry about that single column. So that's why we do walls in column order.
Q. Quick technology term here: What do you mean by "column"? Is that an architectural element, or is it something else?
A. I just mean a column of pixels on the screen. A vertical column of pixels as opposed to a row of pixels. A row is horizontal, like a scan line, left to right on the screen. Columns are top to bottom and rows are left to right.
Q. Now Lighting- do you handle that any special way?
A. This is sort of a general thing. All the lighting in Marathon is done through look-up Tables. We don't do any calculations on the fly. We're not sitting there with a pixel, saying "All right, we need to darken this pixel 15 percent," and do a bunch of Multiplications and divisions. That's true for pretty much everything in Marathon. Anything interesting that happens probably goes through a look-up table.
So we have a Lighting intensity value and we have a pixel color value, and we combine those in the right ways, send them through a table, and we get out a new pixel value. Everything that goes to the screen gets lighted in some way. Even if a pixel's value is 100 percent intensity, it still passes through a lighting table and remains unchanged. On the lowest level, the lighting is done through look-up tables. On a high level, we assign intensities to individual sprites walking around the world, and we can assign intensities to the floors and ceilings of the map. The walls then intelligently pick up the intensities of the ceilings and floors above and below them.
Q. So you don't do any special region Mapping or anything. Say there's an open door and there's a beam of light coming out of it, lighting up the corridor.
A. Right. And we can do that with some tricks. If you've seen any of the map editors for Marathon, we can create a small segment of the floor that looks like a beam of light coming out of a door. We light that segment very bright and light the area around it very dark, so it looks like there's light coming out of the door.
It's a very common trick with engines like the one that we used. You are able to create some pretty neat lighting effects by changing the geometry of your floor. You plan the geometry of your floor ahead of time so it looks like light casting out of a doorway.
Q. For the rendering engine, how many people did you have working on it, and how long did it take?
A. There were three people working on Marathon, and it us a little less than a year. We started in May and were finished in December 1994.
Q. Was there one person handling the engine, or did everybody work on it?
A. Two people worked on the texture mapping and the rendering parts of the game. The third programmer primarily handled writing the Mac user interface and some of the less important parts of the actual game itself.
Q. What sort of things did you do to improve game performance? You mention the look-up tables. Were there other techniques, such as using CopyBits() for blitting to the screen, or color palette management?
A. Not really. we do use CopyBits()- that might be an interesting piece of trivia. We have a lot of 68k assembly code. At the moment, the game doesn't have any PowerPC assembly code. We're relying on the compiler to make our code look good.
Q. What development tools did you use?
A. We use MPW exclusively.
Q. What was the reason for using MPW? Better code optimizations, or just that you were familiar with the environment?
A. Better code optimization. It's also what we happen to be familiar with. We know MPW and have a lot of time invested into MPW scripts and tools. MPW is much more expandable, and it's a more versatile system.
Q. To get back to coding issues, you mention lots of 68k assembly language. Do you have a ballpark idea of what percentage of Marathon is in 68k assembly?
A. Not that much of the whole program itself- I would say five percent at the very bottom. It's located in the texture-mapping routines. Maybe even less than that; it's probably more like two percent, but that is a lot of assembly because Marathon is a very big project. The assembly code probably took me a good two weeks, off and on, to finish. Which is a really high investment for a pretty small part of the project, but you have to do it to make the program run faster.
Q. It sounds like Marathon was written in C.
A Right. The entire thing is written in C.
Q. Did you just do some code profiling and figured out what 10 percent of the program was called 90 percent of the time, and then fine-tune those routines in assembler?
A. The 10/90 thing is a clich%8E, but that's right. That's exactly what we did. We took the game after it was done, we profiled it, and we figured out what was slow and rewrote that in assembly. Profiling was actually helpful for other reasons, too. A lot of things can be fixed in C as well. If your algorithm is bad, then your assembly code can be bad. Assembly was a last resort for us.
Q. So you optimized the C code first. You looked for better algorithms in C before resorting to assembly.
A. We pretty much expected to go assembly code in the texture mapping, but we absolutely refused to go to assembly in any of the high-level game code. If the monsters move around really slowly, it's because their code is slow. If the map monster code is slow, we weren't going to rewrite it in assembly- we just fixed it so that it worked better and faster. Because that's stuff you just don't want to do. Q. I'm guessing that you're considering porting Marathon to another platform at some point.
A. Obviously for portability, assembly language code is a huge liability.
Q. You mention texture mapping. What other parts of Marathon needed that final performance boost from assembly language?
A. Actually, just the texture mapping. That's one reason why the texture mapping was kept separate from the rendering. That front end that builds the surfaces loop. Q. Was there any difficulty in presenting things in 3-D and keeping track of it? I've wandered around in corridors that go one above another.
A. Not really. We planned for that kind of stuff and it works pretty well. There's some tricks, but that was a fairly easy part of the project compared to say, the front end of the rendering engine. The collision detection code is really complicated as well. Q. Why is that complicated?
A Just because it's a lot of gross maps. You're dealing with an object, an arbitrary polygon, that's moving around, and you have to make sure it doesn't go through a wall. In fact, you have to stop the object before it goes through a wall, not right up against the wall. you end up with a pretty weird, complicated set of equations.
Q. Did you use signed integer math and keep away from doing floating point calculations? A. Yes. All the complicated math in Marathon is done in fixed point math for speed. There's no floating point.
Q. How do you manage the game map, or keep things mapped in memory, such as the tunnels? Is there a list, or what?
A. Yes. It's just a bunch of lists. There's a monster list, a projectile list, a list of the walls, doors, stuff like that. It's a fairly straightforward arrangement. Anybody who's seen the map editor can pretty much appreciate what all of our low level data structures look like. There's a set of points, a set of lines that connect points, and a set of polygons, which are made of lines. They're just a bunch of lists in memory.
Q. Now, about Marathon's network capabilities. Suppose several people are playing a networked death match. How do you handle network protocols and communications? How does that big global block of data get updated so that it looks the same on everybody's screen? So that what happens to one person gets relayed (or transmitted) to everyone else?
A. One of the tricks we used in Marathon was to try to make its network operation no different from its local operation. That is, commands from remote machines are really no different than the commands from your local machine. Inside the game engine itself, we don't special-case the networking commands. Marathon is set up so it's almost like there are eight people on the same keyboard as far your machine is concerned. The network protocol itself is packet-based. We don't use any of the fancy, higher-level services of AppleTalk. We don't use any of the data streams stuff. It's all DDP.
Q. Datagram Delivery Protocol.
A. Exactly. We use DDP with some tricks to try to minimize the number of packets you send around the network, especially over LocalTalk, so that we don't overload the network. On an Ethernet network, we're sending packets 30 times a second to make sure that everybody keeps up with the game. The networking code is another thing like the rendering. It's just heinously complicated.
Q. So the game engine sees all the commands and it doesn't matter where they come from, since they're all the same format. However, suppose one guy has the flame thrower and he's flaming some hapless person. For the person on the receiving end of that, you know his state's going to be entirely different from the person wielding the flame thrower.
A. Each person's computer knows who is playing at the keyboard. So, that's the view that they see. If you check the right box in a network game set dialog, you can actually switch between different player's views by hitting the Delete key. That indicates that your computer always knows what is happening to everybody else. So, even if you can't see the stuff, your computer is keeping track of it. Really the only thing your computer is doing differently from everyone else's computer is the point of view. Rendering a different view of the world.
Q. So, in the game engine, part of that global information is events coming in. They could be from anywhere, say another machine. For one person's state, perhaps he's being hit by a rocket. And for another person, he's the guy that shot the rocket.
A. Each machine has to know who the guy at the keyboard is playing. So the game knows what to show. There's a checkbox in the setup game dialog which allows you to see other players on the map. If that box is checked, you can see other players on your map. You're also able to switch to their point of view by hitting the Delete key. That doesn't work in the regular game- that would be cheating. You can see the weapons they're carrying, how much health they have, everything about them. Even their motion sensor.
Q. For the point of view, when you finally get an image rendered, do you use CopyBits() to get it to the screen?
A. Exactly. CopyBits() is extremely fast.
Q. Did anything specific stand out when you did performance tuning or the design of the game in general?
A. I think the most important thing we did was remove the Mac operating system from the game as mush as possible. We call the MacOS to draw graphics, play sound, or get something from the keyboard. So we're not doing anything with windows. We're not calling our event loop- WaitNextEvent() rather- really often. We call it very infrequently. We're not handling mouse clicks through the operating system. Most of our graphics are bitmaps, so we're not doing a lot of line-drawing calls, rectangle-drawing calls, or other QuickDraw stuff. So really we don't use many OS calls, just Time Manager calls, CopyBits() and GetKeys().
Q. As you built the game, were there instances for which you realized the design was flawed? Flaws where you said, "We need to redesign this for better play," or "It's easier for somebody to navigate around if this code was changed"?
A. Marathon suffered that calamity many times. We did that with the maps. We changed the maps to make the game play different. And we did that with the game code as well. Especially the rendering engine. I forget the exact number, but it was fully rewritten at least three times. It also suffered a lot of small changes here and there. The texture-mapping routines underwent the same thing. They were fully rewritten at least twice. Other parts of the game had the same thing happen. You wrote something and it doesn't work, then you fix it. A lot of times when you do something for the first time, it doesn't work. That happened a lot.
Q. Were there performance issues, where something works, but it's so slow you had to use a different algorithm or change the game architecture slightly or a lot, perhaps to improve performance?
A. Yes, that happened. It's kind of interesting because most of the time, for instance, the rendering engine and texture mapping are the most speed-critical parts, and we rarely rewrote those for speed. We rewrote them because they didn't do something right or we needed to do more with them. Every time we rewrote them, they would get faster, of course, because we would get better at it. So, the only rewrite that was specifically intended to speed the game up was the one that put the texture mapping into assembly. We never rewrote a huge part of the code just because it didn't run quickly. It was usually because it didn't do something we wanted it to do.
Q. These rewrites were more for design or game play issues than for performance.
A. Right. One of the reasons that Marathon was started only in May was that we were rewriting large parts of it that we were not happy with. We could have shipped it at the end of August, but we weren't happy with it, so we didn't. I think that was a really good decision. I would make the same decision again. If I'm not happy with something, we're not going to publish it. We're going to continue to do cool 3-D stuff and we are working on something now, but we're not talking about it.
Q. Will this something use advanced MacOS services like QuickDraw 3D?
A. No, it will not. The hardware acceleration options in Quickdraw 3D are very interesting to us. I'm really excited about having hardware acceleration for 3-D texture mapping. But the software services of QuickDraw 3D, which is primarily what is available now, are not as interesting to us because we'll always be able to outdo the software because we're trying to code a very specific case, and QuickDraw3D handles the general cases.
© Hayden Press
All Rights Reserved.
Back to the Marathon's Story page.