基本圖形數據結構

我想在Unity中編寫一個簡單的基於文本的遊戲，玩家必須從他們的牀'我們說，'A''通過'節點'移動到出口'G'直接連接。下面是該我試圖優雅捕獲的信息的示例：基本圖形數據結構

A直接連接到B，C，和d B被直接連接到A和C C被直接連接到A和B d是直接連接到A和E E被直接連接到F和G F被直接連接到任何操作（比方說，比賽結束了？） G被直接連接到E

，所以我需要能夠做的如下： 1）存儲節點銀行 2）存儲節點之間的連接可能是單向 3）跟蹤當前位置 4）蛋糕（結冰）改變這些連接的事情發生在比賽

我可以創造了我的頭頂部的任何執行不會很好地擴展到，讓我們比如1000個節點。我應該如何解決這個問題？

來源

2015-06-13 Brent Allard

navmesh是你的朋友。 – David

我編輯了你的標題。請參閱：「[應該在其標題中包含」標籤「]（http://meta.stackexchange.com/questions/19190/）」，其中的共識是「不，他們不應該」。 –

順便說一句，1000s的節點並不是很大。除非必須，否則我不會擔心效率問題。請記住，「如果它不起作用，它無法快速工作並不重要」 - 拉維拉。 –

有各種圖形數據結構你可以看看。我建議你去看看在這個線程信息討論有關高效的圖形數據結構：

https://softwareengineering.stackexchange.com/questions/148313/what-is-the-most-space-efficient-way-to-implement-a-graph-data-structure

一個高效的圖形數據結構，它可能適合你的遊戲目的將使用鄰接矩陣是https://en.wikipedia.org/wiki/Adjacency_matrix，因爲你可能會發現在兩個單元之間移動你的角色或對象會經常發生在遊戲中。因此，鄰接矩陣可以幫助您快速找到特定細胞的同胞細胞。但是，這種方法需要一些內存來存儲圖形中任意兩個兄弟單元之間的所有可能的鄰接關係。

但是，如果您的圖肯定是有向圖，其中任何兩個節點之間的所有連接都是單向的。您可能想要查看鄰接列表https://en.wikipedia.org/wiki/Adjacency_list您在哪裏存儲每個單元格中鄰接節點的列表。因此，查找特定單元格的兄弟節點所需的時間較少。

來源

2015-06-13 00:33:51

你的問題是非常相似的道路網絡：

class Crossroad { 
    List<Road> roadList = new List<Road>(); 
} 

class Road { 
    Crossroad start; 
    Crossroad end; 
    bool isOneWay; 
} 

class RoadNetwork { 
    List<Crossroad> crossroadList = new List<Crossroad>(); 
    List<Road> roadList = new List<Road>(); 
    Crossroad currentCrossroad; 
}

1）存儲節點的銀行：RoadNetwork.crossroadList

2）節點可能是單向之間存儲的連接：類路

3）跟蹤當前位置：RoadNetwork.currentCrossroad

4）蛋糕（結冰）改變這些連接的東西在遊戲中發生：你CA n總是改變crossroadList和roadList。

來源

2015-06-13 11:25:00 JinJi

基本圖形數據結構

回答

相關問題