使用附加信息扩展 Pointer/Reference

Question

我正在编写一个程序，当玩家穿过迷宫时程序会生成一个迷宫。每个迷宫块可能有一个北、东、南和西邻居。我正在考虑使用 pointer/reference 存储每个邻居，但我还必须保存路径是否空闲（用于未来迷宫生成或如果邻居已经生成则玩家移动）或是否被阻塞的信息。

我想到了以下方法：

// 1. aggregate data in a new data type
struct Pathway {
    bool isFree;
    MazeTile* neighbor;
}
Pathway north = {true, nullptr}

// 2. store data paralelly
MazeTile* north = nullptr;
bool isNorthFree = true;

// 3. Use inheritance to create a blocked tile
MazeTile* south = new BlockedMazeTile();

就我个人而言，我会选择第一种方法，但我以前从未见过这样做。第三个看起来不错且易于扩展，但该解决方案受限于底层迷宫设计，不能用作此类问题的通用方法。

那么，这些解决方案中哪一个是首选 - 如果 none，该怎么做？

Answer 1

当然，这要视情况而定，但我会选择第一个。

它比第三个更好，因为如果需要，您可以在不重新创建 class 实例的情况下解锁迷宫图块。谁知道，明天在你的魔法土地上会发生什么，对吧？灵活一些会更好。以防万一;)

此外，如果可能，您可以将迷宫图块存储为数组，前提是您的游戏区域或多或少是方形的。那么您根本不需要任何对相邻图块的引用。只是 blocked 标志或任何表示下一个方块有入口的东西。

Answer 2

我也建议#1，但它并不像您想象的那样罕见，因为图式数据结构将附加数据存储到连接节点的边中。

如果你想让它变得非常紧凑，你可以做的另一件事是让这些边缘（路径）简单地将索引存储到 MazeTile 而不是指针。使用索引，您可以将辅助数据存储到高位，例如，指示路径是否被阻塞或您需要的任何内容。

编辑：

根据要求，这里更详细地介绍了基于索引的解决方案。假设您这样做：

class Pathway 
{
public:
    /// Creates a new pathway.
    Pathway();

    /// Sets the index of the neighboring maze tile/node.
    void set_maze_tile(int new_index);

    /// @return The index to the neighboring maze tile/node.
    int maze_tile() const;

    /// Sets whether the pathway is free or not.
    void set_free(bool val);

    /// @return True if the pathway is free.
    bool is_free() const;

private:
    int index;
};

要做到这一点，您需要将这些迷宫图块分配到一些连续的内存块中（例如：使用 std::vector 或其他某种动态数组——它可以在不使索引无效的情况下增长）。

现在你可以这样做：

enum
{
    free_bit = 1 << (sizeof(int)*8 - 1),
    index_mask = ~free_bit
};

Pathway::Pathway(): index(0)
{
}

void PathWay::set_maze_tile(int new_index)
{
     const bool was_free = is_free();
     index = new_index;
     set_free(was_free);
}

int PathWay::maze_tile() const
{
     return index & index_mask;
}

void PathWay::set_free(bool val)
{
    if (val)
        index |= free_bit;
    else
        index &= ~free_bit;
}

bool PathWay::is_free() const
{
     return (index & free_bit) != 0;
}

有点难看，低级风格的代码，这个界面是一种无聊的 getter/setter 设计，但它会压缩你的路径，使其在 64 位上通常占用大约 16 个字节（会计对于通常的结构 padding/alignment) 到只有 4 个字节，这不仅有助于减少内存使用，而且还可以提高速度（更大的空间局部性，适合高速缓存行的更多相邻路径）。

它确实将您的无符号索引范围从 2^31 减少到 2^30（允许大约十亿个迷宫图块）。您可以使用 unsigned int 将该范围加倍到 2^31（尽管可能不值得这么麻烦，除非您实际上打算处理接近该比例的东西）。

使用附加信息扩展 Pointer/Reference

Extend a Pointer/Reference with additional information

architecture