作者azureblaze (AzureBlaze)
看板GameDesign
標題Re: [程式] 圈地面積 最小面積取得相關 (方向判定)
時間Wed Feb 27 12:12:29 2013
先說一下我對這個規則的理解：
把他當作拿美工刀在紙上割
如果某個區域被割下來的時候，把較小的那個區域丟掉
////////////////
資料結構：
class Face{
Edge top,bottom,left,right;
bool removed;
};
class Edge{
Face first,second;
bool cut;
};
考慮到更複雜的網格時你可能要把Face改成接受不定多數的Edge，
然後再加個Vertex來紀錄Edge間連接的狀況這樣才可以行走。
不過現在要的好像沒這麼複雜，所以使用格子的xy座標和上左方向就好了
////////
演算法:
當我割了一條新的邊的時候，我需要知道:
有沒有形成新的區域?
檢查方法：
把這個Edge標記為cut
從兩個Face中隨便挑一個，就統一用first好了
開始對first做flood fill
如果fill到了second，代表這條邊沒有產生新的區域，所以可以照常繼續。
如果形成新的區域，接下來的問題就是哪塊比較大:
對first和second各作一次flood fill，
在fill的時候可以用一個counter，每多fill一塊就加1
(更一般的狀況就在Face中紀錄面積，一樣加上去)
最後就可以比較兩邊大小了
(計算大小其實可以在檢蹅新區域的時候就順便做)
最後看哪邊比較小，就再對first或second做一次flood fill，
把那邊所有的Face標為removed
(也可以在比大小時就紀錄該區域有哪些face，
不過flood fill其實也沒多慢)
希望對你有幫助
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.171.56.169
1F：→ zop:將圍過的邊都標注cut,還在畫的線標注run,行徑確定產生run之後, 02/27 12:31
2F：→ zop:只要碰上cut,就等於包覆一個區域,同時作兩個區域的flood fill, 02/27 12:32
3F：→ zop:比較之後標注小的區域為removed,然後removed內的cut全部清除, 02/27 12:33
4F：→ zop:只留最外圍的cut,機體只能在cut上還有未removed的區域行走,另 02/27 12:34
5F：→ zop:外,機體碰上run爆炸！(倒退也爆？XD) 02/27 12:35
6F：→ azureblaze:確實檢查前面的邊就可以判斷新區域，免去flood fill 02/27 13:03
7F：推 euph:感謝您的討論 我也想過類似的方法 不過在做FF的時候 要怎麼判 02/27 13:09
void FloodFill( Face f,byRef int area){
f.flag();
area += 1;
foreach(Edge e in f.edges){
if(e.cut) continue; //邊被切過了不用處理
Face n = e.getNeighbor(f); //取得跟這個邊相接的另外一個面
if(n.removed) continue; //面被切掉了不用處理
if(n.flaged()) continue; //面被處理過了
FloodFill(n,area);
}
}
//while new region created if Edge e is added:
FloodFill(e.first,areaFirst);
ClearFaceFlags();
FloodFill(e.second,areaSecond);
ClearFaceFlags();
if(areaFirst > areaSecond){
FloodFillRemove(e.first);
}else{
...
}
※ 編輯: azureblaze 來自: 1.171.56.169 (02/27 13:35)
8F：推 euph:我也有想過你的想法 只是你丟進去的第一個FACE會被countinue 02/27 13:45
9F：→ euph:因為那一個FACE的其中一邊就是CUT 然後就無法遞迴出去 02/27 13:47
10F：→ azureblaze:只有那邊不做，其他三邊還是會處理啊? 02/27 13:50
11F：推 euph:了解 我是以一整個FACE為單位 所以再切割成四個邊進去做檢查 02/27 13:55
12F：→ euph:好 我試著寫看看 感謝 :D 02/27 13:55
13F：推 euph:感謝 我把FACE分成四邊去做檢查再往外遞迴 就沒問題了!! 02/27 19:10
14F：→ euph:大感謝!!! 只是效能有點恐怖就是了 XDDD 02/27 19:10
15F：推 euph:後來我修改了一下 當如果檢查兩邊的時候其中一邊有碰到邊界 02/28 15:48
16F：→ euph:就回傳false這樣可以加速很多不必要的檢查 邊界是只全體的邊 02/28 15:49
17F：→ zop:可是如果是四邊都已經不是原先的邊,會不會判定失效？ 02/28 16:45
18F：→ zop:喔,看你敘述,應該是不會 02/28 16:45