周二进度报告：更优化的建造系统
2016/7/19

[ 这个建筑终于竣工了！]
(特别鸣谢：Kythandra… 详见即将到来的石炉第200次Twitch直播)
(直播地址： twitch.tv/stonehearth)
-----萌-----萌-----哒-----分-----割-----线-----
大家好久不见——又是我，Chris(或者叫我“弄脚手架的那个”就可以)。Stephanie这周把进度报告这一光荣的任务交给了我——于是本周我们就理所当然地稍微深入讨论下刚登陆A17的新建筑系统。如果你们很想知道石炉里脚手架和生物上蛋白折叠过程有着怎样的相似性和联系性，那么这篇文章就是为你们准备的！
从城市建设角度来看，石炉这款游戏非常特殊，我们给玩家工具可以设计出以像素为单位的各种各样的建筑，但建造却是委托给炉民完成的——你们设计，然后他们一块砖一块砖地造出来。我们还需要让炉民的建造行为至少看起来可以让牛顿瞑目，但是对于各种各样天马行空的建筑来说，要达到这个简单的要求似乎也会变得异常艰难，以至于，说实话我们制作团队在很长一段时间里也低估了这个问题的复杂性。不过现在，我们的新建造系统已经从根本上反思了以前建造的弊端并优化了大部分。
建筑能够持续的核心是，炉民永远能够到达需要新添加方块的那个地方。要保证这一点，脚手架就必不可少。于是，建造也就只是一个问题而已，即什么时候在哪里应该放脚手架？以前的建造系统及其“乐观”，只有在需要造某个部分的时候才会把脚手架搭到那里。这种“恰恰好”的建造态度对于相对简单的建筑来说还可以，但在复杂的建筑面前就“船到桥头自然沉”了。

[很简单…但造不起来]
例如上图的建筑，在老式建造系统下很容易使炉民混乱。特别是如果他们碰巧先造了里外两面墙，那么再想要造夹在当中的那面墙时，就没地方放脚手架了，于是也就罢工了。在对该问题尝试解决多次后，我们清楚地了解到建造系统真正需要的，其实是脚手架预建造系统——换句话说，炉民需要先制定出一个计划，弄清楚脚手架建造的位置与次序，再开始整体建造。
在预建造处理时，我们首先要生成一个数据依赖图像。这个东西整体上可以说看成大蓝图，并给出建造次序，例如“先造地板，再是墙体，最后是屋顶。”它会给出要完成建筑，所需建造的各个部分及所有辅助结构，并排出它们的总次序。有的排序是按照物体间顺序的，例如屋顶坐在墙体上，故墙体必须优先于前者建造。这种空间顺序是比较容易计算的。

[屋顶骨架连接着墙体骨架…]
一旦模型的空间形状确定，我们开始给建筑的每一个部分周围放上脚手架，让炉民们可以顺利到达上面的每一个点(然后不罢工)。先判断一个部分周围是否存在其他建筑(部分)，如果没有，那就可以很顺利地按放上脚手架，完工并开始计算其他部分。然而通常情况下，周围都是有东西的——要么就是自己这部分的脚手架被挡了，要么就是脚手架需要坐在其他方块上。从这里开始，事情就变得有趣起来了，哦摩西罗伊。
在这两种情况下，我们都需要更新数据依赖图像。若本部分脚手架需要搭在另外一部分上，则那个部分要优先建造；也就是说我们这部分开工的时候，那里方块理论上就已经是实体而非虚影了，脚手架也就可以理所应当地踮着方块搭起来。而另外一种情形，我们这部分脚手架与其他部分重叠了，那么这一部分要先造，而且在其他部分开始建造之前要把脚手架先拆掉。这就需要再一次更新数据依赖图像，确保该部分与剩余部分的依赖性(排至最优先建造)，并确保建造完成后脚手架拆卸至不影响其余部分建造——对于那些本来被影响的部分，这里我们的脚手架就属于“反依赖”。

[红色标注的脚手架正在拆除以防止影响二层地板；]
[绿色标注的则正在建造中…]
我说什么来着：因缺思婷。
你们在A17新系统中围观炉民建造时或许已经发现了，他们先造脚手架，再造建筑，然后拆掉部分脚手架给其他部分让路。他们也会未雨绸缪了呢…
可是，这个数据依赖图像也带来了一个致命的缺陷：玩家不可以把设计一个建筑，让里面的部分循环依赖最后形成死循环：“只有造了楼梯才能完成地板，可是楼梯又要地板先造”，这就像你要求一个疯子去证明自己精神不正常。最后什么都造不了，也就是所表现出来的罢工。
有时候，我们会发现如果不陷入这种死循环，脚手架也没地方放。这种稀有情况下，我们就权且做个弊一旦开始建造，就*噗付*造好了…我们承认这是当下解决此种十分棘手的情况比较好的办法，但是还是希望大家围观炉民一点一点造房子的好，并且如我所言，此类情况极其稀有，并且只有密切关注着炉民从他们行为方式上才能判断出来。(译注：绝大部分情况还是寻路问题)
或许你们尚有疑问，为什么会这么难？人类可以在建筑过程中轻轻松松搭好脚手架怎么电脑就这么难办到？其实，微妙的地方就在于要给我们的建筑图像找到一个“漂亮的”遍历[详见https://en.wikipedia.org/wiki/Tree_traversal]，不产生任何造不了的情况。简单的算法(每条路都试一遍！)往往会随着建筑复杂性的增加而使机器变缓：这样你要建造一个中型建筑可能也要个几百万年来等机器找到最佳路径了。于是，同时要让遍历“漂亮”，又要防止上面提到的死循环，这就是一个NP完备问题[详见https://en.wikipedia.org/wiki/NP-completeness]这是计算机科学里一个比较深奥的问题，这篇小文章里也不去叙述。总之，单单使用基于图像的蓝图来规划建造是不够的。我以后会尝试更多建筑，让遍历越来越完善，然后数据依赖图像也可以随之提高可行性；对我个人来说，也算是一场探险。
于是，建筑方面完结了么？不，远远没有！现在有很多建筑都可以建造了(其实应该说是绝大部分)，但还有许许多多bug需要清除(例如炉民造封闭的建筑物把自己困在了里面出不来)，当然，玩家体验我们也会重视。预计在接下来石炉的开发中会有更多更好的优化与提升。

【格式可能会乱0.0】