The Struggles of Developing StarCraft 135
An anonymous reader writes "Patrick Wyatt led production efforts for several of Blizzard Entertainment's early games, including Warcraft 1 & 2 and StarCraft. Wyatt has just published an in-depth look at the development of StarCraft, highlighting many of the problems the team encountered, and several of the hacks they came to later regret. Quoting: 'Given all the issues working against the team, you might think it was hard to identify a single large source of bugs, but based on my experiences the biggest problems in StarCraft related to the use of doubly-linked linked lists. Linked lists were used extensively in the engine to track units with shared behavior. With twice the number of units of its predecessor — StarCraft had a maximum of 1600, up from 800 in Warcraft 2 — it became essential to optimize the search for units of specific types by keeping them linked together in lists. ... All of these lists were doubly-linked to make it possible to add and remove elements from the list in constant time — O(1) — without the necessity to traverse the list looking for the element to remove — O(N). Unfortunately, each list was 'hand-maintained' — there were no shared functions to link and unlink elements from these lists; programmers just manually inlined the link and unlink behavior anywhere it was required. And hand-rolled code is far more error-prone than simply using a routine that's already been debugged. ... So the game would blow up all the time. All the time.'"
Wyatt also has a couple interesting posts about the making of Warcraft 1.
THANKS! (Score:2, Interesting)
Ignorance + Ego (Score:5, Interesting)
There are certain types of software development that seem to attract people who have a combination of significant ignorance and huge egos. Game development is one such field, and Ruby on Rails web development is another.
These people often are quite young, and as a result of this often have little to no academic background or formal training of any sort. Although they're quite ignorant, they don't realize this fact. This prevents them from keeping their egos in check, which in turn makes them think they know everything. Believing that they're all-knowing, they never both to seek further education or investigate alternatives, and continue to make the same mistakes over and over.
Having worked in both the game development industry and doing web development more recently, I do have to say that the RoR programmers are much worse than the game programmers. At least the game programmers usually have some understanding of algorithms, and many have a solid understand of mathematics, even if it's all self-taught. Compare this to the RoR programmers, many of whom refuse to learn about databases, even though they're generally developing database-driven applications. You wouldn't believe how many times I've encountered people like this who don't know any SQL, and who don't even know what database indexes are.
Re:The largest source of Bugs in Starcraft? (Score:4, Interesting)
Oh wait, I may have the wrong thing in mind...
Re:Thus demonstrating my assertion (Score:5, Interesting)
Funny you should mention this. I just returned from a job fair at a major university where we were interviewing and hiring programmers. Yes, the new grads tend to be pretty green, but some of them are really good. It's not terribly hard to separate those who may just lack experience but who grok the fundamentals from those who really need to reconsider the last four years of their lives. I actually talked with seniors in CS who couldn't describe the difference between a queue and a stack.
As for the article specifically... Yes, they had "fresh-out-of-college newbie programmers working crunchtime with no supervision". Hired by programmers who were themselves once "fresh-out-of-college newbie programmers working crunchtime with no supervision". It's a self-perpetuating cycle that is really prevalent in the games industry. (Or at least was prevalent at the time this story takes place, which is roughly the same era in which I was a games programmer. Thankfully I got out. That scene is nuts!)
You had to have been there (Score:5, Interesting)
I was working 'down the street' if you will at the time, as a programmer on one of their direct competitors (Age of Empires), and it's easy to forget the circumstances we all were working under at the time.
People weren't using Templates in games for a couple of reasons - Familiarity being one, but the state of the code was new, and especially the asm outputted by compilers was often very inefficient which it was not outright BUGGY if you pushed it. Templates were still very new then.
Also, you tend to forget how slow and limited PCs were then -- Your phone today probably runs circles around not just the machines that games were run on, but the PCs used to develop them.
The System Specifications "On the Box " for Starcraft were - A Pentium 90 (or equivalent - that could be a 486-133) , 16MB of RAM and Windows 95 or NT 4.0, and a SVGA video card with 512kb or 1MB of VRAM. Think about that for a minute. These were 2d video cards, not 3D. Age had almost identical specs. A full rebuild of AoE on our Dev machines (Pentium Pro) took 15-20 minutes to make.
It was very normal to worry about saving 2 bytes, or just a few cycles of CPU time back then. So you did everything bespoke by hand, and didn't genericsize much.
And to be honest. We didn't know then what we know now. The programming practices most of my peers just do automatically today -- we hadn't developed/learned them yet. We did what we could with what we had in knowledge and tools, and shipped complete AAA games for costs in man-hours and dollars that seem ludicrously small today.
Don't get me wrong, Besides being a lot of work, It was a lot of fun too. One thing I remember was our companies putting each other on the Beta Test list for our upcoming games.
Re:Criminally Insane (Score:2, Interesting)
Game devs were using Wacom C compiler. C++ wasn't even used much, never mind templates. You had actions overloaded like,
struct object;
typedef void (*action_func)(struct object *);
struct object{
[object data here]
action_func action; /* THIS HOLDS YOUR "AI" */
struct object *next;
struct object *prev;
};
Of course, most devs would abstract insertion and removal and moving functions of data from such an object linked list.
I suspect more errors occurred when the object was removed from one list, but ended up still live in another list. That was the hack. First the object existed in one area, but they needed another list to cut cycles, so they reused pointers and ended up with using deleted memory.
The cause of this is not simply "crap programming", but crappy design. Or perhaps "moving target" during development.
Re:Thus demonstrating my assertion (Score:5, Interesting)
> "scrapped it to increase the speed of save time"
That seems to be a real flaw in the mindset of games (and system) developers. They put in all these hacks thinking it'll shave off little slivers of execution time and overall make big savings when it is not the most significant impact on the assembled system. The time savings are usually negligible compared to bigger optimizations you can do later (using a profiler) and the development time increases (meaning you don't have time to run the profiler since you are too busy hunting down dumb bugs). As the great Don Knuth joked, "Premature optimization is the root of all evil".
If you are a developer on these forums bragging how you used some trick to save a sliver of time it would be good to take note of this StarCraft experience - since more experienced devs simply roll their eyes when they hear such talk (recognizing such development practices as n00b traps, which we probably were tempted by ourselves at some point in the past). Write the program to be correct first (usually means the most straightforward efficient implementation, rather than the absolutely fastest implementation, should be used). Then, you can refactor (you *are* writing unit/integration tests, aren't you?) to get more efficient, all the while guided by your profiler to prioritize the development time you have remaining.
nb: the best speed-ups are almost always algorithmic. Code hacks are minor. For example, by sitting down for several hours with a pencil, paper, and google I was able to analytically work out the optical transmission of a multi-band (eg. RGB) light source through and exponential density decay atmosphere using Mie and Rayleigh scattering into a simple analytic expression (for direct and single-scattered illumination) rather than use the integration that many other people use (eg. as published). This allowed me to implement the algorithm in a GLSL shader in real-time and saved on precious Video RAM (eg. no need to precompute and store the integral). Sure, other people have done this too, but my point is that the big speed up for me was to sit down and think rather than make minor code twiddles. Unfortunately, you need to be a good mathematician (using basic calculus and geometry in my case) rather than just a good coder to do this (which I guess may be hard for the poor young schleps that games companies hire and burn out).