Auto-organized / smart inventory system?

Question

for the past week I've been working on an inventory system with Unity3D. At first I got help from the guys at Design3 but it wasn't too long till we split path, because I really didn't like the way they did their code, it didn't have any smell of OOP whatsoever.

I took it further steps ahead - items take more than one slot, advanced placement system (items tries their best to find the best close fit), local mouse system (mouse gets trapped in active bag area), etc.

Here's a demo of my work.

What we would like to have in our game, is an auto-organizing feature - not auto-sort. We want this feature because our inventory's going to be in 'real-time' - not like in Resident Evil 1,2,3 etc where you would pause the game and do things in your inventory. Now imagine your self in a sticky situation surrounded by zombies, and you don't have bullets, you look around, you see that there are bullets nearby on the ground, so you go for them and try to pick them up, but they don't fit! you look at your inventory and find out that if you reorganize some of the items, it will fit! - now the player - in that situation doesn't have time to reorganize because he's surrounded with zombies and will die if he stops and organizes the inventory to make space (remember inventory in real-time, no pausing) - wouldn't it be nice for that to happen automatically? - Yes!

(I believe this has been implemented in some games like Dungeon siege or something, so sure it's doable)

take a look at this picture for example:

Yes, so if you auto-sort the issue you will get your spaces but it's bad because: 1- Expensive: it doesn't need a whole sort operation to free those spaces, in the first picture, just slide the red item at the bottom to the very left, and you get the same spaces that you got from the auto-sort. 2- It's annoying to the player: "Who the F told you to re-order my stuff?"

I'm not asking for "How to write the code" for this, I'm just asking for some guidance, where to look, what algorithms are involved? Is this something related to graphs and shortest path stuff? I hope not cuz I didn't manage to continue my college studies :/ But even if it is, just tell me and I will learn the stuff related.

Notice there could be more than just one solution. So I guess the first thing I have to do is figure out if the situation is 'solvable' - if I know how to determine if a situation is solvable or not, then I can 'solve' it. I just need to know the conditions that makes it 'solvable'. And I believe there must be some algorithm/data structure for this.

Here's a pic for more than one solution of trying to fit a 1x3 item:

The arrows show just one of the solutions, but if you look you will find more than one. This is what I ultimately not auto-sorting but find a solution and applying it.

Note that if I spend time on it I will come up with a way to solve it, but it wouldn't be the best way, it's like, holding a car wheel with your feet instead of your hands! XD Or just like trying to solve an issue that requires arrays, but you're not yet aware of their existence! So what is the right approach to this?

Updates from Commentary

@Stephen I'm really no guru in Alogs, you mentioned 'knapsack' and @BlueRaja - Danny Pflughoeft mentioned a 2D bin packing algo. Are they somehow related/same? - I'm still confused as to how should I approach this.

And yes I'm already using a "heuristic" but I didn't really know that I was :D it finds the first available slot, and see if the item fits there.

I don't know if ordering items based on their "bulkiness" (which I call nSlotsRequired=nRowsReq*nColsRec) would work, because you have a 2x2 and 1x4 items for example, they have the same bulkiness, but different shapes and will have a different effect on how the rest of the items next will go. SO... :/

I watched this video, I really liked the full packing idea, but I wonder how to go about it since the inventory is 2D. I'm not even sure that bin packing is the key here because, well it's true that I can have more than one bag, but in our game it's just gonna be one bag. So, it's a matter of fitting items in 'one' bag and not more than that. So the examples in that vid (the pipes and buses) don't really match with my problem. Also watched some stuff about this knapsack thing, I didn't see how the 'value' is related to my items/inventory, but I guess 'weight' is the same as bulkiness, not sure.

Answer 1

This is a variation of the knapsack problem. As Danny Pflughoeft mentions it's NP-Complete. Meaning that it can't be solved in linear time, if I remember correctly.

But you can try to solve this in several steps. It's basically a sorting problem.

I would start by calculating the 'bulkiness' of each item: this could be calculated several ways:

• bulkiness = max(length, width);

• bulkiness = length*width

• bulkiness = sqrt(length*width)

Then start putting items with the highest score first into the inventory. Since they most likely won't fit into the remaining space later. Small items will fit always.

You need an heuristic (a fancy name for educated guessing ;-) ) for your placing strategy. Something like trying to fit items in the first free slot from top-left or something.

Diablo II inventory sorting strategy worked somewhat similar I think. Stuff like swords and spears would end up top left, then clothes and armor, then buckler and so on.

I think you really need to try this out and tweak the algorithm (different bulkiness calculation, different heuristic), until it works reasonable enough.

Answer 2

Haha, @Everybody who helped, thanks. I managed to finally solve it. Here's what I basically did:

IEnumerator AddItem_Sorted (Item item)

1. Trivial condition: check if we got the min nRequiredSlots for the item to fit in, if we do have it, proceed...
2. we'll empty out all the bag - putting the items in a placeholder (list or something)
3. add the wanted item to the VERY last slot/place it could fit in, making sure it's sure in its horizontal shape
4. using the first-fit decreasing algo we'll add the rest of our items
5. during the adding, we'll use dynamic programming (memoisation) to remember that index that we're adding at (index of next available slot)
6. if all adding is success, we have managed to fit our wanted item, and somehow sort the bag - from big to small items
7. if we couldn't add all the items, this means that, this wasn't a solvable situation, so we have to get the bag to its previous state
8. one way to do that, (came out of my mind's surface), is to copy the state of the bag before this whole opperation, and then if it fails we'll snap to that previous state, or even better, in during the 'emptying' of the bag, we memorize where each item was, so that if the op fails, we'll get them back - using AddItem(item, index) - at their previous indices :)
9. this whole process might take time, so we could divide the load on separate frames, using my lovely yield :)
10. DONE! \m/ (@~9:00)

UPDATE:

1. I made an array that stored the indices of all the added items, that way I don't have to go and look for the occupied slots for me to free - big boost.

2. no need to add at the last slot, in fact sometimes it might not work that way, I've added the wanted item to the rest of the other items and sorted it with them.

As you can see from the video, it needs a bit of optimizing, the sorting is not perfect, I would like to use full bin packing, but it's already performance-greedy. I'm open to any optimization suggestions, thanks again :)