自作プラグインの動作を軽くしたい

[BumbleB]

お世話になっております。
今回は自作したプラグインの動作が特定条件で重くなってしまうという問題があり、どうすれば軽減できるかアドバイスをいただければと思い相談いたしました。

●プラグインPF_SAN_TileToner_MovingRangeDisplyay.jsについて
このプラグインはサンシロ氏のSAN_TileTonerの機能を使って、SRPGでよくあるような移動範囲や攻撃範囲を表示するために作りました。
基本的な流れは
①MovingRangeTestで呼び出されるとsetMoverとsetActorで対象とするキャラクターの座標やステータスを取得
②startSearchは再帰処理でsearch4を呼び出し続けて移動範囲を作成する
という手順になっています。

困っているのは、今のところ対象キャラクターの敏捷性分だけ移動できるように設定しているのですが、
この数値が8～9くらいから少し表示までにラグが生じ、13～14くらいに設定するとほぼスタック状態になってしまいます。これを軽減するにはどのような改善方法があるでしょうか？

●わかっていること
重いのはMoving_Range.prototype.searchの処理ということはわかるのですが、
例えば$gameMap.setTileTone（タイル染色の処理）を省いてもあまり変化はなく、単純に処理の繰り返し回数が増えすぎているということなのかなと思っています。
ただこの再帰処理を使った移動範囲作成も、解説サイトなどをみてみようみまねで作った感じなので、無駄な処理がまだ色々あるのかなと考えて投稿した次第です。ご助言ありましたらぜひよろしくお願いします。

サンプルプロジェクト↓
https://drive.google.com/file/d/11Z15hy ... sp=sharing

SAN_TileToner（サンシロ氏のサイト）↓
https://github.com/rev2nym/SAN_TileToner

[Plasma Dark]

再帰的に経路探索して色をつけていくのは良いのですが、枝刈りをしないと計算量が指数的に増えていきます。
最短経路問題で検索すると、この問題への対処法を見つけることができます。

各マスを探索する際に最大の残り移動力を記録しておき、次に同じマスを探索しようとする際に残り移動力がそれ以下の場合は、その探索を打ち切ってしまいましょう。

ここからは余談ですが、その他、コードを見て気になったところを列挙しておきます。

厳格モードを使用しましょう。
厳格モード - MDN
エラーをちゃんとエラーにしてくれます。
MovingRangeTest関数をグローバルに定義するのであれば、 window.MovingRangeTest と明示してあげれば動くようになります。

varの使用を直ちにやめましょう。
再代入が不要である場合にはconstを、そうでない場合でもせめてletを使うようにしましょう。
varはスコープに関する挙動が直感的でなく、同名のシンボルを再宣言できてしまう危険性があります。

class記法の利用を検討してみてください。
ツクールのコアスクリプトよりもスッキリ書くことができるため、私個人の意見としては新しいクラスを定義するのであれば、class記法をオススメします。

コード: 全て選択

class Moving_Range {
  constructor() {
    this.clear();
  }
  
  clear() {
    this._mover = null;
    ...(省略)
  }
}

プラグイン名がtypoしていそうです。
Displayと思われるところが、Displyayになってしまっていますね。

比較は厳密な等価性で行うクセをつけることを推奨します。
等価性の比較と同一性 - MDN

ほとんどの場合、緩い等価性を使用することは推奨されません。厳密な等価性を用いた比較の結果は予測しやすく、型変換がないため、よりすばやく評価できる可能性があります。

カプセル化とクラスの責務を意識してみてください。
(この項目は初学者にはやや難しいところなので、すぐに理解できなくても大丈夫です。コードを読みやすくしたいと思ったときに、思い出してみてください)
コードを書く際は、_で始まる要素にクラスの外部から直接アクセスしないようにすることが望ましいです。

例えば、 $gameActors._data[$gameParty._actors[0]] は別の書き方ができます。

コード: 全て選択

$gameParty.leader()

あるいは

コード: 全て選択

$gameParty.members()[0]

であればパーティの他のメンバーのアクター情報にもアクセスできます。
アクターIDをベースにアクセスしたいのであれば、 $gameActors.actor(actorId) としましょう。

クラスの責務については少し難しいかもしれませんが、本当にそのクラスが持つべき役割であるのかを考えるということです。
コアスクリプトの解釈次第であり、個々人で答えに差が出るものですが、ひとまず私の考えを記しておきます。

_movingRange を保持すべきは本当に Scene_Map クラスでしょうか。
Sceneクラスはゲーム中の状態そのものを保持するのではなく、状態を参照してシーンの処理を行う責務を担っています。
つまり、ゲーム中の状態であるMoving_Rangeのインスタンスを直接Sceneに持たせるよりは、 Game_XXX クラスに持たせるほうが自然であるように思います。
ただし、Game_XXXクラスの内容は一部を除いてセーブデータに含まれてしまうので、セーブデータに含まれない一時データとして Game_Temp に含めるのが良さそうです。
(規模が大きくなる場合は、新規に Game_MovableRange みたいなクラスを作っても良いとは思いますが、そこまでしないなら Game_Temp が一番手軽かなと思います)

移動可能範囲の計算を行うものとして、 calcMovableRange 関数を Game_Temp クラスに定義しておけば、こんな感じのコードにできます。

コード: 全て選択

function Game_Temp_MovingRangeDisplayMixIn(gameTemp) {
  gameTemp.calcMovableRange = function () {
    this._movableRange = new Moving_Range();
    this._movableRange.setMover($gamePlayer);
    this._movableRange.setActor($gameParty.leader());
    this._movableRange.startSearch("move");
  };
}

Game_Temp_MovingRangeDisplayMixIn(Game_Temp.prototype);

実際には引数としてmoverやactor, modeの情報を受取る関数になるかもしれませんが、その場合でも別に Scene_Map クラスに定義する理由はないかなと思います。
Game_Temp クラスに定義しておけば、ひとまず $gameTemp.calcMovableRange() 等として呼び出せるので、Sceneクラスに直接アクセスしなくて済みます。

[BumbleB]

Plasma Darkさん
いつもありがとうございます！そしてここまで詳しく添削していただけるとは…とても助かります。

まず本題の処理の軽減ですが

各マスを探索する際に最大の残り移動力を記録しておき、次に同じマスを探索しようとする際に残り移動力がそれ以下の場合は、その探索を打ち切ってしまいましょう。

ということですね。今回でいうとTiledataにmovePowerの数値を持たせて探索する前に比較する…といったかたちでしょうか。色々試してみます。

それからJavascript全般についてですが、自分はこれまで初期のツクールMVのプラグイン講座で勉強して、基本その書き方に合わせてきたので、できるところからアップデートしていきたいと思います！
実際constとletとか厳格モードとか、使わなくてもいいなら手を出さないでおこうみたいな意識が多かったのですが、やはり曖昧な書き方を減らすというのが大事ということなんですね。
classについてはいまいち理解していないのでこれから勉強して使いこなせるようにしていきたいと思います。
（カプセル化・クラスの責務という考え方も少しずつ……まだまだその段階ではないですが意識しようと思います）

改めてこのような個人レッスンまでしていただき恐縮です。「動けばいいや」から脱却して少しずつレベルアップできるよう精進いたします。

[名無し蛙]

そもそも軽量化を考えるのなら再帰アルゴリズムは使用しない方が良いと思いますよ。
コード量が少なく魅力的ではあるんですけど
一般的には関数呼び出し時のオーバーヘッドが大きいとされています。（厳密には言語や状況に拠りますけど）
まぁ、移動可能範囲の計算くらいなら適切な枝刈りさえすれば実用可能かもしれませんが。
例として非再帰の移動可能計算処理の方向性を考えるのならこんな感じですかね？

コード: 全て選択

// 開始位置x、開始位置y、移動力
// ret: [移動可能位置x, 移動可能位置y]の配列
 const testMethod = (x, y, n) => {
     let a = [];
     a.push([x, y]);
     for (n--; 1 <= n; n--) {
         const b = [];
         a.forEach(pos => {
             [[-1, 0], [1, 0], [0, -1], [0, 1]].forEach(cor => {
                 const cand = [pos[0]+cor[0], pos[1]+cor[1]];
                 const c = a.concat(b);
                 if(!c.some(p => p.toString() === cand.toString())) {
                     b.push(cand);
                 }
             });
         });
         if (0 < b.length) {
             a = a.concat(b);
         } else {
             break;
         }
     }
     return a;
 }
 
 // 初期位置(10, 10)、移動力20指定
const test = testMethod(10, 10, 20);
// 結果を表示
test.forEach(pos => $gameMap.setTileTone(pos[0], pos[1], 0, 0, 200, 150)); 

追記：気になったので少し効率化しました。少し複雑化したので元のコードは残しておきます

コード: 全て選択

const testMethod = (x, y, n) => {
    const a = [];
    a.push([[x, y]]);
    for (n--; 1 <= n; n--) {
        const b = [];
        a[a.length - 1].forEach(pos => {
            [[-1, 0], [1, 0], [0, -1], [0, 1]].forEach(cor => {
                const cand = [pos[0]+cor[0], pos[1]+cor[1]];
                const c = a.reduce((arr, elem) => arr.concat(elem), []).concat(b);
                if(!c.some(p => p.toString() === cand.toString())) {
                    b.push(cand);
                }
            });
        });
        if (0 < b.length) {
            a.push(b);
        } else {
            break;
        }
    }
    return a.reduce((arr, elem) => arr.concat(elem), []);
}

更に追記：軽量化案を思いついたので更に効率化しました。
ここまでやれば多少広いマップ全域を走査しても数ミリ秒程度に収まると思います。
良ければ高速化の参考にしてください。

コード: 全て選択

const testMethod = (x, y, n) => {
    const a = [];
    a.push([[x, y]]);
    const check = [];
    for(let i=0; i<$gameMap.width(); i++) check.push(Array($gameMap.height()));
    check[x][y] = n;
    for (n--; 1 <= n; n--) {
        const b = [];
        a[a.length - 1].forEach(pos => {
            [[-1, 0], [1, 0], [0, -1], [0, 1]].forEach(cor => {
                const x = pos[0]+cor[0];
                const y = pos[1]+cor[1];
                if ( !$gameMap.isValid(x, y) ) return;
                if( (check[x][y] || 0) < n ) {
                    b.push([x, y]);
                    check[x][y] = n;
                }
            });
        });
        if (0 < b.length) {
            a.push(b);
        } else {
            break;
        }
    }
    return a.reduce((arr, elem) => arr.concat(elem), []);
}

[BumbleB]

名無し蛙 さん
ありがとうございます、ちょっと処理の内容を理解するのに時間がかかってしまったのですが、確かに10以上の移動範囲を指定してもほとんど重くならないですね！使わせていただきたいと思います。

いろいろてこずってしまったのですが、アドバイスを参照して改善版を作成しました。配布用というよりは直した成果くらいのものなのですが、あげておきます。まだ至らない所が色々とあると思いますが、大目に見ていただけると幸いです…。

[BumbleB]

ごめんなさい！教えていただいた非再帰の移動可能計算処理についてなのですが
もう少しお伺いしてよろしいでしょうか。

あれから少し書き換えてリージョンが設定されているタイルだけ移動できるようにしました。
これを利用して、森や荒れ地のような移動困難な地形を設定して、そこを通過する時は移動力がリージョンの数値分減少するようにしたいと考えています。
例えば、通常の地形は1マスごとに移動力-1で移動範囲を計算しますが、リージョン番号が2以上のときはその数値分移動力をマイナスして移動範囲を計算するということですが、この非再帰の処理でも実装することができるでしょうか？

色々試してみたのですがちょっと自分には難しそうだったので、ご教授いただければ幸いです。

[名無し蛙]

あれから少し書き換えてリージョンが設定されているタイルだけ移動できるようにしました。
これを利用して、森や荒れ地のような移動困難な地形を設定して、そこを通過する時は移動力がリージョンの数値分減少するようにしたいと考えています。
例えば、通常の地形は1マスごとに移動力-1で移動範囲を計算しますが、リージョン番号が2以上のときはその数値分移動力をマイナスして移動範囲を計算するということですが、この非再帰の処理でも実装することができるでしょうか？

少し本筋からズレるんですけどMVには地形タグ（$gameMap.terrainTag(x, y)）というものがあるので
地形に応じて移動力減衰という仕様を加えるのならリージョンよりもそちらを活用した方が良いと思います。

それで直接添削したいのは山々なんですけど
テスト環境を揃えるのが面倒なので引き続き自分が書いたコードの改修で回答したいと思います。

コード: 全て選択

const testMethod = (x, y, n) => {
    const a = [];
    a.push([[x, y]]);
    const check = [];
    for(let i=0; i<$gameMap.width(); i++) check.push(Array($gameMap.height()));
    check[x][y] = n - $gameMap.terrainTag(x, y);
    for (n--; 1 <= n; n--) {
        const b = [];
        a[a.length - 1].forEach(pos => {
            const balance = check[pos[0]][pos[1]];
            [[-1, 0], [1, 0], [0, -1], [0, 1]].forEach(cor => {
                const x = pos[0]+cor[0];
                const y = pos[1]+cor[1];
                if ( !$gameMap.isValid(x, y) ) return;
                const moveCost = 1 + $gameMap.terrainTag(x, y);
                if( (check[x][y] || 0) < (balance - moveCost) ) {
                    b.push([x, y]);
                    check[x][y] = balance - moveCost;
                }
            });
        });
        if (0 < b.length) {
            a.push(b);
        } else {
            break;
        }
    }
    return a.reduce((arr, elem) => arr.concat(elem), []);
}

変更、及び追加をしている箇所は

コード: 全て選択

check[x][y] = n - $gameMap.terrainTag(x, y);
const balance = check[pos[0]][pos[1]];
const moveCost = 1 + $gameMap.terrainTag(x, y);
if( (check[x][y] || 0) < (balance - moveCost) ) {
check[x][y] = balance - moveCost;

の5点。元々の

コード: 全て選択

if( (check[x][y] || 0) < n ) {

という条件式のnの部分を少し複雑化させただけで大筋に変更はないと思います。
二次元配列checkに保存する数値を残り移動力に変更した程度です。
これで地形に応じた移動力の減衰にも対応出来るのではないかなぁと。

追記：ちょっと変更
地形タグ0を移動減衰1に、それに地形タグ分の数値をコスト増加させた方が設定し易いですかね。
それと移動開始地点の地形タグを把握し忘れていたのでそこも修正。

[BumbleB]

名無し蛙　さん

度々ありがとうございます！遅くなってしまいましたが、無事実装できました。
地形タグも考えたのですが、今のところ1枚絵（パララックスマッピングプラグイン）でマップを作ろうと思うので
タイルは貼らない予定でした！
でも透明なダミータイルで地形効果を表現するみたいなやり方もあると思うので、リージョン設定だと他のプラグインと折り合いがつかない…みたいなときには試してみようと思います。ありがとうございます。