Improving inventory system

Help and Feedback Code Review
#1

NOTE: Code Review is heavily regulated to prevent threads from being derailed by minimally valuable feedback such as micro-optimizations. Ensure your responses are within the scope of the thread (i.e. you are not here to convince others to code like you – just to objectively improve the original implementation), and if you predict that replying to someone’s post will end up in a long-winded discussion, PM them instead and work with them to improve their post without derailing the thread.

Overview

For my game, I have an inventory system similar to Terraria/Starbound’s where the player has a limited number of slots in their inventory for items, and those slots have a max stack size (configured per item). The inventory is also split into different categories, so players have 40 slots for items, 40 slots for consumables, etc.

Problems

I’m not satisfied with what I have right now. Adding/removing items to/from the inventory takes 0.15 seconds because the server has to loop through each slot, checking both if it’s the desired item so it can be added to the stack or removed, in addition to checking if there’s enough room in the slot to add to or remove from.

I also have issues with verifying whether changes are valid are not. Right now I deep copy the inventory each time a change is going to be made because otherwise I can’t drop the changes if I find the request is invalid part-way through the operation. The alternative is to essentially call the operation twice – one to iterate through the inventory/all items to ensure the request is valid, and then another to iterate through everything again to commit the changes. The operations are already slow, so calling them twice would be bad.

Repro

Repro.rbxl (23.9 KB)

All that needs to be reviewed is in ServerStorage.InventoryService. Everything else is test code created specifically for this repro. There are some clickable buttons in the game which print out inventory state and operation times in the output to show weaknesses of the current implementation.

Desired improvements

I’d like the operations to complete as close to instantly as possible, without having to slowly iterate through the entire inventory for each item I add/remove. I’ve looked through the operations and found a few things that I can make faster, but ultimately I think the largest problem is that I’m iterating through the entire inventory so often. I could maybe keep a hash as well with linkedlists of filled slots per item, sorted by position in inventory, but that would use up a lot of memory.

I’d also like to avoid having to deepcopy the inventory or call operations twice to ensure that they’re valid. I thought of maybe saving the changes the operation needs to make as it’s iterating through, and if the request is valid, loop through those changes at the end and commit them, but worst case this is still as bad as the current approach. If I’m adding a bunch of different items or most slots are already full and I have to split over a large number, I have to iterate over most/all the inventory.

Any suggestions for how I can improve these? Main focuses are the two issues mentioned, but feel free to comment on anything else you see that could use improvement.

7 Likes
#2

Is that 0.15 seconds from latency or the time it takes to loop?

I’d recommend you do checking both on the server and the client, and have everything visual on the client with just the server doing post-action checks (reverting visual changes when the action was invalid).

I’m thinking you could improve the looping stuff by somehow giving each slot a key (based off the item). If there is more than one item stack, the key has a number appended to it.

Your code would recursively loop through different variations of the key until none are found (e.g. Carrot1, Carrot2, Carrot3).

One issue with this off the top of my head would be how would you handle empty stacks (‘Empty’ key using same append system?) but all of the other issues I can think of have a solution.

1 Like
#3

The timing is only server workload and does not account for replication or anything that happens on the client. Slowness is 100% due to algorithms used on the server.

Creating keys for each item is essentially the same as creating a LinkedList for each item with its slot positions. With that approach:

{2 carrots}, {2 potatoes}, {4 carrots}, {5 apples},
{2 carrots}, {2 potatoes}, {4 carrots}, {5 apples},
{2 carrots}, {2 potatoes}, {4 carrots}, {5 apples},
{2 carrots}, {2 potatoes}, {}, {5 apples}

becomes

{
    {2 carrots}, {2 potatoes}, {4 carrots}, {5 apples},
    {2 carrots}, {2 potatoes}, {4 carrots}, {5 apples},
    {2 carrots}, {2 potatoes}, {4 carrots}, {5 apples},
    {2 carrots}, {2 potatoes}, {}, {5 apples}
},
{
    Carrot = {1, 3, 5, 7, 9, 11, 13},
    Potato = {2, 6, 10, 14},
    Apple = {4, 8, 12, 16},
    Empty = {15}
}

Looking at it written out, the extra memory usage doesn’t seem significant enough to matter. That should work, but I’m open to further improvements.

3 Likes
#4

My idea was more like:

{
    Carrot1 = {Position = 1, Stack = 20},
    Carrot2 = {Position = 5, Stack = 3},
    Empty[1-38] = {Position = ..., Stack = ...}
}

But your solution would probably work better. Yours would also be less data to save too (for lots of items).

1 Like