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

[AmosYang (LetMeGoogleThatForYou)]

※ 引述《yhn0tgb60 (呦厚厚)》之銘言：
: 最近在研究模擬城市的一項功能
: 就是每個建築物都會去判斷 自己是否有電線連結到發電廠
: 目前我想的辦法寫一個尋路程式(例如 A*)
: 每蓋一個建築物 或是蓋一個電線 或是拆一個電線
: 就對所有的建築物  跑尋路程式
: 而電線是道路  終點是發電廠
: 判斷建築物 是否可以透過電線 找到發電廠
: 不過這個運算量很可怕...
: 當建築物一多 或是電線一多
: 只要在哪裡 一直重複 拆一個電線 或是蓋一個電線
: 程式就跑掛了
: 而模擬城市在近20年前  就已經做到這個東西
: 模擬城市的地圖並不小  而且那時候的電腦也很差
: 我想也許他們有更好的方法在處裡這個問題 ???
: 想和大家討論一下這個問題   謝謝了 ^^

很有趣的問題 :D

從遊戲設計的角度來看，這裡面有偷機取巧的空間 XD

我記得在遊戲裡電線的連結或移除並不會馬上造成影響，
而是會隔個 1 到 3 秒才會出現影響

這個幾秒鐘的間隔有可能是程式在拼命運算造成的延遲
也有可能是一種偷機的方式，也就是說，
「如果有玩家在短時間內一直把電線建了又拆拆了又建
  不要去理他，等他去做別的動作時，我們再來算電線連結的問題」

且，視區域數量的不同，使用的演算法也可以改變
例如，假設城市的規模是中等或小型，那就使用比較耗時但保證正確的演算法
因為城市的規模小，玩家多半可以察覺到明顯的錯誤，所以需要保證正確的的演算法
但也因為城市的規模小，所以就算使用比較耗時的演算法，影響也不會太大

當城市的規模是大或佔滿了整個地圖，就可以換成比較快但有可能會有誤差的演算法
從玩家的角度來看，當你要照顧整個地圖時，如果有幾塊區域缺電
你大概不會很仔細的確認供電量這類的「小事」，只要電線連接好了
5000$ 直接核電廠蓋下去

是故，從遊戲設計的角度來看，有時候「絕對正確的演算法」並不一定是最好的答案
只要遊戲整體塑造出來的遊玩經驗有趣，很多地方是可以偷機的

(當然這是在 game design 板是這樣講，
 如果你移駕到 prob solving 板去
 就會有人跟你談 disconnected subgraph detection 的 algorithm 了 XD

 這背後的問題其實蠻複雜的
 因為每個發電廠還有限制供電量，我記得核電是 150 區，火電是 50 區
 是故，除了要算 node 間的 connectivity 還要算供電量
 再考慮到記憶體使用量
 我覺得在當年那種硬體上，我覺得遊戲程式應該有偷機… XD )

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 65.87.177.87

補述

SimCity Source Code Is Now Open
http://developers.slashdot.org/article.pl?sid=08/01/12/1846256

看起來 SimCity 的 source code 有放出來…直接去看吧 :D
※ 編輯: AmosYang        來自: 65.87.177.87         (07/09 19:28)
→ Splash5:推推
→ Splash5:剛剛有玩一下 電線就算連結好也不會馬上有電
→ Splash5:而且I,C,R三個區塊其實也可以看成是電線的一種..
→ Splash5:game design要的是看起來像真的 至於實際上是不是真的
→ Splash5:那就是另一回事了 :p..
→ a1234957:現在為了效能而偷機的例子還是有吧 應該是說聰明
推 laymu:推，演算法的確不是最快最正確就是最好的。還是要因地時宜
推 rexrainbow:推~
→ kazuto:猜可能是類似填色的方法?
推 lightmaple:推一個
推 abovelight:看到了離散數學和組合圖形學的影子了
→ yhn0tgb60:謝謝  我研究看看
推 cowbaying:說的好  只要看起來像回事就好  實際上...
推 chrisho:偷雞