Introduction
A lot of games allow the player to pick up, carry around, use, sell, buy, drop, drink, wear various items. For such a thing to happen without becoming an overwhelming task for the programmers, a coherent system for managing all these actions becomes necessary. In this article, I will present and discuss a simple and basic system for managing objects, that can easily be extended to cover more complex cases.
System architecture : what's what?
Keeping all item information along with each item is overkill: all small health potions have the same name, looks and properties. Sure, some objects might have "personal" data such as ammunition, charges, enchantments, nicknames or durability that must be stored on the item itself, but this can be added later on.
The items will be represented by objects of a cItem class that will act as a black box - users of the class do not need to know how it is working on the inside. These objects will actually contain an item index which indicates what kind of item they are. To get the properties of an object, there will be a cItemDatabase that holds all the information for all the possible item indices an object can have, and which can be asked for this for information.
Finally, to represent piles of various items with various amounts (whether it is a pile on the ground, a pile being traded to somebody else, or in the player's backpack) there will be a cItemPack class which acts just like any pile of items: you can count the objects, add some, or remove others.
The items
The first and foremost step is to implement the class that will represent the items - since it's what we're going to move around and use most of the time anyway. An "item" variable should obviously have the following properties:
- Be set to another object
- Compared to another object (to see if it's the same) Because we will need to manipulate the objects, we also need the object to have the following (from a programming standpoint) :
- Be able to return an unique identifier for debugging purposes
- Be able to be built from that unique identifier
- All items must be fully ordered This leads to the following class definition:
class cItem { unsigned long type; public: cItem( unsigned long ); cItem & operator= ( const cItem & ); bool operator== ( const cItem & ) const; bool operator< ( const cItem & ) const; unsigned long getID( ) const; }; This is it: a constructor (from an identifier), assignment and comparison operators, and an identifier function. The private type variable is the item index that will be used later to get the item properties from the item database.
Also note that the const keyword appears in a lot of places: it is quite a good programming practice to mark as const variables that should not be modified by the function they are passed to, and as const functions those member functions that can be called without altering the object. This way, when the cItem class will get bigger later on, it will become better to pass objects by reference, in which case marking certain variables as const prevents those hard-to-spot bugs where one of those references is mistakenly modified (they cause a compiler error instead).
As far as the behavior of the object goes, the implementation is quite straightforward:
cItem::cItem( unsigned long t ) : type( t ) { } cItem &cItem::operator =( const cItem & o) { type = copy.type; return( *this ); } The constructors and assignment operator are quite easy right now, since they simply have to set the type to whatever is required. The type of the object is used for comparisons as well:
unsigned long cItem::getID( void ) const { return( type ); } bool cItem::operator ==( const cItem & i ) const { return( type == i.type ); } bool cItem::operator <( const cItem &i ) const { return( type < i.type ); } As the system grows, so will the item class and its members, but it will happen transparently: new things will be added, but the behavior of the previously implemented methods will remain the same.
Item Piles
Joe user would expect an item pile to have the following properties:
- Turning an item into a pile with a single item
- Creating an empty pile
- Removing all the objects from a pile
- Adding a specific amount of a certain object to a pile
- Removing a specific amount of an object (if there are not enough, then mention how many more objects would have been necessary).
- Counting the objects of a certain type.
- Combining two piles together. It is similar to associating to each item an integer (the amount of said item present in the pile). As far as implementation goes, the user will need to access (read and/or modify) at a moment's notice the amount of a particular item present in the pile, which rules out all list containers and their O(n) random access.
A vector where the indices are the item types would be the fastest method, allowing O(1) access, but this approach has two problems : first, item piles can contain as little as a single object, so allocating an array just for one is wasted memory (especially when the vector's length is equal to the number of different items in the game). Second, an item is not just a number: it also has other properties than its type. Having two items with the same type but with different properties in a single pile would lead to big problems (forcing us into a vector of item containers later on). The only way to avoid this is basing the access not on the type of object, but on the comparison functions for the object.
The next best random access time is O(log n), and can be implemented with either sorted vectors or maps (or sets) without any serious memory hits. Going the vector (or set) way would be impractical, because we would have to store item-amount pairs in the container, making the implementation more complex to code. A map, however, works perfectly.
This leads us to the class definition for item piles:
class cItemPack { std::map< cItem, unsigned long > contents; public: cItemPack( cItem & , unsigned long ); void clear( ); unsigned long add( const cItem & , const unsigned long ); unsigned long remove( const cItem & , const unsigned long ); unsigned long getAmount( const cItem & ) const; const std::map< cItem, unsigned long > & getItems( ) const; cItemPack & operator= ( const cItemPack & ); cItemPack & operator+= ( const cItemPack & ); cItemPack operator+ ( const cItemPack & ) const; }; I have chosen to allow only positive amounts of objects. While this could have been useful to represent a NPC merchant's "plans" about what to buy or sell, it only adds unnecessary complication, since in almost all cases an item pile represents a physical entity where negative amounts are impossible. Next up is the implementation:
cItemPack::cItemPack( cItem & i, unsigned long a ) { contents = a; } void cItemPack::clear( void ) { contents.clear( ); } cItemPack & cItemPack::operator=( const cItemPack & o ) { contents = o.contents; return( *this ); } The two constructors, the clear function and the assignment operator are pretty straightforward: there is nothing to specifically initialize. The "from item" constructor showcases the ease of use associated with the map implementation: items can actually be used as indices to access elements of the map. The following function adds a definite amount of a certain object to the pile, and returns the amount of objects after the addition:
unsigned long cItemPack::add( const cItem & i, const unsigned long a ) { return( contents += a ); } A function that returns the amount of a certain type of object could work as well, but it would be convenient if it could be used on a const object. The problem with this is that the [] operator on a map is not a const function, so the code needs to work around this by using a const iterator, setting it to a possible amount of that item in the map, and if the item is not present, return 0.
unsigned long cItemPack::getAmount( const cItem & i ) const { std::map< cItem,unsigned long >::const_iterator j; j = contents.find( i ); if( j == contents.end( ) ) { return( 0 ); } else { return( j->second ); } } However, a little bit more care needs to be taken of the removal function, because we have to check if there are enough elements inside the pile to be removed (you would not want the player to unequip 200 helmets and end up with 199 bonus headgear). The value returned by the function will be the amount of items that could not be removed (because there were some missing):
unsigned long cItemPack::remove( const cItem & i, const unsigned long a ) { unsigned long t = contents; if( a > t ) { contents = 0; return( a-t ); } else { contents = t-a; return( 0 ); } } Also, there are the functions for combining two piles together. The + operator uses the += operator (because it is easier to add objects from one pile to another pile, than adding two piles together into a new one).
cItemPack & cItemPack::operator+=( const cItemPack & o ) { std::map< cItem,unsigned long >::const_iterator i; for( i = o.contents.begin( ); i != o.contents.end( ); ++i ) { add( i->first, i->second ); } return( *this ); } cItemPack cItemPack::operator+( const cItemPack & o ) const { return( cItemPack(*this) += o ); } And finally, in order not to restrict ourselves to these functions as far as reading through the pile goes, I have added a final function that returns a const instance of the map, which can then be used to access directly the data about the various objects (namely through iterators).
const std::map< cItem,unsigned long > & cItemPack::getItems( void ) { return( contents ); }
The Item database
The database will of course be dependent on the data to be stored for each item. For the purposes of this article, the information stored will be the name of the object, a short description of it, its value and its weight. They will be stored into structures, one structure per item:
struct sItemData { std::string name, description; unsigned long value, weight; }; The item database at its core should be an easy means of accessing information about an object based on its type. This leads to the following properties:
- Returning the item data for any given item
- Creating an item corresponding to a given item name To represent the data manager, I've chosen to use a monostate object. It is an object that can only exist in one instance at a time, but unlike a singleton, that instance is not directly accessible. However, it could become useful at a point or another to re-load the object, in which case the new version will simply replace the previous one. As a monostate, the object should have:
- Functions to initialize it (when the program starts)
- Functions to delete it (when the program exits) There is no actual need to turn this object into a class, a namespace will do:
namespace cItemDatabase { const sItemData & getData( const cItem & ); cItem create( const std::string & ); void initialize( const std::string & ); void unload( void ); }; There is an additional concern: exceptions. There are three possible errors in the above functions. First, all functions that require the object to be intialized beforehand cannot fail silently because they need to return something (and it would be a bad idea to fail silently because this can cause bugs). Next, the create function may not find an item corresponding to its argument, it must then have a way to alert the user. And finally, the user might try to get the data for an object that does not exist in the database. This will go through this enum type:
enum eDatabaseError { IDBERR_NOT_INITIALIZED, IDBERR_INVALID_NAME, IDBERR_INVALID_ITEM }; More exceptions may come later on, depending on new behaviors we will implement into the database (such as an IDBERR_OUT_OF_COFFEE if we ever implement coffeemaking solutions).
First, the variables required for the implementation :
namespace cItemDatabase { std::deque< sItemData > item_database_entries; bool item_database_initialized = false; }; The above boolean serves as an indicator to tell if the object has already been initialized. I have chosen to store the data as a deque because it allows a O(1) random access without sacrificing memory usage (we need to store all the objects anyway), and because unlike a vector it does not need a contiguous memory space. The initialization and deletion functions are the following:
void cItemDatabase::initialize( const std::string & s ) { item_database_entries.clear( ); //FILE LOADING SEQUENCE item_database_initialized = true; } void cItemDatabase::unload( void ) { item_database_entries.clear( ); item_database_initialized = false; } I did not write here any actual loading process, because I think it's up to you to choose the one that fits best your style (all of them should be doing the same thing anyway: filling up the deque with the items). The source code provided at the end of the article, however, is fully functional, albeit with the help of a possibly buggy loading system (which is not error-checked at all).
const sItemData & cItemDatabase::getData( const cItem & i ) { if( item_database_initialized ) { unsigned long type = i.getID( ); if( type >= item_database_entries.size( ) ) { throw IDBERR_INVALID_ITEM; } else { return( item_database_entries[type] ); } } else { throw IDBERR_NOT_INITIALIZED; } } The getData function extracts the type identifier of the object and checks if it is withing the bounds of the database, which causes it to either return the correct object, or throw an invalid item exception. Since item descriptions can get fairly large, it is best to return a constant reference of an existing description instead of returning a copy. It is both natural and necessary for the reference to be constant: modifying it would cause bugs in other areas of the code, and the description of an item type is not something that should not be modified from inside the game anyway.
cItem cItemDatabase::create( const std::string & s ) { if( instance == 0 ) { throw IDBERR_NOT_INITIALIZED; } unsigned long i; for( i = 0; i != instance->data.size( ); ++i ) { if( i->name == s ) { return( i ); } } throw IDBERR_INVALID_NAME; } The creation function, as simple as possible : it checks that there is an instance somewhere, then runs through the entire map looking for an object with the same name as it. Naturally, it's a time-consuming O(n) process, so I suggest using it sparingly (it is not meant for mainstream use anyway, only for debugging/cheating/scripting purposes, as name-to-identifier correspondence can usually be evaluated at release time).
cItem cItemDatabase::create( const std::string & s ) { if( !item_database_initialized ) { throw IDBERR_NOT_INITIALIZED; } long i; for( i = item_database_entries.size( )-1; i >= 0; --i ) { if( item_database_entries.name == s ) { return( cItem(i) ); } } throw IDBERR_INVALID_NAME; } The implementation of the above function is quite straightforward: check if the data has been initialized, then run through the entire vector until a match is found, and if there is none, throw an exception.
Conclusion
This six-file coding spree has left us with a basic, yet efficient item system. Applications using this system will be moving around cItem instances without knowing what's inside, and whenever some data is needed, a quick call to the database will bring up everything. Item piles are even more useful than items themselves because they can represent the player's inventory, items on the ground, or any kind of item stack anywhere.
The way the system works is demonstrated in the zip file that comes with the article (see below). The archive contains all the source code in a VC++6 project/workspace, along with two additional files that provide a testing scaffold. The associated executable is a dos console application that loads an object list from a file, and allows you to manage an inventory by adding, removing and looking at things inside.
(Download the source code here)