In busted I use a form of 2-dimensional "sparse" arrays.
It works as follows:
- The map has a .rows attribute. The .rows attribute is sparse. It can have a row in .rows[1] and another one in .rows[3], but not in rows[2].
- Each row is a weak sparse list of cells. (It can have row[1] and row[4], for example).
- Each cell has 0 or more "items". It also has a "itemsCount" value, starting at 0.
- The map also has a nonEmptyCells table.
When an item is inserted in the grid, the rows and cells it touches are created if they don't exist, and then the item is inserted in all the cells.
When an item is inserted in a cell, cell.itemCount is increased. It also makes map.nonEmptyCells[cell] = true.
When an item is removed from a cell, it decreases cell.itemCount. It also makes map.nonEmptyCells[cell] = nil if cell.itemCount == 0.
When parsing sections of rows/cells, one has to check that they exist - there are some extra ifs.
These extra checks (creating rows and cells, increasing/decreasing itemCount) make insertion, deletion and parsing is a bit slower than in pure 2-d arrays, but the memory consumption is similar to a 1-d structure while the insertion cost is not so big. I say this based on 3 things:
- The biggest cost is creating cells when they don't exist, and that cost is not that big (1 if + creating 1 table with another table inside)
- Once an item is inserted in a cell, it is likely that it stays on that same cell for many frames, so the initial cost of inserting dilutes, especially in very static items, like map tiles.
- Once an item has "created" the cells, other items using that cell don't have to pay to create it again.
- The garbage collector doesn't run on every frame. Cells with lots of activity (with cell.itemCount switching between 0 and 1 a lot) will likely stay in memory.
But I confess that I have not run exhaustive tests.
