I don’t understand why you would even use a linked list over a preallocated flat array.
You have a fixed maximum number of units. Everything in the game still needs to work when that number of units is in play. So it seems to me that preallocating an array with space for a pointer for every unit would be strictly easier and also use half as much peak memory. Nowadays you could maybe argue cache effects… it sort of sounds like they used linked lists because they had them available and for no other reason.
there were lists for each player’s units and buildings, lists for each player’s “power-generating” buildings, a list for each Carrier’s fighter drones, and many many others.
It sounds like the point wasn’t storage or memory — for all we know they were stored in a big array, that doesn’t stop them from partaking in linked lists too — but traversal across different axes of kind of thing.
It does sound like memory was a driving concern, though.
Some of the link fields were shared among several lists, so it was necessary to know exactly which list an object was linked into in order to safely unlink. And some link fields were even stored in C unions with other data types to keep memory utilization to a minimum.
I don’t dispute that memory was a concern; I dispute that using linked lists implies anything about memory use.
for all we know they were stored in a big array, that doesn’t stop them from partaking in linked lists too
They needed ways to quickly traverse lists of certain kinds of things, along different axes, where those things might participate in multiple lists. Those things might’ve been allocated in a big array (with a bitmap or something alongside to mark which spots were free), they might’ve been individually heap allocated, who knows/what I’m saying doesn’t bear on that.
Presumably they did not want to maintain multiple big arrays of pointers for each class of thing to track, and again, some of the items didn’t have a (player-facing) limit, like buildings (which don’t count towards the unit count), so it’s not clear how easy those would’ve been to stick in a big array anyway.
But that’s still besides my point: the lists were for easily finding different kinds of things, and single objects could well participate in multiple such lists, maybe even dropping in and out of them over time (maybe a list for “units selected by player”?) while still being allocated and live. The thread starter says:
I don’t understand why you would even use a linked list over a preallocated flat array.
and I’m saying, well, even ignoring the situations where that may not be feasible (above re: buildings), they may well have done that anyway, because the linked list isn’t (or isn’t just) what they picked to allocate them in; they were functional.
It wasn’t until many years later that the mantra “favor composition over inheritance” gained credence among programmer-kind
I’m glad somebody had that insight as far back as the mid-90s. I first heard it professed—with this phrase or otherwise—probably around 2012 when this article was written. I was at the stage of knowing inheritance tangles when I saw them, but not knowing great general solutions, and being semi-thankful for single inheritance over multiple. Given that so many felt this pain, what took us so long to learn the lesson?
Composition didn’t feel like OO programming. Languages like C and Pascal already had composition. Inheritance was the magic sauce that OO was bringing to the table, so why wouldn’t you try to use it?
Smalltalk had a lot of composition-based patterns. It was only second-wave languages like Java that went all-in on inheritance. Self (which, in many ways, was the Smalltalk that Smalltalk wanted to be) blurred the line a lot by having arbitrary numbers of prototype chains, which were either inheritance or delegation depending on how you think about it.
A lot of the reasons to prefer composition to inheritance came from the inflexibility of the inheritance models of the later languages. There were two big problems:
You can’t inherit from two things in Smalltalk / Java / JavaScript. You can adopt two things as members. If your model is ‘users of this API inherit from this class’ then you run into problems when people want to use two APIs that follow the model in the same logical unit.
If you can inherit from two things, but they both implement one or more methods in common, even more so if they are coincidentally named but have very different semantics. With delegation, it’s always explicit which class you’re forwarding to.
Newer languages tend towards a more nuanced view of preferring inheritance for interfaces and composition for implementation.
Well inheritance is the new hot stuff that is gonna solve all the problem of programming. So you have to use it! It is very important that you understand the difference between being a square and having a square. And to design a correct ontology in your application. You wouldn’t want to incorrectly model your account class hierarchy, do you?
Plus think about the code reuse! Software programmer are an expensive bunch, aren’t they? Now, when somebody need to write code that look like other existing code, he can just extends an existing class and overwrite a few methods, and boom, new feature for free. Bertrand Meyer call this the Open Close principle, and we hear this Uncle Bill or something guy is adding it to its SOLID acronym. (This will not at all cause confusion later on when we discover the idea is terrible, and the Uncle guys is forced to pretend it always meant something else, and that something else, nobody really get what it is.)
Look: your software project is already late and over budget, meaning that it has, by definition, failed. (The fact that a late delivery can still earn you millions of dollar and position you as an industry leader is irrelevant, what matter is that you failed to follow the plan). Software is in crisis. And OOP is the cure you absolutely need.
You are in luck: we sell a bunch of tool to help you in your OOP journey, like CASE tool to draw class inheritance diagram. It’s UML compliant, and it connect to our system that will handle the RUP project methodology which is the other part that you need. With this, your architect can do all the important work and inexpensive code monkey can fill the rest.
By the way, you probably will need coaching, we’ll send you expert consultants to teach you how to do Object Modeling properly. They are not cheap, but can you afford to be late while the dot com boom disrupt everything? pet.com , by 2005 will have destroyed traditional brick and mortar pet store. You can’t afford to fall behind what everybody else in your industry is doing, can you? Remember: if it doesn’t work, it’s because you are doing it wrong and you need to hire even more coach to learn it correctly. That’s why we love when you use inheritance: the mess it create mean we can bill you a lot of those coach. Keep doing it!
Now, eventually, the world will call us on our bullshit, but it doesn’t matter. Your organisation keeps failing at software because it’s a cesspool of red tape and incompetence. We know you’ll be back for Scrum, Web 2.0, Big Data, NoSQL, NoCode tools, the Blockchain and AI. We are not worried. You guys always come back.
The future is here, it’s just not evenly distributed. I still run into people who haven’t heard the good word! And the perennial argument is that class-based (multiple) inheritance is great for UI frameworks.
Funny, UI frameworks are where I felt we finally and recently got free of inheritance, with React+hooks, SwiftUI, and Jetpack Compose. Other parts of our applications went functional style in the mid-2010s when language changes enabled them, but UI frameworks were a huge lift to replace. Still are, if we look at their comparative maturity.
Overhead is generally 50-100% the salary. It includes equipment, licenses, rent, benefits, etc. And there’s probably some marketing money in there as well.
^ this. We’re used to a lot of major infrastructure elements being free today, but one has to remember that back in 1996, making games like StarCraft meant:
Expensive licenses for compilers (and more often than not, IDEs), plus build servers and the like, where applicable
A lot of expensive (and slow) marketing for things that are now rather easily covered via social media
Practically no BYOD anywhere, in an age of very rapid PC tech growth – a decent 1996 PC wouldn’t take you very far in 1998
Stone age automation (so lots of in-house tech and/or manual overhead)
Tech factors alone accounted for pretty awful overhead.
Support programmers in the 90s would write things like level editors, asset importers, installers etc. A lot of the stuff that modern game engines like Unity or Unreal provide by default.
Typically someone who did some programming but also had other duties. For example, they might also do game design or level design. It could also be someone who worked on a minor part of the game:
Even the [Starcraft] project lead was co-opted to finish the [Diablo] installer that I had half-written but was too busy to complete.
I don’t understand why you would even use a linked list over a preallocated flat array.
You have a fixed maximum number of units. Everything in the game still needs to work when that number of units is in play. So it seems to me that preallocating an array with space for a pointer for every unit would be strictly easier and also use half as much peak memory. Nowadays you could maybe argue cache effects… it sort of sounds like they used linked lists because they had them available and for no other reason.
It sounds like the point wasn’t storage or memory — for all we know they were stored in a big array, that doesn’t stop them from partaking in linked lists too — but traversal across different axes of kind of thing.
It does sound like memory was a driving concern, though.
I don’t dispute that memory was a concern; I dispute that using linked lists implies anything about memory use.
They needed ways to quickly traverse lists of certain kinds of things, along different axes, where those things might participate in multiple lists. Those things might’ve been allocated in a big array (with a bitmap or something alongside to mark which spots were free), they might’ve been individually heap allocated, who knows/what I’m saying doesn’t bear on that.
Presumably they did not want to maintain multiple big arrays of pointers for each class of thing to track, and again, some of the items didn’t have a (player-facing) limit, like buildings (which don’t count towards the unit count), so it’s not clear how easy those would’ve been to stick in a big array anyway.
But that’s still besides my point: the lists were for easily finding different kinds of things, and single objects could well participate in multiple such lists, maybe even dropping in and out of them over time (maybe a list for “units selected by player”?) while still being allocated and live. The thread starter says:
and I’m saying, well, even ignoring the situations where that may not be feasible (above re: buildings), they may well have done that anyway, because the linked list isn’t (or isn’t just) what they picked to allocate them in; they were functional.
I guess you haven’t played StarCraft?
Maybe coincidentally, and somewhat off topic for this site but probably of interest in this thread, there’s a digital antiquarian StarCraft history article this week.
I’m glad somebody had that insight as far back as the mid-90s. I first heard it professed—with this phrase or otherwise—probably around 2012 when this article was written. I was at the stage of knowing inheritance tangles when I saw them, but not knowing great general solutions, and being semi-thankful for single inheritance over multiple. Given that so many felt this pain, what took us so long to learn the lesson?
Composition didn’t feel like OO programming. Languages like C and Pascal already had composition. Inheritance was the magic sauce that OO was bringing to the table, so why wouldn’t you try to use it?
Smalltalk had a lot of composition-based patterns. It was only second-wave languages like Java that went all-in on inheritance. Self (which, in many ways, was the Smalltalk that Smalltalk wanted to be) blurred the line a lot by having arbitrary numbers of prototype chains, which were either inheritance or delegation depending on how you think about it.
A lot of the reasons to prefer composition to inheritance came from the inflexibility of the inheritance models of the later languages. There were two big problems:
Newer languages tend towards a more nuanced view of preferring inheritance for interfaces and composition for implementation.
Well inheritance is the new hot stuff that is gonna solve all the problem of programming. So you have to use it! It is very important that you understand the difference between being a square and having a square. And to design a correct ontology in your application. You wouldn’t want to incorrectly model your account class hierarchy, do you?
Plus think about the code reuse! Software programmer are an expensive bunch, aren’t they? Now, when somebody need to write code that look like other existing code, he can just extends an existing class and overwrite a few methods, and boom, new feature for free. Bertrand Meyer call this the Open Close principle, and we hear this Uncle Bill or something guy is adding it to its SOLID acronym. (This will not at all cause confusion later on when we discover the idea is terrible, and the Uncle guys is forced to pretend it always meant something else, and that something else, nobody really get what it is.)
Look: your software project is already late and over budget, meaning that it has, by definition, failed. (The fact that a late delivery can still earn you millions of dollar and position you as an industry leader is irrelevant, what matter is that you failed to follow the plan). Software is in crisis. And OOP is the cure you absolutely need.
You are in luck: we sell a bunch of tool to help you in your OOP journey, like CASE tool to draw class inheritance diagram. It’s UML compliant, and it connect to our system that will handle the RUP project methodology which is the other part that you need. With this, your architect can do all the important work and inexpensive code monkey can fill the rest.
By the way, you probably will need coaching, we’ll send you expert consultants to teach you how to do Object Modeling properly. They are not cheap, but can you afford to be late while the dot com boom disrupt everything? pet.com , by 2005 will have destroyed traditional brick and mortar pet store. You can’t afford to fall behind what everybody else in your industry is doing, can you? Remember: if it doesn’t work, it’s because you are doing it wrong and you need to hire even more coach to learn it correctly. That’s why we love when you use inheritance: the mess it create mean we can bill you a lot of those coach. Keep doing it!
Now, eventually, the world will call us on our bullshit, but it doesn’t matter. Your organisation keeps failing at software because it’s a cesspool of red tape and incompetence. We know you’ll be back for Scrum, Web 2.0, Big Data, NoSQL, NoCode tools, the Blockchain and AI. We are not worried. You guys always come back.
The future is here, it’s just not evenly distributed. I still run into people who haven’t heard the good word! And the perennial argument is that class-based (multiple) inheritance is great for UI frameworks.
Funny, UI frameworks are where I felt we finally and recently got free of inheritance, with React+hooks, SwiftUI, and Jetpack Compose. Other parts of our applications went functional style in the mid-2010s when language changes enabled them, but UI frameworks were a huge lift to replace. Still are, if we look at their comparative maturity.
Same! I only meant that I’ve read many persuasive arguments from people with deep experience.
“I just need this one base class…”
That was a small budget in the mid-90s? That makes me wonder what kind of money was going around for games studios.
That’s a budget of perhaps 8-10 people for a year.
which sounds about like what the original pitch was for (orcs in space).
But this was the 90s. You think games devs were making over 100K back then? I think they struggle to make that even now
Overhead is generally 50-100% the salary. It includes equipment, licenses, rent, benefits, etc. And there’s probably some marketing money in there as well.
^ this. We’re used to a lot of major infrastructure elements being free today, but one has to remember that back in 1996, making games like StarCraft meant:
Tech factors alone accounted for pretty awful overhead.
Let’s not forget Battle.Net too!
Good points. I wish there was more transparency in project spending. It’d be nice to know where the money gets spent.
What’s the role of a support programmer in game development?
Support programmers in the 90s would write things like level editors, asset importers, installers etc. A lot of the stuff that modern game engines like Unity or Unreal provide by default.
StarCraft shipped with a full level editor; IIRC it was a stripped down version of their internal tool.
Modern game teams still have tool engineers too.
Typically someone who did some programming but also had other duties. For example, they might also do game design or level design. It could also be someone who worked on a minor part of the game: