# 2D sort for inventory items?

I asked this question some time ago. Now I ended up with just a sorter method that will sort the items based on their bulkiness/nSlotsRequired. Here's what I'm doing:

1. I store all the items I have in a one-dimensional array.
2. Empty the bag.
3. Sort the array.
4. And start putting them back into the bag again.

Now, this is clearly not the best way to sort something, I mean, if I have an array I wouldn't just store its values somewhere else, empty it, sort the other array and then copy them back. Even if I had a 2D array, I would sort it by considering it a 1D array. 1st element's index is 0, 2nd is 1, 3rd is 2, 4th is 3, 5th is 4, etc.

General formula to convert from a 1D index to a 2D:

• row_index = _1D_index % nRows;
• col_index = _1D_index % nCols;

For example the 5th element has the 1D index of 4, to get the row: 4 % 3 = 1, to get the col, 4 % 4 = 0, so your element is at 1,0. What's the point of all this? Now you can just make a function

int GetAt(int index)
{
return array[index % nRows][index % nCols];
}


and something along the lines of:

void Swap(int index1, int index2)
{
int r1 = index1 % nRows;
int c1 = index1 % nCols;
int r2 = index2 % nRows;
int c2 = index2 % nCols;
int temp = array[r1][c1];
array[r1][c1] = array[r2][c2];
array[r2][c2] = temp;
}


But the problem is: 1- items take more than one slot. 2- Even if I were to just swap them in a way that they're sorted, they still have to get to their positions, I mean, the biggest one would go to the top left, beside it is the smaller, etc.

Taking notice that:

1. I already have an array of the items' indices/places in the bag, so I don't have to look for them.
2. I have an array of the available slots in the bag, that way I don't have to go through all of them to find where items fit. I just start from the next available slot placing the items (I update those arrays everytime I add/remove an item)

is there a more efficient way of doing this? Can I just, sort the items right away without having to empty the bag, store them somewhere else, etc? - It would make more sense. I couldn't think of a way :/ Maybe sort only the items that needs sorting? Thanks for any help.

EDIT: Here's what I have so far (sorting feature @~9:00)

• You could avoid this entire problem by getting rid of the grid and letting the user drag and drop the item anywhere inside the inventory screen, on any pixel coordinate. Then add a text filter so typing in "hand" would only show handguns, or "shell" only shotgun shells, etc... Just thinking outside the box (pardon the pun) for a moment =) – Patrick Hughes Jul 7 '13 at 2:27
• Oh, heh :) That's a very basic feature I have letting the user place items around, swap them, etc. A demo if you like youtube.com/watch?v=J-RxdtzI6Hs. I didn't quite get your text idea though. The whole idea is just to reorder the items in a quick fashion - time is of the essence in our game. – vexe Jul 7 '13 at 2:30
• possible duplicate of Auto-organized / smart inventory system? – Sean Middleditch Jul 7 '13 at 4:05
• @PatrickHughes: wait a sec, you meant like, when you turn off align icons to grid in Windows? But wouldn't things be less organized and start to overlap? - Also calculations would be more complicated. And from my narrow vision I don't see how would I avoid autosorting by this approach. – vexe Jul 7 '13 at 4:07
• It worked well for Ultima, back in the day, with full overlap and all that. Just trying to toss ideas out in case you get stuck and need something workable. The whole "place things on a grid" is an NP-complete computing problem, there is no fast or guaranteed solution short of a full exploration of every permutation. – Patrick Hughes Jul 7 '13 at 5:11