Javascript と Vue を組み合わせて、あらゆる迷路画像の自動パス検索を実現します。

序文

最終的な効果を直接体験できます: https://maze-vite.vercel.app/

パスファインディング前:

パスファインディング後、画像上に赤いパスが自動的に生成され、青い領域が探索された領域になります。

ここでは、携帯電話で撮影した迷路写真をプログラムが完全に処理できることを示すために、意図的に携帯電話を斜めから撮影しました。

プログラム全体を Vue 3 + Vite で書くつもりですが、実際には Vue を使用するかどうかは問題ではありません。複雑なインターフェースは含まれませんし、他のフレームワークを使用することも、フレームワークをまったく使用しないことも完全に可能です。

2次元配列、一方向

最初から始めるべきだと言ったので、非常に簡単な迷路から始めましょう。

私たち人間にとって、この迷路は非常に単純で、明らかな道が 1 つしかありません。しかし、コンピューターがそのような迷路を解くには、まだ少しの労力が必要です。

この迷路を表現するには、2 次元配列が適しています。

定数m = [
  [1, 1, 0, 0, 0],
  [0, 1, 1, 1, 0],
  [0, 0, 0, 1, 0],
  [0, 0, 0, 1, 1]
]

1 は歩行可能なグリッドを表し、0 は歩行不可能なグリッドを表します。各グリッドは[x, y]で表すことができます。たとえば、開始点は[0, 0]、終了点は[3, 4]です。

次に、次のような関数があります: functionsolveMaze function solveMaze (matrix, begin, end) {//...} 、matrix は迷路を記述する 2 次元配列、begin は開始点、end は終了点、最終的な戻り値は順序付けられたセット、各要素はグリッドであり、正しいルートの軌跡を表します。

ここで使用する戦略は非常にシンプルです。開始点から開始し、周囲を見回してどのグリッドが通行可能かを確認します (斜めに歩くことはできません)。次に、このグリッドに移動し、終了グリッドに到達するまで上記の手順を繰り返します。前の手順のグリッドも記録し、戻らないように除外する必要があることに注意してください。詳細については次のコードを参照してください。

// 迷路.js

関数 getPoint(m, x, y) {
  (x >= 0 && y >= 0 && x < m.length && y < m[x].length) の場合 {
    m[x][y]を返す
  } それ以外 {
    0を返す
  }
}

関数 getNextPoint(m, current, lastPoint) {
  [x, y] = 現在の値とする
  次のポイントを [
    [x - 1, y]、[x + 1, y]、[x, y - 1]、[x, y + 1]
  ].find(p => {
    r1 = getPoint(m, p[0], p[1]) > 0とする
    r2 = !isSamePoint(p, lastPoint) とします。
    r1 && r2を返す
  })
  次のポイントを返す
}

関数 isSamePoint(p1, p2) {
  p1[0] === p2[0] && p1[1] === p2[1] を返す
}

関数solveMaze（行列、開始、終了）{
  パス = [] とする

  // 現在のポイント let current = begin
  パス.push(現在)

  // 前回歩いた道 let lastPoint = begin

  // ランダムにポイントを選んで進む while (1) {
    if (isSamePoint(現在, 終了)) {
      壊す
    }

    validPoint = getNextPoint(行列、現在のポイント、最後のポイント)

    パス.push(有効なポイント)
    lastPoint = 現在の
    現在の = 有効なポイント
  }
  戻り経路
}

定数m = [
  [1, 1, 0, 0, 0],
  [0, 1, 1, 1, 0],
  [0, 0, 0, 1, 0],
  [0, 0, 0, 1, 1]
]

コンソール.log(
  迷路を解く(m, [0, 0], [3, 4])
）

getNextPoint は次の通過可能なグリッドを取得し、solveMaze は最終的な通過可能なパスを取得します。コンソール出力は次のようになります。

これらの座標は最終的な歩行軌跡であり、正しいように見えます。

基本インターフェースのマッピング

テストと観察を容易にするために、データ構造を Web ページにマッピングする必要があります。

// 迷路.js
// ...

//solveMaze関数をエクスポートし、Vueコンポーネントがexport {を呼び出すようにします
  迷路を解く
}

<テンプレート>
  <div>
    <div class="div-matrix">
      <div v-for="(行, x) 行列内" :key="x">
        <div クラス="セル" 
          :class="{ black: p <= 0, path: isPath(x, y) }"
          v-for="(p, y) 行内" :key="y" :style="{ 左: `${y * 2.5}em`, 上: `${x * 2.5}em` }">
          {{ begin[0] === x && begin[1] === y ? 'B' : '' }}
          {{ end[0] === x && end[1] === y ? 'E' : '' }}
        </div>
      </div>
    </div>
  </div>
</テンプレート>

<スクリプト>
'./maze' から {solveMaze} をインポートします

エクスポートデフォルト{
  データ （） {
    戻る {
      開始: [0, 0],
      終了: [3, 4],
      行列: [],
      パス: []
    }
  },
  メソッド: {
    isPath(x, y) {
      const p = this.paths.find(path => path[0] === x && path[1] === y)
      戻るp
    }
  },
  作成された（）{
    定数m = this.matrix = [
      [1, 1, 0, 0, 0],
      [0, 1, 1, 1, 0],
      [0, 0, 0, 1, 0],
      [0, 0, 0, 1, 1]
    ]
    this.paths = 迷路を解く(m, this.begin, this.end)
  }
}
</スクリプト>

<スタイル>
.トップ{
  下マージン: 1em;
}
.div-matrix {
  位置: 相対的;
}
.セル{
  境界線: 1px 黒実線;
  幅: 2em;
  高さ: 2em;
  位置:絶対;
  テキスト配置: 中央;
}
.セル.パス{
  境界線: 1px 赤実線;
}
。黒 {
  背景：黒;
}
</スタイル>

最終結果:

実際には、対応する div は 2 次元配列マトリックスを通じて生成され、配列内の要素値によって黒と白が決まります。パス配列には結果のパスが格納され、パスは赤い枠でマークされます。これにより、後でテスト結果を確認しやすくなります。

幅優先、包括的検索

次の迷路を見てください。

定数m = this.matrix = [
  [1, 1, 0, 0, 0],
  [1、1、1、1、1]、
  [0, 1, 0, 1, 0],
  [0, 1, 0, 1, 1]
]

上記のコードに適用すると、ページが停止していることがわかります。これは、迷路に分岐があり、アルゴリズムがぐるぐる回っているためです。もう一度同じ道を歩かなくて済むように、通った道を記憶する何らかの手段が必要です。その方法は難しくありません。現時点で歩けるグリッドをキューに入れるだけです。そして、最後のグリッドに到達するまで、キュー内のグリッドに対して同じことを繰り返します。

アルゴリズムの処理を容易にするためには、グラフ構造という新しいデータ構造を使用してそれを表現する必要があります。

グラフ構造はリンク リストと非常に似ていますが、最大の違いは、各ノードが異なるノードを指す複数のポインターを持つことができることです。

同時に、2 次元配列の次元を 1 次元に削減します。

定数m = [
  1、1、0、0、0、
  1、1、1、1、1、
  0、1、0、1、0、
  0、1、0、1、1
]

このアクセスはそれほど直接的ではありませんが、必要なのは 1 つのアドレス指定だけであり、コピーと転送は 2 次元配列よりもはるかに便利です。

次に、ノードを表す Node クラスと、グラフ構造全体を表す NodeGraph クラスを作成します。

クラスノード{
  コンストラクタ (x, y, 値) {
    this.x = x
    this.y = y
    this.value = 値
    this.checked = false
    this.nearNodes = []
  }
}

クラス NodeGraph {
  コンストラクタ（行列、幅、高さ）{
    this.nodes = []
    this.matrix = マトリックス
    this.width = 幅
    this.height = 高さ
  }

  ビルドノードグラフ（）{
    {幅、高さ} = thisとする
    
    (y = 0; y < 高さ; y++) の場合 {
      (x = 0; x < 幅; x++) の場合 {
        ノード = this.getNode(x, y) とします。
  
        上へ = this.getNode(x, y - 1)
        下げる = this.getNode(x, y + 1)
        左 = this.getNode(x - 1, y) とします。
        右 = this.getNode(x + 1, y) とします。
        node.nearNodes = [ 上、下、左、右].filter(node ​​=> node && node.value === 1)
      }
    }
  }

  getNode (x, y) {
    {ノード、幅、行列} = this
    (x >= 0 && y >= 0) の場合 {
      ノード = ノード[y * 幅 + x]とします。
      if (!ノード) {
        値 = 行列[y * 幅 + x]とする
        （値 !== 未定義）の場合{
          ノード = 新しいノード(x, y, 値)
          ノード[y * 幅 + x] = ノード
        }
      }
      戻りノード
    } それ以外 {
      nullを返す
    }
  }
}

buildNodeGraph は、マトリックス配列をグラフ構造に変換します。各ノードの nearNodes は、次に探索できるグリッド セットに相当します。チェックされているかどうかは、ノードが探索されたかどうかを示します。

各ステップのステータスの変化を簡単に確認するには、画面上で現在のグリッドとキュー内のグリッドをマークする必要があります。完全なコードは投稿しませんが、codesandbox で自由に読むことができます。

青い枠線はキュー内のグリッドで、小さな人物は現在のグリッドです。右下隅に到達すると停止します。

今私たちが行ったことは、小さな男をスムーズに終点まで移動させることだけですが、どうすれば目的のパスを取得できるのでしょうか?この方法は、前のノードを記録するために、ノードに追加の属性 parent を追加することです。 nearNodes を取得するときは、現在のノードを各 nearNode の親に割り当てます。

// ...
for (let ノードの current.nearNodes) {
  ノードがチェックされている場合は false になります
	node.parent = 現在の
	キュー.push(ノード)
  }
}
// ...

次に、現在のノードから親を読み取り、1 つずつ遡ります。

関数buildPath(endNode){
  パス = [] とする
  ノード = endNode とする

  while (ノード) {
    パス.push(ノード)
    ノード = ノード.親
  }

  戻り経路
}

効果：

小さな男が端に到達すると、赤い四角が最短経路になります。

マップ編集

コードを少し変更するだけで、迷路をリアルタイムで編集できるようになり、テストがより便利になります。

操作: 四角をクリックすると白黒の状態が変更され、Alt キーを押しながらクリックすると新しいターゲット ポイントが設定されます。

外部アクセスをより便利にするために、solveMaze のローカル変数を NodeGraph クラスに徐々に移動します。パスファインディングが終了したら、関数を終了せず、while ループを使用して新しいターゲット ポイントが設定されるまで待機することに注意してください。

// ...

    if (equalsNode(current, nodeGraph.endNode)) {
      while (equalsNode(current, nodeGraph.endNode)) {
        スリープを待つ(1000)
      }
      続く
    }
// ...

経路探索アルゴリズムの最適化

次のシナリオを想像してください。

スタート地点とゴール地点は直線上にあり、間に障害物はありませんが、この小さな男はあちこち走り回っており、ゴール地点に到達するまでに時間がかかります。これではうまくいかないので、最適化する必要があります。

各ノードから終点までの距離を記録するために、Node クラスに endDistance 属性を追加します。getDistance 関数は、座標に基づいて距離を直接計算できます。この距離は、途中にある可能性のある障害物を考慮していませんが、ルート評価にも非常に役立ちます。

クラスノード{
  コンストラクタ (x, y, 値) {
    this.x = x
    this.y = y
    this.value = 値
    this.endDistance = 0 // 途中の障害物を無視した終点までの距離 this.checked = false
    this.parent = null
    this.nearNodes = []
  }
}

関数 getDistance(nodeA, nodeB) {
  定数 x = Math.abs(nodeB.x - nodeA.x)
  定数 y = Math.abs(nodeB.y - nodeA.y)
  戻り値 (x + y)
}

毎回、endDistance が最小のノードが popBestNextNode メソッドを通じてキューから取り出されます。

クラス NodeGraph {
// ...

  ポップベストネクストノード(){
    {キュー} = this
    bestNode = キュー[0]とする
    bestNodeIndex = 0 とします
    {長さ} = キューとする

    (i = 0; i < 長さ; i++) の場合 {
      ノード = キュー[i]
      （node.endDistance < bestNode.endDistance）の場合{
        bestNode = ノード
        ベストノードインデックス = i
      }
    }

    キュー.splice(ベストノードインデックス、1)
    ベストノードを返す
  }
// ...
}

endDistance が存在するため、開始点からの歩数を記録する beginDistance も存在する必要があります。この値は座標から直接計算されるのではなく、前進するにつれて累積されるため、beginDistance は推定値ではなく実際の値になります。

// ...
for (let ノードの current.nearNodes) {
  ノードがチェックされている場合、ノードの値は次のようになります。
	node.parent = 現在の
	ノードがチェックされている = true
	node.endDistance = getDistance(node, nodeGraph.endNode)
	ノードの開始距離 = 現在の開始距離 + 1
	ノードコスト = ノード終了距離 + ノード開始距離
	ノードグラフ.キュー.プッシュ(ノード)
  }
}
// ...

将来的に新たな要素が追加される可能性を考慮し、コストを表現するためにコスト属性が直接追加されます。現在、コストは endDistance + beginDistance です。コストが小さいほど、優先度が高くなります。

このような状況で、小男は最初は上から近づこうとしましたが、前進し続けるうちに歩数が増え、下ったほうがよいと判断し、上のルートをあきらめました。

これで、悪役の行動がより信頼できるものになりました。

画像のパスファインディング

私が描いたこのランダムな絵をパラメータとして取ってください:

目標は、ポイント B からポイント E に到達することです。この画像のピクセルを読み取り、それを白黒カラーに基づく配列に変換し、solveMaze 関数に入力するだけです。

これを行うには、画像を選択するための type="file" の入力タグが必要で、URL.createObjectURL(File) を通じて URL を生成し、次に new Image() を使用して、本文に追加する必要のない img タグを作成し、その URL を img.src に渡します。 CanvasRenderingContext2D.drawImage() を介してそれを Canvas にコピーし、次に CanvasRenderingContext2D.getImageData() を呼び出してピクセル配列を取得します。

現時点では、この画像には数万のピクセルがあり、各ピクセルに div があるとブラウザが処理できず、将来的に画像がさらに大きくなるため、レンダリングに div を使用することはできません。

ここでは、レンダリングに Canvas を使用し、3 つの Canvas を配置します。1 つは迷路の元の画像を表示し、1 つは探索したノードを表示し、もう 1 つは現在の最短パス、つまりパス配列内のノードを表示し、これら 3 つの Canvas を積み重ねます。最後に、コールバックで最後の 2 つの Canvas を更新するだけです。

上記の画像をコンピュータにダウンロードし、[ファイルの選択] ボタンをクリックして画像を選択すると、効果を確認できます。他の画像を選択することもできますが、開始点と終了点の座標はハードコードされており、コードが最適化されていないため、大きすぎる画像を処理するのは難しい場合があります。

注: クロスドメインの問題が発生した場合は、自分で画像をアップロードする必要があります。

出発地をカスタマイズし、いつでもルートを変更できます

クリックイベントの offsetX と offsetY を使用することでクリック座標を知ることができ、開始点と終了点の座標を保存できます。変更があった場合は、以前のパス検索関数を停止し、現在のパス検索関数を再実行します。そのため、関数を終了するかどうかはループ内で判断する必要があります。これはコールバックで行うのに適しています。

次に、画面を更新する前のサイクル数を自由に調整するための入力ボックスを提供し、経路検索の速度を調整できるようにします。

カラー画像の処理

プレビュー: https://codesandbox.io/s/maze-vite-8-h845p?file=/src/App.vue (クロスドメインエラーが発生した場合は、自分で画像をアップロードしてください)

もう iframe は入れません。iframe が多すぎると、このページがかなり固まってしまう気がします。

以前は、白いピクセルが歩行可能な領域であると想定されていました。今後は、同様の色を持つ近くのピクセルを歩行可能な領域として使用するようにすると、より効果的になります。

RGBA カラー データを直接solveMaze に渡し、ループ内で隣接ノードと現在のノード間の色差を計算します。差が大きすぎる場合は、キューに入れられません。

RGBA 整数のチャネルを分離するには、次のように記述します。

/**
 * ノードのRGB値を取得します * @param {Node} ノード 
 * @戻り値 
 */
関数 getNodeRGB (ノード) {
  {値} = ノード
  r = 値 & 0xFFとする
  g = 値 >> 8 & 0xFF とします
  b = 値 >> 16 & 0xFF とする
  [ r, g, b ] を返す
}

RGB カラーの類似性を調べる最も簡単な方法は、2 つの色を 3 次元座標を持つ 2 つの点と見なし、それらのユークリッド距離を調べることですが、これは人間の目の知覚モデルには適合しません。詳細な方法はWikiですでに公開されています: https://zh.wikipedia.org/wiki/ColorDifference

この部分の計算は少し複雑なので、color.js で記述しました。

結果：

コード内の colorDiffThreshold に注意してください。現在、2.25 を使用しています。高すぎると壁を通り抜けてしまいます。低すぎると、簡単に道を見つけられなくなってしまいます。

パフォーマンスの最適化

画面を 2 回クリックした後、パス検索が開始されるまでしばらく待つ必要があります。これにより、CPU が大量に消費されます。 DevTools でパフォーマンス アナライザーを開き、パフォーマンスが最も消費される場所を分析します。

明らかに、solveMaze 関数がほとんどの時間を占めています。以下の呼び出しツリーを展開します。

buildNodeGraph と getNode は最適化の重要なポイントです。コードを開くと、各文で消費される CPU 時間を直接確認できます。

57行目のif (!node) {...}は判定が単純ですが、時間がかかります。これをnode === undefinedに変更すると、値の判定が不要になります。ノード配列へのアクセスと読み取りにも時間がかかります。最初にnew Array(length)で初期化してみてください。これで改善されるはずです。最適化されたコード:

少し良くなったようです。

パスファインディング中のパフォーマンス監視:

buildPath はかなり時間がかかることがわかりましたが、それは当然です。結局のところ、ループのたびに呼び出され、チェーン全体を完全にトラバースするからです。解決方法も簡単です。最終結果が出力されるときに呼び出すだけです。これまでの経験から、while (node) を while (node ​​!== null) に変更します。

今では彼の存在は全くありません。

次は for...of ステートメントです。これを、最も高速な従来の配列の添え字の自己デクリメントに変更することをお勧めします。もちろん、日常の使用では for...of の方が読みやすくなります。

次に、popBestNextNode を実行します。

ここでは、配列全体が毎回走査され、コストが最小のノードが検索され、最後に配列要素の削除操作も行われます。 JavaScript 配列が連続したメモリに格納されているのか、それとも分散されているのかを判断するのは非常に困難ですが、いずれにしても、代わりにバイナリ ヒープを使用するとパフォーマンスが向上します。自分で実装するのではなく、既存のものを使用します: https://www.npmjs.com/package/heap-js。カスタム コンパレータが new Heap() に渡され、popBestNextNode の実装が this.queue.pop() を返すように変更されることに注意してください。

最後に、buildNodeGraph 内の 2 つの for ループを削除し、すべてのノードを事前に初期化しないようにして、NodeGraph に新しいメソッドを追加します。

  getNearNodes (ノード) {
    {x,y} = ノードとする
    上へ = this.getNode(x, y - 1)
    下げる = this.getNode(x, y + 1)
    左 = this.getNode(x - 1, y) とします。
    右 = this.getNode(x + 1, y) とします。
    [上、下、左、右]を返します。フィルター(node ​​=> node !== null)
  }

後続のパス検索ループでは、隣接するノードを取得するために getNearNodes が呼び出され、初期の遅延が大幅に削減されます。

最後に、次の 2 つの戦略が提供されます。

• 厳密: 隣接するピクセル間の色の差が特定の値未満の場合、それらのピクセルはキューに追加されます。歩行エリアの色の変化が少ない画像の場合、結果はほぼ最短経路になります。
• ファジー: 隣接するピクセルは色の違いに関係なくキューに追加され、その違いの値はノードのコストとして特定の係数で乗算されます。どのような絵にも合い、最後には必ず道が見つかります。 。 。

nearNodes = nodeGraph.getNearNodes(現在) とします。
(i = nearNodes.length - 1; i >= 0; i--) の場合 {
  ノード = nearNodes[i]とする
  ノードがチェックされている場合は false になります
	ノードがチェックされている = true

	colordiff = getNodeColorDiff(ノード、現在のノード)
	const colorDiffThreshold = 2 // 許容される色差、範囲 0~100

	node.parent = 現在の
	node.endDistance = getDistance(node, nodeGraph.endNode)
	ノードの開始距離 = 現在の開始距離 + 1

	if (mode === "1") { // 厳密な node.cost = node.endDistance + node.beginDistance

	  色差が閾値未満の場合
		ノードグラフ.キュー.プッシュ(ノード)
	  }
	} else if (mode === "2") { // ぼかし node.cost = node.endDistance + node.beginDistance + (colordiff * width * height)
	  ノードグラフ.キュー.プッシュ(ノード)
	}
  }
}

ソースコード: https://gitee.com/judgeou/maze-vite

これで、Javascript と Vue を組み合わせて、任意の迷路画像の自動パスファインディングを実現する方法についての説明は終わりです。Javascript と Vue を組み合わせた迷路の自動パスファインディングに関する関連コンテンツの詳細については、123WORDPRESS.COM の以前の記事を検索するか、次の関連記事を引き続き参照してください。今後とも 123WORDPRESS.COM をよろしくお願いいたします。