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