为将移动数据的二维地图选择最佳数据结构

Question

我需要一些帮助，以更快地实现对 two-dimensional 阵列进行完整转换的方法。

我的问题是我有一个包含游戏地图数据的二维数组。这个游戏有点像 Geometry Dash，但在 Game Boy Advance 上。到目前为止，我有一张看起来像这样的地图：

int map1[9][40] = {
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 0, 0, 0, 0 },
    {0, 0, 0, 0, 2, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0 },
    {0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
    {1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1 },
};

但要阅读这张地图，我必须遍历每个元素，看看是否应该将其绘制到屏幕上 (x >= 0 && x <= screen_width)。

考虑一下，我认为我应该使用 doubly-linked 列表。这样，我可以通过将 header 节点移动到尾部来移动列表，然后只绘制前 15 个节点（或左右）的数据。与遍历二维数组中的每个元素相比，这是否会提高性能？虽然 looping-through 不一定是 game-crushing 性能缺陷，但我确实想对其进行优化。

如果是这样，我将如何实现这个 doubly-linked 列表以包含与二维数组相同的数据？

Answer 1

首先使用doubly-linked列表会使性能变差。你目前的方法是我现在想到的最快的方法。首先，您需要了解数组和链表在底层是如何工作的。对于阵列，我强烈建议您观看 this 5 分钟的视频，因为用文字解释会花费太长时间。了解数组的工作原理后，您需要将其与链表进行比较。当访问数组中的元素时，计算机所做的只是将内存地址递增索引乘以数组类型的大小，然后取消对该地址的引用。当访问或更好地说通过链接列表循环时，您会做更多的事情。首先，您将取消引用该项目，然后处理数据，然后查看下一项是否为 NULL，然后跳转到下一项，取消引用该项目，依此类推。

简而言之，经验法则是：如果不知道数组的长度，请仅使用链表。

现在回答你的问题。如果你想实现这样的 2D 链表，你的结构将如下所示：

struct LinkedList {
    struct LinkedList* data;
    struct LinkedList* prev;
    struct LinkedList* next;

prev 和 next 将只是指向上一个和下一个项目的指针。其中数据将是实际数据。

这是一张图，有望解释我的意思：

所以总的来说你的解析方法比链表好。但是我认为最快的解析是即时解析。

为将移动数据的二维地图选择最佳数据结构

Selecting best data structure for a 2-dimensional map that will shift the data

c

algorithm

game-boy-advance

data-structures