Tough times on the road to Starcraft

http://www.codeofhonor.com/blog/tough-times-on-the-road-to-starcraft

by phenylene • 14 years ago

360 68 14 years ago

Interesting to see how you feel bad about shortcuts you make at the beginning of a project to save time, and later regret them wishing you had done it 'right' to begin with. However the cost of doing it right at the beginning sometimes is greater than the difficulty of hacking to the finish line at the end.

chrischen• 14 years ago

There is no finish line.

nostrademons• 14 years ago

Yeah, the problem is that software projects always take 10x as long as you expect them to, so when you think you are 90% of the way there, it's more like you're 9%. If you know that you are only 9% of the way there, you will develop in a very different way than if you think you are 90% there, preferring long-term code health over quick hacks. (This in turn might shorten the total project so that you're 20% of the way there, but you can't count on that, because if you start assuming it you'll get careless and lose the benefit of long-term thinking.)

kennywinker• 14 years ago

I wish to know more about the "voice-to-phoneme" compressor he mentions. Anyone have any links handy? Google is failing me.

polemic• 14 years ago

Yeah, how cool would that have been. If you could do a JS port, you could you use that to build a super lightweight Skype clone :D (audio capture from Flash, or Mozillas audio capture..)?

grimboy2• 14 years ago

http://en.wikipedia.org/wiki/WebRTC

rcthompson• 14 years ago

Random google search for "phoneme compression" turns up this patent: http://www.google.com/patents/US6789066

It sounds to me like you build a library of common sounds that voices make (these are the phonemes), and then you use just combinations of these phonemes at specific times and volumes to get as close to the target waveform as possible. Then you store the sequence of phonemes, which is probably a triplet of integers (phoneme ID, timestamp, volume level), along with a waveform representing the difference between your phoneme-generated waveform and the original. You compress both of them. Since the difference is much smaller than the original waveform, you save lots of space.

deathhand• 14 years ago

I never knew the importance of Storm.dll but now it makes sense on why it was always corrupted.

jimrandomh• 14 years ago

The main takeaway I got from this article is don't mix data structures and application logic. This matches my experience; complex data structures work fine if all the operations performed on them are in one place where they can be unit tested (or at least carefully inspected), but it works very badly if they're scattered or mixed with other things.

latimer• 14 years ago

Really interesting read. He mentioned that he'd talk more about the pathing in another post. I hope it will explain something I've always wondered about which is why the dragoon pathing/AI was not so good compared to other units.

nialo• 14 years ago

I think the explanation is actually pretty simple: because of the combination of how they had to break the tiles up into smaller tiles and the dragoon's relatively large size. The AI imagines it can get through spaces it can't, or a gap turns out to be filled with other units, or similar.

(disclaimer: I'm just guessing, no inside knowledge. certainly feels right though)

netcoyote3• 14 years ago

[note: I wrote the StarCraft article]

You're right -- it was related to the size of the units. Because they were larger they needed to find wider paths that weren't obstructed by terrain or other game units.

TeMPOraL• 14 years ago

I always felt that Goliaths were significantly dumber. There was also a funny glitch we discovered with friends - they could shoot from a greater distance than they thought they could, ie. at some point[1] if you ordered them to attack enemy Sunken Colony, they would come within it's attack range, but if you stopped them (via button Stop, or Hold Position) just outside Sunken Colony's firing range, they would start shooting to it anyway. I abused this quite a lot on my friend back then ;).

PS. I'll never forgive the patch 1.13e. It removed the most amazing bug ever, that allowed to turn StarCraft upside down via specially prepared maps (think units changing weapons on demand, or terrain morphing at realtime). People were doing amazing things with it... for about two weeks that went between discovery and the beforementioned patch.

[1] - this was long time ago, I think around patch 1.11.

jmtame• 14 years ago

One thing I always think about is how the code works behind games like Starcraft. I find myself trying to understand the data structures and algorithms behind seemingly simple mechanisms like creep spreading or revealing the fog of war. Are there any other writings like this that talk about the technical side of popular games?

netcoyote3• 14 years ago

Gamasutra has some good articles; check out http://www.gamasutra.com/category/programming.

Here's a good one: http://www.gamasutra.com/view/feature/3094/1500_archers_on_a.... It talks in detail about the network code and unit synchronization logic used for Age of Empires, which is more or less the same as that used by Warcraft and StarCraft.

cpeterso2• 14 years ago

Here are some game tech articles that I found interesting:

* Fixing Pathfinding Once and For All: http://www.ai-blog.net/archives/000152.html

* Scenegraphs: Past, Present, and Future: http://www.realityprime.com/articles/scenegraphs-past-presen...

* Evolve Your Hierarchy: Refactoring Game Entities with Components: http://cowboyprogramming.com/2007/01/05/evolve-your-heirachy...

Too• 14 years ago

Evolve your hierarchy is a really good read for everybody, not only game programmers. It shows in a very convincing way why the classic Cat : Animal inheritance model taught in every Java-school doesn't work when things scale up and proposes a better alternative.

steve89183• 14 years ago

I acknowledge Starcraft's dominance, but my personal favorite game of all time was Total Annihilation. At the time (98/99), it was probably the most advanced game out there. I played my cousin across the country over 33kps modem, and we each had 500 units moving around at the same time. With 1000 units total, each 3D rendered, the action slowed down a lot, but it never crashed, and allowed us to play entire games across the country reliably. It was truly a feat of software engineering.

Chris Taylor (the creator of TA) came out with Supreme Commander in 2007, which I bought a new computer for just to play, but I only played it for a few months, more because I got busy rather than not enjoying the game. But both games never seemed to catch on as much as Starcraft 1 and 2 have. I'm seriously considering picking up Starcraft 2 but it's already 2 years old, so I think I probably missed the boat.

ericdykstra• 14 years ago

...And I was the guy that played the turned based Lords of the Realm II for some reason.

Anyway, Starcraft 2 is still pretty active on the casual side, and with the new expansion coming out later this year (already in public, but not open, beta) it will surely drive a flock of new players. On the note of Supreme Commander, one of the top players of that game has been a Starcraft 2 pro since beta (TheLittleOne, aka TLO).

ricardobeat• 14 years ago

Hey, I played - along with my father - LOTR II too, it was nice :) I still have some memory of the soundtrack and effects, maybe the best part of that title.

I still miss something like Commandos: Behind Enemy Lines, that was a surprisingly great game.

steve89183• 14 years ago

I have to say that I do prefer RTS, my first one being Ancient Art of War waaaaay back :)

However, I did get in my share of turn-based games. I remember when I first played Civilization, it was over Christmas break during college, and I didn't go home because it was too expensive. I ended up playing Civ for 3 days straight, and my Christmas dinner was toast, 6 boiled eggs and peanuts... whatever I could rustle up quickly without taking too much time away from the game.

meric• 14 years ago

I remember playing Lords of the Realm 1 on a Win3.1 laptop my aunt gave me in 2004. The combination of RTS and TBS is awesome. Today I am into the Total War series, the latest being Shogun 2.

I love Starcraft 2 as well, and play it occasionally. In Starcraft however you're forever stuck in skirmish mode; there's no possibility of conquering a whole country in a very long campaign like in Total War or Lords of the Realm, and developing your nation into an economic powerhouse on the way there.

beefsack• 14 years ago

If you haven't seen it yet, you'd probably be very interested in Planetary Annihilation (http://www.kickstarter.com/projects/659943965/planetary-anni...) which is being made by a significant portion of the original TA and SupCom teams.

steve89183• 14 years ago

Wow, thanks for that link, it looks amazing! This might be the first Kickstarter campaign I might contribute too...

suby• 14 years ago

You can play a starter version of SC2 for free, if you're interested. It lets you play online against others, but you're only allowed to play as Terran, and you're not allowed to play ranked matches, only custom games. You might have a hard time finding people to play against if they haven't updated the map list from the link below, but I suspect they have. Worth checking out if you think you might be interested.

http://us.battle.net/sc2/en/blog/3250656

As for missing the boat, a lot of people still play SC2. They're going to be coming out with an expansion soon, so the game should see an influx of new players when that happens.

Macha• 14 years ago

No, the starter edition map pool has been unchanged since its announcement.

FredBrach• 14 years ago

The famous TotalA soundtrack is here: http://www.youtube.com/watch?v=BxAdOQtAFEs

jiggy2011• 14 years ago

Whenever I've seen clips of Starcraft / Starcraft 2 played at a high level it looks a lot more like an action game than strategy.

I see a lot of "micro" (or clicking really quickly to move a unit into range to fire but then out of range of the enemy unit's retaliation).

Supreme Commander 2 seems to have moved somewhat in this direction too, most of the online games I have played are on quite small maps.

I guess this is because big scale strategy games just take too long to play and people just don't have the time.

As an extreme example of this , I remember some years ago when I shared a house with some avid gamers who were into Heroes of might and magic. I remember two of them took a week of work and played a single game of HOMM (4 or 5 , can't remember which) for the entire week and still weren't done by then end. Bearing in mind this was playing for around 16 hours a day for 7 days straight. So 112 hours in a single game.

I don't think I've ever seen a finished game of HOMM in my life.

marshray5• 14 years ago

Whenever I've seen clips of Starcraft / Starcraft 2 played at a high level it looks a lot more like an action game than strategy.

That's because the high-level strategy is invisible until you understand it. It's things like subtle variations in build order, timing, unit and expansion placement, etc.

Search YouTube for Day[9]'s screencasts, watch a few, and notice how many there are. SC2 is a very deep and difficult game. Even if you're really good with fast action and micro, you won't get far without a good strategy to match.

baq• 14 years ago

check out the open source Spring engine: http://springrts.com/. it started as a full 3d implementation of TA. now it has it's own games, but some are heavily inspired by the original.

wavesounds• 14 years ago

I really like this article. I think the dynamic involved in working tons of hours on a project like this is really interesting. On one hand you have peer pressure and pride in your work. And on the other you have code degradation with lack of sleep. I wonder if he feels becoming a VP of Blizzard had to do with or was in spite of the long hours.

suresk• 14 years ago

Interesting read. Reading articles like this makes me wish the sources to some of those older RTSes (Starcraft, Warcraft, Age of Empires) were available to look at - I'm sure there'd be some interesting stuff in there.

grimboy2• 14 years ago

Looks like this is as close as you'll get for now: http://bazaar.launchpad.net/~stratagus/stratagus/trunk/files...

ETA: Just remembered. They open source 7 Kingdoms a few years back so you can find out what the code from a commercial RTS looks like. http://www.7kfans.com/wiki/index.php/Download

rurounijones• 14 years ago

MechCommander 2 source also available: http://www.microsoft.com/en-gb/download/details.aspx?id=1145...

pixie_• 14 years ago

Great read. I've been there. Write an awesome code base to have someone come along to replace it all with crap.

soup10• 14 years ago

Are AAA games still coded like this? Where you hack your way to the finish line. Or is there more process and things like code reviews?

chipsy• 14 years ago

The 90s represented a period of growing pains where the industry was scaling its budgets and team sizes very quickly and, for the most part, didn't have any processes in place to deal with scale or to maintain a codebase for the long term - why would they, when up until that point, games usually shipped within a year or less, and the technology changed with almost every project?

Today the picture is still varied, but engineering practices have generally improved - for example, daily standups are popular with many studios now, there's a corpus of books and lectures about how to architect an engine or various subsystems, etc. A lot of today's commonplace material was being put into production for the first time then, and was previously only known in some other context - research, high-end graphics and simulation, etc.

In current AAA the bottlenecks mostly lie with the art and design teams. Programmers still have plenty to do, but they're also quite frequently building on old technology that has some roots in the 90s - which entails a whole different set of problems.

NickPollard2• 14 years ago

Things are better now, though certain elements are still present. There's a lot of code churn in games - once a project is finished, unless you're making an immediate sequal it's not uncommon for almost the entire code-base to be thrown out and to start again for the next project. Most games are rather fire-and-forget affairs (with maybe a couple of DLC/patches) so maintainability isn't as high a priority as with a lot of other software.

Also the performance constraints make a lot of modern techniques difficult or impossible to use - so you do get a lot of hand-rolled code for things that could be library functions, just because it's a bit faster in a critical game loop.

The timelines of game development do lead to things being a bit rushed, and with how much a game can change during development the programmers are often forced to cut corners. On the projects I've worked with I always here at least a few programmers at the end saying "I wish I had time to do this properly, I worked out a great plan for the system, but we didn't have time".

That said, engineering practices and management are definitely better - Code reviews are pretty standard now, most studios are better at training and documenting.

pandaman• 14 years ago

Pretty much. I'd not say the SC is even bad - I've seen much worse projects with much bigger budgets. "Enterprise" process would be outlandishly expensive considering the amounts of code and requirements (millions LOCs, running in tight time and memory constraints for hours without crashing or even glitching, even on PC you would not want the user to lose several hours of progress to a crash, on conoles you just cannot release).

reitzensteinm• 14 years ago

The part about hand maintained lists is a common pitfall in game development. When you're trying to push out frames at 60fps, you generally need to be caching quite a lot of values, for example, "Get all units that are moving" or "Get all units from side x".

The absolute best way to handle this is to start off with safe, conservative functions, that don't cache at all - create a list, iterate over each entity, add whatever fits the condition.

Then, after profiling to see what's slow, you hand roll a system that keeps a specific list updated continuously; and then importantly, keep around the old function, and in debug mode compare the lists occasionally (I usually do it every 100th access, so the game is still playable).

After that, you may not know what's causing a cached value to go out of sync, but you can at least know it's happening, instead of getting some of the most convoluted and maddening bugs imaginable. The kind that make you want to take up farming (and I'd be a shitty farmer).

marshray5• 14 years ago

The part about hand maintained lists is a common pitfall in game development.

Whenever I hear something about hand-maintained data structures I think probably some manager or lead programmer banned C++ templates and other abstraction mechanisms because they were "too tricky and hard to understand".

Peaker3• 14 years ago

Standard templated linked lists are suboptimal. Simple C lists ala Linux's list.h are simpler and more optimal, behavior-wise.

Daniel_Newby2• 14 years ago

What am I missing about path finding? A simple filter on the nearest neighbors can weed out paths that are too narrow, then Dijkstra's algorithm can find the path. After you find a path the first time, it can seed subsequent rounds for efficiency. So what am I not seeing?

NickPollard2• 14 years ago

The biggest problem in games is the number of units - you might send 12 units through a narrow pass, and the game needs to have the units go through smoothly without blocking each other too much. From what I remember, the shipped version of Starcraft still had problems where you'd send a group somewhere, they'd get a little bit stuck going through, and one or two units at the back would then re-path to a really convoluted round-trip rather than just waiting half a second then continuing their original path.

Daniel_Newby2• 14 years ago

Ah. Thanks.

kzrdude• 14 years ago

The bigger units like dragoons and goliaths were notorious for stupid behavior in groups.. so it was never really resolved, and became a feature that progamers had to deal with.

d0m• 14 years ago

" I plan to write more about path-finding in StarCraft because there are lots interesting technical and design bits."

Please, please do so. I find these articles so interesting.. I'm a Warcraft/Starcraft/Starcraft2 fan and love to see the engineering part of them. Thanks for writing these articles.

Evbn2• 14 years ago

Why is isometric pathfinding different from square tile pathfinding? Isometrics is a UI issue, it is still a square grid. Because each tile had non constant terrain? But that just seems unrelated to isometricity.

jongraehl• 14 years ago

The article describes a scenario where the map editor deals with isometric tiles, but something compiles them into square tiles.

I think they would have wanted a pathing graph finer than the full isometric tile anyway. I don't understand how much additional, wasteful pathing computation resulted from the engine actually using square tiles either.

j-kidd• 14 years ago

The perpetual 2 months deadline is interesting. Is it because 1 month is definitely too short, while 3 months will invoke the wrath of Boss? I think a 2 months period hits the sweet spot where developers feel like they can get a lot done, without noticeably impacting the schedule.

danbmil99• 14 years ago

TL; DR: C++ really sucked back then

TimJRobinson• 14 years ago

It's been a while since I coded in C and I'm confused as to how you made a double linked list that can read in O(1) time. Wikipedia has a page in it but even that says it takes O(n) time, does anyone have an example or tutorial on how this is implemented?

zenlikethat• 14 years ago

In the article he says:

"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)."

It seems the implication is that one is parsing over the list already. When parsing over the list, if you do a comparison that indicates the node should be removed (i.e. if the unit's health is below 0), you do not have to traverse back through the list again from the beginning to get the relevant pointer from the node before the current element in the list, since you already have the pointer to the previous node in the current node. Likewise for insertion.

But I don't think, strictly speaking, it's possible to have a linked list that actually has a lookup time of O(n) .

Kelliot• 14 years ago

'so Blizzard wouldn’t have a long gap between game launches.'

You've already lost me

Tough times on the road to Starcraft

Related Stories