T w e n t y S i d e d

The project is now officially over budget. I expended vast quantities of time obsessing over framerates and benchmarking this weekend. My budget was about 30 hours, and while I haven’t been keeping a rigorous tally of hours, I’m well past the deadline and not yet done. But the end is in sight. I’ve determined to get this thing done this week. All told, it looks like I’ll have sunk 40 hours into it. For perspective, if this was a game with an eighteen month budget, I would just have missed going gold and admitted that we were going to need another six months. And that our entire staff spent six months of the budget playing Left 4 Dead. Good thing I don’t have investors.

I’m afraid this stretch of the project is likely to be a bit dry. It can’t all be colored pixels and bloom lighting. Sometimes I have to go and fuss over dull numbers and time things, which makes for unspectacular screenshots. I’ll do my best to make this interesting.

By now the program is running like a slow pig, and has been for a while. 30FPS for a little city like this is appallingly slow, and before I move on to grander things I need to know how it’s going to run.

The first step in speeding up a program like this is finding out where the bottlenecks are. There are several aspects of rendering that I look into when facing slowdowns:

1. CPU bottleneck: The program just isn’t running fast enough and so it isn’t sending polygons to the GPU fast enough.
2. Throughput bottleneck: The software is capable of sending the polygons faster, and the GPU is capable of rendering them faster, but because of drivers or hardware limitations you just can’t send the data fast enough. You’ll run into problems like this if you’re trying to render a whole bunch of lightweight, easy-to-draw polygons. (With “bunch” in this case meaning “hundreds of thousands” or even “millions”.) If you’re drawing a bunch of tiny little triangles with no special lighting effects or texturing, (what the heck are you drawing, anyway?) you can run into this bottleneck. I don’t encounter this very often due to the fact that I’m usually working on the lower end of the tech curve. (Although I’m pretty sure I ran into it during the terrain project. I can’t remember now.) In any case, I understand this bottleneck is one of the reasons for the move from PCI to AGP, and from AGP to PCIe slot interfaces. The newer bus interface lets you pump more data to the GPU. I have… wait, let me write some code to do a count…. Okay: 40,804 polygons. That’s not counting a few special case groups like the cars, ground or sky, but that number is probably within 1,000 polygons of the total. So I don’t think I have to worry about throughput on anything built in this century.
3. Fill-rate bottleneck: This has always been where I do most of my work. Problems like this usually come from filling the screen with expensive polygons. In contrast to the earlier case where I might have been drawing millions of cheap polygons, perhaps I’m slowing things down by drawing just a few expensive ones. Fifty polygons sounds pretty pathetic compared to a million, but if all fifty polygons cover the entire screen and do complex blending, then you’ll end up with a fill rate problem. Your program is sending those 50 polygons nice and fast, and there are so few they won’t clog up the hardware pipeline, but the graphics card is going to take a long time to draw them. Full-screen effects (like bloom lighting and depth-of-field) can cause fill rate problems.

An analogy I like: The CPU is a waitress taking orders. The throughput is the rate at which she can put order strips up to be read by the cook, who is the GPU in this case. Fill rate problems mean he’s not cooking stuff fast enough. (Yes, I know they’re called servers today, and not “waitresses”. But the restaurant used in this analogy is a roadside greasy spoon diner in 1978. She doesn’t care if you call her a waitress, as long as you tip well and the kids don’t make too much noise.)

The third type of slowdown is easy to spot. If making the window smaller speeds things up, then it’s a fill rate problem. If not, then it’s probably a CPU problem. I’m sure I’m not having a fill-rate problem, but I check anyway because you don’t begin research by assuming you know everything.

I shrink the window. No change in the framerate. I shrink it to almost nothing. Still no improvement. Just for fun, I turn off writing to the z-buffer and change the program to draw the buildings as translucent. This will make all of those polygons many, many more times expensive and will ensure that the GPU has to draw every. single. one. Then I make the program run full-screen.

Take that, fancy-pants hardware! Let’s see how you like choking on 40,000 two-sided alpha-blended, screen-filling polygons!

Hm. That actually looks kind of cool.

No change.

Wow.

Not only is my graphics hardware not the bottleneck (which I already suspected) but it’s not even being reasonably challenged. Going back to the waitress analogy, here we have a cook that can prepare meals faster than the waitress can write them down. She writes down a four-order meal with appetizers and desserts, and the food is done before she can get back out on the floor to take another order.

As someone pointed out earlier in the series, these new cards are designed for rendering with complex pixel shaders that do fancy bump mapping, specular mapping, texture layering, dynamic light passes, lighting objects at grazing angles, and a whole bunch of other intense math. On every single pixel it draws. Here I’m simply asking it to take one lone texture map and apply it to the polygon, and I doubt I could hope to keep the thing busy with such a lightweight job.

Actually, tests reveal there is one thing it’s slightly sensitive to, which is changing textures. Back in step one I made texture maps for the buildings. Think of rendering as painting. If I ask you to paint a red stroke on the canvas, then a blue one, then a red one, it will take longer than it would to do both red strokes and then the blue. It takes a moment to lower your brush, clean it off, load it up with paint again, and bring it back up to the canvas. I can get a small performance boost by making sure I render all of the buildings that share a common texture at the same time. With eight textures and (roughly) 3,000 buildings, rendering them in a random order will cause the graphics card to have to change paint over 2,500 times. If I sort the buildings, it will only have to do so 8 times. This gives me a modest performance boost of around 10fps. That’s nice, but it’s trivial compared to the real optimizations I’ll need to do. I should have gone after inefficiencies like this one later on, and go after the low-hanging fruit first. But I did this one more or less by accident as part of my tests.

(Note that I’m writing this after the fact, and I didn’t keep a perfect record of how much of a performance boost I got from each step. The numbers I give for framerates are vague recollections and guesses.)

Shamus Young is a programmer, an author, and nearly a composer. He works on this site full time. If you'd like to support him, you can do so via Patreon or PayPal.

Streetlights

Now it’s time to round out the scene with lights. But in order to place the streetlights, I need to know where the streets are. In an earlier step I reserved street space, but now I’ll take that space and divide it up into sidewalks and specific lanes.

That done, I can have it scan over the world and look for places that need streetlights.

Bloom Lighting

I add another render pass for doing bloom lighting. The effect is of course striking, but unrealistic.

I don’t want to embrace or discard the feature, so I make it so the effect can be toggled off and on. Naturally enabling it causes a performance hit, but I can’t really appraise how bad it is until I get some of the more egregious slowdowns fixed and the overall performance optimized.

Cars

Now for cars. Since I have the lanes defined, I can just drop cars randomly onto lanes and let them figure out which way to go. They then select a speed and drive in a straight line until they get to the edge of the map, and then they randomly appear in a new location and repeat the process. The program draws a simple 2d panel at a car’s location. If the car is heading away, it draws it red, otherwise, white. This would look crazy if you were looking straight down on the scene, but up here in the News 5 chopper it looks okay.

I thought it might be cool to have the cars engage in more elaborate behavior. So I wrote a bunch of code to have them switch lanes if they find themselves behind a dawdler, and randomly make turns when they come to an intersection. I spent over an hour fussing with a couple of intersections and tuning the car behavior to make lane changes and cornering look natural. It was still a little stiff, but I was confident that with a bit more tuning I could make it work.

Then I pulled back to the city-wide view and found that all that work was almost completely unnoticeable. It was actually hard to spot a car doing something interesting. On the rare occasions where I was looking when a car made a turn, the robotic movement actually hurt the verisimilitude of the scene instead of helping. Both turns and lane changes actions are very complex. Turns are not linear. Cars decelerate before the turn, increase the rate of turn as they go, and begin to accelerate again before the turn is completed. This is aside from the fact that steering with the front wheels produces some fairly noticeable differences between the movement of headlights and taillights. Worse, the tiny bit of AI I’d written was slowing the program down. It was small and simple, but multiplied by hundreds and hundreds of cars it was causing a measurable performance hit.

So… I wasted a bunch of time writing code that slowed down the program and looked terrible when you noticed it at all.

Click & drag over text. Press delete.

This is a classic case of oversimulation. The programmer (me, in this case) sits down and thinks “oooh! I know how this system works, so I’ll write a simulation of it!” It’s a deadly trap, because once you start simulating one thing (cars changing lanes) then you suddenly need to simulate other things (making visually believable lane-changing movements for automobiles) which requires still other things (turning behavior of a car) and pretty soon you’re coding some sort of time-devouring boondoggle when all you wanted was to write a few simple rules about going around slow people.

John Carmack talked about this at Quakecon in 2004. (That article is long. The relevant passage is about halfway down.) During development of Doom 3, they had a programmer write a complex audio / acoustics engine that would try to propagate sounds realistically. It was supposed to make big rooms echo, dampen sounds in other areas, and so on. In the end, the result was worse than the simplistic system it was supposed to replace. It was actually easier to have artists manually specify how things ought to sound and how far particular sounds could travel than to have the game try to intuit it. They scrapped the audio simulation and replaced it with more conventional videogame sound behavior. Luckily for me, my losses were only a bit over an hour. Theirs was months. Then again, I might have incurred the worse losses as a percentage of total budget. (An hour and a half is about 5% of my budget, assuming I stick to it. (Although I’ve lost track of how many hours I’ve sunk into it. Weekends do that, particularly since I had a lot of Left 4 Dead mixed in with the coding hours. Still I’m going to take a wild guess and say I have perhaps three or four hours left before I hit my 30 hour goal. Maybe.))

Street-level detail

I pull back and assess the view now that all of the key details are in place, and I’m not happy with the result. I’d looked at a lot of reference pictures where the streets were pure black, and only streetlights and car lights were visible. But the same effect is not working here in my city. I look down in the blank areas between the buildings and I expect to see a street. The black void looks unnatural.

Looking at the reference photographs again, I realize that the “black street” effect is something you only get at extreme distances. Looking down from above, the streets are always brightly lit. As a test, I make a cheap texture map to slip under the city. It’s a single huge texture that just shows all of the streets. It’s of such low detail that a lane of traffic is just one pixel wide.

The street is awful, cheap, lo-res, and doesn’t even fit in with the buildings. And yet it still looks better than the pitch black. My original concept for the streets is unacceptable. I need to somehow depict the streets in this world.

Cheap, 1-pixel lanes, no lines on the road, no surface detail, nothing. But it still looks better than black.

But this is almost dragging us back to the problems that come with oversimulation. I wanted to just hint at the streets. The last thing I wanted was to draw the eye down there with a bunch of detail. Making streets that are illuminated is fundamentally different from my intent, which was to leave things in shadow and get by using smoke & mirrors. If I make a well-lit street, then this will draw the attention of the viewer. My light-source cars will no longer look right, because it won’t be black cars on a black background, it will be invisible cars on a light background. If I add little cars, then the user will probably notice that the streets are barren – no traffic lights, lines, or crosswalks. If I add all of that, then my high-detail streets will look out of place next to the silhouette buildings. If I add a bunch of storefront-type detail, then those blank areas around buildings will stand out more. What will I do then? Add little parks and parking lots?

This sounds like a lot of fun, actually, but adding all of that detail would obliterate my time budget. In fact, each of those elements could turn into a week-long project in itself, all to simulate something I did not want the user to see in the first place!

I need to think about this.

I think the next step should be to begin optimizing performance. I’m down to 30 frames a second (varies) at this point, and so this needs to be done. (Remember my budget is ~100 FPS.) Once I have that finished, I’ll know how many CPU / GPU cycles I have to waste on street details. And maybe I’ll get some good ideas in the meantime.

Shamus Young is a programmer, an author, and nearly a composer. He works on this site full time. If you'd like to support him, you can do so via Patreon or PayPal.