The Struggles of Developing StarCraft

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.

Comments

Teaching opportunity?

[theRunicBard]

This is so pefect for Computer Science courses! Someone might actually look up from their laptop at the lecture slides if this gets mentioned!

Re:Teaching opportunity?

[K. S. Kyosuke]

"How Not to Do Stuff 101"? Don't do memory management by hand, use functions to factor out common operations? Honestly, I'm surprised that something written in this way made its way out the software shop doors in a working state.

Re:Teaching opportunity?

[aintnostranger]

I'm surprised that something written in this way made its way out the software shop doors

ROFL. I think most software is like that, what surprises me is finding that some widely deployed software is well coded.

Re:Teaching opportunity?

[jones_supa]

"How Not to Do Stuff 101"?

Maybe. Lessons like that can be fruitful for education too.

Re:Teaching opportunity?

[neonKow]

"How Not to Do Stuff 101"? Don't do memory management by hand, use functions to factor out common operations? Honestly, I'm surprised that something written in this way made its way out the software shop doors in a working state.

How about "why not to do this," or "trade-offs of doing it like this," or "pitfalls of hacky solutions in big projects."

There is a lot more to teaching how to avoid mistakes than just a checklist of what not to do; you have to give students and understanding of why not to do things, and how to think through all the possible pitfalls that their design decisions will make. I'd would've definitely enjoyed learning good coding practices from one lecture based on real life-lessons learned.

Re:Teaching opportunity?

[Anonymous Coward]

There are people who are very good at what they do. They study, read books, perhaps do their own scientific research, they learn from mistakes and constantly try to improve not only themselves, but also people and company around them. But there are not many of these people. Not only does it require passion, it also requires experience and most often a little luck that you have met someone who taught you things.

Most people want to either do the minimum that is required or they simply lack of experience or knowledge that would be needed. In managers the numbers are even worse. Because of this great majority, it doesn't matter what kind of knowledge the humankind has, because it won't be used.

Thus demonstrating my assertion

[Chelloveck]

Thus demonstrating my long-time assertion (ever since my stint in the video game biz) that video game developers are crap programmers. No common routines to manipulate a heavily-used data structure? Not even a set of macros? This kind of story belongs over on The Daily WTF.

Re:Thus demonstrating my assertion

[Chris Mattern]

If you actually RTFA, you'll discover that this error was made by fresh-out-of-college newbie programmers working crunchtime with no supervision.

In other words, video game programmers.

Re:Thus demonstrating my assertion

[Lonewolf666]

Without experience on the job. And this is important. I remember my own university time as a nice source of theoretical knowledge, but things like good development practices were not a topic.
Of course, any halfway smart developer will eventually figure it out. But it may take one embarassing failure as a wake-up call. Tough luck (but maybe well deserved) for a company who only hired newbies and no experienced developers as team leaders.

Re:Thus demonstrating my assertion

[Anonymous Coward]

If you actually RTFA, you'll discover that this error was made by fresh-out-of-college newbie programmers working crunchtime with no supervision.

Fresh out of college newbie programmers that no one is mentoring? My college hires (well, my entire team, but especially my college hires) have every line of code they write code reviewed. Any more senior member of my team would have said "I don't sign off on this checkin until you use common routines for manipulating these data structures". And if they had signed off on it, I would have seen it, and then I would have asked the senior people who signed off on the checkins WTF?

This is a management failure, not a fresh out of college newbie programming failure.

Causation. Learn it. What really causes the crap?

[VortexCortex]

Thus demonstrating my long-time assertion (ever since my stint in the video game biz) that video game developers are crap programmers.

Broad Generalisations are almost always wrong. There are some game developers, especially those who have experience in other fields of software, which aren't "crap programmers". Video Games are some of the most hardware intensive programs, utilising every major feature and capability that the system supports. Sometimes it's acceptable to break the 'best practices' rules to get a little performance (if the profiler says it's warranted), but I agree there's no reason to be manually managing linked lists.

Sometimes a 'Lead' programmer will be the worst of them all, and the others must follow the bad example or be made an example of. Let's not lump all game programmers into the horrible coder pile. As you've pointed out, TDWTF has plenty of examples of nightmares from all sectors, not just video games. That the game developers allow studios to get away with "crunch time" consistently instead of firing the dumbasses in charge who purposefully gork the schedule is both a large source of bugs and proof we need a union or better work conditions at least. I can forgive crunch for one project. Maybe even two in a row... but every single game? Yeah, that's either abuse or incompetence. Either way, it's why I only buy (and work on) indie games now. They tend to have better working conditions, even if some of the beginners in the indie market churn out even worse code -- At least they have an excuse in not knowing any better; What's that say about the "pros"? That they're all crap programmers, or that the programmers are forced to write crap code? I put it to you that it's the latter, not the former.

Re:these days: STL and Boost

[CastrTroy]

Yeah, but starcraft was written ages ago. It was released in 1998. Which means they probably started coding it in 1996. Possibly earlier. It was probably based off code from Warcraft which was released in 1992. It wouldn't be a stretch to say a lot of the code is close to 20 years old. Granted, it still gives them no excluse for not writing their own library so they didn't access the data structures 100 different ways, but it's not like standard libraries were avaialble for a lot of this stuff back then.

Re:Horrible, awful inaccuracy in post.

[smellotron]

Please explain how a doubly linked list now makes add & remove O(1).

Suppose you have a collection of unit objects, and your main game loop involves iterating through each of them and performing some time-step (move, regenerate energy or health, cooldown weapons, etc.) Now at any point in the "simulation" that is an RTS game, a single unit decides/discovers that it must be deleted. If you are already iterating over units in a doubly-linked list, it is exactly 2 pointer operations for the unit to remove itself from the master list. If you had used a singly-linked list you would need to spend O(N) time searching for the previous unit.

Oh, and given that you're already iterating over every single unit in the game, you don't need the random lookup that a hashtable provides. Actually, you probably can't afford the lookup table unless it is already solving another problem for you. CPU cycles and cache footprints matter when you want to push the limits of the hardware.

Re:You had to have been there

[Anonymous Coward]

Quake most emphathetically needed a Pentium to run fine. This was because the rendering engine used a trick to do perspective corrected texture mapping, but the trick was not fast enough on anything lesser than a Pentium.

Still, I do not understand your point. Quake used QuakeC for in-game scripting (the movement/behavior of enemies was written in QuakeC and then compiled to bytecode, to be executed by the actual Quake game engine which was written in C/ASM). The entire game was *not* written in it.