7

問題があります。タイル エンジンのアルゴリズムが必要です。

歩行不可能なタイルを格納する 2 次元配列があります。

ライト エンジンを実装したいのですが、このエンジンにはシャドウ ハルが必要です。

したがって、これらのシャドウ ハルを作成するアルゴリズムが必要です。

1配列の歩行不可能な部分 ( sを持つセル) を囲む四角形のセットが必要です
。次に例を示します。

http://makerland.de/Zerlegt.png

黒いタイルは1s です。それらを完全に囲む赤い長方形のセットを見つける必要があります。

4

2 に答える 2

2

次のようなものを試してください。

  1. 必要なすべてのポイントを含むリストを作成します。（あなたの場合、すべての座標1）

  2. このリストの各ポイントについて：

    1. 不要なポイント（a 0）に到達するまで、このポイントからY軸をループダウンします。
    2. 0ステップ1で取得したポイントと終了Y座標の間に任意のY値を持つX座標に到達するまで、X軸に沿って右にループします。
    3. 見つけた長方形を長方形のリストに追加します
    4. 元のリストから長方形内のすべてのポイントを削除します。

これはおそらくこれを行うための最速の方法ではありませんが、機能するはずです。

于 2011-07-22T00:52:12.063 に答える
2

さらに考えた後、私はより速い解決策を思いつきました：

  1. 、、、およびプロパティを使用して不変のRange構造体を作成します。StartXStartYEndY

  2. Range画像の高さに等しい長さの現在のsのスパース配列と、単一のnull許容のcurrentRange変数を維持します。この配列には、各Y座標で始まる範囲が含まれます（存在する場合）

  3. 各列について、

    1. クリアcurrentRange

    2. 列の各セルについて：

      1. currentRangeがない場合、または存在するがこのセルの前で終了している場合（if currentRange.EndY <= y）、currentRangeをyranges配列の'番目の要素に設定します。
        したがって、currentRangeは常に現在のセルを含む範囲を参照するnullか、現在のセルが範囲内にない場合を参照します。

      2. 現在のセルが次の場合1：

        1. 範囲内にいる場合は、何もしません。範囲は次の列に続きます。

        2. 範囲内にいない場合は、または列の終わりに到達するまで列をループダウンしてから、見つけたばかり0の範囲からループの終わりまで伸びる新しい範囲を作成します。 次に、次の場合に進みます（現在のセルが現在または列の終わりにあり、範囲内にないため） 新しい範囲を作成するためにループするときに既存の範囲にヒットした場合は、停止することができます新しい範囲をその下に継続させるか（ファジーエッジに最適）、または既存の範囲を閉じて（以下を参照）、新しい範囲を下に伸ばして既存の範囲を引き継ぎます。1
          0

      3. 現在のセルが次の場合0：
        1. 範囲内にいる場合は、範囲を閉じます。
          1. 範囲の開始XとYから現在のYと範囲の終了Xまで伸びる新しい長方形を返します。
          2. アクティブな範囲の配列から範囲をクリアします。

このアルゴリズムはO(x * y)、計算とO(y)空間にあります。これが問題の最速の解決策だと思います。

このアルゴリズムをローテーションして、列ではなく行をスキャンすることもできます（範囲が右方向ではなく下方向に引き伸ばされるように）。これはO(x)ストレージに保存されます。

C＃の実装は次のとおりです。

class BoxFinder {
    class Range {
        public Range(int startX, int startY, int endY) {
            StartX = startX;
            StartY = startY;
            EndY = endY;
        }

        public int StartX { get; private set; }
        public int StartY { get; private set; }
        public int EndY { get; private set; }
    }
    public BoxFinder(int[,] data) {
        Data = data;
        Width = data.GetLength(0);
        Height = data.GetLength(1);
        ranges = new Range[Height];
    }

    public int[,] Data { get; private set; }
    public int Width { get; private set; }
    public int Height { get; private set; }

    private Range[] ranges;
    public IEnumerable<Rectangle> GetBoxes() {
        for (int x = 0; x < Width; x++) {
            Range currentRange = null;
            for (int y = 0; y < Height; y++) {
                Func<Range, Rectangle> CloseRange = r => {
                    currentRange = null;
                    ranges[r.StartY] = null;
                    return new Rectangle(
                        r.StartY,
                        r.StartX,
                        x - r.StartX,
                        r.EndY - r.StartY
                    );
                };

                if (currentRange == null || currentRange.EndY <= y)
                    currentRange = ranges[y];

                if (Data[x, y] == 1) {
                    if (currentRange == null) {
                        int startY = y;
                        for (; y < Height && Data[x, y] == 1; y++) {
                            if (ranges[y] != null)
                                yield return CloseRange(ranges[y]);
                            //If there are fuzzy edges, break; instead
                        }
                        ranges[startY] = new Range(x, startY, y);
                        if (y == Height)
                            continue;
                        //Otherwise, continue to the next if in case a previous range just ended
                    }
                }
                //No else; we can get here after creating a range
                if(Data[x, y] == 0) {
                    if (currentRange != null)
                        yield return CloseRange(currentRange);
                }
            }
        }
    }
}
于 2011-07-24T18:56:13.673 に答える