地図の連結成分を調べるプログラム

Question

地図の連結成分を調べるプログラムを書いています。
連結成分とは、ここでは、20×20のマス目状の領域において、上下左右で繋がっている黒マス同士が作る領域のことです。
領域は、二次元配列wall_2により管理しており、値0を持つマスが黒、値1を持つマスが青（壁の役割）、そして連結領域を見つけるスタートになるマスを値2として設定しています。
この値2のマスから徐々に領域を広げてゆき、連結領域の値を0でなくしてゆく関数がmove_map()と名付けた関数なのですが、この関数の実行結果が嫌に遅いのが気になっています。
もし原因についてわかる方がおられましたらよろしくお願いします。
また、move_map()という関数は一度実行しただけだと、連結領域全体に広がらないような気がするのも気のせいでしょうか？
御助力お願いいたします。

ソースコード１
ソースコード２

※追記

let wall_2 =[];
for(let i=0; i<20; i++){
    wall_2[i] = [];
    for(let j=0; j<20; j++){
        wall_2[i][j] = 0;
    }
}
for(let i=0; i<20; i++){
    wall_2[i][5] = 1;
}

for(let i=6; i<20; i++){
    wall_2[5][i] = 1;
}

wall_2[0][0] = 2;

function Max(array){
    points = []
    for(let i=0; i<20; i++){
        for(let j=0; j<20; j++){
            if(array[i][j] === Math.max(...(array.flat()))){
                points.push([i,j])
            }
        }
    }
    return points;
}



function move_map(array){
    number = Math.max(...(array.flat()));
    console.log(number);
    console.log(Max(array));
    for(let i = 0; i < Max(array).length; i++){
        X = Max(array)[i][0];
        Y = Max(array)[i][1];
        console.log([X,Y]);
            if(X+1 <20 && array[X+1][Y] === 0){
                array[X+1][Y] = number + 1;
            }
            if(-1 < X-1 && array[X-1][Y] === 0){
                array[X-1][Y] = number + 1;
            }
            if(Y+1 <20 && array[X][Y+1] === 0){
                array[X][Y+1] = number + 1;
            }
            if(-1 < Y-1 && array[X][Y-1] === 0){
                array[X][Y-1] = number + 1;
            }  
    }
}

Max()という関数は領域中に振った値のうち最大値をとる点の座標を配列として取得する関数です。

Comments

[ppaul]

OpenCVのFloodFillを使えば済む問題なのではないですか？

[justmeet0924]

そういうものがあること自体知りませんでした・・・・。
確かに同じ機能なのかもしれません。
しかし、自分で実装すると、そこからの発展を自分で考えられたりと、色々と利点があるので・・・。
なかなかに難しい問題なのでしょうか？
プログラム自体は簡潔なものに見えるのですがね。

[justmeet0924]

また、プログラミングを教える際の教材にしようという狙いもあります。
こういうものが簡単に組めるよね〜、って紹介したいのです。

[fana]

（同じ話を先に回答に書いちゃったけど）
"FloodFill" はアルゴリズムの名称なのでOpenCVとは無関係にとりあえずググると良いのでは．

[fana]

何やら解決したことになってますが，

> また、move_map()という関数は一度実行しただけだと、連結領域全体に広がらないような気がするのも気のせいでしょうか？

こっちの話はどうなったのでしょう？　誰も（明示的には）触れていない状況ですが．

＃質問として項目を複数並べたのであれば→それら全てに決着をつける形で閉じてほしい，と思う．

[justmeet0924]

解決結果については、次の質問で触れています。ご興味ありましたら、そちらもご覧くださると助かります。

[fana]

【move_map()という関数は一度実行しただけだと不十分である可能性がある】という疑念を抱いていたのではないのですか？
この点についてはどう解決したのですか？
「やっぱ気のせいだったわ．一回実行すりゃあまともに動くわコレ」とかいう話なのかそうでないのか？
あるいは「この点については明確になってないけど，とりあえずもういいや」という話なのですか？

この話の顛末をあえて他の質問に書く 必要性/正当性 は無いと思いますが．

[justmeet0924]

僕が勘違いしていた点について。
forループの条件式は、「一度読み込んだらループ文中の処理に影響されない」という思い込みがありました。
ループ文中の条件式に、「i < Max(array).length」というループ処理の回数を規定する式がありますが、これがループ文中の処理に影響を受けて、増大する、という問題点がありました。
arrayが二次元配列で、２から始まって、０の空隙を２以上の整数で埋めていくので、それに応じて、Max(array)という配列に点がたくさん代入されていくことになる。
また、Max(array)というのはarrayに振ってある値の最大値をとる点たち、なのですが、これはすなわち空隙に向かって進んでいる領域の境界上の点であり、さほど数が多くならないはずです。
しかし、僕の書いたプログラムでは、＋１が上手く機能しておらず、領域の境界のみならず、内部の点まで最大値を取り始め、その結果、Max(array).lengthが膨大になり、処理が無駄に増えていたようです。

[justmeet0924]

その点を整備していくと、１度に自分の周囲の値０の領域を１マスずつ進んでいく関数が作れました。

Answer 1

2重ループの中で、配列を毎回展開していたのでは遅くなるのは当然。

function Max(array){
    points = [];
    let M = Math.max(...(array.flat()));

    for(let i=0; i<20; i++){
        for(let j=0; j<20; j++){
            if(array[i][j] === M){
                points.push([i,j])
            }
        }
    }
    return points;
}

Comments

[justmeet0924]

素晴らしいですね。
そういう視点があること自体新鮮でした。
現代のコンピューターに対する過信が生んだ失敗ですね。
実感としては、画像を読み込んだりする処理（？）の方が数千倍負荷がかかってるような気がします。
小さい箱に入った色情報を何万個と処理するので。
20×20の配列って意外にパワーがある？

[justmeet0924]

適切に答えてくださったこと、感謝します！

Answer 2

JavaScript を使った事ない者の推測でしかないのですが，

Max()という関数は領域中に振った値のうち最大値をとる点の座標を配列として取得する関数

という（話だけでも遅そうな）やつを何度も呼ぶというのが遅い理由ではないでしょうか．

要は，ペイントソフトの「同じ色が繋がっている個所を塗りつぶす」みたいな処理をしたいのだと思うので，そこで「最大値をとる」という処理が何故必要なのか？という点がわかりかねますが，
やりたいことは単なる幅優先探索みたいな処理なのだと見受けるので，「幅優先探索」で検索すれば出てくるようなスタック構造キューを用いたような実装をしてみて，速度を比較してみてはどうでしょうか．

Comments

[fana]

うお，サクッとボケてたぜ．
幅優先ならキューだな．スタックにしたら深さ優先な方向だ．