3

外壁 (W としてマーク)、環境ブロック (E)、オープン スペース (o)、アクティブ ポイント (A) を含むグリッド (下の例) があります。現在、このグリッドは [,] に格納され、すべてのデータが特定のポイントに関連付けられています。アクティブなポイントが囲まれているかどうかを判断しようとしています (環境ブロックによってブロックされているため、グリッドの上部に到達できないと定義されています) が、この問題を解決する簡単な方法を見つけるのに苦労しています. 私は A* を実装することができ、そこにあるすべてのサンプル コードで多かれ少なかれ簡単であることを知っていますが、パフォーマンスへの影響が実際には必要ではなく、一見些細な操作に値するとは思いません。

W--Top Of Grid--W
W---------------W
W-EEAEE-----EEE-W
WEEEEEEE-EEEEAEEW
WEEEEEEE--EEEEEEW
WEEEEEEEE-AEEEEEW
WWWWWWWWWWWWWWWWW

下の 3 行目の A は、最後の行の A と同様に、グリッドの上部へのパスを描画できますが、4 行目の A はできません。実際のパスは気にしません。オブジェクトがトラップされているかどうかを判断する必要があるだけです。このプロジェクトの最適なソリューションは何ですか?

価値があるのは、ターンベースのグリッド ゲームの C# プロジェクトであるということです。

あなたが提供できる助けを前もってありがとう、それは大歓迎です。

4

1 に答える 1

2

トップグリッドからの塗りつぶしですべての問題が解決すると思います。上から氾濫し、次にどの「A」が氾濫しているかを確認します:)

アルゴリズムは、プロセス全体で1回だけ各ノードにアクセスすることを保証しますが、最悪の場合、これを高速化することはできません。そして、どの言語でも簡単に実装できます。

ウィキペディアのアルゴリズムは次のとおりです。

 Flood-fill (node, target-color, replacement-color):
 1. If the color of node is not equal to target-color, return.
 2. Set the color of node to replacement-color.
 3. Perform Flood-fill (one step to the west of node, target-color, replacement-color).
    Perform Flood-fill (one step to the east of node, target-color, replacement-color).
    Perform Flood-fill (one step to the north of node, target-color, replacement-color).
    Perform Flood-fill (one step to the south of node, target-color, replacement-color).
 4. Return.

...そしてそれは次のように見えます:(ウィキから）

フラッドフィル

要するに：

  1. 上のグリッドからの洪水。「W」と「E」が洪水をブロックします（写真の黒いセルのように）
  2. 浸水後、「A」を含む場所がいくつ浸水しているかを確認します。
于 2012-08-02T08:48:29.233 に答える