實現與負座標

三角形/六邊形網格A *繼使用this question作爲新問題的基礎的我也有一個問題，我期待爲完美地解決儘可能明顯的傳統：實現與負座標

我有實現六方地圖這樣：

（想在這裏插入圖片..但我不會因爲允許被新......請參見上面的鏈接）

但我現在想知道如何（優雅）用這些類型的座標爲這種類型的地圖實現A *。我有在典型的平方網格（我認爲是笛卡爾網格）上使用A *的經驗，而我在那裏處理它的方式似乎與這個座標系統不兼容。

通常我會生成一個二維字節數組。數組的索引將對應於網格座標，並且所述索引處的值將給出該節點的「權重」。（0無法通過，數字越大，稱重越大，數字越小）。

實施例： sbyte[,] pathGrid = new sbyte[5, 5] { {0,0,1,0,0}, {9,5,1,3,0}, {9,5,1,3,0}, {9,5,1,3,0}, {0,0,1,0,0} };

凡0的將是無法通行，則1的將是容易橫過，以及更高的數字將「成本」更遍歷。（抱歉格式化..我是一個堆棧溢出newb：P）這個數組將根據我的地圖的組成生成，然後饋送到我的路徑查找算法，這反過來會吐出一個節點列表（路徑），如果找不到路徑，則返回null。

但是，使用這種類型的網格，這是不可能的（至少乍一看）由於負座標（顯然不在數組中）和網格不遵循相同的事實規則作爲「典型」網格。

有辦法解決這個用我的A *方法，我認爲，但他們都比較草率（轉換網格座標和使用空節點）如果有人已經想到了一個辦法能夠完美做到這一點我想知道。閱讀在任何情況下:)

感謝（順便說一句，我在C＃/這樣做。對於它的價值網）

來源

2011-05-08 Jesse Purdy

通過給所有座標值添加一個常量，可以輕鬆地克服負座標問題，將它們轉移到非負區域。將問題視爲一個二維網格看起來就像是一個非常簡單的方法，即使你必須在這裏或那裏轉換一些座標。 – 2011-05-08 23:30:55

一個很好的座標系可以是「環號」，「單元號」，其中環號從中心六邊形上升，並且單元號從一個點開始並且順時針（或者逆時針，並不重要）工作。每個「環」中的小區數目是2n *（2n-1）/ 2，其中n是環索引的1個數目。不知道如何真正在這個系統中做A *，但我不認爲它很難，也沒有浪費的細胞。它也很容易確定鄰接關係。 – soandos 2011-05-08 23:38:37

你可以存儲你的座標在詞典：

var nodes = new Dictionary<Point, Vector[]>;

這樣你不僅限於正座標，而你還沒有從每個節點上有限的路徑數

來源

2011-05-08 23:42:22

嘿乍一看這看起來像一個完美的解決方案..我仍然需要制定一些怪癖，但現在這是我接受的答案:)非常感謝。我一定會讓你（任何人閱讀）知道它是否完全符合預期的完全整合。如果它確實工作的很好，那麼我覺得它很笨，因爲它很簡單：P – 2011-05-09 01:03:10

讓我知道如果你需要更多的細節，這是我以前實現A *的方式，所以我很確定它可以被開發工作。乾杯! – 2011-05-09 01:18:22

我相當確定現在一切正常。再次感謝：） – 2011-05-09 03:35:04

即使數組的索引從0開始，你的程序不需要從概念上以這種方式處理數組。例如，如果您總是添加例如3添加到索引中，然後使用它們來查找數組，您實際上有一個索引從3開始的數組。爲了簡化以這種方式處理數組，您可以創建一個名爲例如ArbitraryBaseArray，它包裝一個數組和一個指定所需基本索引的數字。

然後，您可以創建一個包含ArbitraryBaseArray數組的HexGrid類，每個類都有其自己的基本索引（取決於十六進制區域的左邊緣的外觀）。這個類可以有一個索引器，它可以讓你查找基於兩個十六進制座標的特定元素。它也可以有一個靜態方法，在給定六邊形網格座標的情況下，返回一個具有六個相鄰座標的數組;這個方法可以被A *使用。（請注意，雖然您鏈接的問題中的插圖對每個六角形瓷磚使用三個座標，但是兩個座標就足夠了。）

來源

2011-05-08 23:35:44

實現與負座標

回答

相關問題