作者moremusic (my way)
看板GameDesign
标题Re: [程式] 模拟城市的电线连接判断是怎麽做的阿???
时间Fri Jul 9 23:38:48 2010
我有个初步想法
只要建筑物有新增或移除
就先把所有的建筑标记为"无电"
然後用扩散法
从发电的来源(电厂)开始
向邻近的可以导电的建筑标记为"有电"
接下来把这些"刚得到电的"建筑
再用跟电厂同样的方法把电扩散出去
用递回做程式码会很精简
这个做法应该会比A*快很多
如果不用递回做的话
可以把这个演算法改写成回圈
每次game loop只要做渐进式的扩散
如果再细想思考的话
应该可以用扩散法为基础
修改成不用每次建筑物有新增或移除
就全部重新算一次
※ 引述《yhn0tgb60 (呦厚厚)》之铭言:
: 最近在研究模拟城市的一项功能
: 就是每个建筑物都会去判断 自己是否有电线连结到发电厂
: 目前我想的办法写一个寻路程式(例如 A*)
: 每盖一个建筑物 或是盖一个电线 或是拆一个电线
: 就对所有的建筑物 跑寻路程式
: 而电线是道路 终点是发电厂
: 判断建筑物 是否可以透过电线 找到发电厂
: 不过这个运算量很可怕...
: 当建筑物一多 或是电线一多
: 只要在哪里 一直重复 拆一个电线 或是盖一个电线
: 程式就跑挂了
: 而模拟城市在近20年前 就已经做到这个东西
: 模拟城市的地图并不小 而且那时候的电脑也很差
: 我想也许他们有更好的方法在处里这个问题 ???
: 想和大家讨论一下这个问题 谢谢了 ^^
--
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 118.166.64.138
※ 编辑: moremusic 来自: 118.166.64.138 (07/09 23:44)
1F:推 artpoet:推 07/10 00:14
2F:推 yhn0tgb60:谢谢 不过递回...会不会很恐怖阿 = = 07/10 00:37
3F:推 fasthall:这不就是BFS而已? 07/10 01:05
5F:→ valkidy:flood-fill algo 07/10 01:21
6F:推 zhewei:宽度优先的搜寻 07/10 02:46
7F:推 KanoLoa:BFS怎会比A*快 ? H(f) 太差才会吧 ? 07/10 11:49