推 artpoet:推 07/10 00:14
推 yhn0tgb60:謝謝 不過遞回...會不會很恐怖阿 = = 07/10 00:37
推 fasthall:這不就是BFS而已? 07/10 01:05
→ valkidy:flood-fill algo 07/10 01:21
推 zhewei:寬度優先的搜尋 07/10 02:46
推 KanoLoa:BFS怎會比A*快 ？ H(f) 太差才會吧 ? 07/10 11:49
我有個初步想法
只要建築物有新增或移除
就先把所有的建築標記為"無電"
然後用擴散法
從發電的來源(電廠)開始
向鄰近的可以導電的建築標記為"有電"
接下來把這些"剛得到電的"建築
再用跟電廠同樣的方法把電擴散出去
用遞迴做程式碼會很精簡
這個做法應該會比A*快很多
如果不用遞迴做的話
可以把這個演算法改寫成迴圈
每次game loop只要做漸進式的擴散
如果再細想思考的話
應該可以用擴散法為基礎
修改成不用每次建築物有新增或移除
就全部重新算一次
※ 引述《yhn0tgb60 (呦厚厚)》之銘言：
: 最近在研究模擬城市的一項功能
: 就是每個建築物都會去判斷 自己是否有電線連結到發電廠
: 目前我想的辦法寫一個尋路程式(例如 A*)
: 每蓋一個建築物 或是蓋一個電線 或是拆一個電線
: 就對所有的建築物 跑尋路程式
: 而電線是道路 終點是發電廠
: 判斷建築物 是否可以透過電線 找到發電廠
: 不過這個運算量很可怕...
: 當建築物一多 或是電線一多
: 只要在哪裡 一直重複 拆一個電線 或是蓋一個電線
: 程式就跑掛了
: 而模擬城市在近20年前 就已經做到這個東西
: 模擬城市的地圖並不小 而且那時候的電腦也很差
: 我想也許他們有更好的方法在處裡這個問題 ???
: 想和大家討論一下這個問題 謝謝了 ^^
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.166.64.138
※ 編輯: moremusic 來自: 118.166.64.138 (07/09 23:44)