用附加信息擴展指針/參考

Question

我正在編寫一個程序，當玩家穿過它時，程序會產生一個迷宮。每個迷宮瓦片可能具有北，東，南和西鄰居。我正在考慮使用指針/引用來存儲每個鄰居，但是我還必須保存路徑是否空閒（用於將來的迷宮生成，或者如果鄰居已經生成，只是玩家移動）或者是否被阻止。

我已經想到了以下方法：

// 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(); 

我個人與第一種方法去，但我從來沒有看到過的。第三個看起來不錯並且容易擴展，但是解決方案必須與底層的迷宮設計綁定，並且不能用作這種問題的一般方法。

那麼，這些解決方案中的哪一個纔是首選解決方案 - 如果沒有，那麼解決方法是什麼？

Answer 1

這取決於，當然，但我會去第一個。

它比第三個更好，因爲如果需要，您可以在不重新創建類實例的情況下解鎖您的迷宮圖塊。誰知道，明天你的魔法土地會發生什麼，對吧？靈活性會更好。以防萬一;）

此外，如果可能的話，如果您的遊戲區域或多或少是正方形，則可以將迷宮拼圖存儲爲數組。那麼你根本不需要任何對鄰居貼圖的引用。只是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個字節到僅僅4個字節，這應該不僅有助於減少內存使用，而且還會獲得更多的速度（更大的空間局部性，更多的相鄰路徑擬合進入緩存行）。

它確實降低了從2^31到2^30的無符號索引範圍（允許大約10億個迷宮塊）。您可以使用unsigned int將範圍加倍到2^31（儘管除非您真正打算處理接近該比例的東西，否則它可能不值得費心。