Better algorithm than Midpoint Circle for tile map brushes on iso grid

Question

I'm working on this iso grid game (more precise: dimetric projection, indexed in typical diamond layout) and wanted to implement circular brushes to paint tiles on my map just like you would in any image editing software. I started with the Midpoint Circle Algorithm, but noticed right away, that the result doesn't look like what I want for small brush sizes between 1 and 7.

I would much rather have something like this:

Ignore, that the first circles are not filled, that of course is easy. Are there any suited algorithms for shape generation on iso grids? I probably don't even want circle shapes, but alternating quad and cross-like/x-shapes.

Here is the code for first image sample taken from Wikipedia:

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

Not sure how to improve the code for small circles. But as you mentionen you may actually not want (just) circles anyway, I though this [post about 'virtual pixels'](http://stackoverflow.com/questions/22881312/c-sharp-drawing-text-using-custom-pixels/22881391#22881391) may be of interest. It explains how you can use normal drawing (GDI+ or whatever) to create a template from which you then pick the brush pixels. This way you can use all the graphics primitives, including even fonts.. — TaW, Jul 14 '16 at 07:18

score 5 · Accepted Answer · edited May 23 '17 at 11:51

You did not specify layout of your isometric grid. I am assuming diamond as it is more easy to implement there. However in integer arithmetics is really hard to implement the half cell resolution of the radius. For full cell resolution radius disc filling use simple 2 nested fors with inside circle test. The result looks like this:

Just ignore the tree and tile list overlay of my Isometric editor. Here the C++ source code for this:

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

It uses disc/circle equation:

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

With some integer round off tweaking for better looking results. The code is based on this isometric engine of mine:

Improving performance of click detection on a staggered column isometric grid

After applying smoothing of edges the result is like this:

If you want to implement the half cell radius resolution you got more options for example:

use floating or fixed point arithmetics
use diameter as calling operand instead of radius so you just update the equation accordingly (with rounding avoidance)

I go for #2 so use:

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

The closest I got is this (with special case for 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;
    }

It looks like it need adding of at least one special case and or tweak the rr constant a bit more.

[Edit1] After lunch and some more taught...

From integer point of view much better equation is:

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

Better algorithm than Midpoint Circle for tile map brushes on iso grid

1 Answers1