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".<p>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.<p>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).<p>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).
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.<p>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.
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.
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?
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.
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.
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.
" I plan to write more about path-finding in StarCraft because there are lots interesting technical and design bits."<p>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.
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?
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.
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?