Re: [程式] 模擬城市的電線連接判斷是怎麼做的阿???

[chenglap (無想流流星拳)]

※ 引述《yhn0tgb60 (呦厚厚)》之銘言：
: 我想也許他們有更好的方法在處裡這個問題 ???
: 想和大家討論一下這個問題   謝謝了 ^^

我覺得以上的分析本身走錯了方向.
因為你分析出來的, 是忽視了以下這些東西:

1. 模擬城市有電量的限制的, 並不是只要連到發電廠就有電, 而
   是要發電廠支持得住發電量

2. 在模擬城市表現出來的是發電廠會先提供更接近區的電力.

3. 可以有兩個不同地方的發電廠, 所以終點可以有兩個, 但到底
   決定由誰供電卻是謎題.

4. 一個較近的電廠的供電額滿, 還是會使用較遠的電廠, 所以也
   不是單純找最近的電廠

因此, 最基本的問題是, 「哪個是起點, 哪個是終點」, 這件事根
本就無法在一開始時決定, 既然連起點和終點都不明白, 我們不需
要假定這個系統是建立在「路徑搜尋」之上的.

而我認為最簡單的做法就是「顏料滲透」法.

在古早時代的語言 BGI 帶的繪圖指令中, 已經有 floodfill 這種
指令, 簡單來說, 就是填色. 把一個區塊填滿, 直至碰到邊為止.
這種指令在 286 的電腦上也不會用很多的時間, 而運作的方式很
簡單, 就是從一點開始不斷擴張出去, 直至填完為止. 可以用
recursion 或者 BFS 類似的方式達成.

然則, 你把電網想像成一幅圖的話, 運作方式也是相同的. 很簡單
, 由電廠開始, 你只要加一個參數是「電量」, 每經過一個會使用
電的點處, 就減去相對的數量, 直至填滿或者數值不足為止.

你可以想像成, 每座電廠相當於一瓶滾珠, 而電網則是一個迷宮,
你做的事情就是在迷宮幾點倒下滾珠, 隨他們自己滾動而已.

你有幾座電廠, 就做幾次, 模擬城市一當中沒有小型電廠 (風電,
水電) , 只有大型電廠 (煤電, 核電) , 所以電廠的數量不會太多
, 應該不會超過十個. 相連的電廠更可以直接將電量相加計算.

那麼一次的工作量, 大概就是等於電廠數 x floodfill 的工作量,
另外, 因為不用顯以及有限額的關係, 所以工作量應該比
floodfill 要低. 而模擬城市本身的更新速度其實並不很頻繁, 一
個月可能只更新五次左右而已.

那是 286 也可以支持得來的. 至於你開電纜, 關電纜, 也不會有影
響, 運算不應該在你建築或者拆除時進行, 而應該用 timer 計時
器定期進行.

所以這並非一個「searching」動作, 而是一個「floodfill」的動
作, searching 需要找最短的路線, 而你 floodfill 根本就不用顧
慮這問題, 只要節省了「尋找最短路線」這個要求, 你就會發覺你
不需要用那麼複雜的 algorithm 了.

一開始把這問題想成是「路徑尋找」的問題就是盲點, 那會誤導你
解決問題的方向的.

--

基於飲水思源的理念, 還是該打的廣告,
 hkday.net --- 碩果僅存還願意和其他地區轉信的香港 BBS

--
推 LPH66:附註一下, floodfill 的感覺其實就像上一篇那個動畫的樣子
另外, DOS 時代編釋出來的程式, 效能是高於 Windows 時代的. 特
別是有可能在裡面使用了組合語言, 其實 286 也是一枚很快的 CPU
, 只是不可能受得住現代 OS 和高階語言一層又一層的剝削而已...

只要不濫用高階的 call, 你會發覺即使 286 也是很見用的. 老實
說自從我擁有人生第一部 486 之後, 我從沒覺得過電腦慢...

→ yhn0tgb60:ㄟ 我目前的考慮還沒這麼複雜
→ yhn0tgb60:就假設在單一電廠 電廠的電量和範圍都沒有限制
那麼更簡單.
就是相等於一次 floodfill.

→ yhn0tgb60:只是單純想知道建築物是否有連到發電廠
如果只是這樣, 只做一次 BFS 就足夠了.
因為 BFS 中間產生的數據會顯示所有連得到去的點.
※ 編輯: chenglap        來自: 218.252.90.21        (07/10 00:44)
推 yhn0tgb60:謝謝了  我研究看看 ^^
推 bill42362:就類似水管工人的遊戲吧 @@"
推 Bencrie:BGI是說那個Turbo C/C++ 的Borland Graphics Interface ?
推 ddavid:單純想知道是否有連到發電廠那就是Connect Component問題，
→ ddavid:不管用DFS BFS還是啥別的，只要是不遺漏的Search都一樣。
→ ddavid:打錯，Connected Component，少打個ed XD
→ chenglap:對 BGI 就是那個.