採掘タートルで整地する：　（8）山を切土して空洞があったときの対策

• チュートリアル「採掘タートルで整地する」
  • (7) ＜＜ (8)この記事 ＞＞ (9) まだ

遅れた言い訳

先週末に連載の続きを書くと言いましたが、遅くなってすみません。

記事はできていたのですが、説明用のSS画像撮るのが面倒で放置してました。

さきほど撮ってきたので、公開です。

前回までのお話

前回で、高さを自動認識しつつ自動切土するプログラムを紹介しました。

たとえば凹凸のある地上で以下のコマンドを打ち込むだけで、プログラム開始地点の位置と高さを基準として、1チャンク（16x16）範囲の丘を削り、平らに整地してくれます

> cutland 16 16

燃料を補給するロジックは入れていないので、プログラム開始前にあらかじめ余裕を持って補給しておいてください。

インベントリに松明とチェストを入れておくと松明自動設置＆チェストにアイテム収納してくれるという便利な機能もついています。

しかし問題点も

このように便利なプログラムなのですが、実際に使ってみると以下のような問題点がでてきます。

• 水ブロックの対策は無し
• 大きな山を削っているときに、中に空洞があると挙動がおかしい

まず、タートルは水ブロックを認識できないために、切土範囲に池などの水溜りがあるとそのまま水が下までダバーしてしまい。せっかく設置した松明が流れてしまいます。

この対策は非常に面倒なので、本プログラムでは考えないことにします。あらかじめ水溜りは埋め立てるなどして対策してください。

そして後者の空洞問題が今回の課題となります。もう少し詳しく説明しましょう。

空洞の中にいるとそこが最高地点なのか判断できない問題

前回のプログラムは、高さを自動認識するために、タートルが自分の正面または真上にブロックがあるかどうかを判別して、あるならば1m上昇、ないならばそこが最高地点というアルゴリズムを使いました。

このアルゴリズムは小さな丘を削っているうちは問題ないのですが、削る対象が大規模になると問題が発生する可能性があります。

たとえば山を削っている途中で、高さが2以上ある深い空洞に出会ったとしましょう。

以下はその空洞の断面図だと思ってください。説明のためのモデル図です。

この位置にいるタートルの正面および真上にはブロックが存在しません。

そのため先のアルゴリズムでは、この位置が最高地点と判断してしまいます。

その結果、1歩前進します。また、そこでも正面と真上にブロックが存在しないので、さらに1歩前進します。

2歩前進して初めて正面に壁を発見し、壁伝いに最高地点を探して上っていくことになります。

最終的に、最高地点と誤って認識した最初の2歩分は真上にブロックが残ったままとなります。

たとえこの2ブロックの上にどれだけ土や石が重なっていようと、です。

この問題は、タートルは自分の隣接位置しかブロックの有無を判別できないことが原因です。この制約があるかぎり、この問題を根本的に解決することは難しいのです。

そこで、行き当たりばったりながら、次のような方法で対策しました。

対策案

上図を見てわかるように、問題は、タートルの真上の何もない空間です。

たとえば上図のときに、タートルが真上に1歩上昇していたならば、真上にブロックがあることを検知して、最高地点の探索が開始できます。

そこで、「存在するであろう空洞の高さ（CAVE_HEIGHT）というパラメータを用意し、タートルが最高地点と判断したあとにその高さ分だけ上昇させて本当に最高地点かどうかを再判断させる」という対策を採ります。

このCAVE_HEIGHTというパラメータは、プログラム実行時にオプションとして入力が可能です。大きな山を削るときに「高さ3の空洞くらいがありそう」と思ったら、追加で3を引数として渡すことにします。

# 16x16範囲の丘や山を切土し平らにする。山の中に高さ3の空洞があっても対処可能とする
> cutland 16 16 3

この対策案は実装が簡単なのですが、実際のタートルの動きは無駄な動きが増えるので注意が必要です。

なにせ、たとえ明らかに何も無いところでも、無駄に3m上昇するわけですから。

たとえ話をするならば、強度の近眼の人がめがねを無くした状態で壁伝い移動するのに等しいわけで、無駄な動きをしてしまうのは仕方ありません。妥協しましょう。

ソースコード

http://pastebin.com/9qRkNaSz

前回とほとんど同じなので省略。無駄にコード長いですし・・・。

ソースコード解説

実は、前回から修正した箇所はほぼ2箇所だけです。

新パラメータCAVE_HEIGHTの入力処理部分と、最高地点を探索するgoTop()関数の修正だけです。

順番に解説しましょう。

パラメータ入力処理部分

local args = { ... }
if #args == 3 or #args == 2 or #args==0 then
  DEPTH = tonumber(args[1]) or DEPTH
  WIDTH = tonumber(args[2]) or WIDTH
  CAVE_HEIGHT = tonumber(args[3]) or CAVE_HEIGHT -- expect the hight of cave
else
  error('seichi <DEPTH> <WIDTH> (CAVE_HEIGHT)')
end

このプログラムの実行方針は、

1. プログラム実行時に奥行き・幅のパラメータを一緒に入力する（空洞の高さはオプション）。
2. 毎回同じ値を入力するのが面倒ならばソースコードの先頭（CONFIG部分）にあるDEPTH、WIDTH、CAVE_HEIGHTのデフォルト値を書き換えるとパラメータ入力なしで同じ実行ができる。

となります。それを踏まえて以下をご確認ください。

• プログラム実行時に一緒に入力されるパラメータを配列argsに代入しています
  • cutland 16 8 3とプログラム実行されたのならば、args=["16", "8", "3"]となっています。
  • ポイントは、CCでは入力パラメータは全て文字列として渡される点です。
• if文で配列、すなわちパラメータの数が2か3か0ときだけ処理を実行し、それ以外のときにはエラーを返すようにしています。
  • パラメータが全く入力されていないときには、このソースコードの最初のほうで設定してあるデフォルト値を使います。
• DEPTH = tonumber(args[1]) or DEPTH
  • tonumber()関数で文字列を数値に変換しています。
  • また、orを使ったこの記法は、入力値がなかった（tonumber(args[1])がnil）ときにデフォルト値を使って変数を初期化するLuaの典型的な記法です。

最高地点を探索する関数

わかりやすくするために、前回のプログラムのコードと比較しましょう。

-- 前回：　正面と上にブロックがあったら1m上昇。なければ終了。
function goTop()
  while turtle.detectUp() or turtle.detect() do
    surelyUp() --上にブロックがあっても破壊して必ず1m上昇する関数
  end
end

前回のプログラムにおけるgoTop()関数は、重要な関数ながらとてもシンプルですね。

すこしだけwhile文の使い方が特殊なので補足すると、

turtle.detectUp() or turtle.detect()という条件式は、まず上にブロックがあったらTrue、なければ正面のブロックの有無でTrue/Falseを返します。

この条件式の実行結果によって、whileの中を実行するかどうかを決定します。

以下は今回の修正版です。

-- 今回の修正版
function goTop()
  repeat
    for i=1,(CAVE_HEIGHT-1) do
      surelyUp()
    end
    local flag_rose = true
    
    while turtle.detectUp() or turtle.detect() do
      surelyUp()
      flag_rose = false -- execute from beginning, if detects a block
    end
  until flag_rose
end

今回の修正版を読み解くには2つポイントがあります。

まず1つ目のポイントは、関数実行開始するとすぐに(CAVE_HEIGHT-1)だけ上昇していることです。

たとえ無駄な動きと言われようと有無を言わせません。タートルは強度の近眼なのですから仕方ない。

なお、CAVE_HEIGHTから1を引いているのは、高さNの空洞ならば(N-1)上昇すれば天井ブロックに接し、検知できるためです。

上昇後、whileの条件式で真上と正面にブロックがあるか確認し、最高地点を探索・上昇するところまでが1つのセットとなります。

そして2つ目のポイントは、repeat文を使うことでこの処理セットを何度も繰り返していることです。

なぜ繰り返す必要があるのでしょうか？　解説しましょう。以下のモデル図をみてください。

アルファベットのF？　いえ違います。

空洞の上に、さらに同じ規模の空洞があることを示しています。

この図では2つですが、場合によっては同じ規模の空洞がそれ以上の数、上に積み重なっている可能性があります。

スタートしたらまず上昇、上にブロックを検知したので最高地点探索のためにさらに上昇。

とりあえず、上図の位置まできました。ここが最高地点でしょうか？

いえ、違いますよね。

今回の修正アルゴリズムの肝は、一旦最高地点と判断したあとにさらに指定した高さだけ上昇するのでした。

ここからさらに上昇して、真上にブロック検知　→　最高地点探索のため上昇　→　もうブロックがないのでここが最高地点ですか？　いえまだダメです。

さらにもう一度上昇して、真上・正面にブロックがない　→　今度こそ最高地点だ（正確には最高地点より少しだけ上）！

と動くことになります。

今回は、空洞が上に2段でしたが、本番では3つかもしれません。4つかもしれません。そして、タートルにとって、その時にならないといくつ積み重なっているのかわからないのです。

そのため、繰り返し回数を明示的に指定するfor文ではなくrepeat～until文を使っています。

繰り返しは、flag_rose*1の値がtrueのときに終了します。

まず最初にCAVE_HEIGHT-1だけ上昇することでflagをtrueにし、繰り返し終了条件を整えます。

ただしここで、上や正面にブロックを見つけてしまうと最高地点の探索が始まってしまうのでflagをfalseにして再度最初から繰り返します。

この一連の処理によって、空洞も考慮した本当の最高地点（ただしそれよりも少し上の位置）へと移動することができます。

おわりに

ここまでの連載で、奥行き・幅・高さを指定して直方体空間を掘りぬくプログラムと、今回の奥行き・幅だけを指定して高さを自動認識して切土するプログラムを紹介しました。

本当の整地プログラムを作るためには、土地を削るだけではなく、小さな穴を埋める機能も無くてはなりません。

この機能については、また次回お話しする予定です。

なお、次回の記事掲載予定は未定です。

（リクエストが多ければ優先度を上げて早めに記事を書くかも？）

*1:roseはriseの過去形