5

壁を定義する大きな長方形で構成される大きなダンジョンで行われるスペースシューターを作成しています。ゲーム内のすべては、FarseerPhysicsを使用して物理的にシミュレートされます。ただし、問題が1つあります。ダンジョンを十分に大きく見せたいのですが、グリッドに少なくとも80x80の長方形が必要です。つまり、最悪のシナリオでは、6400の物理的にシミュレートされたボディがありますが、これは正確ではありません。ご想像のとおり、パフォーマンスに適しています。

私の一時的な解決策は、グリッドを垂直スライスに分割することでした。これにより、すべての列について、ブール値の追加操作を使用してすべての長方形が追加され、結果の凹多角形を使用してボディが作成されます。パフォーマンスは少し向上しますが、ポリゴンは混乱したり、存在しなくなったり、通常は通過可能であるはずのウェイをブロックしたり、無効になってFarseerをクラッシュさせたりする傾向があります。

どういうわけか壁の最大の領域を見つけてそれらを1つの大きな長方形にマージし、すべての穴が埋められるまで小さな長方形に対してこれを続けていくようなアルゴリズムを作成することを考えていましたが、これを実装する方法がわかりません。パフォーマンスの問題と、現在私が抱えている凹多角形の混乱を解決できるので、完璧な解決策のようです。誰かがこのようなものを実装する方法についての手がかりを持っていますか？

私のゲームの多くのものが物理エンジンに依存しているため、物理エンジンの使用を完全に停止することは解決策ではありません。

編集：これが今の体の様子の小さな例です:(すべての数字は体です） http://i.imgur.com/6x06o.png

そして、これが私が彼らになりたい方法です：

ここに画像の説明を入力してください

4

3 に答える 3

1

質問が正しく理解できないかもしれませんが、問題を解決するためのヒントになると思うアルゴリズムを提案させてください。

あなたの問題は、正方形が自由で非自由である長方形の貪欲から始まります。最初から、自由な正方形は壁を構築するためのものであり、自由でない正方形は中空のスペースです。

  1. Foreachの空き正方形は、その正方形の周りを拡張し、その正方形が属することができる最大の領域を確認します。拡張とは、その正方形からすべての方向に進むことを意味しますが、自由な正方形から領域を構築することは可能です。この最大の領域を指定されたフリースクエアに関連付けます。
  2. 関連する面積が最大の正方形を選択し、その正方形の周りを拡大して、結合された壁を作成します。このマージに属する正方形は、非フリーとしてマークされます。完了した空き正方形がなくなった場合は、手順1に進みます。

完了したら、壁の可能な限り最大のブロックをグループ化する必要があります。

明確にするために、自由な正方形の周りの拡張とは、与えられた正方形からすべての利用可能な方向に構築できる仮想の最大の長方形を取ることを意味します。

n*m長方形行列に対するこのアルゴリズムの複雑さは、直感的にはO(n*n*m*m)です。実際には、データが非常に速くなると思います。このアルゴリズムは、オブジェクトの数を最小限に抑えるのではなく、すべての領域の合計を最大化することに注意してください（質問に従って）。体の総数を最小化するという問題は、複雑さの点ではるかに難しいと私は思います。

于 2011-07-17T01:42:14.413 に答える
1
于 2011-07-17T02:13:35.430 に答える
0

Using Farseer one should use EDGES instead of constructing your map/world/level with so many bodies, which could result in performance issues.

If you can find a way to convert your map into a list of sequential vertex coords, maybe an algorithm that traces the walls and generates the list, you could then do this...

Create 1 body and add FIRST edge:

Body dungeon = BodyFactory.CreateEdge(world, start, end);

Then loop through all other vertex coords in sequence and then attach each new edge to the previous edge end coordinate. (chaining edges together in sequence until done)

FixtureFactory.AttachEdge(start, end, dungeon);

This results in 1 body instead of having 35+.

于 2013-02-10T05:17:11.827 に答える