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.
Not so hard (Score:5, Informative)
Re: (Score:1)
This article is about SC gaming development back in the 90s, the TC post is off topic and nothing to do with SC or the trials and errors it went through.
Re:Not so hard (Score:5, Funny)
There is no cow problem.
Re: (Score:2)
Hey, DRM is hard.
Yeah, DRM is hard, and Blizzard should be able to compensate its programmers for selling you DRM instead of giving their time away for free. Heck, they even package in a game as a bonus! This is partly sarcasm, because I do believe a portion of the higher prices we now pay are due to the waste of time (ours and theirs) that is DRM.
Re: (Score:2)
Bad code is a nightmare to debug (Score:2, Funny)
... congratulation... what a fresh piece of news !
Teaching opportunity? (Score:5, Insightful)
Re:Teaching opportunity? (Score:5, Insightful)
Re:Teaching opportunity? (Score:5, Insightful)
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? (Score:4, Insightful)
"How Not to Do Stuff 101"?
Maybe. Lessons like that can be fruitful for education too.
Re: (Score:2)
How? These kinds of issues are OLD. They have been talked about, discussed, studied, and explained to death.
At some point, you have to say, it's either the teachers or it's the students.
For this dll "problem", just using a macro fixes the problem while retaining maximum speed [no function call]. Unless they are doing stupid "I know I'm in the middle of the list, so no need to do nil checks" BS.
Re: (Score:2, Insightful)
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 kn
Re:Teaching opportunity? (Score:5, Insightful)
"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: (Score:3)
Yes, it's very context dependent. Too much architecture, and you "lasagna code" - so many layers it's impossible to understand. Not enough architecture, and you get "spagetti code". If you care too much about nice code, you get Haskell - beautiful by ultimately pretty useless. If you don't care about good code, you get Fortran - extremely useful, but so ugly no-one wants to modify it. (Yes, it's possible to write practical stuff in Haskell, and nice code in Fortran ... but it's rarely seen in the wild).
THANKS! (Score:2, Interesting)
Re: (Score:1, Funny)
Dude, No one, and I repeat NO ONE is going to ever suck your balls until you get out of your mom's basement, stop playing WoW 24/7 and give up the Cheeto habit.
Re:THANKS! (Score:4, Funny)
Huh. That's odd. The first time I had my balls sucked was in my mom's basement while playing WoW and eating Cheetos. That girl was awesome.
Re:THANKS! (Score:5, Funny)
Dude, the family dog doesn't count.
The largest source of Bugs in Starcraft? (Score:5, Funny)
Obviously the Zerg.
Re:The largest source of Bugs in Starcraft? (Score:4, Interesting)
Oh wait, I may have the wrong thing in mind...
Thus demonstrating my assertion (Score:5, Insightful)
Re: (Score:1)
yes, the fact that no programmer thought of writing general purpose list_add / list_remove functions is telling.
Re: (Score:1)
If you RTFA you would see that they had that at the beginning, scrapped it to increase the speed of save time and then realized their mistake too late to fix it for release date.
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).
Re: (Score:1)
In every situation where I have tried for this approach, one of two things happen:
1. A middle manager demonstrates the "working" software at the 6mos mark, see how much work we have done, and then the senior manager goes "Wow, that's great, lets drop the delivery date from 6 months from now to 2 months!"... and you end up running your ass off trying to get the last critical bugs out before they ship it .. and try to bring up anything and they say "Hey, we seen it working, it's ready!", argue and you'll be o
Re: (Score:2)
> and then the senior manager goes "Wow, that's great, lets drop the delivery date from 6 months from now to 2 months!"
Well, it is your job as developer (or actually, the project manager's job) to show the work plan you have and point out what has yet to be done. It is mostly a matter of education such folks, and of course, planning (you do develop and maintain a work plan, yeah?). Just because they are senior and a manager doesn't mean you can't patiently explain why they can't arbitrarily move dates
Re: (Score:1)
How do you write unit tests for a game? Or, less broadly, a physics solver? Reverse IK solver? Spawning algorithms? LOD level calculator? Frustum-culling? Shaders?
Re: (Score:2)
This does explain why they aren't making huge changes to HOTS, though, the code is so brittle it would be too hard, and break too many things.
It also explains why Blizzard takes so long to get games out the door....
Re: (Score:3)
[sarcasm]I'm glad that before you commented, you read any of the summary, or article, instead of just skimming the title and leaving a couple of snide comments.[/sarcasm]
This is StarCraft, the RTS game from 1998, not StarCraft II, the very modern game with a giant game engine. Games and code tended to be a bit more skeletal.
Re: (Score:2)
Re: (Score:2)
"Skeletal?" Is that what "crappy, hacked up code" is called now?
Re: (Score:2)
This is just ugly, horrid programming practice. I remember a project I worked on years ago that managed training documents with a built-in tree structure to the contents (1, 1.1, 1.2. 1.2.1, 1.2.1.1, etc.), and the first thing I did was write a library to manage a generic double-linked tree structure with a generic pointer to the actual content block, so I could use the same list manipulation functions for all the document types.
Re:Thus demonstrating my assertion (Score:5, Informative)
If you actually RTFA, you'll discover that this error was made by fresh-out-of-college newbie programmers working crunchtime with no supervision.
Re: (Score:2)
"fresh-out-of-college"
If it was an actual CS/IT course, and not, say, English Literature, then it's hardly an excuse.
Re:Thus demonstrating my assertion (Score:5, Insightful)
In other words, video game programmers.
Re:Thus demonstrating my assertion (Score:4, Insightful)
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: (Score:2)
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!)
Re: (Score:2)
Re: (Score:1)
Or, possibly, they're looking for people who code a lot in their spare time instead of only doing the programming required of them in their degree. Which is, by the way, not enough to be particularly useful without further training. I am someone who codes a lot in his spare time and, though I haven't graduated yet, the few employers I've worked at love me because I require very little training and can pull my weight even as a co-op/intern. I know one guy in my year who's being actively head-hunted thanks to
Re: (Score:2, Troll)
Or, possibly, they're looking for people who code a lot in their spare time instead of only doing the programming required of them in their degree
No, because as far as HR are concerned the 1000 hours of spare time you spent on your personal project don't count as experience in anything. If it's not for a company, it didn't happen.
Re: (Score:2)
Also they rewrote a linked list data structure out of need (or what they thought was a need) and not out of "hey let's write our own!"
Re: (Score:2, Insightful)
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
Causation. Learn it. What really causes the crap? (Score:5, Insightful)
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: (Score:2)
this was the 90s (Score:2)
associate hash maps were some exotic thing found in unversities. your main tools, turbo pascal and microsoft C++, had no such thing. you would have had to write the whole hashmap from scratch. considering they couldnt wrap their heads around writing linked list functions, i dont think a hash map would have worked out any better for them.
but people should remember the times. this was when a few MB of RAM was considered pretty damn good, dialup was normal, you went to something called a 'software store' to bu
Re: (Score:2)
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.
It's very common with programmers (Score:3)
I call it Smartest Motherfucker in the Universe Syndrome. You see it all the time on Slashdot: People who seem to think they are gods gift to development. They'll talk about how amazingly stupid Company X is for not doing thing Y, when it is clear they have NO idea of all the shit that would be involved in that. They berate others for bugs in code, yet their own code is bug ridden, and so on. They are just convinced they are WAY smarter than all those other dumb programmers (and IT people, and managers, etc
Re: (Score:3)
I find giving them a huge task with complicated data structures and having them fuck it up does wonders for their humility.
Re: (Score:2)
Here's an interesting data point that reinforces your statement. For a long time Sun Microsystems was considered to have the best assembly of engineers in IT (although their sales team was balkanized and not customer focussed, hence Sun's demise, but that is a different store). The Sun engineers knew it, and anyone who knew anything also knew it.
For a long time Sun was subject to 'Not Invented Here' (NIH) syndrome. Since they were the smartest whatever they didn't seem to look around much since they woul
Re: (Score:1)
Sun were far from the best. Even Unix in those days was not even viewed as the best, just "good enough".
There were plenty of other contenders with superior reliability and uptime - just more expensive and hence people bought Sun - since it was cheaper and good enough.
Re: (Score:3)
who don't even know what database indexes are.
Or people who kind of do and put them all over the place. Nothing says fun like a clustered index on a GUID with a default fill factor.
Re:Ignorance + Ego (Score:4, Informative)
Testify, brother!
My favorite SQL Prima donna was a guy that sr mgmt thought was a prodigy; they overrode our objections and put him solo on a project. Not knowing basic shit like normalization, his app hinged on queries that make my eyes to water just thinking about them a decade later: if QueryName matches name1 or name 2 or name 3 or name4, then again for every other advanced search field. The pinnacle was the advanced search query. It went on for a dozen pages, several just querying 8 wildcardable keywords against almost all columns. Since everything was one huge flat file of redundant columns, indexing couldn't save it. 'Find me commercial plumbers in zipcode X' often timed out after 10+ minutes and would peg one of 2 cpu's on the E450 we were using.
Two encounters like that bozo convinced me that Prima donnas are a project-killer sort of risk, even if (like code-smell) you sense the problem long before you can articulate the specifics. (NOTE: primadonna != smart or brilliant or savant).
Re: (Score:2)
primadonna != smart or brilliant or savant).
It also != one word [wikipedia.org]. Stick with words and phrases you know.
Re: (Score:2)
+5 Insightful, for basically trying to start a language-war? Really?
Good programmers are good programmers, and idiots are idiots, regardless of the language or framework they use.
Re: (Score:2)
Re: (Score:2)
Criminally Insane (Score:3)
I'm a scientist with a CS minor and some experience doing SW engineering (probably badly) on small projects. Even *I* know you abstract the actual storage and provide some simple accessor/insertion functions to prevent people from actually touching the storage implementation. For a couple of reasons: 1) to prevent goofballs from creating pointer messes, and 2) so that, if you want to, you can completely rip out the actual storage implementation and replace it without breaking anyone's code. I'm sure there are also reasons 3) - Eleventy, but those two are pretty obvious. Not to mention which, it only adds maybe a couple hours (if you're diligent and paranoid) over the short term, and probably saves weeks over the long term.
Not to mention which, aren't there standard libraries to do this stuff? Did STL not exist back then?
Re:Criminally Insane (Score:5, Informative)
STL was around, but C++ compilers were still shitty. You could get internal compiler errors or codegen problems if you tried to do anything complicated with types (like partial specialization). I also doubt that STL was taught in CS degrees then, you had to discover it existed yourself.
Re: (Score:1)
Even today, STL tends to be avoided in game programming. Most STL implementations are pretty well developed and tested these days, but a lot of senior developers are still burned from back when it wasn't. More importantly, there is a lot of need for control over how the memory is managed, especially in memory limited systems like consoles. Think static buffers and memory pools instead of new calls everywhere. STL doesn't (or at least since last I checked) work well within those guidelines.
Re: (Score:1)
You can use any allocator regime with STL - it's part of the standard. The allocator is specified in the container template type. The best reason not to use it was the 1996 era compiler errors for templates; 10-50 lines of template stack trace per error. God help anyone working on that, I don't know how the guy who wrote STLport survived.
Re: (Score:3)
Back then most compilers didn't even do templates. We're talking 1996- Borland was still one of the most popular compilers, and if it ever had templates it was the last version.
Re: (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 obje
Re: (Score:2)
You're absolutely right. But you have to account for ego. There are developers out there that just don't trust anything not written by them. These guys are self righteous know it alls, and they don't take well to criticism. Thus if you ever do get a chance to look at their code you quickly realize a few things:
1. No comments
2. Basic functionality is rewritten all over the place
3. They produce unnecessarily large sloc.
4. The code does not handle non go-path well, if at all.
5. Motherfuckers like poin
Re: (Score:1)
Re: (Score:1)
TFA part 2 : http://www.codeofhonor.com/blog/avoiding-game-crashes-related-to-linked-lists [codeofhonor.com]
The author suggests to ditch the STL in favor of "intrusive lists". In intrusive lists the links are part of the data structure. It breaks the data/container separation but provides many benefits in term of performance and reliability.
Re: (Score:2)
Macros I actually used extensively when I was in college, and wanted to use common data structures in C code. Of course I only knew about those macros because I knew people who were very involved in FreeBSD that told me about them. (Though writing common functions for linked-list implementations is something you kinda learn in FRESHMAN level CompSci classes.)
Re:these days: STL and Boost (Score:5, Insightful)
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: (Score:3)
Even 1998, Visual Studio had old STL headers which caused memory corruption, data loss, and crashes.
Apparently a legal dispute stopped them from providing STL updates for 6.0, and they pointed users at Dinkumware's site for manual patching. I think these were the same as the 1997 VC 5 STL, so problems around 1995-1998 with STL were to be expected.
It was developed privately and presented as a standard in 1993. HP's 1994 release was the basis for a lot of implementations.
There were bugs, and they were found
Re: (Score:1)
Re: (Score:2)
> "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."
Microsoft were famous for doing stuff like this. I remember some story about changing the bootloader for a 5% speed up when booting a 386 that hampered Windows for a few versions (since they needed to remain as backward compatible as they could all sorts of cruft hung around). This kind of thinking cost them a lot of headaches over the year
Re: (Score:2)
Re: (Score:2)
In the 1995, while working for Motorola, I was the assembly language geek asked to save 1 CPU cycle on a critical code loop that Sega promised a PPC console design win if we were able to succeed. The loop was only 16 lines of assembly code which their geeks felt was already maximally optimized based on their experience with an NEC chip. Later business considerations that were MGMT101 issues and not /. issues saw us lose the design win, but I was successful after about 3-4 hours (saved 2 clocks in the firs
A low UID means ... (Score:1, Insightful)
If only you had a 5 digit UID to lend any credence to your history in the industry.
A low UID means that you know about slashdot a long time ago. It does not mean a damn thing on any other topic.
The GP has point. There was a balance, even in the mid to late 90s. The GGP overstates things, if you were worried about the overhead of calling a common function you made that function an inline or macro. And the fact that my current slashdot account has a 7 digit UID in no way changes the fact that I actually worked on Starcraft and know Pat Wyatt and his partner in crime Mike O'Brien.
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2, Insightful)
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.
Class Hierarchy (Score:2)
CUnit In case you couldn't tell, a CThingy is a sprite that can be drawn, a CFLigny is some kind of particle engine, a CDoodad/CUnit is some artificial separation of concerns. This is in SC1, btw.
Re: (Score:2)
I never understood the practical purpose of prepending a "C" to each of your class names.
Today, it serves a very useful purpose: It unambiguously identifies a 1990s-era Microsoftie who can't change his ways.
Re: (Score:2)
really? (Score:2)
Blizzard was never any good when it came to programming. Their games are always extremely slow, so you can tell in the back the code is doing some pretty funky inefficient stuff, and the bugs are a glimpse at the underlying spaghetti code. Blizzard's coding should be taught in classes as: What not to do. They're still horrible programmers: UT3 renders ultra-realistic scenes 60fps flawlessly with all the settings on max, while Diablo 3 struggles to draw some top-down view... and that's just the optimization!
Re: (Score:2)
hmm (Score:1)
Horrible, awful inaccuracy in post. (Score:1)
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).
Please explain how a doubly linked list now makes add & remove O(1). The rest of us shlums have been relying on hashtables when we needed O(1) and assumed linked lists of any variety were always going to be O(n) at best...
Re:Horrible, awful inaccuracy in post. (Score:4, Insightful)
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: (Score:2)
Your assumption is you already have the item you want to remove. The quote was "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".
Of course you can write code to be efficient with a list if you are not searching the list, and if you have a reference to a node without any context to the traversal, a doubly linked list is a good idea. But your explanation was a speci
Unit limit (Score:2)
With twice the number of units of its predecessor — StarCraft had a maximum of 1600...
Nope. Starcraft's unit limit is 1700.
Re: (Score:2)
Re:Slashdot and Wikipedia are for fags. (Score:5, Funny)
Re: (Score:2)
Wait a second - did you just try to troll fans of a 15-year-old game? For your next trick, maybe you can jump into the Genesis-vs-SNES wars, or go political and claim that Dole's going to kick Clinton's ass?
Re: (Score:1)
Never heard of it.