私は、で行われるスペースシューターを作っています大きなダンジョン。壁を定義する大きな長方形で構成されています。 Farseer Physicsを使用して、ゲーム内のすべてが物理的にシミュレートされます。ただし、1つの問題があります。ダンジョンを十分に大きくしたいのですが、グリッドに少なくとも80x80の長方形が必要です。つまり、最悪の場合、6400の物理的にシミュレートされたボディがあります。あなたが推測できるように、正確にパフォーマンスに優しい。
私の一時的な解決策は、グリッドを垂直スライス。すべての列に対してブール加算操作を使用してすべての長方形が追加され、結果の凹多角形を使用してボディが作成されます。少しパフォーマンスが向上しますが、ポリゴンは混乱し、存在しなくなり、通常は通過可能な無効なウェイをブロックし、Farseerをクラッシュさせる傾向があります。
私はある種の何らかの方法で壁の最大領域を見つけてそれらを1つの大きな長方形にマージし、すべての穴が埋められるまで小さな長方形に対してこれを続けるアルゴリズムですが、これを実装する方法がわかりません。それは完璧な解決策のように思えます。パフォーマンスの問題と、私が今抱えている凹面の多角形の問題を解決できるからです。
私のゲームでは多くのことがエンジンに依存しているため、物理エンジンの使用を完全に停止することは解決策ではありません。
編集：ここでは、ボディが今どのように見えるかの小さな例です：（すべての数字はボディです）
そして、これは私が彼らになりたい方法です：
回答：
回答№1は1私は質問を正しく理解していないかもしれませんが、あなたの問題を解決するためのちょっとしたヒントだと思うアルゴリズムを提案させてください。
あなたの問題は、正方形がある長方形の欲から始まります 無料 そして ノンフリー。最初から 無料 正方形は壁を構築するもので、 ノンフリー 正方形は中空のスペースです。
- フォアハ 無料 広場は 拡張 その正方形の周りに、その正方形が属することができる最大の領域が何であるかを参照してください。沿って 拡張 その広場からすべての方向に進むことを意味します。 無料 正方形。この最大のエリアを指定されたエリアに関連付けます 無料 平方。
- 最大の関連付けられた領域を持つ正方形を選択し、その正方形の周りに拡張することにより、マージされた壁を構築します。このマージに属する正方形は次のようにマークされます ノンフリー。もうない場合 無料 完了したら、ステップ1に進みます。
完了したら、壁の可能な限り大きなブロックをグループ化する必要があります。
明確にするために、 拡張 〜の周り 無料 square与えられた正方形からすべての利用可能な方向に構築できる仮想の最大の長方形を取ることを意味します。
長方形に対するこのアルゴリズムの複雑さ n*m マトリックスは直観的に O(n*n*m*m)。実際には、それは非常に速いと思いますあなたのデータ。このアルゴリズムは、オブジェクトの数を最少にするのではなく、すべての領域の合計を最大化することに注意してください（質問どおり）。ボディの総数を最小化する問題は、複雑さの点ではるかに困難です。
回答№2の場合は1
これは、私のゲームの1つで使用したものです（C＃でもありません）。
まず、固体の壁で配列を作成し、次のような構造を作成します Wall、intergersと x, y, width そして height、ブロックごとに1つずつ作成します。
次に、それらをループし、同じものをマージします y そして height、およびネイバー（x₁ + width₁ = x₂）。
次に、もう一度ループします。今回は x の代わりに y （およびその逆）、および使用 width の代わりに height （およびその逆）。
これは最適化されていませんが、より速くするために変更できます。これは私のゲームで使用した実装でした。あなたには遅すぎるかもしれません。
これを実行すると、38個のボディが生成されます（これは投稿した例と同じボディ数です）：
最後の2つのステップで順序を逆にすると、36個のボディが生成されます。
回答№3の場合は0
Farseerを使用すると、使用する必要があります エッジ 多数のボディでマップ/ワールド/レベルを構築する代わりに、パフォーマンスの問題が発生する可能性があります。
マップを連続した頂点座標のリスト、おそらく壁をトレースしてリストを生成するアルゴリズムに変換する方法を見つけることができれば、これを行うことができます...
1つのボディを作成し、最初のエッジを追加します。
Body dungeon = BodyFactory.CreateEdge(world, start, end);
次に、他のすべての頂点座標を順番にループしてから、新しい各エッジを前のエッジ終了座標にアタッチします。 （完了するまでエッジを順番につなぎます）
FixtureFactory.AttachEdge(start, end, dungeon);
これにより、35以上ではなく1つのボディになります。