What is a good Java data structure to store RPG Game items?

Question

I'm building a RPG dungeon game in Java and I'm stuck on creating a data structure.

I have a lot of Thing objects that I can copy to populate a dungeon with. For instance, there is a bread Thing object, and a sword Thing object, a chain mail Thing object, and monster Thing(s), etc. I want to store them in a central Library and then be able to retrieve an object using certain queries. I want to store them using the following fields:

int minLevel
int maxLevel
double probability
int[] types

So a rusty sword would have a minLevel of 1, a maxLevel of 3, a probability of rarity(3%),and [type.SWORD,type.WEAPON,type.ITEM,TYPE.EQUIP]. A better sword would have minLevel 2, maxLevel 10, rarity (1%).

Then I want to retrieve a random type.SWORD from the library and say I'm at level 3. I should get a rusty sword more often than the better sword based on their probabilities. If I retrieved a type.SWORD from the library requesting level 10, I would only get back the better sword.

I hope this makes sense.

EDIT At the initialization stage, all the basic objects will be created. Things like the available weapons, armor, foods, potions, wands, all the basic possible Things that have a unique graphic tile in the game. Then when I want to place an object somewhere, I just make a copy of one of the available Things, adjust it's stats a little, and plunk it down in the world. The actual items are all subclass of the root Thing class, such as class Creature,Item,Equip(extends Item),Weapon(extends Equip),Armor(extends Equip),Food(extends Item), etc. But I want to tag them different in the Library database, I want to use extra tags, such as type.RARE, type.ARTIFACT, type.CURSED, so I want extra tags besides the class.

The game use LIBGDX to be available on Android and as an Applet. I use the free Rltile set, which has thousands of good tiles. I will use Pubnub or Google App Engine to provide multiplayer support.

Answer 1

i can think of three answers:

1. write your own Library that stores these things in Maps with custom methods. so you might have a Map<Type,List<Object>> that stores lists of things by type and then a method that takes a type, retrieves the list from the map, and selects something by probability (that's easy to do - you just some up the probabilities, generate a random number between 0 and the sum, and then walk through the list, subtracting the item's probability from your random value until it's negative - you return the item that made it negative[*]). you can also filter the list first by level, for example.

   if you have a real mix of different things, and don't want to base this on types, then another option (slower, but more flexible) is to place everything in a list and then filter by your needs. a nice way to do that is with guava - see Iterables.filter and Predicate at https://code.google.com/p/guava-libraries/. you could provide an interface that takes a predicate and returns a random selection from whatever is left after filtering. predicates are easy to construct "inline" with anonymous classes - see examples at https://code.google.com/p/guava-libraries/wiki/FunctionalExplained#Functions_and_Predicates

2. stick all this in a database. maybe i am too enterprisey, and games people would never do this, but it seems to me that a small, embedded database like sqlite or H2 would be perfect for this. you can then select things with SQL queries (this is already a long answer so i won't give more details here).

3. change your design. what you describe is not very OO. instead of having types, your Things could implement interfaces. so the Weapon interface would have a getMinLevel() method, for example. and then, with a design like this, use a database with ORM (hibernate).

what you're doing is kind of ambitious and i suspect is more about learning than anything else (no criticism intended - this is how i learn stuff, by making things, so just assuming you are like me). so choose whichever you feel most comfortable with.

[*] this assumes that you always want to return something. if the probabilities are normalized and you want to be able to return nothing, select the initial value from 0-1 (or 0-100 if using percentages). and, if nothing turns the value negative when you run through the list, return nothing.

Answer 2

The easiest approach is to put all your objects in a single large arraylist, and use repeated sampling to select an object.

The procedure to select a random item is very simple:

1. Select a random number from 0 up to the size of the ArrayList
2. Get the object at that index from the library
3. If the object fails to meet any criteria you specify (e.g. "is a of type.SWORD or type.MACE?") go back to start
4. If the object is outside the minimum or maximum level, go back to start
5. If the object has a rarity of less than 100%, create a random number from 0-100%. If the random number exceeds the object's rarity, loop back to start. Most objects should have a rarity of say 10-100%, if you want extremely common objects then you can add them multiple times to the library.

This procedure will produce an object that meets the criteria sooner or later (if it exists) and will do so according to the rarity percentage.

The one slight trickness is that it will loop infinitely if no such object exists. Suppose there is no weapon in the library at level 17 for example? To get around this, I would propose widening the minLevel and maxLevel after every 100 tries to ensure that eventually one is found. Ensure you always have a level 1 object of each type available.

For safety, you might also want a bailout after say 100,000 tries (but remember to throw an exception - this is a problem if you are asking for things that don't exist in the library!).

P.S. I implemented a similar library system in a roguelike game called Tyrant that I created many years ago. Source is here if you are interersted:

https://github.com/mikera/tyrant/blob/master/src/main/java/mikera/engine/Lib.java