首先（回顾上次的内容和本次的实践）在上一篇文章中，我们使用了Minecraft Education Edition的代码构建器（MakeCode）来制作一个在Overworld（主世界）上绘制圆形并计算圆周率的程序。为了追求逻辑的简便性，我们采用了一种方法，即在包含所需绘制圆形的正方形区域中进行全面搜索，找到距离中心小于或等于半径$r$的区域。然而，使用这种方法，计算量会以$r^2$的级数增加。由于各种原因，Minecraft Education Edition上的绘制限制为$r=128$。但当我们尝试对更大的$r$进行模拟时，这种计算量的增加将成为问题。因此，在本文中，我们将改进程序以更高效地绘制圆形（即更快地绘制）。最终的结论是通过改进逻辑，我们可以在计算量与$r$成比例的程度上绘制圆形，而不是$r^2$。

值得一提的是，本文所介绍的逻辑与上篇文章中的逻辑相似，fujitanozomu已经给出了实现示例，并将其作为对上篇文章的评论提交，还包括了关于应用到更大r值的适用性分析。非常感谢fujitanozomu先生。

在本文中，我们将着重介绍通过改进逻辑可以使得程序变得更快的效果，并通过Minecraft的视频和PowerShell的执行时间比较来展示。

ロジックの改良これまでロジックで、計算量が$r^2$のオーダーで増加していってしまうのは、探索範囲となる正方形の領域をくまなく探索しているためです。$xz$平面上の、点$(x_c,z_c)$を中心とする半径$r$の円を表す二次曲線の方程式、$ (x-x_c)^2 + (z-z_c)^2 =r^2$をうまく用いることで、$x$軸方向の探索だけで、円の範囲を求められるようにロジックを改良します。円の中心が原点となるように座標変換を行うことで、方程式は$ x^2 + z^2 =r^2$のように簡便化できるので、以後はこちらの形式で問題を取り扱うことにします

$x$軸方向の座標$x_1$における円周の座標を$(x_1,z_1)$とするとき、円の方程式から$z_1$は、$z_1 = \pm \sqrt{r^2-x_1^2} $ となり、$\sqrt{r^2-x_1^2}$から$-\sqrt{r^2-x_1^2}$までの範囲が円の内側となります。また、円は$z$軸に対する反転($x$を$-x$に置き換える変換)に対しても対象性があるので、$-x_1$においても同様のことがいえます。次の図は半径10の円を描いたものですが、$x=\pm 7$において、この方法で特定される円周の位置を4か所の青丸、円の内側の領域を赤（レッドストーンブロック）で示しています。円の内側に相当する領域を特定することができれば、1ブロックずつ中心からの距離を判定しブロックを置いていくのではなく、範囲指定でブロックを埋めていくことが可能となります。

使用之前提到的方法，我们设计了一个程序（图X），用于确定与圆内部相交的区域，并绘制出圆形。与上次的程序相比，重复循环只涉及到变量$x$，计算量减少了。

let y中心座標 = 0
let x変位 = 0
let ブロック数 = 0
let z円周座標 = 0
let 円周率 = 0
let x開始座標 = 0
let z開始座標 = 0
let z変位 = 0
let 距離の二乗 = 0
player.onChat("circle2", function (半径, x中心座標, z中心座標) {
    y中心座標 = -60
    x変位 = 0 - 半径
    ブロック数 = 0
    while (x変位 < 0) {
        z円周座標 = Math.trunc(Math.sqrt(半径 ** 2 - x変位 ** 2))
        blocks.fill(
        GOLD_BLOCK,
        world(x中心座標 - x変位, y中心座標, z中心座標 + z円周座標),
        world(x中心座標 - x変位, y中心座標, z中心座標 - z円周座標),
        FillOperation.Replace
        )
        blocks.fill(
        GOLD_BLOCK,
        world(x中心座標 + x変位, y中心座標, z中心座標 + z円周座標),
        world(x中心座標 + x変位, y中心座標, z中心座標 - z円周座標),
        FillOperation.Replace
        )
        ブロック数 += z円周座標 * 4 + 2
        x変位 += 1
    }
    blocks.fill(
    GOLD_BLOCK,
    world(x中心座標 + x変位, y中心座標, z中心座標 + 半径),
    world(x中心座標 + x変位, y中心座標, z中心座標 - 半径),
    FillOperation.Replace
    )
    ブロック数 += 半径 * 2 + 1
    円周率 = ブロック数 / 半径 ** 2
    player.say("面積：" + ブロック数)
    player.say("円周率：" + 円周率)
})

演示
然后我们将通过视频演示展示一下，画圆的速度有多大的提升。视频中，首先使用上次的程序画了一个圆，然后使用我们这次改良的程序将圆换成了不同的颜色。相信您可以确认画出的圆是一样的，并且改良版的程序实现了更快速的绘制。

对于r的增加，比较执行时间（使用PowerShell）。在之前的節目中，您已經通過Minecraft的視頻觀察到了由於邏輯差異而導致的執行時間差異，現在我們將以更具量化的方式介紹測量結果。改進之前的邏輯以PowerShell實現的是circle1.ps1，改進後的邏輯實現則是circle2.ps1。

circle1.ps1 的中文翻译可以是 ：圆形1. ps1

Param(
   [long]$r = $Args[0],
   [long]$blockcount = 0,
   [long]$xcount = -$r,
   [long]$zcount = -$r,
   [long]$distance =0
   )

$now = Get-Date
$start_log = ("{0:yyyy/MM/dd HH:mm:ss.ffff} {1}" -f $now, $_)
Write-Host $start_log
while($xcount -le $r){
   while($zcount -le $r){
       $distance = $xcount*$xcount + $zcount*$zcount
       if($distance -le $r*$r){
           $blockcount++
       }
       $zcount++
   }   
   $xcount++
   $zcount = -$r
}
$pi = $blockcount/$r/$r
$now = Get-Date
$end_log = ("{0:yyyy/MM/dd HH:mm:ss.ffff} {1}" -f $now, $_)
Write-Host $end_log
Write-Host $r,$blockcount,$pi

Param(
   [long]$r = $Args[0],
   [long]$blockcount = 0,
   [long]$xcount = -$r,
   [long]$zcount = 0
   )

$now = Get-Date
$start_log = ("{0:yyyy/MM/dd HH:mm:ss.ffff} {1}" -f $now, $_)
Write-Host $start_log
while($xcount -lt 0){
   $zcount = [Math]::Truncate([Math]::Sqrt($r*$r - $xcount*$xcount)) 
   $blockcount = $blockcount + $zcount*4 + 2 
   $xcount++
}
$blockcount = $blockcount + $r*2 + 1
$pi = $blockcount/$r/$r
$now = Get-Date
$end_log = ("{0:yyyy/MM/dd HH:mm:ss.ffff} {1}" -f $now, $_)
Write-Host $end_log
Write-Host $r,$blockcount,$pi

在每个程序中逐渐增大半径时的计算时间总结如下表所示。计算时间的单位是毫秒，数值是5次执行结果的平均值。从$r=32$左右开始，我们可以观察到与circle2相比，circle1的计算时间急剧增加的趋势。对于半径大于等于$r=131072$的情况，circle1的计算时间太长，无法在本文提交前进行测量。

rcircle1.ps1circle2.ps1133.637.8272.271.6468.260.2873.4641678.273.23286.86164138.258.6128317.277.62561049.479.85123900.868.8102415330.664204860373.662.84096242002.882.28192962802109.4163843840905143.23278615391490.8220.46553666127313408131072-742.2262144-1422.2524288-27481048576-5388.4
如果将$r$作为横轴，计算时间作为纵轴进行绘制，可以发现circle1随着$r$的增大而呈二次增长，circle2随着$r$的增大而呈线性增长。

总结这是本次文章的总结。

• Advent Calendar 12/1の記事のロジックをより少ない計算時間で実行できるように改良しました。

 

• 改良結果をマイクラ上の円の描画時間で比較できるよう動画にしました。

 

改良前後のプログラムが、それぞれ$O(r^2)$と$O(r)$で増大することを、Powershellでの実行結果から確認しました。

#技术文章