Polymorphic Entity Systems
Every game has some sort of object you can interact with - If it didn't, it wouldn't be so much a game as a movie or a play. Depending on your game, this can be an NPC, a trigger button, a pushable crate, a bullet, a powerup or indeed the player himself. And these objects need to be stored and handled by your game, and there are many ways of dealing with this, many systems to do it with.
One main requirement of such systems is that they must be flexible. They should be able to handle one, or two, or five thousand entities, depending on your game and where the player is in the game. It also has to be extendable. You might - actually, you are highly likely to - decide to add another monster or another type of door during the development of your game.
This is an object oriented way of solving it. For our language, we will use C++, but you can easily implement it in any other object oriented language, such as Java. A similar system can be implemented in non-object oriented languages as well, but we won't go into such matters here. To display graphics, we will use the Allegro game programming library. This tutorial will use STL (Standard Template Library) elements - in-depth knowledge of this is not necessary, but will help to understand what we're doing in some places. You are, however, assumed to have a basic knowledge of pointers, and knowledge of Allegro helps. And, since this is game programming, you are assumed to know about the classic separated draw/logic loops moderated by a timer.
Before we will begin to write any code, we need to plan ahead and design our system. What will we need? How do we make sure our system is extendable? How do we store everything, and how will it all stick together?
Let's tackle them one at a time. First, we should decide what we want out of our objects. Let's start with the common traits, shared by (mostly) every object we will encounter in our game. At the very least, should be able to have some sort of graphical representation, and should respond to the player in some way - furthermore, some should have a mind of their own (like a monster). They should be able to exist somewhere in the system - that is, they should have a position - and some should have the ability to move around.
A few of these may initially seem to pose a problem. In particular, not every object in the game looks the same way. One could easily solve this by just having a sprite stored in our object, and change that accordingly. However, this does not allow for very complex drawing, and it still doesn't solve our second problem - not every object works the same way - doesn't move the same way, doesn't respond to input the same way, and so on. One might be tempted to just create different classes for every single thing, and re-implement functions and change what you need in each one. This, however, isn't what object oriented programming is about, and worst of all it breaks one of our requirements - the system isn't flexible, when everything is of vastly different types like that, and interaction between objects becomes a nightmare.
That's where object oriented programming comes into our system and solves all our problems. No, seriously.
Thinking back on what we were told at school (or read in books, or heard from friends, or received as a mystical message from the heavens), object oriented systems have a little something known as inheritance. If we can create a simple base class, and then inherit from that class, we can get around the inflexibility issue - every object in our world is actually of one and the same class (remember, inheritance is an "is-a" relationship)! Each kind of monster, spaceship or bullet can then be a subclass of that base class, and flexibility is ensured.
We still have one problem, though - they should (mostly) all act differently, but we can't go around having different methods with different names for different types of objects - that is not a flexible solution (how would we know what to call at what point?). A straightforward solution might be to use some massive if..then..else statements to decide what to do. However, this shows to be a rather poor solution in the end, and is prone to create bugs that are hard to track down later. So we need another solution. Again, object orientation comes to our rescue, and we enter what is known as polymorphism.
You might have heard about virtual functions before. Those will come in great use to us as we plan our system. What we want is a function that always has the same name, but can do different things depending on who it belongs to. Well, virtual functions are exactly that. If a method in a base class is defined as 'virtual', any subclass can re-implement that function further down the line, and if it is later called, the 'youngest' of the classes - the latest one re-implemented - will be the one that will be run. This way, we can set up our base class with some simple virtual functions, and just override them as is required by a particular object type. Exactly what we need!
So, in summary: What we want is a "base" we can subclass, and in which we can define virtual functions that we can later override and override again to suit whatever object (henceforth referred to as an ENTITY) we want to draw.
We now have all the components we need for a base entity class. In the following code listing, we have implemented some of the most basic functions. All code will be explained further down. For all code examples, assume intelligent placing regarding header/source files - classes go in headers, and definitions usually in the accompanying source file. For the purposes of inclusion in this tutorial, think of them as "entity.h" and "entity.cpp".
Note that care has been taken here to make sure that our system is properly encapsulated - that's good object-oriented practice. Now, let's see what this actually does.
First, let's just create our class. I'm calling mine "CBaseEntity" - the C being for 'class' - and it doesn't derive from anything else (why should it?). No explaining needs to be done here.
Then, we declare the private members of our class. So far, we only have some positioning information, as we previously decided we needed. I said "private" members before - that's not really true. What we made them is "protected" members, the difference being that these are accessible to our future subclasses, whereas private members wouldn't have been.
On to our public members - here, the constructor and destructor. You might notice something strange here - we have added the "virtual" keyword to our destructor. The reason for this has to do with inheritance and polymorphism. You might remember that normally when an object gets deleted, only the base destructor actually gets called. This is bad in a situation like this, where virtual functions can override behavior and load data of their own - they need their own destructors to be called. The virtual keyword ensures that it gets called. In fact, EVERY destructor in the hierarchy will be called, in order, beginning with the youngest.
Now we get to the virtual stuff. This method, called Draw(), will - as you might have guessed - draw the entity in question. We want to supply it with a BITMAP *, in order for it to know where to draw itself. Whenever we want the entity to display itself, we call its Draw() function - different entities might want to draw themselves differently, so we make it virtual so we can override it in child classes if we want to later.
As the comment said, this is just a simple accessor for setting the position of our object. We haven't implemented a getting accessor yet, but if it ever becomes necessary, it's trivial to implement. We've made it inline to speed things up a little - if you don't know what this means, then you can safely ignore it - it has no impact on the issue at hand here. Note though that inline functions need to be defined like this (in our case in the header).
The constructor and destructor should be fairly straightforward - we just initialize our values in the constructor, and we have no resources that need to be cleaned up in the destructor. After that, we have the default implementation of a Draw() function - in this case, it does nothing at all.
As bland and boring as this class may look, it is the basis on which we will build our system. From this base class, we can derive and override to our heart's content, and our possibilities are almost endless. Save for one thing ... we don't really have a way to store it yet, and neither do we have a way to actually draw our objects. Let's get to that.
As mentioned before, we're going to use STL containers for keeping track of our entities. In this case, we have two main choices - vectors and lists. In our case, the answer is simple. Our entities are likely to change around a lot, so we need the solution that offers the least insertion/removal overhead - we will only do iterations later, not random access, so we don't care much about that overhead. In other words, STL lists (doubly linked lists) are the perfect candidates.
One little problem may rear its ugly head here. Our first impulse might be to store lists of CBaseEntity objects. However, we soon run into a plethora of problems, the foremost being the fact that polymorphism is impossible to do with lists of objects. I will not get into technical detail here, but in short, we have to refer to our objects with pointers, or we will always get the functions from our base class - not what we want. So, a list of pointers to CBaseEntity objects is what we want. Remember that, of course, these pointers can point to subclasses as well - that's the strength of our approach.
So, we add something to this effect to store our entities:
What we have here is a simple STL list capable of storing pointers to CBaseEntity objects. It will be empty by the time it's created. Whenever we want, we can add a simple entity to it with some code like this:
All this is good, but it's not of much use if we don't actually DO anything with this list.
We have our base entity, and we have a list to store them in once instantiated. Now we just need to draw them. Fortunately, this is easy, with the planning we've already done - all we have to do is iterate through the list and call the Draw() method, and all will be well!
This code may look a bit fishy at first - it's mostly STL code. Don't worry, all it does is - as mentioned - it goes through every entity in the list and attempts to call its Draw() function. And since we're using a list of pointers, the proper inherited version of Draw() will be called. Of course, it doesn't do much good now, no matter how many entities we push onto the list - all of them are CBaseEntity objects, with Draw() functions that don't even do anything!
It's time to change that. The following code is an example of an entity class we would subclass from our base entity.
Now let's have a closer look at it. First, we declare a new class called CStar. As the comment says, it's just a simple, white, glowing star - we might use it for something like a starfield, for instance. First, we declare its constructor - this should be straight forward. Note that we after that declare the Draw() function again, just as we did in the base class - in fact, the declarations are identical, save for the fact that we skipped the "virtual" keyword this time (it's not necessary for the subclasses to include it - once in the base class is enough). What this does is tell the compiler that the CStar class will want to override the Draw() function, so that if we call Draw() on an object that happens to be a CStar later, this one will be used instead of the default base one (which does nothing).
Finally, we define both the constructor and the drawing function - nothing fancy here. The constructor basically just calls its parent, and does nothing more. The Draw() function just plots a single white pixel on the bitmap specified. Note how it uses the x/y pair from the base class - a big part of object oriented programming is code reuse - and how the explicit cast to int is required for Allegro to function properly here.
So, what we've done is declared and defined a new TYPE of entity - this could just as well have been a monster, a box, or anything else you might want. We can now use this entity like so:
This is almost identical to the above statement, with one simple change - this time we're creating a new CStar, not a new CBaseEntity, but we still use a CBaseEntity pointer for our variable. This is valid; remember, subclasses are parent classes - the CStar "is a" CBaseEntity (but a CBaseEntity isn't a CStar). We keep it a CBaseEntity so we can push it onto our list later; if you want to access functions declared only for CStar, we would have to cast it at some point (but we don't in this simple case). Next time we iterate through our list to draw, our program will check the type of the objects being pointed to in the list, and call the appropriate Draw() method. If you were to run a program like this, you should be able to see a white dot at the position we moved the star to. If we want another star, we can just repeat the procedure; we can do this indefinitely (or at least until our memory runs out), adding as many entities as we want!
Being able to draw entities is good and all, but there's something missing. Our star doesn't really do much - it just sits there. Now, for a star or backdrop object this might be okay, but it just won't cut it for, say, a monster. It needs to react, and move. Well, if we have one virtual function for drawing, why not have one for doing logic updates, too?
Remember to add an empty definition for this one, too! Now, we want the Think() function to be called every time your logic cycle fires - and it's just as simple as telling all entities to draw themselves:
Now, you can just override the Think() method as you wish, and your entities can now react to the passage of time! It doesn't end here, though, of course. You can add more and more of these virtual functions, for any event you want your entities to be able to react to - examples could include CollidesWith(), TakeDamage(), and so on - I'll leave these as an exercise to the reader.
The problem of having flexible, easily extended objects in your game can be easily solved by using one of the most powerful tools of object oriented programming - inheritance and polymorphism. Because we base everything displayable (or indeed some times invisible) on one common object, we can easily keep lists of one single type, and still benefit from having potentially hundreds of different types of behavior!
Every object in the game can potentially interact with every other - they are all basically CBaseEntity objects or objects of subclasses thereof - as long as you keep track of what their common denominators are. There is no hassle of writing a drawing or logic interface for every type of object, or comparing apples to elephants - this way, they are all really one and the same, and common functions can be applied to both without cluttering up your namespace or making things too complex to extend.