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.) :)

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?

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 :)

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.