3

タイルマップゲームを開発しています。
特定の半径を持ち、特定のポイントを中心とする、ディスク内のタイルにアクセスする必要があります。

正方形のタイルにアクセスするのは簡単です。2つのループを使用するだけで済みます。

for(int i=xmin; i<xmax; ++i)
   for(int j=ymin; j<ymax; ++j)     
       // the tile map[i][j] is in the square

しかし、特定のディスク（完全な円）にあるタイルにどのようにアクセスしますか？

編集：
つまり、境界長方形（ディスクの境界）内の各タイルを処理し、を使用してその長方形内のタイルがディスク内にあるかどうかを判断できます(x-x0)²+(y-y0)²<R²が、そのアルゴリズムを使用すると、役に立たないタイルを探索します。大きな半径を使用する場合、処理するタイルが多く、何度も計算するのが重い
ため、処理が遅くなります 。私が欲しいのは、これよりも効率的なアルゴリズムです。(x-x0)²+(y-y0)²<R²

EDIT2：
完璧なディスクは必要ありません

4

4 に答える 4

6

xの範囲を計算して、 を線形スキャンできますy。次に、この下手に描かれた絵のように、円の中にあるタイルをスキャンするだけです。（クリスマスカラー？）

ここに画像の説明を入力

r半径と x 位置を持つ円がある場合x、最大長 を計算できますy。

ここに画像の説明を入力

y = sqrt(r * r - x * x);

したがって、タイルを反復するためのコードは次のようになります。

int center_x = (xmin + xmax) / 2;
int center_y = (ymin + ymax) / 2;

for(int x = xmin; x <= xmax; x++) {
    int ydist = sqrt(r * r - (center_x - x) * (center_x - x));
    for(int y = center_y - ydist; y <= center_y + ydist; y++) {
        // these are the tiles in the disc
    }
}

ここにいくつかのPythonコードがあります:

from Tkinter import *
from math import *

tk = Tk()
g = Canvas(tk, width=500, height=500)
g.pack()

x0 = 25 # x center
y0 = 25 # y center
r = 17  # radius
t = 10  # tile side length

for x in range(x0 - r, x0 + r + 1):
    ydist = int(round(sqrt(r**2 - (x0 - x)**2), 1))
    for y in range(y0 - ydist, y0 + ydist + 1):
        g.create_rectangle(x * t, y * t, x * t + t, y * t + t
                , fill='#'
                + '0123456789ABCDEF'[15 - int(15 * sqrt((x0 - x)**2 + (y0 - y)**2) / r)]
                + '0123456789ABCDEF'[int(15 * sqrt((x0 - x)**2 + (y0 - y)**2) / r)]
                + '0')

g.create_oval((x0 - r) * t, (y0 - r) * t, (x0 + r) * t + t, (y0 + r) * t + t, outline="red", width=2)

mainloop()

結果のディスクは次のとおりです。

ここに画像の説明を入力

最後は完璧ではありませんが、十分に機能することを願っています（または変更できることを願っています）。

于 2012-12-26T06:10:21.330 に答える
1

正方形の外側のタイルを除外しても、それほど速くはありません。正方形を使用するだけで、円の外側のタイルは無視します。(例: タイルが円の中心からどれだけ離れているかを確認することによって)

for(int i=xmin; i<xmax; ++i):
   for(int j=ymin; j<ymax; ++j):
       if map[i][j] not in the circle:
           break
       // the tile map[i][j] is in the square

パフォーマンスのオーバーヘッドの概算:

Area Square = 2*r*2*r
Area Circle = pi*r*r

Area Square / Area Circle = 4/pi = 1.27

これは、円の代わりに正方形を使用することが唯一であることを意味します1.27 times slower(円の使用に非効率性がないことを前提としています)。

また、タイルに対して何らかの操作を実行する可能性が高いため (円内のタイルを含む反復が大幅に遅くなります)、正方形のレイアウトではなく円のレイアウトを使用すると、パフォーマンスの向上がほぼ 0 になります。

于 2012-12-26T09:19:28.783 に答える
0

境界八角形を使用します。角が切り取られた境界正方形です。ポイント (タイルの任意の角) がその形状であるかどうかを調べるには、これらのテストが必要です。これを 2D ループの中に入れます。 

abs(x) < R
abs(y) < R
abs(x)+abs(y) < sqrt(2)*R

もちろん、sqrt(2)*R を事前に計算します。

これは明らかに円と同じではありませんが、正方形に比べて無駄なスペースをうまく削減できます。

ループ内でなんらかのテストを行わなくても、タイルの中心またはタイルのコーナーのみを完全に通過するループを生成するのは困難です。このようなループを作成するための希望は、ブレゼンハムのアルゴリズムを使用することです。

于 2012-12-25T23:34:50.647 に答える