前提
二次元の迷路のような構造をランダムに生成しています。要約すると、グリッド内に多数の部屋をランダムに生成し、これらの部屋を A* を使用してランダムに廊下に接続します。部屋には、グリッド内の正方形全体を占める壁があります。私が抱えている問題は、これらの壁の作成にあります。
ランダムに生成された部屋をどこに配置するかを決めるために、グリッドをさまざまなサイズの長方形のセルに分割することから始めます。これらのセルは互いに隣接しており、サイズ 1 のセルを使用してそれらの間の残りのギャップを埋めます。その後、これらのセルのランダムな束を選択して、最終的に部屋にします。選択したセルのいずれかが互いに隣接している場合、それらは結合されて 1 つの部屋を形成します。この時点まで、アルゴリズムは完全に機能します。
例
問題
私が抱えている問題は、部屋の 1 つの壁を定義するすべての正方形を繰り返し処理したいときです。ここで、部屋ごとにエリアを作成し、その部屋のエリアに必要なすべてのセルを追加します。PathIteratorを使用して Area のアウトラインを反復処理することに成功しました。唯一の問題は、その反復子の結果が私が望む結果ではないことです。
たとえば、座標 (5, 5)、サイズ (4, 6) の長方形を想定します。私が反復したい結果のポイントは次のとおりです。
- 1行目 (5, 5) から (8, 5) まで
- 2 行目 (8, 5) から (8, 10) まで
- 3 行目 (8, 10) から (5, 10) まで
- 4 行目 (5, 10) から (5, 5) まで
代わりに、次のようになります。
- 1行目 (5, 5) から (9, 5) まで
- 2行目 (9, 5) から (9, 11) まで
- 3 行目 (9, 11) から (5, 11) まで
- 4 行目 (5, 11) から (5, 5) まで
言い換えれば、本地区の内側の上または左側にあると見なされるすべての線は本地区に含まれ、本地区の下または右側にあると見なされるすべての線は本地区に排他的である( Area.contains関数によって返されます)。
単純な正方形を扱う場合、これを修正するのは些細なことのように思えるかもしれませんが、一般的なエリアでこれを修正しようとすると、修正しようとしたあらゆる角度からあらゆる種類の迷惑な特殊なケースが現れ始めました.
私が試したり検討したりしたもの：
- グラハムのスキャン アルゴリズム。「凸包」が何を意味するのか、そして私の部屋がどのようにそうではないのかを理解したときに失敗しました
- パス内の連続する各行を検討し、その大部分がエリアの内側または外側にあるかどうかを確認し、外側にある場合は 1 単位移動します。可能な限り小さい行 (長さ 2 - 3) で実行しようとすると失敗しました
- パス内の連続する 3 点のセットをそれぞれ検討し、それらが作る角のタイプ (どの方向 + 凹角か凸角か) を確認し、角のタイプに応じてこれらの 3 点の中央を調整します。ポイントがどのコーナーであるかを確認する信頼できる方法が見つからないように見えるため、失敗しました
だから私は疑問に思っています、私がここで完全に欠けている明らかなものはありますか? これは単に PathIterator ではできないことであり、独自の「ポリゴン作成」アルゴリズムを実装する必要がありますか? もしそうなら、そのようなものはありますか？私は何日もこのことについて頭を悩ませてきました。インターネット上でもヘルプが見つからないようです。
わかりました、信じられないほど明白なことを思いついたので、これを作ろうとしていたことがどれほど複雑であるかを少し恥ずかしく思います。私はこの問題について盲目的に自分自身を見つめていたと思います。
- 外接する四角形のすべてのポイントを反復します
- 多角形にポイントが含まれている場合は、すべての方向にポイントの翻訳バージョンを作成します。
- ポリゴンに変換されたポイントが 1 つも含まれていない場合、そのポイントはポリゴンの壁の一部であることを意味します。
これは信じられないほど明白で単純なメカニズムです。つまり、少なくとも私は今のところ救われていますが、明らかに非常に非効率的です。そのため、誰かがより良いアルゴリズムを持っていれば、それは大歓迎です!