趣味で開発しているシミュレーションゲーム的なもので当たり判定っぽいものが必要になった。
ゲームでは何匹もの虫がいる。虫1匹毎に周囲の情報を集めてそれを Neural Network のモデルに渡してから次の移動方向を決定する...、みたいな流れになっている。（詳細は省くがこういうゲーム）
その際に周囲にいる自分以外の虫の情報が必要になる。例えば画像のような状態で赤い虫が行動する場合、赤い虫から数px（ピンクの範囲）に存在する虫 4, 5, 6 を取得したい。
2023-12-26 追記
最後の方で紹介しているが R-tree など多次元インデックス（空間インデックス）を実装しているライブラリを探したほうが良いかも。
ちなみに本稿で紹介している手法はグリッド（メッシュ）の方式らしい。
単純な実装
単純には以下のように実装できる。
しかしこの方法では虫の数に比例して計算量が増加する。実際、虫が数百〜数千程まで増えるとパフォーマンスが問題になった。
type Entity = { id: string; x: number; y: number; } // フィールド上にいる虫たち const entities: Entity[] = [ {id: "A", x: 10, y: 9}, {id: "B", x: 20, y: 15}, {id: "C", x: 20, y: 20}, {id: "D", x: 30, y: 50}, ] // 検索したい範囲を決める const query = { xFrom: 10, yFrom: 10, xTo: 20, yTo: 20 } // ループで1匹ずつ検証して、範囲内なら results に追加する const results: Entity[] = []; for (const entity of entities) { const isContained = (query.xFrom <= entity.x && entity.x <= query.xTo) && (query.yFrom <= entity.y && entity.y <= query.yTo); if (isContained) { results.push(entity); } } console.log(results); /* [ { "id": "B", "x": 20, "y": 15 }, { "id": "C", "x": 20, "y": 20 } ] */
グリッドに分割する方式
単純な実装では全ての虫をチェックする必要があったので遅くなった。
そこで、フィールドを細かいグリッドに分割しその範囲に存在する虫ごとに区切るようなデータ構造を使用してみた。
このように分割するとチェックする範囲は緑と青のマスだけで十分になる。
青いマスは確実にピンクの範囲の内側にあるため、4 は確定する。緑色のマスには範囲内と範囲外の虫が含まれるため、2, 5, 6 だけ座標が範囲内にあるのかをチェックするだけで良くなり速くなった。
単純な実装では 1~8 の 8回座標を比較する必要があったが、グリッドに分割する方式では 2, 5, 6 の 3回だけで良くなった。更に、虫が増えたとしても白いマスに存在する虫は精査の必要がないため単純な増加は起きない。（密に存在しなければ）
更に、メモリ効率も悪くない。一つの Array ではなくマスの分 Map に分割してオブジェクトを保持する必要はあるものの、オブジェクトは重複して保存されることはない。オーバーヘッドは 空の Map が求めるサイズ * マスの数なのでグリットを細かくしすぎなければ大した差は出ないはず。
最初のものと比較すると大分複雑になるが、以下のように実装できる。
type Entity = { id: string; x: number; y: number; } type Query = { xFrom: number; yFrom: number; xTo: number; yTo: number; } const height = 50; const width = 50; const gridHeightCount = 5; const gridWidthCount = 5; // 各マスに Map を使用すると、虫の座標が変わった際の更新が単純で高速になる（今回は考慮しないが） const grid: Map<string, Entity>[][] = [ [new Map(), new Map(), new Map(), new Map(), new Map()], [new Map(), new Map(), new Map(), new Map(), new Map()], [new Map(), new Map(), new Map(), new Map(), new Map()], [new Map(), new Map(), new Map(), new Map(), new Map()], [new Map(), new Map(), new Map(), new Map(), new Map()], ]; // 座標をグリッドの index に変換する function xIndex(x: number): number { if (x <= 0) { return 0; } if (x >= width) { return gridWidthCount - 1; } return Math.floor(x / (width / gridWidthCount)); } function yIndex(y: number): number { if (y <= 0) { return 0; } if (y >= height) { return gridHeightCount - 1; } return Math.floor(y / (height / gridHeightCount)); } const entities: Entity[] = [ { id: "A", x: 10, y: 9 }, { id: "B", x: 20, y: 15 }, { id: "C", x: 20, y: 20 }, { id: "D", x: 30, y: 50 }, ] // グリッドへ登録する for (const entity of entities) { grid[yIndex(entity.y)][xIndex(entity.x)].set(entity.id, entity); } function search(query: Query): Entity[] { const isContained = (entity: Entity): boolean => { return ( entity.x >= query.xFrom && entity.x <= query.xTo && entity.y >= query.yFrom && entity.y <= query.yTo ); }; const yIndexFrom = yIndex(query.yFrom); const yIndexTo = yIndex(query.yTo); const xIndexFrom = xIndex(query.xFrom); const xIndexTo = xIndex(query.xTo); const results: Entity[] = []; // 1マスだけが対象の場合 if(yIndexFrom === yIndexTo && xIndexFrom === xIndexTo){ for(const target of grid[yIndexFrom][xIndexFrom].values()){ if (isContained(target)) { results.push(target) } } return results; } // 絶対範囲の内側なのでチェックはしない（画像の青い範囲） for (let y = yIndexFrom + 1; y <= yIndexTo - 1; y++) { for (let x = xIndexFrom + 1; x <= xIndexTo - 1; x++) { for (const target of grid[yIndex(y)][xIndex(x)].values()) { results.push(target) } } } // 範囲内に存在するかどうかが確定しないのでチェックが必要（画像の緑の範囲） for (let x = xIndexFrom; x <= xIndexTo; x++) { // top 一列 for (const target of grid[yIndexFrom][x].values()) { if (isContained(target)) { results.push(target) } } // bottom 一列 for (const target of grid[yIndexTo][x].values()) { if (isContained(target)) { results.push(target) } } } for (let y = yIndexFrom + 1; y <= yIndexTo - 1; y++) { // left 一列 for (const target of grid[y][xIndexFrom].values()) { if (isContained(target)) { results.push(target) } } // right 一列 for (const target of grid[y][xIndexTo].values()) { if (isContained(target)) { results.push(target) } } } return results; } const results = search({ xFrom: 10, yFrom: 10, xTo: 20, yTo: 20 }); console.log(results); /* [ { "id": "B", "x": 20, "y": 15 }, { "id": "C", "x": 20, "y": 20 } ] */
npm package として公開してみた
個人的な開発で使うものとして作ってみたが、パッケージとして管理できたら面白いんじゃないかと思いたち npm のライブラリとして公開してみた。公開までは無料で簡単に行えた。自分だけがアクセスできる private な package を登録したい場合は月 7ドルかかるらしい。
GitHub Actions を設定してテストや npm 公開の自動化もついでにやってみた。これが無料で使わせてもらえるのすごいね。
ちなみにこちらでは、先程考慮しなかった座標の変化にも対応している。
R-tree という多次元インデックス（rbush）
この記事を書いたあとで気づいたのだが、R-tree という多次元（ライブラリは2次元）空間を効率よく検索するための木構造アルゴリズムを見つけてしまった。
パフォーマンスを比較すると検索速度に関しては完全に負けている。しかも search2d（自作）は点（高さと幅がゼロ）のオブジェクトしか対応していないに対し RBush は矩形に対応してる。基本的にこちらで良さそう。
ただし、データの登録速度に関しては search2d の方が20~30倍速かった。ひょっとすると高頻度で座標の更新がある & 矩形オブジェクトの検索が不要な場合はアドバンテージがあるかもしれない。
[ { name: 'Map1dSearch', // search2d (自作) registerTimeMs: 10, searchTimeMs: 118, deregisterTimeMs: 4 }, { name: 'RBushSearch', // rbush (R-tree) registerTimeMs: 351, searchTimeMs: 89, deregisterTimeMs: 2 } ]
