Tough times on the road to Starcraft(codeofhonor.com)
codeofhonor.com
Tough times on the road to Starcraft
http://www.codeofhonor.com/blog/tough-times-on-the-road-to-starcraft
68 comments
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.
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?
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) .
"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) .
TL; DR: C++ really sucked back then
'so Blizzard wouldn’t have a long gap between game launches.'
You've already lost me
You've already lost me
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.
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.
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.
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.
There is no finish line.
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.)
Although I agree with your sentiment, I read the parent as saying something different. There's literally no finish line. It's not just that projects take longer than planned.
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.
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.
> 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.
And games often are among the rare exceptions.
Actually, not so much. Leveraging the technology from your last game development cycle is par for the course.
You're missing his point: Large or small parts of a codebase may be reused from project to project, but, especially in the days of Starcraft, games are often released as finished products, closed cases that the developers quickly move on from after shipment.
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.
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.
I wish to know more about the "voice-to-phoneme" compressor he mentions. Anyone have any links handy? Google is failing me.
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.
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.
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..)?
I never knew the importance of Storm.dll but now it makes sense on why it was always corrupted.
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.
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.
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)
(disclaimer: I'm just guessing, no inside knowledge. certainly feels right though)
[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.
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.
Thanks for the countless hours of SC fun over the years. Amazing how far things have come, but really how little has actually changed when it comes to what makes the game fun and engrossing.
Did you guys have any idea what sort of an impact it would have in Asia (more specifically with the Korean players)?
Did you guys have any idea what sort of an impact it would have in Asia (more specifically with the Korean players)?
Nope. We thought we would sell about 4000 copies in Korea, to the extent that anyone on the team was thinking about it at all. Timing is everything - we just happened to hit the Korean market when everyone lost their jobs and started playing in PC Bang. Kinda lucked out and sold a copy to every man, woman and child in Korea.
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.
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.
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?
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.
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.
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...
* 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...
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.
Reading this Starcraft story and "Evolve Your Hierarchy" reminds me that, in retrospect, most of the class inheritance hierarchies in my student and early professional projects were bad design. These days, I think implementation inheritance is a code smell.
"Prefer composition over inheritance" is an item in Bloch's Effective Java.
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.
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.
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.
Wow, thanks for that link, it looks amazing! This might be the first Kickstarter campaign I might contribute too...
I contributed and the team has been very active in sending updates via email. Nice to know they are caring about suggestions too. In the meantime, you should get the sc2 HOTS expansion when it comes out soon. Everyone is going to have to relearn sc2 with the new expansion anyway, so it's a great time to jump in. Until then... just watch some streams to get familiar with the game. http://www.teamliquid.net/video/streams/
...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).
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).
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.
I still miss something like Commandos: Behind Enemy Lines, that was a surprisingly great game.
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.
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 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.
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.
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.
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.
No, the starter edition map pool has been unchanged since its announcement.
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.
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.
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.
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.
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.
The famous TotalA soundtrack is here: http://www.youtube.com/watch?v=BxAdOQtAFEs
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.
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.
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
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
MechCommander 2 source also available: http://www.microsoft.com/en-gb/download/details.aspx?id=1145...
Great read. I've been there. Write an awesome code base to have someone come along to replace it all with crap.
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?
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.
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.
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.
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.
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).
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).
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).
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".
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".
Standard templated linked lists are suboptimal. Simple C lists ala Linux's list.h are simpler and more optimal, behavior-wise.
Well I didn't say you had to use std::list. One can implement exactly the same behavior as Linux list.h in C++, but type-safe and namespace-scoped.
But some managers prefer #defines. To each his own.
But some managers prefer #defines. To each his own.
The behavior of list.h essentially boils to downcasting from a list node to its container. Allowing multiple list nodes in the same container, and re-use of the same node for different lists. How do templates make this type-safe?
http://www.boost.org/doc/libs/1_51_0/doc/html/intrusive/list...
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.
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.
I tried reading the code in intrusive/list_hook.hpp and intrusive/list.hpp, and it's quite difficult to read. 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 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.
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.
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.
I tried reading the code in intrusive/list_hook.hpp and intrusive/list.hpp, and it's quite difficult to read.
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?
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?
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?
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.
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.
Ah. Thanks.
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.