Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

WebsiteWill

Database Design Questions

This topic is 5379 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello again. I am currently trying to come up with a good database design to be used in storing all of the items in a game. I am currently thinking along these lines. I will have a master list of items. Each item in the list has a unique key and name as well as a weight, and any other stats common to ALL items. Now, some items will have various stats that other items will not have. For instance, weapons will have an damage and speed factor while armor items will have AC factor. Containers will have a capacity attribute. I don''t want to simply include ALL possible attributes into the main table because this would amount to a LOT of wasted space. To accomplish this I am thinking that weak entities could be a way to go. This way if an item has defensive stats and magical stats then there will be a record in the weak entity defensive stats table for it''s defensive stats and a record on the weak entity magical stats table for it''s magical stats. This seems like it may work well for the master items list. However, considering that multiple players can have multiple instances of the same item (playerA has 2 broad swords and playerB has 3 broad swords) and each of the swords may have a different quality or durability value but are otherwise the same. I can''t think of an effective way to store this kind of information into a MySQL database. Players will have an inventory consisting of weight. So the number of items a player can have depends only on the sum of all his items weights. Therefore, a player inventory table needs to be able to adapt in size according to the number of items owned. Likewise, if he owns 2 broad swords one with quality 5 and another of quality 10 then these are obviously distinct entities (they would be even if they had the same quality). But, so far the only identifier I have is for a generic broad sword item. Seeing my troubles here? This is really boggling me. I am currently thinking of a single large player inventory table that holds every item owned in the game and each item is indexed by PLAYER_ID, ITEM_ID, ITEM_INSTANCE So this table might look something like this PLAYER_ID ITEM_ID ITEM_INSTANCE 001 0004 01 001 0004 02 002 0004 01 When a player loses an item then it removes this largest ITEM_INSTANCE first. Now, if all items were exactly the same this would work well. But since each instance might have a different quality (or some other uniqie stat) then I would have to include ITEM_QUALITY (or other stat) into the primary key so that I can be sure to delete the correct item if the player loses it. This also would work except for the many cases where an item won''t have a quality associated with it. Things like bottles of water come to mind here. I don''t want to add extra fields to every item when many of them won''t be needing the fields. So for the master items list I am making a table that includes fields for all stats shared between every single item (ID, NAME, WEIGHT, TYPE are some). Then maybe a weak entity for defensive stats, one for offensive stats, one for magical effects. This way, I will have an offensive stats table that can be queried to get the offensive stats of a broad sword if the broad sword has offensive stats. This seems like it will be efficient on storage space except that I am making defensive stats a table for all stats. So if a breastplate adds 3 to strength then it would create an entri into the defensive stats table that has 3 in strength and 0''s everywhere else. This isn''t a good use of space but the other alternative i can think of would be to make an individual table for every possible stat I will need and is an item has multiple stats then it will be listed in multiple tables... I''m hoping for some ideas of a better way to accomplish this. What would be nice would be to see how other people have done this, EQ, DAoC, AC some to mind but I know that will never happen Any input is appreciated. Thanks, Webby

Share this post


Link to post
Share on other sites
Advertisement
Hi,

For your problem, what could be less buggling could be to replace this long primary with a new generated key. The item should be separated in their type and instances where there could be several type of items that can have several instances of them in the world each with a definite primary key not dependant on who does have it, where it is or what it is doing. That way, you will be able to use that key even when the item is transfered from one player to another.

Composed primary are often replaced with a less complicated generated key, like a serial number.

ZixThree

Share this post


Link to post
Share on other sites
So you are saying that instead of using something like
NAME, TYPE, QUALITY as the primary key I should just include a new attribute of say ITEM_ID and use that as the primary?

Then just keep one LOOOOONG list of every single item in the game? This way, if two players make a trade, all that needs to be changed in the database is that
PlayerA no longer has Item#567876
PlayerB now owns Item#567876
??

This would be nicely efficient. Now, a really long list of ALL items or multiple not so long lists of items arranged by type (weapons, armor, misc) or even farther into (head_items, feet_items, slashing_weapons).

Is there a benefit of arranging items into smaller tables as opposed to a single huge table with regards to storage and retrieval?

My initial design was to have a long list of all item templates (items with definite stats) and then in a separate table (actual item instances found in the game) where all items dropped in the game (player crafted, quested, npc dropped, etc) would need to include the extra dynamic properties in order to uniquely identify the item. A serial number would work nicely here as opposed to a multi-part primary key as long as the time to delete items from the database (when a player destroys or uses up an item) doesn''t get too long. I would obviously need to reuse my serial numbers in this instance. However, considering EQ for an example. Almost every player in the game would hold a stack (20 units) of water or more. Are you saying that each individual water would need a serial number? This seems like it would be better done if the item template were used as well as a simple
PlayerA now has 20-9=11 Waters left
PlayerB now has 1+9=10 Waters

I need to read up on database design a bit more so I can make some decisions on how to arrange my data. The master list of templates seems like it would be the most efficient so long as I can make it so that not all items in the list have to share the same attributes (weapons have damage, armor has AC). I''m still thinking of using weak entities for the separate types of stats not shared by all items and seeing how the mapping turns out. Depending on the relationships it may turn out that the most efficient model will be to make a master item list that contains EVERY possible stat and just NULL the attriutes not needed for any particular item, though I doubt this will turn out to be the case.

An easy way would be to just scratch item decay and quality factors all together, but that would just be waaaaay to easy

Thanks for the advice so far,
Webby

Share this post


Link to post
Share on other sites
I don''t know much about database design, but something in your post caught my eye.

PlayerA no longer has Item#567876
PlayerB now owns Item#567876

You probably only have to track the "desireable" items in your game, which turn out to be a very small percentage of overall items. I''m sure that that''s how EQ does it, for example. Most items are run of the mill and the server doesn''t need to care about their ownership history.

Share this post


Link to post
Share on other sites
Performance, and space: you want as much of the former as you can get and use as little of the latter as possible. The latter can be achieved by choosing the appropriate column types and by sharing the same row of a table with as many other tables as need it (rather than entering the same data values into multiple rows). The former is not so easily achieved, and what works for one particular dataset may not work for another. This involves a combination of good design and well-structured queries. Queries can be tested and easily modified as needed. While the DB design can be easily tested, it''s a pain to go back and set up implement a new design if it''s botched.

Trying to map an object-oriented program design to a relational database is a problem to which there is no right answer. As you have already discovered, an RDBMS does not support inheritance. There are several object-relational mapping libraries around, some free, some commercial. I know they exist for C++, but my experience with them has been on the web front using Java. They greatly simplify the task of storing objects in a DB. However, simplification comes at a price, primarily in the form of performace penalties, but also in the form of wasted space.

Working with what you''ve got, there are several approaches you could take. There is a database design process called Normaization. I studied it the first time I had to design a DB and, being a programmer and not a DB designer, found it difficult not to think in terms of objects. When using a relational DB, thinking in terms of objects can hurt you in the performance area. You have to think in terms of relationships.

quote:

I will have a master list of items. Each item in the list has a unique key and name as well as a weight, and any other stats common to ALL items. Now, some items will have various stats that other items will not have. For instance, weapons will have an damage and speed factor while armor items will have AC factor. Containers will have a capacity attribute...

... However, considering that multiple players can have multiple instances of the same item (playerA has 2 broad swords and playerB has 3 broad swords) and each of the swords may have a different quality or durability value but are otherwise the same



The programmer in me sees the same thing you do here, a list of items, and different subclasses of those items. The part of me that has fought with mySQL on a few fronts is seeing item attributes. If you were to do a direct 1-to-1 mapping, you would not have an item table. Each concrete sublcass of Item would have a table, the columns of which would map to all of the storable attributes of that subclass. Depending on how far down the class hierarchy the new attributes go, this could end up with a Sword table and a Container table, or perhaps tables for BroadSword, LongSword, Backpack, Chest, etc... Obviously, this is not the most efficient method.

You could decompose this a bit. Say, have a table for Item, then another table for Sword. The Sword table would have a foreign key that indexes into the Item table. In otherwords, each subclass has a table that only contains the new attributes it defines, and a foreign key that matches a row in the table for its super class. This approach is something I have seen quite often, but again is not always the most efficient.

Now, the above approaches are naive in that we don''t consider dependancies or redundancy. It''s sort of like brute force terrain rendering versus CLOD: the above methods are the brute force technique; Normalization is CLOD. Normalization involves a few steps to get the design into 4 ''Normal Forms'' (First Normal Form, Second Normal Form, Third Normal Form, Fourth Normal Form - there''s also a Fifth Normal Form, but it''s not really necessary). When you start out, your database is not in any of the four forms (theoretically). Your first step, then is to get the design to the First Normal Form.

What you might do in this case is go ahead and make your item table using all of the possible attributes of all possible items as the columns. You would do the same for all of your top-level objects (characters for example). At this level, it''s okay to think in terms of objects because you have to start somewhere. To get to First Normal Form, you would go over each table and identify columns that are redundant, create new tables for colums that are related, and assign a primary key to each row. When you have met the all 3 criteria, then you have a DB in First Normal Form. From here, you follow more criteria to get to the Second Normal Form and so on to the Fourth. At the Fourth Normal Form you can consider your DB ''normalized'' and stop.

I don''t recall all of the criteria for each Form, as I haven''t designed a DB (formally) in a while. I suggest you do a google for ''database normalization'' or ''database design normalization'' to find more detail on the process. In the end, you''ll wind up with tables you (probably) wouldn''t have expected to have. And you can be fairly confident that the final design will be just about as performant as it can be (YMMV, of course).

Share this post


Link to post
Share on other sites
Normal Forms sound pretty nifty. This would definitely allow me to get a broad view of everything the game would need (character, NPC, item, spell, account, quest). Pretty much every major noun that''s mentioned in the development of a multiplayer game

From there, if moving into the next normal forms will allow me to streamline the database then that''s what I need.

Heck, it may (doubtful) be the case that simply having a massive ALL POWERFUL ALL INCLUSIVE items list would be sufficient but I can see ways of speeding that method up already. It''s a good enough, or even a best way, that I am searching for.

Thanks much. I now have something solid to Google for

Webby

Share this post


Link to post
Share on other sites
Hmmm. As I struggle with this and tables grow infinitely large, I begin to wonder if my approach is correct.

I have an idea and design of what kinds of items are in the game. Some instances are character, equippable_item, ownable_item(but not equippable), spell, weapon, armor, city, zone, npc, etc.

Each of these items is essentially an object with many stats. Many of the stats are objects in themselves, many stats have multiple values (possibly of the same thing). Like, character can have a stats object and a saves object and an inventory object. The inventory would contain items (and duplicates of items). So I am wondering if there is a systematic algorithm for discovering all of this that is necessary.

So, do I take my design and list all of the major items like PC, NPC, Trade Skill, Trade Skill Recipe, Weapons, Armor, City, House, etc and then break each major category down as far as possible into a table with many columns from which I can begin to normalize into smaller, more manageabe, less data-redundant tables?

Or do I sit around and try to list every specific piece of data that needs to be stored and then begin grouping these pieces of data into the objects that contain them. I know this approach seems back-asswards, leaves to root approachy but my wife made a good point about this method. With a list of all final items (leaves of a tree) it could be easy to see where the leaves belong.

Dunno. I progress each time I work with it but something always pops up that makes me go "Ahhh BALLS! another snag". The latest of which was this scenario. Here I am trying to come up with all columns necessary to represent a Dynamic_Object in the game. These are things like houses, trees, boulders and other non-mobile items that players can interract with and would include stats like type, hitpoints, number of rooms, layout, etc. Everything that may be necessary for the item functionality I have planned. Then I thought, well a forge would fit this category. It has hitpoints (if we allow players to destroy them) but it also has the ability of being used to craft items and as such will have slots which players fill with items before hitting a combine button. Thus, is this the same type of item as a house would be. And then I ponder whether I need to make another item type called maybe tadeskill_containers. Then for that matter, a house and a tree are functionally different. Players can click on, attack, enter a house. But they can only click on and attack a tree.

As you can see, it''s extremely difficult to know when you have a good object and when a new object type is in order.

I still think that coming up with the main object types in the game would maybe be the best way towards a good design. After that, it may become apparent which main objects share similar stats and which ones would be best suited to multiple tables.

So...a weary designer reaching out for a glimpse of hope and some nice tips from anyone who has possibly done this sort of thing before.

The normal forms technique will be a great help but not until I have a grasp of exactly what information I will need to be storing in the database.

TIA
Webby

Share this post


Link to post
Share on other sites
That's a given. If you don't know what's to be in the DB, then you can't very well design the DB

But again, you are still thinking in terms of objects. I had assumed you already knew what was going into the DB when I said:
quote:

At this level, it's okay to think in terms of objects because you have to start somewhere



However, since you haven't gotten that far, IMO you should either 1) not touch the DB until you have everything laid out in the Game Design or 2) don't think in terms of Objects at this point when thinking of the DB. Remember when I said to think in terms of attributes?

Let me relate a little RL experience. My first serious DB design (as in more than just one or two tables) was for a web application that would support pontentially a few hundred thousand members, and 4 member account types (not counting admin). Each account type had varying degrees of information associated with it and a number of features that could be used soecifically by that account type. Once account type had gobs (and I mean oodles & oodles) of data associated with it, and would be searchable by other account types to varying degrees (confused yet?). Add to this a point system which would be used to access certain site features (points that could be excahnged for cash, frequent flyer miles, and other forms of 'virtual cash'), a voting system, a natural language search (in Korean even!)... and I started out as the only programmer/DB guy!

Needless to say, I struggled with the DB design for what seemed eternity. The data set was enormous. I was constantly torturing myself over speed vs. space concerns. The design of the app itself was a cakewalk by comparison. And I started out using my OO app design as a basis for the DB design. After several attempts, I stepped back and looked at the problem differently. Instead of worrying how to represent my app objects most efficiently in the DB, I asked the simple question, 'What data do I need to store?' From that point, I made a list, made an initial naive design, then went through the Normal Forms. The final design came after 2 complete revisions and then some modifications at the advice of a couple of experienced DB guys I know.

Get my point? As you add items into your game design, keep a seperate list of the data you need to store. Once the game design is complete, you should have a nice list of all of the data in a format that does not induce an OO mindset. Divide that up however you will (the game objects will be barking at you from the back of your mind - don't totally ignore them as it will aid you in grouping data into the initial tables, but don't heed them completely!), then start the normilzation process.

DB design is truly an exerice in patience. I would even go so far as calling it an art (at which only the truly eccentric excel). I would never wish to work as either a DB designer or admin, but in the limited experience I have had with DB design I have learned the following:

1) In most cases, it isn't as difficult as you make it out to be.

2) There's never a right way to do it (normalization zealots would give me the old William Wallace treatment for that one)

3) There's always a (or more) better way(s) to do it (depending on how many experts you talk to, of course)

So now that I've proven to be no help to your plight whatsoever, let me advise that you try 2 or 3 different designs, and put them out somewhere for opinions. Maybe search through some DB-related newsgroups and find someone willing to review your initial designs.

Another programmer told me once to think in terms of a tree. Each root table stores data that is shared by no other table. Some of the data can be grouped into sub-categories, which qualifies a new table (branch, or node). The root will contain a foreign key to this branch. The new table will also branch any needed sub-categories and retain the appropriate foreign keys. A leaf in this scenario is a table that cannot be branched. He was fixated on this tree idea and religiously argued that it is the best for DB searches. In essence, I see it as just another way to look at Normalization. It accomplishes the same goals, for the most part (albeit the perspective is skewed and the results won't always be the same). Regardless, it's another way to look at the problem.

[edited by - aldacron on September 26, 2003 12:19:33 PM]

[edited by - aldacron on September 26, 2003 12:20:00 PM]

Share this post


Link to post
Share on other sites
So Webby, are you ending up using MySQL then? I''m looking at it with great interest (in fact, I''m already using it as my database tenatively), but I''m not sure about the GPL license. My read on it (and this is only what I *think*), is that I can use MySQL as a database for my server without the project falling under the GPL license, since the server will not be distributed, and thus no MySQL code goes out to the clients.

However, the client will be distributed (obviously), so it could not use a MySQL database lookup (not that I want it to). But the whole thing is a bit murky, since the client logs into the server which uses MySQL to collect data to send to the client. So I''m not entirely clear on the legalities, heh.

Also, I''ve heard some not so good things about MySQL++ (the C/C++ interface). The impression that I''m getting is that it''s buggy. Anyone have further info?

[Sorry, I don''t mean to hijack this thread. It''s a very interesting read, and I''m interested to know how thngs turn out for you. I''m dealing with many of the same issues right now myself. My solution so far (in case you are interested ) involves seperate tables for various classes of generic items, such as melee weapons, all of which have the same attributes (thus it keeps the NULL entries down to a minimum). So far I have tables for melee weapons, ranged weapons, consumables (food, water, potions, etc), and armor (there will be more to be sure). Each of these generic tables has entries that describes a class of items (such as broadsword, shortsword, longbow, and so on), which includes its generic name, weight, base damage, and the index (which is the primary key for that table)), and whatever else the class of items have in common. Then I have a single table of all the specific items that exist in my game (i.e. broadsword #23576) which includes a primary key index, a foreign key into one of the generic tables (and *which* table it uses), and modifiers to the characteristics of the item (such as added damage, condition of item, a text input for player descriptions (ala AC item descriptions), where the item is (or who it belongs to), etc). In my system, stacks of items are regarded as a single item (I have a stack number entry in the specific item table, as well as a max stack number in the generic lists). The generic item tables are pretty easy and straightforward, I''ve had no problems with those so far. The specific item tables are giving me fits, however. The biggest problem I''ve run into so far is temporary modifiers (like spells). You mentioned you played AC, so you know that it is very common to cast multiple spells on a weapon (for instance) to increase it''s damage, speed up its attack rate, and so on. That''s the part that''s giving me trouble, because how do you store these variable number of modifiers on the item in a table? I''ve been toying with the idea of putting the effects of temporary modifier items (like spells and potions and the like) into a separate table with a foreign key into the specific item list to show what it belongs with, but I haven''t got it entirely worked out yet (one issue, for instance, is what if the effect affects a player rather than an item? Sheesh). Oh, and "items" (i.e. defined in my game as "things a player can pick up") is the only thing I''ve worked on database wise so far (except for player character data, which is trivial in comparison). So I haven''t really gotten as far as you in dealing with some of the issues you are talking about. Actually, I don''t mean to give the impression that I''m even very far along with the Items I have the tables designed and populated somewhat, and the specific items table populated with some test data, but nothing is integrated into the server code yet, I''ve not even installed MySQL++ at this point.]

-Ron

Share this post


Link to post
Share on other sites
Hey Ron

In regards to MySQL nd the GPL, you are 100% correct. If you are making a client/server game, you can use MySQL as the backend database for your server. So long as you do not distribute any part of MySQl to your clients. Also, your clients will NEVER EVER directly query the database for any reason. Allowing such actions is one apical tip in the roots of all game programming evil However, you may allow clients to send requests to the server that will then cause the server to access the database for some reason. This is all fine and good and is allowed by the liscense. I researched this and that is the 100% consensus from all people (professors and an actual attorney) who I have spoken with. So feel free to use it for your server.

Now, to the design, I think I am getting some where. Like you, I term game "Items" as anything a player can pick up and put into inventory as the rightful owner. These items will very over everything from looks to the numbers of stats. It''s that very thing that is the hardest to grab. For now what seems like it may be working out (ER diagram wise) is something like this.

Entity = Generic_Item
Generic_Item Attributes = ID, Name, Weight, etc.
Include here EVERY attribute that ALL items will have in common.
Now, say some items have bonus stats (strength, stamina for examples from the traditional RPG). This will lead to a new entity I call
Generic_Item_Stats
This will have attributes like (Strength, Stamina, etc).
Between Generic_Item and Generic_Item_Stats is a relationship I call
Has_Stats
Make other entities for Saves, Procs, User_List, and anything else that even a single item may have that not all items share. If necessary (to save even more space possibly) you can group the stats into single tables
Strength, Stamina, etc in their own tables. This way, if an item only has one stat then you won''t have null values in all the unused stat slots.
After you get these entities and relationships you will be able to decide the participation levels (1,1 or 1,N or N,M)
Once done with all entities, relationships and participations, you will find it pretty easy to map these into what will actually be your tables in your actual DB. Keep in mind, that just because you have a block in an ER diagram doesn''t mean it will work out as it''s own table. It all depends on the participation levels. But from there you can see if the design is working out or not. So far it is going well for me.

Mayhaps I will post my entire database design at some point. Or at least some example of how one could be designed.

So far, this approach is working nicely for me. A good database design book has helped out a lot as well.
Also, I use a nice program called Wizflow for playing around with my Er diagrams. It''s very intuitive and perfect for drawing ER diagrams or any kind of flowchart. Been using the evaluation version for a while but bought the license tonight because it is completely helpful for this kind of designing and it''s pretty much the cheapest to be bought. Imagine that, one of the best diagramming packages being the cheapest as well! And, no, I''m not affiliated with Wizflow at all. Least, no more than the fact that I am using it for my designs.

Anyway, we should keep in touch. We can maybe gleam some insight from one another from time to time.

Peace,
Webby

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!