Tough times on the road to Starcraft
codeofhonor.com
codeofhonor.com
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).
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".
But some managers prefer #defines. To each his own.
How do templates make this type-safe?
By using composition instead of inheritance, it avoids the downcasting.
If you want to, you can even have objects that are elements in several different lists using tag types to let the compiler keep the lists from getting cross-linked. Or you may prefer to use the node pointers for different things at your discretion.
Self-removal on destruction can be useful too. All without any more run-time overhead than the two pointers you need in C.
Also, the examples do not showcase using the same list member node to put in multiple lists. There's also the unsafety of putting the list node in a union (mentioned in the article) which adds unsafety regardless of templates or not.
I agree about destructors improving safety, I was specifically talking about templates.
With list.h, it is possible to get the same safety (unless I am misunderstanding something about the boost example) by wrapping the list anchor and node structs with a struct (typically done by a macro to define the anchor/node), which adds an array-of-0-elements of the type of the container. This allows adding the same type checks demonstrated here using templates, implemented in the list iteration, insertion/deletion and downcasting macros.
Yeah those Boost projects sometimes go off the deep end with the overengineering and abstraction a bit.
However, it does seem that it inserts an extra pointer to the member (beyond the prev/next) in order to avoid the "cast".
If it's a true C++ pointer-to-member often those can be completely optimized out if the compiler has the type information available at the time.
I've done a (much simpler) intrusive DLL template that certainly did not have that additional pointer, but I'm not sure if it met all of your requirements. I know it supported membership in multiple lists, but I don't think they were heterogeneous collections.
If it indeed does so, it is again less optimal than Linux's list.h. On 64-bit machines, 8 extra bytes for each list element is not always negligible.
Agree, I'm all for performance. At least when I'm on that kind of project.
Also, the examples do not showcase using the same list member node to put in multiple lists.
For that you could derive from multiple base hooks with different tag classes, or compose multiple member_hook<class T, class Hook, Hook T::* PtrToMember>. Each would have a different PtrToMember, but it would be known at compile time and thus should be optimize-outable.
There's also the unsafety of putting the list node in a union (mentioned in the article) which adds unsafety regardless of templates or not.
Boost has a safe type-discriminated union class you could probably use for that if you wanted to.
With list.h, it is possible to get the same safety (unless I am misunderstanding something about the boost example) by wrapping the list anchor and node structs with a struct (typically done by a macro to define the anchor/node), which adds an array-of-0-elements of the type of the container. This allows adding the same type checks demonstrated here using templates, implemented in the list iteration, insertion/deletion and downcasting macros.
Perhaps you could add an array of size 1 to represent the element data following the last pair of pointers. Or I may not be understanding this. Can you point me to an example online?
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.
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).
I still miss something like Commandos: Behind Enemy Lines, that was a surprisingly great game.
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.
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.
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.
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.
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.
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.
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.
(disclaimer: I'm just guessing, no inside knowledge. certainly feels right though)
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.
Did you guys have any idea what sort of an impact it would have in Asia (more specifically with the Korean players)?
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.
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.
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.
* 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...
With rare exceptions, software begins when it's shipped. What everybody thinks of as the finish line is actually the starting line. Successful software is maintained, extended, and enhanced for years and even decades afterwards.
And games often are among the rare exceptions.
Digital distribution has made the subscription-based (MMO of your choice), "MVP"/"paid beta" (Minecraft, Terraria, and other indie games), and long term microcontent/paid update (TF2, various iOS games) approaches more viable than ever, but many game genres and corporate cultures are very much locked into the idea of shipping a finished product and moving on from it.
As an example of both the modern "continuous updating" and traditional/greedy "shipment oriented" approaches to development in a genre traditionally considered "ship and forget", you could imagine a company that makes adventure games (or interactive fiction or visual novels or whatever you want to call them) for smart phones that reuses and improves their game engine from release to release. Since a well-done adventure game should still be appealing even years after its original release, one approach would be to backport engine improvements to their older games in order to make them more attractive to long-tail customers. You might think of this as "we're selling stories, not engines." A more traditional approach (still employed by many Japanese developers) is to wait for a significant hardware or platform update and re-release the game, usually (but not always) updating the visuals or enhancing the interface, often several times, in hopes of milking fans dry with minimal effort (lazy ports) or risk (updated rereleases of games they already know people will buy). With the success of iOS and Android as continuously improving platforms in contrast to traditional static consoles, we may see less of the latter strategy in coming years.
On the other hand, Activision's Call of Duty series has been very successful sticking to an unquestionably franchise-oriented approach. Each game is basically the same as every other one before it, dressed up in a slightly different coat of paint, with slightly tweaked gameplay mechanics, etc, yet people enthusiastically plop down $60+ for every new release. Activision has no incentive to backport their engine improvements to their older titles because they want people to move on to the latest and greatest installment, and no one wants to buy the old installments anyways -- no one actually wants Modern Warfare 1, 2, or even the latest installment of today, specifically. They just want access to the latest iteration of the Call of Duty formula and all of its players, and they're willing to pay $60+ every year to do so.
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
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.
"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) .
You've already lost me
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.