Sign in to follow this  
formalproof

Comment my RPG data organization plan

Recommended Posts

I'm trying to outline the data structure plan for my rpg. This is my first ever large-scale game, so I'm not sure at all on how to do this. I'd still like to get it right the first time though, so please comment my plan and tell me what you think. I'm using C++/Allegro and the game will be a tile-based RPG. First of all, I wanted to avoid using pointers too much. Instead, I have every game object stored in a std::map, and give each object a unique key which I use instead of a pointer. The reason for this is that I think using pointers would be error prone, and string keys are easier to save to the disk than pointers. I couldn't find out what the complexity guarantee for accessing an object in a std::map through it's key, but I'd guess it's almost constant, so it shouldn't be much slower than using real pointers? Second, I'd like to store all the game objects currently present in the game world in a single std::map, and then I have their keys placed in whatever other containers they should be in, such as the player's inventory, a map tile, active monsters list, etc. Is there something wrong in using this kind of giant master object collection? I'm not yet sure how many objects there are going to be in the game, but if it's not millions, I don't think using a giant collection would be too slow? I think std::map keeps its elements sorted somehow, but will the slowdown would be noticeable? Third, I don't want to create lots of separate classes for things like weapons, potions, etc. Instead I have just one Item class, and each item has a effect script according to it's type (e.g. a weapons effect script is "increase players attack rating by "2d6+1" or something like that.) This is because I don't want to write a new C++ class each time I create a new item/monster type. --- Data Structures: GameObject - a parent class for all game objects (excluding map tiles.) - derived classes: Item (item's which can be picked up), Character, Effect (objects which cannot be picked up but which can affect characters, such as missiles, fireballs, portals, etc.) Character - a base class for all object's which have an AI (plus the player class) - derived classes: monster, npc, player, etc. MapTile - a class representing a tile in the game map. Has a vector for storing the keys of the objects which are located in the same map position as the tile. Sprite - graphical presentation of an object. Each GameObject and MapTile has one. Script - a class representing an effect. E.g. "heal 'player' 10 hp." Probably implemented as just a string in the game's scripting language. When the script is run (e.g. the player uses a potion) a call is made to the game's script processing function with the string as an argument. The script statements will probably be of the form "<effect> <the affected object's key>." If the key of the affected object is not explicitly known, I'll probably use something like "attack 'monster at location x,y'" and leave it to the script handler function to sort out what the monster's real ID is. --- Collections: ObjectModelDataBase.xml - an offline database containing all (abstract) object types and their properties used in the game (e.g. weapons and how much damage they do.) ObjectModelCollection - an online version of the object model database. Probably a std::map with the keys being the object type names, such as "healing potion", "short sword", etc. ObjectCollection - this is the giant master object list I mentioned. When an object is created, it is initialized with values from ObjectModelCollection corresponding to the objects type. GameAreaMap - a 2d array consisting of MapTiles. Plus lots of other collections such as Inventory, ActiveMonsterList, etc. They will propably be implented as std::lists or vectors. --- So that's the outline... Like I said I don't have much game programming experience and I'd really like to get some feedback. It could be that I'm doing something horribly wrong, and I want to notice it now when I'm still in the planning phase. (I'd like to minimize the amount of major rewrites during the game's development.) :)

Share this post


Link to post
Share on other sites
Quote:
Original post by formalproof
First of all, I wanted to avoid using pointers too much. Instead, I have every game object stored in a std::map, and give each object a unique key which I use instead of a pointer. The reason for this is that I think using pointers would be error prone, and string keys are easier to save to the disk than pointers.

I couldn't find out what the complexity guarantee for accessing an object in a std::map through it's key, but I'd guess it's almost constant, so it shouldn't be much slower than using real pointers?

Second, I'd like to store all the game objects currently present in the game world in a single std::map, and then I have their keys placed in whatever other containers they should be in, such as the player's inventory, a map tile, active monsters list, etc.

Is there something wrong in using this kind of giant master object collection? I'm not yet sure how many objects there are going to be in the game, but if it's not millions, I don't think using a giant collection would be too slow? I think std::map keeps its elements sorted somehow, but will the slowdown would be noticeable?


Although starting from a good intent (avoiding pointers for purposes of easier serialization and avoiding errors), your implementation will cause more problems than it solves. First, to address your question, accessing memory within a map is logarithmic, meaning that although it's not very important, the time required to retrieve an object will still increase as the total number of objects increases. A hash-map would work in constant time. However, all of this ultmately still adds an important constant factor to any accesses, especially if working with string keys. Remember, "ten times slower" is a constant factor, but not one you'd like to see crop up ten thousand times per frames.

To implement polymorphism, you will still have to use pointers in your map, meaning that you will not eliminate all serialization difficulties related to pointers (though you will certainly eliminate some, such as multiple references to the same object).

Pointer errors usually come from accessing an object that doesn't exist. Using maps doesn't solve this problem, since you can still attempt to access a key that does not exist. This problem would thus be more easily solved with a smart pointer class that prevents dereferencing null pointers (and also handles serialization).

Last but not least, how do you generate new names for your objects, for instance when casting or other automatic object creation behaviors? Generating a pointer is easier than generating an integer, which in turn is easier than generating an unique string identifier.

Ultimately, the master object collection does not gain you anything over using plain old reference semantics with adapted safeguards in a smart pointer class, so I would suggest using the smart pointer class instead, and dropping the idea of the master collection. Beyond a psychological "feeling safe" effect, there is simply no design benefit to using one here.

Quote:
Third, I don't want to create lots of separate classes for things like weapons, potions, etc. Instead I have just one Item class, and each item has a effect script according to it's type (e.g. a weapons effect script is "increase players attack rating by "2d6+1" or something like that.) This is because I don't want to write a new C++ class each time I create a new item/monster type.


Yes, this is a good idea, as long as you realize that you will still need a new C++ class every time you create a new script.

Quote:
GameObject
- a parent class for all game objects (excluding map tiles.)
- derived classes: Item (item's which can be picked up), Character, Effect (objects which cannot be picked up but which can affect characters, such as missiles, fireballs, portals, etc.)


What's the point of having a base class for all of these?

Quote:
Character
- a base class for all object's which have an AI (plus the player class)
- derived classes: monster, npc, player, etc.


Yes, seems correct to me.

Quote:
MapTile
- a class representing a tile in the game map. Has a vector for storing the keys of the objects which are located in the same map position as the tile.


A tad inefficient. You might wish to consider a sparse layer-based approach to objects, since in most cases only a handful of tiles in an entire level contain anything. So, keep a layer for tile information (such as aspect) and another layer for contents.

Quote:
Sprite
- graphical presentation of an object. Each GameObject and MapTile has one.


This sounds acceptable.

Quote:
Script
- a class representing an effect. E.g. "heal 'player' 10 hp." Probably implemented as just a string in the game's scripting language. When the script is run (e.g. the player uses a potion) a call is made to the game's script processing function with the string as an argument.


I'm wondering... why not just write your entire game in a scripting language? Since you seem to defer most of the behavior to a scripting language, and there doesn't seem to be any computation-heavy processing except perhaps for a small rendering core, using an existing scripting language would be a superior technical choice.

Quote:
ObjectModelDataBase.xml
- an offline database containing all (abstract) object types and their properties used in the game (e.g. weapons and how much damage they do.)


Writing this directly in a script language would be easier than writing-and-parsing XML.

Quote:
ObjectModelCollection
- an online version of the object model database. Probably a std::map with the keys being the object type names, such as "healing potion", "short sword", etc.


Yes, a typical usage of the flyweight pattern...

Quote:
ObjectCollection
- this is the giant master object list I mentioned. When an object is created, it is initialized with values from ObjectModelCollection corresponding to the objects type.


...except you're not using the flyweight pattern. Why initialize with values instead of simply referencing existing ones?

Overall, planning is good. But don't forget that the choice of tools is important (C++, or a scripting language, or both?), that the difficult tasks are often not those you think (a scripting language, no matter how simple, will probably take longer to develop than to use), and that using the language features (or slightly adapting them) is always an order of magnitude easier than reinventing them.

Share this post


Link to post
Share on other sites
Quote:
Original post by formalproof
I couldn't find out what the complexity guarantee for accessing an object in a std::map through it's key, but I'd guess it's almost constant, so it shouldn't be much slower than using real pointers?

Time complexity should be somewhere around log(n). If you need faster access, you can use a hashmap instead.

Quote:
Original post by formalproof
Third, I don't want to create lots of separate classes for things like weapons, potions, etc. Instead I have just one Item class, and each item has a effect script according to it's type (e.g. a weapons effect script is "increase players attack rating by "2d6+1" or something like that.) This is because I don't want to write a new C++ class each time I create a new item/monster type.

What are those "sripts"? Are you using a scripting language like lua?

Share this post


Link to post
Share on other sites
Quote:


Although starting from a good intent (avoiding pointers for purposes of easier serialization and avoiding errors), your implementation will cause more problems than it solves. First, to address your question, accessing memory within a map is logarithmic, meaning that although it's not very important, the time required to retrieve an object will still increase as the total number of objects increases. A hash-map would work in constant time. However, all of this ultmately still adds an important constant factor to any accesses, especially if working with string keys. Remember, "ten times slower" is a constant factor, but not one you'd like to see crop up ten thousand times per frames.

To implement polymorphism, you will still have to use pointers in your map, meaning that you will not eliminate all serialization difficulties related to pointers (though you will certainly eliminate some, such as multiple references to the same object).

Pointer errors usually come from accessing an object that doesn't exist. Using maps doesn't solve this problem, since you can still attempt to access a key that does not exist. This problem would thus be more easily solved with a smart pointer class that prevents dereferencing null pointers (and also handles serialization).

Last but not least, how do you generate new names for your objects, for instance when casting or other automatic object creation behaviors? Generating a pointer is easier than generating an integer, which in turn is easier than generating an unique string identifier.

Ultimately, the master object collection does not gain you anything over using plain old reference semantics with adapted safeguards in a smart pointer class, so I would suggest using the smart pointer class instead, and dropping the idea of the master collection. Beyond a psychological "feeling safe" effect, there is simply no design benefit to using one here.


Sounds like you're right. Is there some particular smart pointer implementation you would recommend, such as the one in boost?

Quote:
Quote:
GameObject
- a parent class for all game objects (excluding map tiles.)
- derived classes: Item (item's which can be picked up), Character, Effect (objects which cannot be picked up but which can affect characters, such as missiles, fireballs, portals, etc.)


What's the point of having a base class for all of these?


So that I can use one vector<GameObject> instead of having separate vectors for items, characters, etc. for example. Another way could be to have just one object class, and then let it have a member variable which says what kind of object it is. I don't know which way would be the best?

Quote:
Quote:
MapTile
- a class representing a tile in the game map. Has a vector for storing the keys of the objects which are located in the same map position as the tile.


A tad inefficient. You might wish to consider a sparse layer-based approach to objects, since in most cases only a handful of tiles in an entire level contain anything. So, keep a layer for tile information (such as aspect) and another layer for contents.


Do you mean it's inefficient memory-wise? Should I just move the object collection vector to the second layer (the first one being the tile layer), or have a separate layer for each object?

Quote:
Quote:
Script
- a class representing an effect. E.g. "heal 'player' 10 hp." Probably implemented as just a string in the game's scripting language. When the script is run (e.g. the player uses a potion) a call is made to the game's script processing function with the string as an argument.


I'm wondering... why not just write your entire game in a scripting language? Since you seem to defer most of the behavior to a scripting language, and there doesn't seem to be any computation-heavy processing except perhaps for a small rendering core, using an existing scripting language would be a superior technical choice.


Because I don't know any scripting language well enough. :)

Can you recommend me any tutorials/books about organizing a game's scripting system? Right now I feel like writing some custom lightweight script system, perhaps hard-coding more things than I meant to before reading your post, just to get a playable game done quickly.

Quote:
Quote:
ObjectModelDataBase.xml
- an offline database containing all (abstract) object types and their properties used in the game (e.g. weapons and how much damage they do.)


Writing this directly in a script language would be easier than writing-and-parsing XML.


Hmmh, why would it be easier? Reading & writing XML isn't that hard.

Quote:
Quote:
ObjectCollection
- this is the giant master object list I mentioned. When an object is created, it is initialized with values from ObjectModelCollection corresponding to the objects type.


...except you're not using the flyweight pattern. Why initialize with values instead of simply referencing existing ones?


I'm not sure what you meant by "referencing existing ones", but the values (such as a monster's HP) can chance when the game is running. The monster just gets its initial HP from the databank.

Quote:
Overall, planning is good. But don't forget that the choice of tools is important (C++, or a scripting language, or both?), that the difficult tasks are often not those you think (a scripting language, no matter how simple, will probably take longer to develop than to use), and that using the language features (or slightly adapting them) is always an order of magnitude easier than reinventing them.


Just thinking, how do you represent pointers in a scripting language? For example in the script "heal player 10 hp", the scripting system would need to replace "player" with the pointer to the player object. I still need to do much more research on scripting obviously :)

Anyway, thanks for the answers. You've already helped me a lot :)

Share this post


Link to post
Share on other sites
Quote:
Original post by formalproof
Sounds like you're right. Is there some particular smart pointer implementation you would recommend, such as the one in boost?


Depends on your objective. boost::shared_ptr is your elementary staple for developing your game state.

As a whole, don't forget that your game is separated into (mostly) three main sections: the instance data (such as input, network, physics), the simulation data (game object positions, states), and the view data (video and audio entities), but only the simulation data needs to be serialized. Therefore, I usually advise using a serialization wrapper around your smart pointers in the simulation data, so that you can serialize things easily, and using normal smart pointers or even references for anything else.

Quote:
Quote:
What's the point of having a base class for all of these?


So that I can use one vector<GameObject> instead of having separate vectors for items, characters, etc. for example. Another way could be to have just one object class, and then let it have a member variable which says what kind of object it is. I don't know which way would be the best?


The underlying question was, why do you need to have a vector of all game objects? I'd bet my lunch that you don't.

Quote:
Do you mean it's inefficient memory-wise? Should I just move the object collection vector to the second layer (the first one being the tile layer), or have a separate layer for each object?


Yes, memory-wise. Move any sparse data to a sparse data structure.

Quote:
Because I don't know any scripting language well enough. :)

Can you recommend me any tutorials/books about organizing a game's scripting system? Right now I feel like writing some custom lightweight script system, perhaps hard-coding more things than I meant to before reading your post, just to get a playable game done quickly.


Writing a lightweight script system is not easy. I'm an experienced developer and language design is my main field of knowledge, and I would still expect to spend a full-time week to design a relevant script system with an adapted language. You're an inexperienced developer unfamiliar with language design and using tools that are not adapted (in this case, C++), so expect to spend one or two full-time months working on it if you go for any kind of quality. Otherwise, you'll just waste time developing something that's less efficient than writing everything in C++ from the beginning.

Move to an existing scripting language, such as Python or Lua, which are fairly easy to set up and connect to C++ (for instance, using boost::python) and to write code in.

Quote:
Hmmh, why would it be easier? Reading & writing XML isn't that hard.


I didn't say it was hard. I said it was harder. If you use your scripting language to set up objects, all you have to do is run your script through your existing interpreder.

When working with XML, you have to set up an XML parser (or develop one yourself, if you're crazy), possibly also set up a DTD or schema to test the validity, and then write an entirely new set of binders to match XML data with program data, even though that set of bindings was already present in the scripting system.

Quote:
I'm not sure what you meant by "referencing existing ones", but the values (such as a monster's HP) can chance when the game is running. The monster just gets its initial HP from the databank.


I see. My mistake.

Quote:
Just thinking, how do you represent pointers in a scripting language? For example in the script "heal player 10 hp", the scripting system would need to replace "player" with the pointer to the player object. I still need to do much more research on scripting obviously :)


It usually happens by binding host-language pointers to script-language global symbols. For instance, the globally accessible symbol "player" in your scripts is bound to the current instance of the Player class. That, or you can bind classes, meaning this. will refer to the same object both in the host- and the script-language.

Share this post


Link to post
Share on other sites
Quote:
Original post by formalproof
Sounds like you're right. Is there some particular smart pointer implementation you would recommend, such as the one in boost?


The Boost smart pointers come highly recommended.

Quote:
Quote:
Quote:
GameObject
- a parent class for all game objects (excluding map tiles.)
- derived classes: Item (item's which can be picked up), Character, Effect (objects which cannot be picked up but which can affect characters, such as missiles, fireballs, portals, etc.)


What's the point of having a base class for all of these?


So that I can use one vector<GameObject> instead of having separate vectors for items, characters, etc. for example. Another way could be to have just one object class, and then let it have a member variable which says what kind of object it is. I don't know which way would be the best?


That's missing the real point of the question - why do you want absolutely everything in one vector? When would you ever need to search a single structure for something that might be an Effect or an Item?

Quote:
Can you recommend me any tutorials/books about organizing a game's scripting system? Right now I feel like writing some custom lightweight script system, perhaps hard-coding more things than I meant to before reading your post, just to get a playable game done quickly.


Unfortunately, integrating scripting is not trivial, unless you go with an existing language, and even then there are a fair few issues to bear in mind. Typically you have methods on your game objects which you choose to expose to the scripts, and the scripts manipulate the game through those exposed methods.

Quote:
Quote:
Quote:
ObjectModelDataBase.xml
- an offline database containing all (abstract) object types and their properties used in the game (e.g. weapons and how much damage they do.)


Writing this directly in a script language would be easier than writing-and-parsing XML.


Hmmh, why would it be easier? Reading & writing XML isn't that hard.


Because it's far easier to write a structure out once, than to have to write it twice (once in code and once in XML) and handle the code that transfers one to the other.

Quote:
I'm not sure what you meant by "referencing existing ones", but the values (such as a monster's HP) can chance when the game is running. The monster just gets its initial HP from the databank.


The idea would be that you separate out attributes that can change from those that cannot. Those that cannot, you reference, thereby sharing that data across all instances.

Quote:
Just thinking, how do you represent pointers in a scripting language? For example in the script "heal player 10 hp", the scripting system would need to replace "player" with the pointer to the player object. I still need to do much more research on scripting obviously :)


Typically you'd have injected an object called 'player' into the script context, and when you call heal() on it, that object stores a value that corresponds to however you look it up in your code, whether that's a pointer, an ID value, whatever.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this