遊戲樹的C++實現

我將以C++結構來代表國際象棋遊戲。我認爲，最好的選擇將是一個樹形結構（因爲在每個深處我們有幾個可能的動作）。遊戲樹的C++實現

這是一個很好的方法嗎？

struct TreeElement{ 
    SomeMoveType move; 
    TreeElement *parent; 
    std::vector<TreeElement*> children; 
};

如何有效地將這種數據存儲在文件中？有沒有辦法確保整個樹結構將存儲在內存的相同部分，這將允許使用mmap函數？

來源

2012-02-19 Dejwi

您不能以某種方式將該結構保存到文件中，因爲它包含指針並使用「vector」。 – 2012-02-19 15:19:56

這些是三個非常廣泛和非常不同的問題，彙集成一個。請不要這樣做。 – 2012-02-19 15:21:46

我會嘗試命名節點（只是使用指針值）並在Depth-first ordersearch中遍歷樹，這樣您可以生成一個有序的1維數組，如：[{node：1，move：..，parent ：0}，{節點：2，移動：..，父：1}，{節點：3，移動：..，父：2}，{節點：4，移動：..，父：3}] – arthurprs 2012-02-19 15:26:36

要將數據存儲在同一部分內存中，您可能希望爲您使用的std::vector<TreeElement *>提供一個Allocator對象，並從您的塊中分配該對象。

爲了能夠序列化它，而不是存儲實際的指針，你可能會考慮在塊中存儲偏移量。然後，當您讀取數據時，您可以將塊起始地址添加到每個偏移量以將其重新轉換爲地址。

根據您使用的操作系統/編譯器，可能已經有一些支持。例如，微軟的編譯器支持__based指針，這幾乎就是我所描述的：一個基地址，並且基於該地址的每個指針實際上只是一個偏移量，而不是一個完整的指針。提及mmap表示可能不直接提供給您，但是它可能是您正在使用的編譯器/操作系統具有類似的內容。否則，您可能必須自己完成這項工作（例如，使用based_pointer課程）。

真正的問題是你爲什麼試圖序列化移動樹。在一個典型的情況下，您最好只保存當前的棋盤位置（或者等同於移動歷史記錄），並根據需要重新生成移動樹。這足夠小，它很容易儲存。

來源

2012-02-19 15:29:14

我認爲使用std :: vector並不是創建樹的最佳方式，單鏈表的樣式樹構造可能更簡單也是最好的。

來源

2012-02-24 07:00:51

遊戲樹的C++實現

回答

相關問題