基于舞王借刀的图灵完备设计
植物大战僵尸吧
全部回复
仅看楼主
level 1
古语云:“PVZ不存在科技和技术,简单的规划求解问题,当不起这两个字。”然而事实真是如此吗?
本研究设计了一种组合逻辑电路模型,基于舞王借刀的原理构造了可多次翻转的比特以及三种基本门电路,并演示了一个半加器实例。本文致力于为图灵完备的PVZ提供有效的理论支持。
2024年07月22日 15点07分 1
level 1
一、前置知识充电
本文假设读者已经充分了解PVZ的相关知识,包括但不限于:杨桃索敌机制,舞队移动机制,以及pss特性。如有疑问,请活用吧内搜索。
关于图灵完备:图灵完备指的是一种计算系统或编程语言具备执行任何可计算函数的能力。可以构造基本门电路是图灵完备性的充要条件,因为基本门电路(如与门、或门、非门)能够实现所有布尔逻辑运算,并通过组合构建复杂的逻辑电路,这使得它们能够模拟图灵机的所有计算步骤和算法,从而表明任何可计算函数都可以用门电路来实现,确保了图灵完备性的实现。
2024年07月22日 15点07分 2
视频演示:【半加器十二炮:PVZ数电化探索】网页链接
2024年08月21日 13点08分
level 1
二、基本假设
由于运行时间与游戏内存的限制,PVZ显然不可能实现真正的图灵机。为此,我们假定无穷大地图与时间,(若不加声明)开启僵尸虚弱以简化模型。
所有的土豆地雷均代表pss耐啃王,不会受到啃食伤害。
规定:移动的伴舞代表比特1,停止的伴舞代表比特0。
众所周知,一个舞队包含一个舞王与四个伴舞。对于舞王A0,四个伴舞分别记为A1,A2,A3,A4,其他字母同理。舞王一般作为比特传递与翻转的触发信号,若无此必要,舞队尽量不保留舞王。
规定:触发杨桃攻击的是输入位,接受杨桃子弹的是输出位。
下图展示了杨桃常用的三个借刀位,其中A可作输入位,B可作输出位,C既可作输入位又可作输出位,在第六节示例中均有所体现。
2024年07月22日 15点07分 3
level 1
三、比特与传递
下图展示了将A0由0置1之后,B0由0置1的传递结构。A0与B0停止时,两者均处于杨桃的索敌范围以外,A0前进时,触发杨桃攻击并击杀B0,解除B舞队的停止状态。这个过程在IZE中俗称“借刀”。
2024年07月22日 15点07分 4
level 1
下图展示了将A0由1置0之后,B0由1置0的传递结构。大蒜血量为1,A0与B0同时前进时,A0啃食大蒜,B0正常通过。若A0提前停止,B0啃食大蒜后换行,并进入停止状态。
2024年07月22日 15点07分 5
level 1
四、基本门电路
下图展示了非门的结构,可以实现比特的一次翻转,请读者自行分析。
2024年07月22日 15点07分 6
level 1
对于一组有序舞王A0,B0,C0,D0,E0……若将A1伴舞的栈位用B2伴舞替代,B1的栈位用C2替代,C1用D2替代……由此就实现了停止信号由后向前的单向传递。
同理,再将B4的栈位用A3替代,C4用B3替代……则实现了多个比特“与”的关系,可以用于多个舞队的链接。
2024年07月22日 15点07分 7
level 1
或门的构造更加清晰,只需要在触发位置重叠多个不同来源的舞王即可。
2024年07月22日 15点07分 8
level 1
五、比特的多次翻转
如图所示,1-8的杨桃是上文中的简单传递结构,常用于系统启动的接口,此处不再赘述。
5-4的杨桃是可翻转的比特结构,A0与1-9的舞王通过伴舞的与门链接,若B0保持置0,A舞队也保持置1。若B0置1,则A舞队将会翻转置0,此时再将C0置1,A舞队将再次翻转置1。
如左上角(不完整)显示,此结构可以向左反复拓展,便能形成任意有限次的比特翻转。
2024年07月22日 15点07分 9
level 1
六、示例:半加器十五炮
(特殊规则:暂停出怪)
图中红A伴舞血量为2,红B伴舞血量为3,其余伴舞血量为1。大蒜血量为2,前侧有3个伴舞位置重叠。2-2,1-8,6-8均是经过pss水草缠绕的伴舞,不会被植物阻挡。
2024年07月22日 15点07分 10
level 1
四组伴舞的位置关系如图所示:
通过铲除红A以及红B处的耐啃王置1,红S以及红C将呈现出半加器的运行结果。
具体分析留给读者作为习题。(拓展:提出一种不同拓扑结构的设计,并比较与本示例的优劣。)
此外容易发现,这并不是一个真正的阵。若要运阵,需要在1-1杨桃索敌之前全收九列僵尸,显然不存在完美时机。
2024年07月22日 15点07分 11
level 1
综上所述,PVZ可以构造基本门电路,但是由于每个比特的翻转次数有限,只能运行事先编写好的逻辑,显然弱于常规图灵完备设计。至于时序逻辑部分,期待其他玩家发掘。
本文尚不够成熟,后续可能会多次改进,感谢各位大佬批评指教。
2024年07月22日 15点07分 12
听不懂思密达
2024年07月23日 04点07分
level 1
附:半加器的真值表
2024年07月22日 15点07分 13
level 5
啊?
2024年07月22日 15点07分 14
level 12
膜。
2024年07月22日 16点07分 15
1 2 3 4 5 6 尾页