From Top to Bottom
by Chris "Kiwidog" Hargrove
Download this week's code files: cotc5src.zip (69k)
Be sure to read the license agreement before using the code.
"Noble life demands a noble architecture for noble uses of noble men" - Frank Lloyd Wright
Back again :) Today's article is going to be a bit of a throwback to the first article, as I'll be talking a bit more about a few architectural issues. Don't worry, there's still some new code this time as always, albeit rather small (I've begun a small subsystem to deal with memory management, starting with large zone allocation). But due to the sheer number of e-mails and other discussions I've gotten into recently on the subject, I thought I should talk about some more core design issues sooner rather than later.
I spent the first article talking a lot about encapsulation, separating interface and implementation, and keeping code in black boxes. Today we'll expand on some of that and talk about top-down vs. bottom-up architecture, and its affiliated choices (inheritance vs. composition in C++, for example). If you haven't given much thought to which of these directions your code should be taking, or if you've previously considered the problem trivial, you should start giving it a lot of thought. The problem is far from trivial, and the paths you choose can make or break a project.
The most common questions I've gotten recently have been "You're compiling with C++ but you're using mostly C, why?", "You advise to encapsulate your code but aren't using C++ classes to help that encapsulation, why?", and "It seems like you don't want to use C++ to its full potential, why?". These all boil down the same question: why is my choice of architecture the way it is? I'll try to cover those questions and related design issues today. And while you may not agree with some of my opinions, you should still understand the importance of the issues being addressed. Top-down vs. Bottom-up design is not a choice to be taken lightly.
The Front Lines
A quick mention... according to loonyboi, loonygames will soon have a message board system in place, so there'll be a new (and probably better) way for you to get your ideas about COTC to me and everybody else. In addition, Gringo has also set up a third-party COTC message board. Feel free to use both boards to bring up ideas, questions, comments, flames, and so forth about COTC; I'll be checking both of them regularly.
Let's see... might as well get a couple more Q&A questions out of the way... :)
Okay, on with the show! :)
Software design is an interesting beast. For decades people have been trying to find "the right way" to do things, and nobody has come up with a definitive answer. It's doubtful anyone ever will. But many methodologies have been thought up, ranging in scale from basic to enormous. For all types of systems (especially large-scale systems), most of these methodologies seem to boil down to two basic camps, which I'll just call "top-down" and "bottom-up". To visualize what those mean, think about a pyramid (with a central block at the top and a whole lot of blocks underneath it, getting wider towards the bottom). If this pyramid is a software project, then top-down design thinks of the pyramid primarily in terms of the top brick, while bottom-up design thinks of it primarily in terms of the bottom bricks. Most people mix and match them here and there, but here's some "symptoms" of each that you can recognize in your code and others' code:
If you've programmed for any length of time, you should be able recognize both of these paradigms, and have almost certainly worked with both of them here and there during your projects (consciously or not).
Well, if you haven't given the ramifications of each "pyramid scheme" a whole lot of thought until now, it's time to start. Both choices may seem equally viable on the outside, so all things being equal you should be able to choose either method at will. Once you get down to implementation though (especially in C++), all things are not equal. I wasn't kidding when I said earlier that such choices can make or break a project, and I've seen it happen more times than I can recall. And you know what? It's still happening, and projects are still spinning out of control because of it, often without the programmers ever realizing what happened. If you were never conscious of this decision before, now's the time to remedy the situation.
Top-down design is good for applications that follow a common framework, such as word processors, spreadsheets, and many other end-user applications with a fixed scope. It's also good within certain game programming subsystems like window managers, or entity class trees. But personally, I am very strongly convinced that top-down design is completely and totally inappropriate for game engine architecture or anything similarly large enough in size and diverse enough in scope of implementation. Game engine internals have too many different things going on that have nothing to do with each other, and if you try to connect them via a common top-down thread you'll likely be asking for trouble. At the very least, reuse is crippled (since your low-level subsystems become tied to the project they're in) and distribution of labor becomes troublesome (since the subsystems are so intertwined). And at the worst, your project can grind to a halt because a critical design error made somewhere at the top can devastate every single subsystem in the project. Regardless, game engines designed from the top down will suffer delays, guaranteed. I say this with conviction and I've yet to be proven wrong on it.
So what's the big deal? Why do I stress bottom-up so much over top-down when writing game engine code? It breaks down into two different areas, "logical" issues and "physical" issues. Logical issues are concerns that relate to conceptual design unrelated to its implementation, and physical issues relate to implementing a design in a given language. While I can't talk about all the concerns here, we'll talk about two of the big ones: the logical issue of inheritance vs. composition and how it affects code reuse and encapsulation, and the physical issue of C++ class exposure.
Inheritance vs. Composition
Object-oriented programming pundits have a major problem on their hands, and I don't know how many of them realize it. The problem is an inherent conflict of interest between how OOP is usually taught, and how it often needs to be used in the real world.
Equivalent to the top-down vs. bottom-up issue, OOP has a parallel argument usually known as inheritance vs. composition. With inheritance, you create base objects and derive other objects off of the bases. With composition, you create base objects and contain/use those bases within more complex objects.
Both have their place, and to program effectively you need to know when to use both. Unfortunately, people learning OOP often don't realize this, because of the way OOP is taught. Inheritance is stressed far more than composition. Why? Because it's different. Functional languages like C support composition primarily, and inheritance is difficult to implement. On the other hand, OOP languages like C++ support both composition and inheritance, directly. When people start learning OOP, what's one of the first things they're taught? Inheritance. They're taught to think of objects in terms of "is a" trees, where a bee "is" a winged insect "is" an insect, or that a janitor "is" an employee "is" a human, etc. They're also taught that inheritance is one of the "big new things" supported by object-oriented programming. So what happens? The people being taught mentally assume "OOP means inheritance"...
...and that Pavlovian association ends up haunting them for years.
The truth of the matter is that OOP has nothing to do with inheritance specifically, except that OOP languages support it more directly in language terms. OOP is simply about treating your code and data together cohesively, whether that cohesion be both logical and physical, or purely logical. You can use composition just as well as inheritance and not be "violating" OOP principles. And the reality is you need composition, because inheritance (and top-down design) won't hold up well in many real-world programming situations. Composition, bottom-up design, and other things traditionally considered older "functional" programming concepts do still have their place.
The myth of "OOP means inheritance" has a bad repercussion for OOP as it pollutes the goal of code reuse. I hear a lot of people touting that "OOP allows code reuse", yet they write their code so top-down and using so much inheritance that such reuse is simply not possible. If you think about it, top-down design and inheritance are completely against code reuse, since every component is thought of and dealt with in terms of the application. If the application changes, such code often becomes completely invalid. After all, if you have a class that's at the end of a large inheritance tree, how can you reuse that class without bringing along all of its base classes with it? The bigger the tree gets, the less reuse becomes feasible.
Sorry people, but just because you put something inside a class doesn't mean it's encapsulated.
The only reuse top-down design allows is with core frameworks, where the framework itself gets reused, but that locks users of the framework into that framework's paradigm. Bottom-up design doesn't have these problems, as each component is thought of purely in terms of itself and its subcomponents before the greater application ever becomes a factor. This is an enormous benefit when writing game engine code, since diverse subsystems can be written, tested, and debugged independent of most of the rest of the system, in whatever way works best.
Inheritance does have its use even bottom-up design, in the form of class hierarchies that are limited in scope to the subsystem they're in. If a tree bleeds past the subsystem and becomes involved in the subsystem connections themselves, you instantly have the Pandora's Box violation that you want to avoid. But if it's restricted to small subsystems and hierarchies that don't move past "abstract class -> concrete class" logic, things stay clean. You can be top-down within a subsystem and still be bottom-up in the overall architecture itself.
So don't think that object-oriented programming requires inheritance to connect everything together. Inheritance is just one tool available in your programming arsenal, a tool which coincidentally isn't as easily available in functional languages like C. People often say that it's easier to screw up a design in C++ than it is in C, but can't really explain why. The reason why is because C++ makes both top-down and bottom-up arrangements equally easy to create. Make sure to be aware that every time you use inheritance, you're contributing towards a top-down design (as opposed to composition which contributes towards bottom-up). That can be a good thing if that's what you want to do, but a very bad thing if you don't want to do it or you don't even realize you're doing it.
C++ has a few language problems that make abusing top-down design and inheritance an unwise idea simply from a practicality standpoint. One is the fact that it's too easy to inherit from concrete classes that were never intended to be inherited from. But the biggest one in my eyes is class exposure, an inherent problem in the way C++ classes are created. When you write a class, both public and private data members and method functions are declared, and the class is usually placed in a header file so it can be used by others. The public stuff is not a problem, as that needs to be there (it's the interface to the class after all). But so does the private stuff, and that's bad.
What you've got is a situation where everything using a class knows the private organization of that class, and any time you want to change that organization, the change is exposed to everything uses that class, requiring recompilation. Such compile-time dependencies are insignificant early in a project, but can become a major productivity hit when the codebase gets big enough. This is different than interface/implementation separation in C, where static "private" variables and functions of a subsystem are only listed in a .c/.cpp source file and not in a header, so changing them only requires that one file to be recompiled. Putting an equivalent subsystem in a C++ class would add significantly more compile-time dependencies. It would also expose the internal structure of that subsystem to everything outside it.
This is one of the big reasons I stick with mostly C-like interfaces when possible, even in C++ code. When anything dealing with implementation is exposed, black-box separation is broken, and I don't want that. I'll use C++ classes when they make sense and the benefits outweigh the costs, but I'm not about to incur those costs and invite entropy for no good reason.
Even when my code isn't object-oriented at the physical level in C++, it's object-oriented at the logical level, to such an extreme degree that C++ itself automatically damages encapsulation. So if people look at my C-like interfaces and start wondering whether I know anything about object-oriented programming, my egotistical response is "damn right I do". :) C++ is a language that likes to tempt you, and it has many temptations that are worth taking from time to time. But don't blindly abuse it just so you can pretend you're being object-oriented. Object-orientation and good design go far beyond the keyword "class".
A Conscious Effort
Whether you agree with me or not on any of these issues, you should have very explicit reasons for your choices when considering game engine architecture. Be conscious of why your design is the way it is, and how it will affect your project both at the logical and physical levels. Whichever route you take, there will be consequences.
That's all for now, until next time...
Hey, What About The New Code?
Oh yeah, forgot about that. :) There's only a little bit of new code added this time, starting out a memory management subsystem. There are two files added to the project, mem_main.h and mem_main.cpp. Both of these will likely grow somewhat over time, but for now they just contain a few functions for dealing with large memory "zones". A zone in this case is just a pool of memory that is allocated out of, in a way similar to malloc(), except the zone is freed as a whole. Internally, these functions cascade down to Win32's "VirtualAlloc"-related functions, an easy way to work with Windows' memory paging mechanism. Look at the header file and the implementation; the code should be pretty self-explanatory this time around. We'll use these zones for large data resources once we get into resource management (a topic we'll start next time which merges file loading and memory caching together into one cohesive entity).
Just to give you an idea of the track I'll probably be taking for the rest of the series, it'll likely be something like this:
So we've still got several articles left before the decision needs to be made on the game of choice. Got feedback? Drop me an e-mail, or better yet, throw it on one of the message boards listed near the beginning of the article. :)
Until next time,
- Chris"Kiwidog" Hargrove is a programmer at 3D Realms Entertainment working on Duke Nukem Forever.
Code on the Cob is © 1998 Chris Hargrove.
Reprinted with permission.