Minecraft(我的世界)中文论坛

标题: 【CBL|SF】[1.14]倍增快速 tp
作者: switefaster    时间: 2019-8-15 16:28
标题: 【CBL|SF】[1.14]倍增快速 tp
本帖最后由 switefaster 于 2019-8-15 16:44 编辑

各位好久不见，我又来水帖了
今天我们要解决一个老问题：如何将玩家 tp 到记分板指定的坐标
想必大部分人都会毫不犹豫地想到二分法(传统艺能)
然而二分 tp 法有一个相当明显的缺陷即玩家需要被多次 tp，如果正好途径大量未加载的区块就会卡到生活不能自理，这显然不是一个合格的 CBer 可以认可的结果，而如果想要使用实体作为 marker 传送，则又会遇上区块加载这个大坑。所以今天我们的目标是克服这个缺陷做到一次性 tp 到目标坐标。

算法设计

首先我们来考虑一个简单的解决方案：比如我们需要从数轴上的点 0 tp 到 100，我们可以设两点直接距离为 x 递减1并每次将坐标顺着 x 方向移动一格，当 x 达到 0 时则将玩家 tp 到达到的坐标。实现上我们可以使用 execute positioned 递归。


很显然这种算法的时间复杂度为 Θ(n)，这似乎是个不错的解决方案，而事实上它确实是一个不错的解决方案。不过如果 x 过大，超过了 100000，这种算法可能就显得有些力不从心了。
作为合格的 CBer，我们怎能容忍问题出现在自己面前？
让我们思考这种算法的弊端出现在哪里？很显然，这种算法每一步的跨度实在是太小了。不管 x 是 1, 10 还是 1e9，每一步都只能位移 1 单位，慢到不能忍。
这时候我们会想：要是能每步能跨大一点，并且加起来能准确地达到目标就好了！(ん？)
再详细一点，如果能表示成类似 a[sub]0[/sub]*b[sub]0[/sub]+a[sub]1[/sub]*b[sub]1[/sub]+...+a[sub]n[/sub]*b[sub]n[/sub] 的形式就好了！
答案很明显，我们该使用进制模拟。在这里，我将使用二进制(通常主要是因为处理器对二进制的处理能力最强，然而对 mcfunc 而言这应该没太大影响，除非 mj 给记分板加个位运算)。
现在我们可以整理出我们的新算法了：
我们使用位运算每次取出表示距离的数字 d 的第 i 位(从左向右从0开始)，若第 i 位为 1，则将坐标偏移 i^2 格，直到坐标达到目标位置为止。由此我们可以看出这种算法我们最多进行 d 的二进制表示中 1 的数量次位移，最多进行 log2(d)+1 次位运算，时间复杂度为Θ(log2(n))，比 Θ(n) 快不知道哪里去了。


至此，我们完成了对算法的初步设计。
MCFUNC 实现

事实上实现没有什么好讲的，只有几个需要注意的点：
1. 可以使用 (n / 2^i) % 2 来获取数字 n 第 i 位的内容(0 或 1)
2. 可以将以2为底的 n 次幂的指数和幂运算的结果存放于 as 中方便查找(然而实体多时拉低效率，不过可以少写个幂运算)
3. 需要预处理好的位移和幂的上界建议为 2^30，这主要是由于记分板最多只能存到 2^31-1
4. 获取距离之后要取绝对值，并且要记下符号，按着符号方向 tp
5. i 可以从大往小穷举，一达到目标就立即停止，这样通常会快一点
6. mcfunc 递归回溯的时候并不会帮你还原 scb 的值，所以请注意防止回溯时影响结果
嗯，其他也没什么好讲的，也就各种位移的 mcf 重复工作量比较大而已。由于文件过多我就不直接向这里贴代码了

关于本人提供的示例的说明：ftp:offset 内为各个 2^i 的位移
请设置 distance_x,y,z 为目标坐标随后执行 /function ftp:teleport
注意：我因为懒并没有实现上述注意点中的第 5 点




[groupid=546]Command Block Logic[/groupid]

fast_teleport.zip

43.87 KB, 下载次数: 8
作者: kongbaiyo    时间: 2019-8-15 16:31
好 拿来用了 不用思考了 我代表黑羊羊感谢你
作者: langyo    时间: 2019-8-15 16:41
你已经是个成熟的 sf 了，该学会自己检查帖子了

我到现在还沉浸在二分，可你却给了个平均性能更好的倍增

很棒的思路！
作者: [email protected]    时间: 2019-8-15 16:52
厉害厉害啦啦啦555
作者: ruhuasiyu    时间: 2019-8-15 17:36
你这个是直接改变执行点位置对吧？那也可以直接二分啊？
作者: 169406229    时间: 2019-8-16 00:32
六的起飞，收藏了
作者: 169406229    时间: 2019-8-16 00:32
六的起飞，收藏了
作者: ⊙u⊙    时间: 2019-8-16 09:10
本帖最后由 ⊙u⊙ 于 2019-8-15 19:01 编辑
而如果想要使用实体作为 marker 传送，则又会遇上区块加载这个大坑

剩下的太长没看，而如果我说错了，请一定要来打我

  1. #execute as @s at @s run
  2. tag @s add bar
  3. summon area_effect_cloud ~ ~ ~ {Tags:["foo"]}
  4. execute as @e[type=area_effect_cloud,tag=foo,distance=..1] run function foo:bar
  5. tag @s remove bar
复制代码

  1. #foo:bar
  2. execute store result entity @s Pos[0] double 0.01 run scoreboard players get $x00 value
  3. execute store result entity @s Pos[1] double 0.01 run scoreboard players get $y00 value
  4. execute store result entity @s Pos[2] double 0.01 run scoreboard players get $z00 value
  5. execute at @s run teleport @e[tag=bar] @s
  6. kill @s
复制代码
作者: SPGoding    时间: 2019-8-16 12:24
本帖最后由 SPGoding 于 2019-8-16 12:47 编辑
⊙u⊙ 发表于 2019-8-16 09:10
剩下的太长没看，而如果我说错了，请一定要来打我

当 marker 进入未加载区块以后，@e 选择器无法选中该 marker，传送失败。

丢人，退群吧！


当 marker 进入未加载区块以后，@s 选择器能够选中，传送成功，tql sdl awsl

我丢人，我退群，你不用退了。
作者: zxzpkcxcc    时间: 2019-8-16 12:53
学到了学到了，谢谢大触
作者: (=°ω°)丿    时间: 2019-8-16 13:20
本帖最后由 Teenager_Yang 于 2019-8-16 13:36 编辑

太长不看，我用的方法：
玩家当前位置：x[sub]0[/sub]，y[sub]0[/sub]，z[sub]0[/sub]
需要到达的位置：x[sub]1[/sub]，y[sub]1[/sub]，z[sub]1[/sub]
做差，得到：dx，dy，dz
以 x 轴为例：
世界边境默认大小约为 3x10^7，而 3x10^7 在 2^24 和 2^25 之间。

先判断 dx 的正负，我这里假设为正数。
1、如果 dx 大于 2^24，那么 tp 玩家 2^24 格，然后 dx 减掉 2^24 。
2、如果 dx 大于 2^23，那么 tp 玩家 2^23 格，然后 dx 减掉 2^23 。
3、如果 dx 大于 2^22，那么 tp 玩家 2^22 格，然后 dx 减掉 2^22 。
……
24、如果 dx 大于 2^1，那么 tp 玩家 2^1 格，然后 dx 减掉 2^1 。
25、如果 dx 大于 2^0，那么 tp 玩家 2^0 格，然后 dx 减掉 2^0 。
x 轴的 tp 结束。

↓ 我才知道区块没加载也能用 positioned，我一直以为 positioned 和实体是一个性质……
那用二分法也可以啊……
作者: Ruainbow_    时间: 2019-8-21 23:59
⊙u⊙ 发表于 2019-8-16 09:10
剩下的太长没看，而如果我说错了，请一定要来打我

？？？见鬼，怎么做到的，区块不是还没加载吗？
啥玩意儿，是因为和改变坐标在同一个函数，所以不用第二次选择，而这个函数执行完之前实体还没有消失卸载吗？