Grided Inventory

I haven't played Diablo but a quick look at treemaps seems to indicate they involve displaying a tree structure in a compact space. Presumably you're inventory isn't going to be huge so I'd think the easiest way is just to have an array for the grid. Then something like for the top left corner of an item, store the item ID, and for elsewhere in the items area, store something pointing to the top left corner. Then you just need an ID for empty space.

Thanks for your reply. I have a prototype working much in the same way you have described. This all works nice assuming that the user is the only entity that interacts with the inventory. Meaning the user always drag/drops items into specific location(s) within the inventory grid.

But what I am really getting at is the ability to logically sort the inventory when auto adding an item so that space is optimized. This is where the Treemap comes into play.

Charles P.

From my brief look at treemaps they seemed to be able to vary item size. What you're talking about it called (I think) the rectangle packing problem. I don't think there's any known algorithm so you might have to do this by brute force, which could be practical or not depending on the number of items. There probably are heuristics for it though. All of the games I've played using that system did this by packing objects in the first available space until you couldn't fit in some object or other, but that can get pretty annoying when you have to rearrange you inventory and start dropping things and picking them up again to get everything in.

That is what I was thinking about doing in the first place. Then someone brought up Treemaps.

I guess the most logical way would be to do a little sort of inventory items by "size" and then start pluging-in the big items first, then move to the smaller items. I would assume that this would limit the number of places where large empty areas would appear simply because of grouped odd sizes.

Thanks again Z!

Charles P.

Why not simply add a "Type" variable in every item...?

then use qsort to sort the items based on type...

:)

After you've sorted, simply assign each item a place in the inventory.


There's really no need for "advanced" things like treemaps etc when you're talking diablo stuff. hehe. :)

OK, I don't get it.

How is an items Type going to sort things based on their size? Size is essentially the key property in this sort of situation. But perhaps I am just thinking of the problem from the same angle as you. Please explain.

Quote:

Original post by Rasmadrak After you've sorted, simply assign each item a place in the inventory.

The problem is that that is not simple at all. What if the last item on his list is very large and there is not a space large enough for it?

(Moving this to Game Programming as it's a data-packing question rather than a graphics question).

I'm not sure if this'll help. Maybe it'll spark some other ideas. This is not fully-thought out yet.

What if you were to use recursive calls and solve the 'suitcase' problem in terms of smaller chunks? Start by first sticking in the largest object as you said in one of the corners of the grid.

xxxxooooooo
xxxxooooooo
xxxxooooooo
ooooooooooo
ooooooooooo

(x = object; o = empty space)

Then use the size bounds of that object to break the 'suitcase' into a smaller area or board and get some algorithm going to optimize the packing space (maybe keep track of the best packing scenario by tracking the lowest # of unused spaces). I dont think it's very efficient or elegant but it's the only thing I could think of for solving this.

xxxxooooooo
xxxxooooooo
xxxxooooooo

OR

xxxx
xxxx
xxxx
oooo
oooo

If you make two basic assumptions, that you can't rotate items, and they they are all rectangular x by y items, with no weird shapes, then you can just sort them on size and start packing them in, largest first.

If they have odd shapes, or you're allowed to rotate them, then you'll have to use treemaps.

KSops idea seems to be the basics of Treemaps. Break the remaining areas into smaller parts. While not completely like Treemaps it is similar.

I am not going to assume at this point that items will be squares. However I will assume that they are all going to be rectangles and rotation is not an option.


Charles P.