（我希望這不是重復(fù)的，因?yàn)槲矣龅降脑S多問題都不適合我的需要）我正在開發(fā)一個(gè)基于 2D 網(wǎng)格的游戲，有 2 個(gè)帶網(wǎng)格的玩家。有兩個(gè)玩家：藍(lán)色和紅色，每個(gè)人在單元格中放置一塊石頭。所以我想找到一條穿過所有具有相同顏色的單元格回到起點(diǎn)的路徑，但前提是至少有一個(gè)包含對(duì)手石頭的單元格。從上面的屏幕截圖中可以看出：右上角的紅色石頭不構(gòu)成有效路徑。那些在中心的人也沒有形成一條路徑，即使那應(yīng)該是一條路徑。我能夠找到一條路徑，但它以某種方式壞了，它沒有按預(yù)期工作。
2 回答
牧羊人nacy
TA貢獻(xiàn)1862條經(jīng)驗(yàn) 獲得超7個(gè)贊
解決此類問題的或多或少的標(biāo)準(zhǔn)方法是“掃描線”算法。為簡(jiǎn)單起見，假設(shè)我們正在尋找包裹紅點(diǎn)的藍(lán)色路徑。（您可以同時(shí)或第二次處理包裹藍(lán)色點(diǎn)的紅色路徑，但您可以稍后解決。）
您可以搜索“掃描線算法”以查看它們?cè)谙嚓P(guān)應(yīng)用程序中的工作方式。在維基百科頁面也不錯(cuò)。
對(duì)于這個(gè)問題，掃描線是一組 y 間隔。它使用最左邊（最少 x）個(gè)藍(lán)點(diǎn)進(jìn)行初始化。每組垂直相鄰的藍(lán)點(diǎn)都有一個(gè)間隔。每個(gè)間隔代表通過潛在藍(lán)色多邊形的垂直切片。
算法的其余部分是設(shè)計(jì)當(dāng)掃描線向右移動(dòng)一個(gè)位置時(shí)更新掃描線所需的規(guī)則，增加 x。這將是更新每個(gè)間隔的問題。當(dāng)一個(gè)步驟發(fā)現(xiàn)一組不連續(xù)的垂直相鄰點(diǎn)時(shí)，會(huì)添加一個(gè)新的間隔。在某些情況下，間隔會(huì)“消失”，因?yàn)闈撛诘亩噙呅芜吔缢篮ㄏ胂?C 形）。在其他情況下，它們會(huì)“合并”，因?yàn)樵谙鄳?yīng)的 x 坐標(biāo)處，有一組 1 個(gè)或多個(gè)垂直相鄰的連接點(diǎn)。在其他情況下，多邊形將通過最終的一組 1 個(gè)或多個(gè)垂直相鄰點(diǎn)成功完成。
細(xì)節(jié)會(huì)很繁瑣，但不難通過案例分析來解決。
為了追蹤成功的多邊形，區(qū)間可以包括兩條前面的點(diǎn)鏈：多邊形的上邊界和下邊界。
最后一個(gè)考慮是成功閉合的多邊形是否包含至少一個(gè)紅點(diǎn)。但這很容易。如果對(duì)于任何 x 坐標(biāo)，表示多邊形的區(qū)間用紅點(diǎn)括起來，那么答案是肯定的。這可以記錄為在間隔中維護(hù)的初始假布爾值，每次看到這樣的紅點(diǎn)時(shí)都會(huì)設(shè)置為真。成功關(guān)閉多邊形后，檢查標(biāo)志以查看是否應(yīng)使用它。
通過使用合適的數(shù)據(jù)結(jié)構(gòu)：例如間隔樹，對(duì)于非常大的網(wǎng)格，上述所有內(nèi)容都可以變得高效。但是如果網(wǎng)格比較小，使用簡(jiǎn)單的列表應(yīng)該沒問題。無論如何，首先考慮使用掃描線列表對(duì)其進(jìn)行原型設(shè)計(jì)，然后根據(jù)需要使用更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)進(jìn)行優(yōu)化。
添加回答
舉報(bào)
0/150
提交
取消