我的世界吧 关注:702,541贴子:4,269,297
  • 7回复贴,共1

【命令方块】使用原版命令进行四色定理的自动填充

取消只看楼主收藏回复

1楼成果图





IP属地:广东1楼2023-11-23 04:42回复
    作品鸣谢:@化学爱好者_C60
    这个功能主要由一个数据包实现。
    数据包初始化完成后,会生成一个64*64的画板,在这个画板上使用黑色混凝土搭建出图形,然后执行求解函数,就能进行自动填充了。
    填充过程大致如下
    其中初始化信息,其实就是清理一下画板,再清理一下storage,没啥值得讲的,所以就不详细说明了。其他各个区域的工作原理会在对应章节叙述。
    本部分仅讲述实现思路与具体实现的相关函数,不会对具体命令进行讲解。有兴趣的可以自行下载数据包进行拆包研究。地址稍后补上。


    星座王
    点亮12星座印记,去领取
    活动截止:2100-01-01
    去徽章馆》
    IP属地:广东2楼2023-11-23 04:45
    回复
      要想知道一个区域的填充方式,首先要做的就是知道这个区域在哪,有多大的规模。同时为了便于计算,最好要有一个编号。
      如果知道了一个区域的形状、大小和规模的话,那么进行逻辑分析时就好很多了。
      这里我使用了两个递归函数嵌套穷举x与z来进行逐个方块进行分析,判断这是否是一个新的区域。如果这是一个已经识别过的区域,那么就会跳过这个方块而去分析下一个方块。如果是一个没有识别的新区域,则会试图分析它的形状,以及它的边界。这里主要通过检测空气方块来进行识别。
      由于区域是使用者任意搭建的,极有可能是边界不规则的图形,因此要对区域进行判定只能一个一个方块地进行判定,而不能直接fill。
      当上述两个递归函数发现了一个空气方块时,说明遇到了一个暂未分析过的新区域,于是在该位置放置白色混凝土,并以该点为基点,向东、南、西、北四个方向分别检测。若检测结果为空气,则在该位置放置白色混凝土,并以该点为基点进行同样操作。如果检测结果为黑色混凝土,则说明碰到了边界,此时在边界上方也放置一个黑色混凝土(重要,后面要用到)。这样反复n次后,这个区域就会被填满白色混凝土,同时它的边界也会变高一格,效果如下图所示(可能不太明显)。


      星座王
      点亮12星座印记,去领取
      活动截止:2100-01-01
      去徽章馆》
      IP属地:广东3楼2023-11-23 04:46
      回复
        这里的编号方式,我采用的是使用y轴进行编号。
        在区域识别结束后,将填充的白色混凝土向上复制一层,并将原本填充的那一层从白色混凝土替换为灰色混凝土。这样这个区域的形状、规模与边界信息就会被提取并分离出来,同时不会影响下一个区域的识别。但是为了做好区分,并且为了避免与下一次提取后的结果重叠在一起,因此还需要再向上移动一段距离,如下图所示
        对于第一个区域,提取好后,仅需要向上移动一格即可做到不影响第二次提取。而第二个区域,则需要向上移动两格。这里我采用了一个递归函数,使用execute positioned来调整命令执行的y坐标基准点,并通过计分板进行控制。若当前区域为第一个区域,则向上移动一格后执行clone操作;若是第二个区域,则两次向上移动一格后执行clone,以此类推。这样反复执行了几次后,整体的效果应该是这样的。
        这样,就成功地从玩家随手搭建的区域中识别出来了各个区块的形状、大小及数量。


        星座王
        点亮12星座印记,去领取
        活动截止:2100-01-01
        去徽章馆》
        IP属地:广东4楼2023-11-23 04:47
        回复
          现在我们已经能够识别出来不同区域的形状、规模、边界了,甚至可以直接使用y轴作为其编号,那么接下来,就可以对相邻区域进行判定,便于后期的计算了。
          相邻区域记录的流程大致是这样的
          由于之前在区域识别的同时也将所有区域的边界均识别了出来,编好号并放置在不同的y坐标上,因此只需要识别y轴哪个地方有黑色混凝土,就说明哪几个区域在共用这个边界。于是在画板中检测到黑色混凝土后,检测混凝土上方哪几层有黑色混凝土,则可认定哪些区域正在使用这个边界,即哪几个区域在此处相邻。
          检测到了相邻区域后,接下来要做的就是把它们记录下来。这里我没有想到什么免穷举或者不使用nbt的方法,只好硬着头皮用了,不过性能似乎没我想象的那么差。
          当向上检测到黑色混凝土时,检测当前的y轴,并记录在nbt Temp里。比如,在y=1和y=2处检测到了黑色混凝土,说明区域1和区域2在此处相邻,Temp的值就是 {1:1b,2:1b} 。当检测完一个边界后,检测Temp里的内容。在上面的例子中,Temp里有1和2,于是就使用Temp来覆盖Record.1和Record.2。如此一来,就能够在Record里知道1和2是相邻的,2和1也是相邻的了。如此反复遍历后,会得到如下图所示的结果:
          解释一下,在Record中,11里包含了5个区域,除去自身后有4个区域,说明区域11和这4个区域是相邻的,后续计算中需要保证11的颜色和另外四个区域的颜色不一样。
          由于这个记录中,每个区域都在和自身相邻,这会一定程度地影响后续计算。因此需要从这些记录中剔除自身。这个功能还是由一个函数穷举实现。移除自身后的效果如下


          星座王
          点亮12星座印记,去领取
          活动截止:2100-01-01
          去徽章馆》
          IP属地:广东5楼2023-11-23 04:50
          回复
            求解部分,这个流程图,我至少设计了十几分钟,然后从开始着手写算法到最终debug完成,花了大概有前两部分几倍的时间。
            要想确定一个区域需要填什么色,首先要做的就是知道它周围的区域填色有哪些。
            通过穷举获取区域周围的填色,并进行一定的加工处理即可得到结果。
            不过需要特别提出的是,在假定区域1,3都与区域2相邻的前提下,如果我正在对区域2进行填充,那么即使区域3和区域2相邻,也不考虑区域3的填色,而仅考虑区域1的填色。因为在对区域2进行填色时,区域3并没有填色,因此考虑区域3以及编号更大的区域的填色没有意义。(这里需要指出,即便因为某些原因填了区域3的颜色后需要返回来修改区域2的颜色,此时也不考虑区域3的颜色。具体原因后面会讨论。)
            我的处理方式是,首先通过函数穷举将该区域的相邻区域复制入Temp,然后使用另一个函数对Temp进行穷举,获取需要的区域的颜色填充并转移至NearbyFill这个nbt中(这个nbt会以Byte List的格式储存附近区域的填色,蓝色为1b,绿色为2b,黄色为3b,红色为4b。一个例子是 NearbyFill:[1b,2b,1b],说明这个区域与两个蓝色填色的区域和一个绿色填色的区域相邻)。
            当然,对于第一个区域来说,这个nbt获取不到任何东西,因为没有任何区域的编号比它更小。
            通过对NearbyFill的解析处理,即可得到一个区域的(可能)可用填色。
            这里我建立了一个PossibleSolutionThis的nbt。这个nbt用于记录当前区域的所有填色的可行性。
            首先要对这个nbt进行初始化,设置所有颜色均存在填色可能(四种填色方式均使用1b标记)。
            随后调用一个递归函数,检测NearbyFill中的nbt,判断哪种颜色已经被使用,并将对应的颜色设置为0b。这样递归后,PossibleSolutionThis中就会有一部分颜色可用(标记为1b),而另一部分颜色不可用(标记为0b)的结果出现了(对区域1来说,所有四种颜色都会是1b。而后续的填色过程中,可能会出现所有颜色都不可用的现象,此时认定结果“出错”,需要通过改变之前区域的填充来解决,会在后面详细说明)。


            星座王
            点亮12星座印记,去领取
            活动截止:2100-01-01
            去徽章馆》
            IP属地:广东6楼2023-11-23 04:50
            回复
              现在我们获得了一个区域的可能填充,那么得到答案的最简单的方法就是一个个试。我的策略是先从1(蓝色)开始,1不行就用2(绿色),再不行就3(黄色)或4(红色)。
              通过函数穷举判断PossibleSolutionThis的第一个可用颜色,并保存到FinalSolutionThis这个nbt中。这个nbt即表示当前这个区域正在使用的填色。同时,使用穷举函数将PossibleSolutionThis和FinalSolutionThis保存到PossibleSolution和FinalSolution下对应编号的nbt内。这样FinalSolution里就保存了所有区域正在使用的填色,而PossibleSolution里保存了所有区域的可用填色。结果如下图所示:
              " class="BDE_Image" onload="EditorUI.resizeImage(this, 560)" unselectable="on"/>
              这里的各个NBT的作用:
              PossibleSolution 用于保存所有区域的填色可能
              PossibleSolutionThis 用于保存当前正在分析的区域的填色可能
              FinalSolution 用于保存所有区域的正在使用的填色
              FinalSolutionThis 用于保存当前正在分析的区域正在使用的填色
              除此之外,PossibleSolution也用于出错时能够方便地进行修正,而FinalSolution则用于生成最终解

              回到刚刚抛出的一个问题。如果在分析可用填色时发现无可用填色,说明附近的一个已有填色的区域的填色出错了。由于不知道具体是哪个区域出错,还是只能一个个试。我的选择是为附近的编号比当前编号小的编号最大的区域重新填色。
              首先通过穷举函数获取附近的编号最大但又比当前区域编号小的区域,保存至NearestId中,并转移至记分板。通过穷举函数获取该编号的区域记录下的PossibleSolution和FinalSolution,分别保存至PossibleSolutionThis和FinalSolutionThis中。再通过穷举在PossibleSolutionThis中将FinalSolutionThis的解标记为不可用(0b)。随后复制好其他信息,重新分析PossibleSolutionThis中是否有可用解。
              重新分析的过程中,PossibleSolutionThis是直接从之前的记录中获取的,因此不再需要初始化(甚至因为做过标记,而不能进行初始化)。
              这里讨论一下之前留下的一个问题。如果区域x填充后,区域y被认定无解,而区域x又恰好是编号比y小的区域中编号最大的一个,那么重新填充的x是否要依据其他有填充而编号又比x大的区域进行填充?(比如,区域4和区域5,6相邻,区域5,6互相不相邻,而区域6被认定无解,此时区域4的填充是否需要考虑区域5的填充)
              我的观点是,此处区域4的填充不应参考区域5的填充。因为首先区域5的填充是参考了区域4的,如果区域4有变,那么区域5的填充也会有变化。那么,在之前情形下得到的结论在这种情形下不再适用,所以不应直接使用。因此,区域4的可用填充可以直接从记录中获取,而区域5的填充则需要重新初始化,并重新讨论分析。


              星座王
              点亮12星座印记,去领取
              活动截止:2100-01-01
              去徽章馆》
              IP属地:广东7楼2023-11-23 04:51
              回复
                现在我们已经得到了解,它就存在FinalSolution这个nbt中。我们现在需要做的就是把它实装下来。

                流程大概是这样

                由于FinalSolution是Compound类型,不便于递归,因此我首先通过穷举将其转化为List。通过识别FinalSolution并使用data modify append转化为List类型,保存至FinalSolutionList当中。结果如下:
                有了FinalSolutionList,就可以轻松通过递归调用的方式对图形进行填充了。
                首先读取第一个元素,判断其代指的颜色,随后对第一层进行填充,然后删去第一个元素,并将命令基准点向上调整一格。这样反复读取,直到FinalSolutionList中不再存在任何元素。这样每一层就都能够填充完毕了。
                由于每一层有且仅有一个区域,因此可以直接使用fill命令进行填充。这也是分层标号的优势之一。
                填充好的效果如下:

                现在需要做的就是要把它移动回去了。这里我还是调用了一个递归函数,逐层把区域复制回去。首先调整基准点为第一层,然后将区域移动回原处。然后将基准点向上移动一格,再将第二层移回原处,以此类推,直到将所有图形移动回原处。这样,我们就得到了一个完美的使用四色填充的图形。
                总体来说这个结果还是比较令人满意的,性能也比我预想中的要好很多。不过某些地方由于个人比较懒就没做优化。比如,穷举如果能用二分的话,应该能省下相当量的命令数。同时最后一部分,我后来想了想,转格式是没有必要的,可以直接通过穷举套穷举的方法解决,不需要进行递归。同时,填色和复位也可以放到一步完成。不过最后一部分所占用的命令数微乎其微,对整体性能影响不会太大。
                以及,不知道有没有可能会有免穷举的方法。不过如果要面穷举的话,需要处理的就是大量的List套List然后不断data modify+data remove,估计会相当麻烦,而且相邻区域判定时如何删去大量重复项也是个问题(因为Compound重复项可以直接覆盖,不需要额外剔除,这也是我选择使用Compound的一个原因)。


                星座王
                点亮12星座印记,去领取
                活动截止:2100-01-01
                去徽章馆》
                IP属地:广东8楼2023-11-23 04:52
                回复