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.
No comments:
Post a Comment