次の図は、アルゴリズムが何をしなければならないかを示しています。
文字列マッチングなどの 1D 配列の場合、文字列検索アルゴリズムを使用できます。
ビットマップまたは 2 次元配列でそのような一致を効率的に見つけるにはどうすればよいでしょうか?
PS 与えられた例は、説明のみを目的としています。Bejeweled ソルバーの実装に複雑なアルゴリズムは必要ありません。ゲーム ボードを分割して N x N テーブルを作成し、各セルからピクセルをサンプリングし、RGB 値を確認して各セルに含まれるアイテムを特定するだけで完了です。たとえば、一致するビットマップ領域をクリックし続けるマクロプログラムで使用される一般的な画像領域一致アルゴリズムを知りたいです。
簡単なことではありません。ほとんどのゲームは、リージョン (宝石をちりばめた例で推測したように) またはカラー マップを使用して問題を回避します。カラー マップは、2 番目の描画を維持し、色ごとに位置を特定のアイテムにマッピングします。
ゲーム以外では、ルーチンは行列変換を使用してエッジと頂点を特定しようとします。これにより、マッチングの可能性を検討するデータの量が減る傾向があります。些細な例は、次のようなカーネルでフィルターを使用することです
kernel = [ -1 -1 -1 ]
[ -1 8 -1 ]
[ -1 -1 -1 ]
隣国とのバランスが取れていない地域を強調すること。そこから線と頂点の検出を試みることができ、一致で考慮するアイテムの数を大幅に減らすことができます。「近い」一致を検出する場合は、線形変換を使用して、頂点の変位を測定することで一致までの距離を記述し、一致が同じであるには遠すぎるかどうかを判断するための基準を設定します。
些細な解決策ですが、「完全な」データでのみ機能するのはxor、可能なすべてのオフセットに対して元のビットマップに対してビットマップを作成することです。画像が正確なビットマップで構築されていることがわかっている場合、ビットマップxorと同じサイズのゼロ フィールドが生成されます。この手法は、より高価なxor検証計算を試みる前に、選択したいくつかのピクセルが正確に一致するかどうかをチェックすることで、パフォーマンスをいくらか向上させることができますが、非常に望ましくない方法で考慮するスペースが大きくなると、パフォーマンスが低下します。