算法来访问以矩阵（游戏地图），它是一个光盘的瓦片 [英] Algorithm to access the tiles in a matrix (game map) that are in a disc

问题描述

我的深化发展瓷砖映射游戏。
我需要访问是在一个盘上的砖，具有给定半径和中心的一个给定的点。

I am developping a tile mapped game.
I need to access the tiles that are in a disc, with a given radius and centered on a given point.

访问是在一个正方形瓷砖被容易的，我们只需要使用两个环：

Accessing the tiles that are in a square is easy, we only need to use two loops :

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

但你如何访问是在给定盘（大圈）瓷砖？

But how do you access the tiles that are in a given disc (full circle) ?

编辑：
我的意思是，我可以处理的边框每瓦（边界光盘），并确定该矩形瓷砖是否在磁盘上，通过使用（X-X0）2 +（Y -y0）²＆LT; R ，但与算法，我们将探索无用的瓷砖
。 当使用半径大，有很多瓷砖的过程，这将是缓慢的，因为计算（X-X0）2 +（Y-Yo）²＆LT; R 多次重
我要的是一个算法比这更有效。

I mean, I could process each tile in a bounding rectangle (bounding the disc), and determine whether or not a tile in that rectangle is in the disk, by using (x-x0)²+(y-y0)²<R², but with that algorithm, we would explore useless tiles.
When using a large radius, there are many tiles to process, and it will be slow because calculating (x-x0)²+(y-y0)²<R² many times is heavy
What I want is an algorithm more efficient than this one.

EDIT2：
我并不需要一个完美的磁盘

I don't need a perfect disk

推荐答案

您可以使用<一个href="http://books.google.co.ve/books?id=-4ngT05gmAQC&printsec=frontcover#v=onepage&q&f=false"相对=nofollow>布氏圈算法（3.3节，扫描转换圈）（它仅使用整数运算，是非常准确和流程整圆生产全周的第四部分）在你的瓦片矩阵检测那些瓦片，其形成的圆周，然后从跟踪它们之间排队到向下（或左到右）：

You can use the Bresenham's circle Algorithm (section 3.3, Scan Converting Circles) (it uses integer arithmetic only, is very accurate and process fourth part of the whole circle to produce the entire circumference) in your tile matrix to detect those tiles that forms the circumference, then trace lines between them from up-to-down (or left-to-right):

下面是一个伪实现循环算法：

The following is a pseudo implementation of the circle algorithm:

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);
}

通过这种方法，你应该只处理所需要的瓷砖（加工只有四分之一圈后），没有不必要的瓷砖将被检查。旁边的是，它采用整数运算而已，至极使得它非常快（扣除和解释可以在本书提供的链接找到），生成的圆周被证明是真实的一个最佳逼近。

With this technique you should process only the required tiles (and after processing only a quarter of the circle), none unnecessary tiles would be checked. Beside that, it uses integer arithmetic only, wich makes it really fast (the deduction and explanation can be found in the provided book link) and the generated circumference is proven to be the best approximation for the real one.

这篇关于算法来访问以矩阵（游戏地图），它是一个光盘的瓦片的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！