c - 减少特定数据的内存占用

Question

我有一个网格来划分游戏中的几何形状。该网格中的每个单元格都包含三角形的索引，它可以包含 0 到 n 个索引。

所以最初我想到这个结构来保存该数据:

struct GRID_CELL
{
   unsigned short m_num_indexes;
   unsigned int * m_indexes;
}

这是一个内存有限的系统，很快我就用完了它。我需要存储 60x60x60 网格单元。首先，我想到将 m_num_indexes 存储为 m_indexes 的第一个元素，以减少由于对齐而导致的结构大小(从 8 字节减少到 4 字节)。

然后我想我可以使用这个结构:

    struct GRID_CELL
    {
       unsigned short m_first_index;
       unsigned short m_num_index;
    }

然后将所有索引连续存储在一个 int * 数组中。

你能想到任何其他方式来存储这些信息，并在更小的内存占用中使用(也不会使提取信息变得过于复杂，因为CPU也非常有限，并且必须经常访问这些信息) ？

谢谢!

Answer 1

我们可以将GRID_CELL减少到一个字节——一种单元类型，即:

struct GRID_CELL
{
    uint8_t m_type;
}

struct GRID_CELL grid[60][60][60];

unsigned int *indexes[256];
unsigned short num_indexes[256];

这意味着我们将仅限于 256 个独特的单元格，但对于大多数游戏来说这应该足够了。访问索引:

uint8_t cell_type = grid[x][y][z];
unsigned short n = num_indexes[cell_type];
unsigned int *p = indexes[cell_type];

细胞类型示例:

• 单元格类型0是空单元格(空气)；
• 细胞类型1是水；
• 细胞类型2是地球；
• 细胞类型3是一个障碍；
• 单元格类型128是空单元格中的游戏角色；
• 细胞类型129是水中的一个字符；
• 细胞类型130是地球上的一个字符；
• 单元格类型255是一个独特的单元格(根据情况而变化)；

等等等等

我们也可以尝试使用稀疏矩阵来节省一些字节。但它可能会使游戏引擎变得复杂并减慢速度。以下是有关 Sparse Matrix on Wikipedia. 的一些一般信息