Tough Times on the Road to StarCraft

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

by striking • 12 years ago

165 63 12 years ago

codeofhonor.com

zzleeper• 12 years ago

Not that it's not interesting, but a [2012] next to the title would have been helpful

angersock• 12 years ago

Not really, as the article is covering a project near 20 years old.

Who gives a shit when it was written?

AdeptusAquinas2• 12 years ago

Very interesting article, if horrifying :)

As someone whose only experience is in corporate service IT development, from the outside the game dev industry looks incredibly cowboy-ish; it would be nice to read a story where a team built a game where they met their deadlines, had no crunch times, followed excellent coding standards (CI, unit tests, peer dev etc.) and maybe even used a modern language (perhaps, heretically, a non-native language like C#!)

blister• 12 years ago

Take a look at the Serious Games/MilSim arena. A lot of companies in this space have standardized behind Unity3d (C# based) or as mods for existing engines like VBS2/3. Most of this work is done under government contract and has a fixed period of performance (often 18 months or less).

We often crank out several great games a year on time and under budget. There's a lot of cool stuff going on in this industry right now.

starmole2• 12 years ago

Interesting perspective! You bring up a lot of different points:

- There are tons of positive "post mortem" [http://www.gamasutra.com/features/postmortem/] write ups on gamasutra, but the ones with problems are usually more valuable. One recent example of "doing it right" I remember was the XCOM:Enemy Unknown remake. Check their GDC talks!

- One thing that makes games special is pushing the envelope. Yes, you can make a game on a very solid stack. But it won't stand out.

- Game coders think service people are mad also: How can you use a database that you do not fully understand? You don't even have the source? Using a framework or library or cloud that you do not 100% understand seems "cowboy" to them.

- Games are "fire and forget". That means technical debt is very different. It is bad at the start of a 3 year cycle, but at the end it is totally ok.

- Not mentioned by you but important to point out: While working on games is great for learning and unlike anything else it is also a terrible industry for coders. Insane crunch time. Low pay.

ido2• 12 years ago

    - Games are "fire and forget". That means technical debt
    is very different. It is bad at the start of a 3 year
    cycle, but at the end it is totally ok.

There is also a big difference between AAA, online, mobile, social, casual, etc. f2p games for example are expected to live & be actively supported/updated for many years if successful.

Clash of Clans was released 2.5 years ago and will likely continue to get active support for many more years. FarmVille was released almost 5 years ago. WoW more than 10, for a different kind of game that also isn't fire and forget.

They get a lot of flack for other reasons but engineering wise companies like zynga get a lot of stuff right.

gaius3• 12 years ago

One thing that makes games special is pushing the envelope. Yes, you can make a game on a very solid stack. But it won't stand out.

I know what you're saying, but I wonder how true that is, and my analogy is the movie and music industries. You can make a very successful movie or album without pushing any technical envelopes, infact there are people who consciously and deliberately use "obsolete" tools and techniques.

frik2• 12 years ago

Game coders think service people are mad also: How can you use a database that you do not fully understand? You don't even have the source? Using a framework or library or cloud that you do not 100% understand seems "cowboy" to them.

Not to mention widely used on-premise enterprise software with weird upgrade-paths and hidden costs. If you look behind the curtain there is a lot of legacy cruft in COTS. Customizing such installations seems cowboy-ish to others. SaaS/cloud is better and hide ugly details but may off limits for high confidential data.

Game programmers often reinvent the wheel but learn from others through post mortems (former Game Developer Magazin). Enterprise devs often cook their own customized solution based on COTS. You can still install and play almost all PC games on modern hardware with Win 7+ 64-bit. Try that with old SharePoint, Exchange, SAP, Oracle/Sun, Novell, etc. software and not to mention the troubles to restore an old backup.

As someone who saw both camps, I would say both sides can learn from the other side.

icebraining• 12 years ago

Game coders think service people are mad also: How can you use a database that you do not fully understand? You don't even have the source? Using a framework or library or cloud that you do not 100% understand seems "cowboy" to them.

Is that really true? When a team uses an engine licensed from another company, do they really take the time to fully understand its source?

Teckla• 12 years ago

- Games are "fire and forget". That means technical debt is very different. It is bad at the start of a 3 year cycle, but at the end it is totally ok.

Game companies don't "copy and paste" old versions of games to jump start the development on new versions of games? cp doom1.c doom2.c

ido2• 12 years ago

Please realize the story takes place almost 20 years ago! Things have improved a lot since then (in game dev specifically as well as in software dev in general).

There are still a lot of fucked up companies but you generally just don't hear about the development of >99% of projects.

soup10• 12 years ago

Ironically the horrible path finding gave the game much of it's charm and interesting micro mechanics. The default attack move would cause the units to converge into a single file march... which is suicide against a grouped enemy or defended position.

EvanAnderson• 12 years ago

Prior discussion: https://news.ycombinator.com/item?id=4491216

jokoon3• 12 years ago

What's the point of using linked lists ? Low memory ? I'll never understand why the usage of linked lists is so common.

I mean you don't have fast random access with linked list, aren't hash maps just better for fast insertion/deletion ? Object pools are also pretty great too.

I'll never forget the day a classmate in some game programming school argued that linked list were like vectors (std::vector).

Linked lists only seems viable for insertions, they're not viable for fast deletion since you need to search for the pointer first. Maybe you need to index linked lists instead, but since the heap already allows itself to be fragmented like a linked list can, wouldn't it be better to just use vectors as often as possible so it can be more cache friendly ?

maxerickson• 12 years ago

In a game, I would think most deletions would start from the node being deleted.

flohofwoe4• 12 years ago

(Intrusive) lists were useful when the cost of a memory access didn't matter relative to CPU speed, so that cache thrashing wasn't an issue, and you had a scenario where list nodes had to be inserted and removed frequently, but you don't need random access. In C such intrusive lists are also easier to manage since you don't need to care about dynamic memory management since the list nodes are embedded in some other existing data structure.

Today where avoiding cache misses is the most important optimization, traditional lists have indeed become quite useless, especially the non-intrusive type like std::list.

flohofwoe4• 12 years ago

...but I think linked list were not the main problem, but (1) use of inheritance instead of composition to implement unit behaviour (but we all walked into that trap, and these were the 90's when OOP was still hip and universally seen as a silver bullet), and (2) it looks like objects have been linked to each other quite ad-hoc, instead of providing some sort of 'object relationship system' which encapsulates object linkage and querying for objects. But as I said, these were the 90's and game developers have learned from these mistakes. There's a lot of good whitepapers around about entity component systems, composition, high-level architecture of games and so on. Today it's more about asset creation pipelines and production tools, at least for 'big' game projects.

corysama• 12 years ago

Remember that this code was written a long time ago. It is seriously only recently that I have seen widespread discussion about how poorly linked lists perform in practice despite how theoretically nice they are.

Back in the olden days at least a few things were different compared to today: 1) your only point of reference and authority was academic writing that stressed theory over practice. Blogs weren't around yet. So, you didn't have any random blogs with hard measurements showing that in practice brute force often wins over elegance. 2) Back then, the memory/ALU gap wasn't quite as drastic as it is today. 3) Available memory was drastically smaller than it is today.

Therefore, if you had a list with a length that was highly variable, the obvious go-to container was a linked list. The idea of using an dynamic array of objects or pointers seemed highly wasteful from a memory fragmentation and copying point of view.

Today processors spend most of their time stalling on memory and only dreaming of the opportunity to copy a large, linear chunk of data. It's only now that the performance penalty for random access has exceeded 50:1 for over 10 years that general programming public has started to take the problem seriously.

Retric3• 12 years ago

Until recently main memory was close to CPU speeds and RAM cache was pointless. The issue is the speed of light means the distance between RAM chips and the CPU limits you to MHz* speeds which is not an issue for a 286, but CPU's kept getting faster even if the Speed of light is fixed.

*At 1GHz light can do a six inch round trip, electricity is significantly slower than that. SDRAM is fairly high latency but cheaper and as the best case is not all that fast it's considered a good tradeoff. Adding cache increases latency even further, but tends to make CPU's faster on average.

rcxdude• 12 years ago

Another useful aspect of intrusive linked lists in certain situations (mostly embedded nowadays) is that they work across non-contiguous memory. When you don't have virtual memory or even malloc that can be really important.

falcolas5• 12 years ago

Linked lists have more consistent performance than std::vector. And taking half a second to render one frame when you're averaging 100fps is way worse than consistent 50 FPS.

There was recently an article about intrusive linked lists, and this same question came up. I took the unreal linked list library, and wrote a similar std::vector implementation, and tested it. The test was simple, fire 50,000 bullets at a rate of 500 rounds per second, and remove them when they fall 2 meters. They existed in 3 separate lists: physics objects, renderable objects, and all objects. When they hit the ground, they were removed from all lists. Capture the clock ticks to generate each "frame", and do a few calculations on them at the end.

The average and median operation times for std::vector were indeed a fair bit faster (at -o3, at no optimizations the ILL implementation was faster). However, the worst case for std::vector was... much worse. More than 1000x worse in some runs. One test run showed the worse case taking over two millisecond for a single frame of just manipulating vectors!

    $ ./benchmark_ill
    Minimum: 0.000000
    Maximum: 0.000094
    Average: 0.000005
    Median: 0.000005
    Total Frames Rendered: 18968118
    Total Run Time: 100.663895

    $ ./benchmark_v
    Minimum: 0.000000
    Maximum: 0.004813
    Average: 0.000002
    Median: 0.000002
    Total Frames Rendered: 35859663
    Total Run Time: 100.664009

sillysaurus37• 12 years ago

Wait a sec. You can't bust out numbers like that without being clear about a few key points:

1. What was std::vector's removal algorithm like? Are you sure that .remove() wasn't shifting all elements in the vector? The "correct" removal algorithm in that case looks like this: Swap the target element to the end, and then decrease the vector's size by 1. But if I remember correctly, std::vector's remove method doesn't work like that, so of course it will have terrible worst-case performance if it was shifting all elements of the array when you remove the first one.

2. What's causing the worst-case slowdown? Are you sure you weren't simply seeing the effects of the L2 CPU cache being invalidated?

A linked list will thrash the CPU cache constantly, whereas vectors thrash the cache much less since the elements are stored in contiguous memory. For a modern game running on a modern CPU, vectors are almost always the better choice for that reason.

EDIT: I'm not sure your numbers are trustworthy. For example, there's no way it rendered 35859663 frames in 100 seconds. That would be 358,596 FPS.

Assuming your FPS was actually something like 358, not 358,596, that's still an extremely high FPS. When your FPS is so high, it becomes difficult to accurately measure the reasons for worst-case performance. A sudden spike within a single frame could be for any of a dozen reasons, such as CPU cache eviction, a GPU pipeline stall, or some other program on your computer taking CPU resources.

flohofwoe4• 12 years ago

Dynamic arrays like std::vector must be tweaked for a special use case as well, for instance it is quite essential to pre-allocate the array to a capacity of the expected number of entries using std::vector::reserve() so that no excessive re-allocation takes place while the array grows. Also special care must be taken if the objects have an expensive copy operation (that's where the new move-semantic in C++11 may help a lot).

jokoon3• 12 years ago

already read that article about ILL, did not make much sense to me.

Where do you explain why the vector is slower ?

davexunit• 12 years ago

What's the point of using linked lists ?

The most important quality to me is that singly linked lists are a great simple persistent data structure, whereas the data structures you've mentioned rely on mutation. Linked lists are awesome, seriously.

gaius3• 12 years ago

The team was incredibly invested in the project, and put in unheard of efforts to complete the project while sacrificing personal health and family life.

I wonder if this is "invested" as in, had a substantial equity stake and it was worth the sacrifices of health and relationships because they and their families were setup for life afterwards and retired to a beach in Malibu, or some other meaning...

wingerlang• 12 years ago

.. because they and their families were setup for life afterwards and retired to a beach in Malibu ..

And if the game flopped then? Even a success doesn't guarantee the above does it?

gaius3• 12 years ago

Sure, but they weren't taking that chance were they? They were just being exploited.

brainburn• 12 years ago

He says the maximum number of units is 1600.

If 6 players mindcontrol a drone and an scv and build additional armies, the total number of units could way exceed 1600. Or what am I missing?

ygra• 12 years ago

You'd get the wonderful error »Cannot create more units«. There also was a limit with certain sprites that counted towards that. It was not an uncommon error to see in certain UMS maps that had way too many units running around.

plorkyeran• 12 years ago

You'd also occasionally hit it in zerg-heavy 8 player melee games due to that larvae and overlord count against the limit without consuming any supply. It was always pretty hilarious to see a small pack of mutalisks kill a carrier doom-fleet which couldn't launch any interceptors due to the unit limit.

realrocker• 12 years ago

Really like the story-telling style of the article. Was wondering where could I find a compilation of similar "programming tales"? Apart from http://www.folklore.org/ of course.

hybridtupel• 12 years ago

Does anybody know what happened with part three? Was it ever published?

loteck• 12 years ago

Previous discussions of this entertaining series from 2012 here:

https://news.ycombinator.com/item?id=4491216

https://news.ycombinator.com/item?id=4582123

https://news.ycombinator.com/item?id=5252003

Tough Times on the Road to StarCraft

Related Stories