用于访问光盘中矩阵(游戏地图)中的图块的算法

Question

我正在开发一个瓷砖映射游戏.
我需要访问光盘中具有给定半径并以给定点为中心的图块.

访问正方形的瓷砖很容易,我们只需要使用两个循环:

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²很多次很重
我想要的算法比这个更有效.

编辑2:
我不需要一个完美的磁盘

Answer 1

我们可以做一个线性扫描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()

结果磁盘:

最终并不完美,但我希望它对您有效(或者您可以修改它).

Answer 2

您可以使用布氏圈算法(3.3节,扫描转换圆)(它仅使用整数运算,是非常准确和处理整个圈子产生全周的第四部分)在你的瓦片矩阵来检测形成的那些瓷砖圆周,然后从上到下(或从左到右)跟踪它们之间的线:

以下是circle算法的伪实现:

static void circle(int x0, int y0, int x1, int y1) {
    // Bresenham's Circle Algorithm
    int x, y, d, deltaE, deltaSE;
    int radius, center_x, center_y;
    bool change_x = false;
    bool change_y = false;

    if( x0 > x1 ) {
        // swap x values
        x = x0;
        x0 = x1;
        x1 = x;
        change_x = true;
    }
    if( y0 > y1 ) {
        // swap y values
        y = y0;
        y0 = y1;
        y1 = y;
        change_y = true;
    }

    int dx = x1 - x0;
    int dy = y1 - y0;

    radius = dx > dy ? (dy >> 1) : (dx >> 1);
    center_x = change_x ? x0 - radius : x0 + radius;
    center_y = change_y ? y0 - radius : y0 + radius;

    x = 0;
    y = radius;
    d = 1 - radius;
    deltaE = 3;
    // -2 * radius + 5
    deltaSE = -(radius << 1) + 5;

    while(y > x) {
        if(d < 0) {
            d += deltaE;
            deltaE  += 2;
            deltaSE += 2;
            x++;
        } else {
            d += deltaSE;
            deltaE  += 2;
            deltaSE += 4;
            x++;
            y--;
        }
        checkTiles(x, y, center_x, center_y);
    }
}

void checkTiles(int x, int y, int center_x, int center_y) {
    // here, you iterate tiles up-to-down from ( x + center_x, -y + center_y) to (x + center_x, y + center_y) 
    // in one straigh line using a for loop
    for (int j = -y + center_y; j < y + center_y; ++j) 
       checkTileAt(x + center_x, j);

    // Iterate tiles up-to-down from ( y + center_x, -x + center_y) to ( y + center_x,  x + center_y)
    for (int j = -x + center_y; j < x + center_y; ++j) 
       checkTileAt(y + center_x, j);

    // Iterate tiles up-to-down from (-x + center_x, -y + center_y) to (-x + center_x,  y + center_y)
    for (int j = -y + center_y; j < y + center_y; ++j) 
       checkTileAt(-x + center_x, j);

    // here, you iterate tiles up-to-down from (-y + center_x, -x + center_y) to (-y + center_x, x + center_y)
    for (int j = -x + center_y; j < x + center_y; ++j) 
       checkTileAt(-y + center_x, j);
}

使用这种技术,您应该只处理所需的图块(并且仅处理圆的四分之一后),不会检查任何不必要的图块.除此之外,它仅使用整数运算,这使得它非常快(推导和解释可以在提供的书籍链接中找到),并且生成的周长被证明是真实的近似.