Meilleur algorithme que Midpoint Circle pour les mappes de tuiles sur la grille iso

Question

Je travaille sur ce jeu de grille iso (plus précis: projection dimétrique, indexé en losange typique) et je voulais mettre en place des pinceaux circulaires pour peindre des carreaux sur ma carte juste comme vous le feriez dans n'importe quel logiciel d'édition d'image. J'ai commencé avec le Midpoint Circle Algorithm, mais remarqué tout de suite, que le résultat ne ressemble pas à ce que je veux pour les petites tailles de pinceau entre 1 et 7.

j'aurais bien plutôt quelque chose comme ceci:

Ignore, que les premiers cercles ne sont pas remplis, que bien sûr est facile. Existe-t-il des algorithmes adaptés pour la génération de formes sur les grilles iso? Je ne veux probablement même pas de formes en cercle, mais en alternant des formes en quad et en croix/x.

Voici le code pour le premier échantillon d'image tirée de 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; 
} 

Answer 1

Vous n'avez pas spécifié la présentation de votre grille isométrique. Je suppose que le diamant est plus facile à implanter. Cependant en arithmétique entière est vraiment difficile à mettre en œuvre la résolution de demi-cellule du rayon. Pour le remplissage du disque avec un rayon de résolution de cellules complet, utiliser 2 for emboîtés simples avec test de cercle intérieur. Le résultat ressemble à ceci:

simplement ignorer l'arbre et la liste des tuiles superposition de mon éditeur isométriques. Ici, le code source C++ pour cela:

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

Il utilise l'équation disque/cercle:

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

Avec un entier pour arrondir peaufinage mieux à la recherche des résultats.Le code est basé sur ce moteur isométrique de la mine:

• Improving performance of click detection on a staggered column isometric grid

Après avoir appliqué le lissage des bords du résultat est comme ceci:

Si vous souhaitez implémenter la la résolution de rayon de demi-cellule vous avez plus d'options par exemple:

1. utilisation flottante ou Arithmétique virgule fixe
2. d'utilisation diameter comme appelant opérandes au lieu de radius si vous mettez à jour simplement l'équation en conséquence (avec évitement d'arrondi)

Je vais pour # 2 donc utiliser:

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

Le plus proche que j'ai eu est celui-ci (avec un cas spécial pour 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; 
    } 

On dirait qu'il faut ajouter au moins un cas particulier et ou tordre le un peu plus constante rr.

[Edit1] Après le déjeuner et un peu plus enseigné ...

Du point entier de bien meilleure équation est la suivante:

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