2010
06.11

Even if I’m only at the first steps of the first chapter of the last doryen prototype (!…), I already need more advanced stuff in the core engine than what I had in the latest versions of TCOD… Funny how things never seem to be complex enough when you code a roguelike….

The basic item

This is always around the item core class. For a basic game like Pyromancer, items contain only the item specific data. Hell, pyro doesn’t even have an inventory. Items are used and destroyed as soon as you walk on them…

class Item {
};
class Weapon : public Item {
.. weapon specific data
};

Hard stacks of items

But as soon as you have an inventory, you have to think about item stacks. If your inventory simply display the items in a list, you can have lots of redundant items. For some complex item classes like weapons, this can be acceptable, but for basic items like ranged weapon ammunition (arrows and bolts), you certainly don’t want to list each one independently…

an arrow

an arrow

an arrow

… (repeat 100 times)

Of course, you want to see all arrows as a single stack of items :

100 arrows

Also, in term of performance and memory, it’s certainly better to have a single Item instance with a count of 100 rather than 100 instances. So you add a count member on the item class.

class Item {
   int count;
};

Then it’s only a matter of merging / splitting items when you pick up or drop one.

Picking up :

if the inventory already contains an item of the same type, increase the count and destroy the item on ground

else move the item from ground to inventory.

Dropping :

if count > 1, decrease the count and create a clone with count = 1 on ground

else move the item from inventory to ground.

But you may not want to merge all types of items. If you wear one rusted knife and you pick up an enchanted knife of diarrhoea (target suffers from diarrhoea for 5 sec on successful hit), you don’t want the magic knife to be merged and stored as a rusted one. So you need a flag on each item type that indicates if it is stackable or not.

class ItemType {
   bool stackable;
};
class Item {
   ItemType *type;
   int count;
};

Now picking/dropping operations only do the merge/split on stackable items.

Ok the count member is useless for non stackable items. You could have two inheriting classes StackableItem and NonStackableItem, but I’m not a big fan of Himalayan class hierarchies…

Soft stacks of items

This is what I was using in TCOD but it’s not sufficient. Imagine you have food depreciation. A piece of meat will give you a lot of health points when it’s fresh, but in your backpack, it losses slowly its quality until it’s really rotten and you’d better not eat it or you’ll be poisoned. Since a piece of meat has an internal timer, you can’t merge it with another one (except if their timer match perfectly). Yet, you still don’t want to see :

a piece of meat

a piece of meat

in your inventory. You want :

2 pieces of meat

and if one of them just get rotten, your inventory now contains :

a piece of meat

a rotten piece of meat

That’s what I call a soft stack. In the program memory, the items behave exactly like non stackable items, but in the inventory screen, they look exactly like the stackable ones.Β No merge/split operations here.

What if you want to eat the older piece of meat first ? I think a good solution is to be able to unwrap soft stacks.

+ 2 pieces of meat

click on the ‘+’ button :

– 2 pieces of meat

a piece of meat (rotten in 24min)

a piece of meat (rotten inΒ 12 min)

Of course, unwrapping a 100 items soft stack would be bad. But generally, item count is inversely proportional to its “stackability”. Non stackable items are generally big and you wear only a few of them. Soft stackable items are more numerous, but generally no more than 10 per class. If you walk with 50 pieces of meat in your backpack, there’s something wrong in the game’s balance. Hard stackable items are the most numerous, the king of them being the gold coin (even though wearing 2000 gold pieces in one’s backpack is not very realistic…).

Also note that with the possibility to unwrap soft stacks, you could as well discard non stackable items and have everything soft or hard stacked. But that would represent a lot of wrap/unwrap operations while using the inventory, a bit like using windows explorer and it’s probably better to have the major items (weapons, armors, …) directly accessible as non stackable items.

For soft stacks, you just have to replace the stackable boolean by an enumeration :

class ItemType {
Β Β enum { NO_STACK, SOFT_STACK, HARD_STACK } stackMode;
};

8 comments so far

Add Your Comment
  1. I had a another idea of stack mode. It’s a bit of a mix… Let’s say you have 199 gold coins and one fake gold coin or one cursed coin (idea came from morrowind where cursed coins don’t stack) so it works like HARD_STACK for 199 and SOFT_STACK for 199+1. But you can only see it as a HARD_STACK. If you drop coins then throw a dice,see if that one coin is in pile you want to drop. Buy items with coins and again throw dice to see if the fake coin is in the sum you pay. E.g buying an apple for 1 gold almost certainly will not bring curse of vomitness to you, but buying a sword for 200 will most certainly do that. The same applies for non identified arrow packs. 34 simple arrows + 2 steel arrows (you didn’t notice the difference) +3 arrows of returning (you shoot yourself with these). In short even stacking could lead to a lot of NEW experiences.

  2. These posts are great, you are probably saving me and others from later headaches.

    Warmist, that’s a pretty interesting idea. It would lend a lot of merit to skills based solely on item-identification. Curses could reduce your ability to identify items – maybe you have a stack of “long pointy things.”

  3. 5 seconds of diarrhea, that sounds bad!! Your worst foes in that case would be goblins wearing diapers. πŸ˜€

    Thanks for the post too, you really got me thinking. But, given that you probably don’t really care about the memory occupied by 100 arrow instances, wouldn’t it simplify things immensely to just consider “soft stacks”? Then you’d never have to worry about item counts. Inefficient, yes, but lately I’ve been tending towards less efficiency and more code readability, since by Moore’s Law when my RL is done you’ll be able to run it in your watch, after checking the time of course πŸ˜›

    Taking that line of thinking to the extreme, what about this: items never stack in-memory, it’s just a display thing. Like Google’s approach of “search, don’t sort”! So internally it’s just a big linear list of scattered items. When you open up the inventory, the tree-view that’s presented automatically groups items with the same signature. There are some “stack options”, like “drop some”/”drop all”, or you can expand the node to see them individually and deal with them one by one. So all the functionality is in the tree-view and not in the inventory itself, grouping items explicitly.

    You could define “same signature” as being exactly equal, or simply “looking like the same object”, in my RL that’d be having the same name, display character and color. Since the items inside the stack are easily accessible one-by-one, it’s up to the player to choose actions for the whole stack or individual items inside it. I’ll make an effort to give different names to items that should be functionally equivalent, like “enchanted bronze sword” or “rotten food”. (Hey, gameplay idea: drop rotten food to poison unintelligent adversaries!)

    I had this idea of applying the “search, don’t sort” technique loosely bouncing around my head, but your post provided the structured thinking and insight I needed to formalize this into something useful πŸ™‚

  4. Weird that you’re doing less efficient code, as a python developer πŸ˜‰
    Well, handling hard stack is not a big deal and it really lowers the item count in the game world. You really intend to store 2000 “gold piece” objects in the player inventory ? Or you handle money as a special case (in which case you still doing a hard stack, so why not using it for other object types?)
    I generally try not to do preemptive optimization, but I’m a bit worried about having to update all those items every frame. With its small 400×400 forest map, the cave already has 20 000+ items to handle…. This is due to the fact that I’m trying another experimental approach where everything in the world is an item (trees, doors, walls,…). This will allows nifty things later but it’s a bit heavy on resources…

  5. It may sound a bit goofy, but in my game I’m not planning on having gold coins, they’re not needed as I’m not planning on having shops. BUT it may be a bit unrealistic, in a fantasy setting, for the player to not find any sort of treasure, even if it’s useless. I like Brogue’s approach of treasure counting only for the final score πŸ™‚ But you’re right, this part of my RL needs to be fleshed out a lot more. Also if a player wants to carry 100 arrows in his backpack, it will be full; to counterbalance that, a few well-placed arrows should take out most enemies, I think that 30 arrows on average must be enough. Currently I’m focusing on developing nice melee fight mechanics, so I don’t have a solid plan for ranged combat yet… (damn, you’re exposing all my design weaknesses!! πŸ˜› awesome!)

    Since my maps are always the size of one screen, I don’t have thousands of items in memory at once, but with a freeform system I see why you might bump into performance issues. Out of curiosity, why do you update all items every frame? I went with an event-driven approach, so objects only run some code when reacting to changes; I tried very hard to avoid a generic “every frame” event. When I get to the point where an item needs time-based updates (ie, food rots after 100 turns), I’ll create a time-sorted queue of upcoming events.

    Concerning python’s slowness and my “readability over efficiency” mantra, I’m very selective! The only place where I had a serious bottleneck was rendering, so I needed to obfuscate my code there in order to achieve some speed; that’s why the fill functions were necessary. But everywhere else I like to have my code clean as a whistle, and if I can trade some efficiency for a much more concise and readable algorithm, I’ll do it. Usually this involves integrating some special cases into the generic algorithm instead of treating them differently, even if those could be handled more efficiently. Like this case with the hard stacks… I only waste CPU on them when the player goes to the inventory and interacts with them, anyway

  6. Alternatively could you not just keep the number of item x as an int, then have a method to *create* the object when you use it? Instead of constantly having the object still in memory, you just create it on an “as needed” basis, then decrement “int arrow”.

    Or is that much slower? seems to me like it’d use less ram and more CPU:/

  7. @Jotaf In fact I never considered using a sorted event queue (or rather a binary heap) in a real time game. This is generally used in turn by turn roguelikes but now that you mention it, it would considerably lower the cpu load.
    Something like this :
    http://roguebasin.roguelikedevelopment.org/index.php?title=A_priority_queue_based_turn_scheduling_system
    except that the time is incremented by the last frame length instead of using the first delay in the queue. Then you process all events in the queue that were suppose to happen before current time and you stop when reaching the first event that is still in future.
    Great stuff! Thanks Jotaf, once again, your feedback is priceless πŸ˜‰

    @TSMI : as far as I understand it, what you’re describing is what I call “hard stack”. The object is created when you pull it from the stack instead of creating all the stack objects from the beginning.

  8. Awesome πŸ˜€ I’ll share my impressions when I get to that. In the past I used an event queue (it was an action game) but I ran into some problems when I tried to make the “event actions” too generic (to the point where one of the actions I had available was “modify some object’s property by X amount”). That was a time waster… Today, if I did it again, I’d simply make it wake up the object that programmed the event; it should know what to do. πŸ™‚ (I would also use STL/TCOD lists instead of my buggy home-grown linked list implementation, bleagh! πŸ˜› )