比中点圆算法更好的iso网格瓷砖地图笔刷算法

Question

我正在开发一个等轴测格子游戏（更准确地说是典型的菱形布局），希望实现圆形画笔来像使用任何图像编辑软件一样在我的地图上绘制瓷砖。我从Midpoint Circle Algorithm开始，但很快注意到，对于1到7之间的小画笔尺寸，结果看起来并不是我想要的。

我更喜欢像这样的东西：

忽略第一个圆没有填充的问题，这当然很容易。是否有适合在iso网格上生成形状的算法？我可能甚至不想要圆形，而是交替使用四边形和十字形/ X 形状。

以下是维基百科中第一个示例图像的代码：

static List<IntVector2> GetBrushCircleCoords(int x0, int y0, int radius)
{
    List<IntVector2> coords = new List<IntVector2>();
    int x = radius;
    int y = 0;
    int err = 0;

    while (x >= y)
    {
        coords.Add(new IntVector2(x0 + x, y0 + y));
        coords.Add(new IntVector2(x0 + y, y0 + x));
        coords.Add(new IntVector2(x0 - y, y0 + x));
        coords.Add(new IntVector2(x0 - x, y0 + y));
        coords.Add(new IntVector2(x0 - x, y0 - y));
        coords.Add(new IntVector2(x0 - y, y0 - x));
        coords.Add(new IntVector2(x0 + y, y0 - x));
        coords.Add(new IntVector2(x0 + x, y0 - y));

        y += 1;
        err += 1 + 2 * y;
        if (2 * (err - x) + 1 > 0)
        {
            x -= 1;
            err += 1 - 2 * x;
        }
    }
    return coords;
}

- Xarbrough

---

不确定如何改进小圆的代码。但是，正如您所提到的，您实际上可能并不想要（只有）圆形，我认为这篇关于“虚拟像素”的帖子可能会引起您的兴趣。它解释了如何使用普通绘图（GDI +或其他）创建模板，然后从中选择刷子像素。这样，您可以使用所有图形基元，甚至包括字体。 - TaW

Answer 1

您没有指定等距网格的布局。我假设使用菱形，因为它更容易实现。但是，在整数算术中，实现半个单元格分辨率的半径非常困难。对于完整单元格分辨率半径圆盘填充，请使用简单的2个嵌套for循环和内部圆测试。结果如下：

请忽略我的等角编辑器中的树和瓦片列表覆盖层。这里是此代码的C++源代码：

void isometric::brush_circle(int x0,int y0,int z0,int r)
    {
    r--; if (r<0) return;
    int tp=16;  // filling tile
    int x,y,rx,ry,rxx,ryy,rr=(r+1)*(r+1)-(r>>1);

    if ((z0>=0)&&(z0<gzs))
    for (rx=-r,x=x0+rx,rxx=rx*rx;rx<=r;rx++,x++,rxx=rx*rx)
     for (ry=-r,y=y0+ry,ryy=ry*ry;ry<=r;ry++,y++,ryy=ry*ry)
      if (rxx+ryy<rr)
       if ((x>=0)&&(x<gxs)&&(y>=0)&&(y<gys))
        map[z0][y][x]=tp;

    _redraw=true;
    }

它使用圆的方程：

(x-x0)^2+(y-y0)^2<=r^2

通过一些整数舍入调整可以得到更好的结果。代码基于我的等角引擎:

• 提高交错列等角网格上点击检测的性能

应用边缘平滑后的结果如下:

如果您想实现半单元半径分辨率，您有更多的选择，例如：

1. 使用浮点或固定点算术
2. 使用 diameter 作为调用操作数，而不是 radius，这样您只需相应地更新方程（避免舍入）

我选择#2，因此使用：

(x-x0)^2+(y-y0)^2<=(d^2)/4

我最接近的是这个（对于d=2有特殊情况）：

void isometric::brush_circle(int x0,int y0,int z0,int d)
    {
    if ((z0<0)||(z0>=gzs)) return;
    int tp=16;  // filling tile
    int x,y,rx,ry,rxx,ryy,r=(d>>1)+1,rr=((d*d)-(d>>1))>>2;
    if (d==2)
        {
        x=x0; y=y0; if ((x>=0)&&(x<gxs)&&(y>=0)&&(y<gys)) map[z0][y][x]=tp;
        x++;        if ((x>=0)&&(x<gxs)&&(y>=0)&&(y<gys)) map[z0][y][x]=tp;
        y++;        if ((x>=0)&&(x<gxs)&&(y>=0)&&(y<gys)) map[z0][y][x]=tp;
        x--;        if ((x>=0)&&(x<gxs)&&(y>=0)&&(y<gys)) map[z0][y][x]=tp;
        }
    else
     for (rx=-r,x=x0+rx,rxx=rx*rx;rx<=r;rx++,x++,rxx=rx*rx)
      for (ry=-r,y=y0+ry,ryy=ry*ry;ry<=r;ry++,y++,ryy=ry*ry)
       if (rxx+ryy<=rr)
        if ((x>=0)&&(x<gxs)&&(y>=0)&&(y<gys))
         map[z0][y][x]=tp;
    _redraw=true;
    }

看起来需要添加至少一个特殊情况或微调rr常数。

[编辑1] 午餐后和更多的思考之后...

从整数角度来看，更好的方程式是：

4*( (x-x0)^2 + (y-y0)^2 ) <= (d^2)

void isometric::brush_circle(int x0,int y0,int z0,int d)
    {
    if ((z0<0)||(z0>=gzs)) return;
    int tp=16;  // filling tile
    int x,y,rx,ry,rxx,ryy,r=(d>>1)+1,dd=(d*d)+d;
    if (d==2)
        {
        x=x0; y=y0; if ((x>=0)&&(x<gxs)&&(y>=0)&&(y<gys)) map[z0][y][x]=tp;
        x++;        if ((x>=0)&&(x<gxs)&&(y>=0)&&(y<gys)) map[z0][y][x]=tp;
        y++;        if ((x>=0)&&(x<gxs)&&(y>=0)&&(y<gys)) map[z0][y][x]=tp;
        x--;        if ((x>=0)&&(x<gxs)&&(y>=0)&&(y<gys)) map[z0][y][x]=tp;
        }
    else
     for (rx=-r,x=x0+rx,rxx=rx*rx;rx<=r;rx++,x++,rxx=rx*rx)
      for (ry=-r,y=y0+ry,ryy=ry*ry;ry<=r;ry++,y++,ryy=ry*ry)
       if ((rxx+ryy)<<2<dd)
        if ((x>=0)&&(x<gxs)&&(y>=0)&&(y<gys))
         map[z0][y][x]=tp;
    _redraw=true;
    }

- Spektre