1

タイルベースのゲームをやっています。x、y座標と移動制限に基づいてキャラクターが移動できる配列を返すメソッドを作成しようとしました。

たとえば、 currentPosition:(3,3) moveLimit:1 を入力した場合

その後、返されるはずです ((3,2),(3,2),(3,4),(4,3))

currentPosition:(3,3) moveLimit:2 を入力した場合

次に、 ((3,1),(2,2),(3,2),(4,2),(1,3),(2,3),(4,3),(5, 3),(2,4),(3,4),(4,4),(3,5))

xとyの両方で-1と+1をすべて可能にすることで、再帰的な方法を使用する予定です。しかし、-1 の次に +1 と比較して +1 の次に -1 というように、多くの繰り返しのケースが発生する可能性があるため、非常に非効率的です。

これに適したパターンがあるかどうか知っている人はいますか？

本当にありがとうございました。

4

2 に答える 2

1

最初に、質問と探しているものを正式に定義しましょう。

距離kおよび(x,y)原点 (ソース) として示します。

f((x,y),k) = { (a,b) | abs(x-a) + abs(y-b) <= k }

これは、次のようなすべての点 (a,b) を持つセットを意味します: abs(x-a) + abs(y-b) <= k(距離制限)

次に、関連するすべての要素を取得するには、次のようにします。

moves((x,y),k):
  for i=0 to k+1: //number of steps in the x axis, some number between 0 to k inclusive
     //number of steps in the y axis, some number between 0 to k-i inclusive:
     for j=0 to k-i+1: 
        if (x-i,y-j) is in range: output (x-i,y-j)
        if (x+i,y-j) is in range: output (x+i,y-j)
        if (x-i,y+j) is in range: output (x-i,y+j)
        if (x+i,y+j) is in range: output (x+i,y+j)

ノート：

  1. 両方の軸で可能なすべてのステップを次の制限でチェックするため、これにより条件が保証されます。abs(a-x) + abs(b-x) <= k
  2. ここで「範囲内」は健全性チェックです。範囲外にならないようにしてください (たとえば、正の値のみを取得する必要があると仮定して、-1 の x 値を取得します。
于 2012-11-08T13:51:29.357 に答える
0

要素 (UP、LEFT、DOWN、RIGHT) から長さ「moveLimit」のすべての組み合わせを計算してみてください。

例えば

UUU
UUL
UUD
UUR

ULL
ULD
ULR

UDD
UDR

URR

LLL
...

これにより、すでに計算の数が大幅に削減されているはずです。それでも、同じ位置になるさまざまな組み合わせの動きになる可能性があります。

于 2012-11-08T13:34:35.400 に答える