那些遇到过的问题

如何编写算法以使用中心线正确填充圆？

6 algorithm math processing geometry fill

目前，我尝试编写代码来计算您可以看到的屏幕部分以及由于物体在 2d 中阻挡光线而无法看到的部分，例如在我们中间： 在我们中间和你可以看到的屏幕部分

代码应该在规格非常低的处理器上运行（至少在 2020 年），即 C64。在如此简单的 CPU 上，不可能以足够快的速度为游戏进行如此复杂的数学运算，所以我想出了一个想法：首先，我让所有东西都基于平铺，这使得处理更容易，也意味着我可以改变整个字符或其颜色单元格。然后我只在 Processing 中为 PC 编写代码（这是一种类似于 Java 但更易于使用的编码语言）来计算光线将如何移动（下图应该更容易理解），首先只使用一个矩形（和一个单象限）：

由光线填充的矩形

然后我写了一些完全凌乱的汇编代码，用于使用记录的坐标，根据当前在射线上绘制的射线数量，继续用倒置字符填充瓷砖，直到它们碰到一个对象（/它想要填充的瓷砖是不倒置，也不是空格），然后转到下一条射线。我将半径减小到 7，因此它只占用 256 个字节，这对 ASM 很有用。这完全奏效了，我能够修复每一个错误，结果令人印象深刻，因为我需要添加暂停语句，否则一切都运行得太快以至于你什么都看不到。

灯光演示 1灯光演示 2

工作后，我用圆圈试了一下，使用以下代码设置点：

int pointNum = ceil(radius * PI * 2); // calculates the circumference
for(int i = 0;i < pointNum;i++){
  float angle = map(i, 0, pointNum, 0, PI*2);
  setPixel(sin(angle) * radius, cos(angle) * radius);
}
Run Code Online (Sandbox Code Playgroud)

我以前使用过 Bresenham 圆算法，但效果不佳，所以我尝试了一种更简单的方法。所以 ...

圆圈

所有标记的黑色瓷砖永远不会被任何光线击中，这是一个非常大的问题，因为在游戏中你看不到这些瓷砖没有多大意义。我使用的代码是用Processing编写的：

float[] xPoints = new float[0];
float[] yPoints = new float[0];
float[] xPointsT;
float[] yPointsT;
float[] xPointsHad = new float[0];
float[] yPointsHad = new float[0];
int pos = 0;
float interpolPos = 0;

int radius = 12;
float tileSize = 800.0 / (2*radius+1);

String output = "  !byte ";
int pointNum = ceil(radius * PI * 2);
void setup() {
  size(800, 800);
  frameRate(60);
  xPointsT = new float[0];
  yPointsT = new float[0];
  /*for(int i = 0;i <= radius;i++){
    setPixel(radius, i);
    setPixel(i, radius);
  }*/ //Uncomment this and comment the next 4 lines to get the rectangle version
  for(int i = 0;i < pointNum;i++){
    float angle = map(i, 0, pointNum, 0, PI*2);
    setPixel(sin(angle) * radius, cos(angle) * radius);
  }
  xPoints = concat(xPoints, xPointsT);
  yPoints = concat(yPoints, yPointsT);
}
void draw(){
  if(interpolPos > radius){
    pos++;
    interpolPos = 0;
    println(output);
    output = "  !byte ";
  }
  float x=0, y=0;
  float interpolMul = interpolPos / radius;
  x = xPoints[pos] * interpolMul;
  y = yPoints[pos] * interpolMul;
  interpolPos+=1;//sorta the resolution
  background(0);
  
  stroke(255);
  for(int i = 0;i < 2*radius+1;i++){
    for(int j = 0;j < 2*radius+1;j++){
      if((round(x) + radius) == i && (round(y) + radius) == j){
        fill(0, 255, 0);
        if(output != "  !byte ")
          output += ", ";
        output += i-radius;
        output += ", ";
        output += j-radius;
        xPointsHad = append(xPointsHad, i);
        yPointsHad = append(yPointsHad, j);
      }
      else{
        int fillVal = 0;
        for(int k = 0; k < xPoints.length;k++){
          if(round(xPoints[k])+radius == i && round(yPoints[k])+radius == j){
            fillVal += 64;
          }
        }
        fill(0, 0, fillVal);
        if(fillVal == 0){
          for(int k = 0; k < xPointsHad.length;k++){
            if(round(xPointsHad[k]) == i && round(yPointsHad[k]) == j){
              fill(128, 0, 0);
            }
          }
        }
      }
      rect(i * tileSize, j * tileSize, tileSize, tileSize);
    }
  }
  
  strokeWeight(3);
  stroke(0, 255, 255, 64);
  for(int i = 0;i < xPoints.length;i++){
    line((float(radius)+0.5) * tileSize, (float(radius)+0.5) * tileSize, (float(radius)+0.5+xPoints[i]) * tileSize, (float(radius)+0.5+yPoints[i]) * tileSize);
  }
  strokeWeight(1);
  
  fill(255, 255, 0);
  ellipse((x + radius + 0.5) * tileSize, (y + radius + 0.5) * tileSize, 10, 10);
}

void setPixel(float _x, float _y){
  for(int i = 0; i < xPoints.length;i++){
    if(_x == xPoints[i] && _y == yPoints[i]){
      return;
    }
  }
  for(int i = 0; i < xPointsT.length;i++){
    if(_x == xPointsT[i] && _y == yPointsT[i]){
      return;
    }
  }
  
  xPointsT = append(xPointsT, _x);
  yPointsT = append(yPointsT, _y);
}
Run Code Online (Sandbox Code Playgroud)

（获取矩形的说明在代码中）那些提到的瓷砖似乎永远不会被击中，因为它们上的光线只是跳过它们，但是我能做些什么来防止这种情况发生？您可以减少 interpolPos+=x; 击中更多的瓷砖，因为这样你的步骤更小，但这会浪费相当多的空间，所以我认为这不是一个好的解决方案。理想情况下，您也可以减少绘制的坐标数量以获得更小的视野。有没有人知道如何做到这一点？

小智 1

好吧，我发现了一些在我的情况下对我有用的东西：我只是使用了完全有效的部分（矩形），然后通过忽略距光源较远的每个瓷砖击中（然后半径+ 0.5）将其变成一个圆圈，因为如果没有 + .5，圆看起来很奇怪。你可以自己尝试一下，代码如下：

float[] xPoints = new float[0];
float[] yPoints = new float[0];
float[] xPointsT;
float[] yPointsT;
float[] xPointsHad = new float[0];
float[] yPointsHad = new float[0];
int pos = 0;
float interpolPos = 0;

int radius = 7;
float tileSize = 800.0 / (2*radius+1);

int pointNum = ceil(radius * PI * 2);

String standardOutput = "  !align 15,0\n  !byte ";
void setup() {
  size(800, 800);
  frameRate(60);
  xPointsT = new float[0];
  yPointsT = new float[0];
  for(int i = 0;i <= radius;i++){
    setPixel(radius, i);
    setPixel(i, radius);
  } //Uncomment this and comment the next 4 lines to get the rectangle version
  /*for(int i = 0;i < pointNum;i++){
    float angle = map(i, 0, pointNum, 0, PI*2);
    setPixel(sin(angle) * radius, cos(angle) * radius);
  }*/
  xPoints = concat(xPoints, xPointsT);
  yPoints = concat(yPoints, yPointsT);
  
  xPointsT = new float[0];
  yPointsT = new float[0];
}
void draw(){
  if(interpolPos > radius){
    pos++;
    interpolPos = 0;
    String output = standardOutput;
    for(int i = 0;i < radius + 1;i++){
      int indexPos = floor(map(i, 0, radius + 1, 0, xPointsT.length));
      output += round(xPointsT[indexPos]);
      output += ",";
      output += round(yPointsT[indexPos]);
      if(i < radius){
        output += ", ";
      }
    }
    println(output);
    xPointsT = new float[0];
    yPointsT = new float[0];
  }
  float x=0, y=0;
  float interpolMul = interpolPos / radius;
  x = xPoints[pos] * interpolMul;
  y = yPoints[pos] * interpolMul;
  interpolPos+=1;//sorta the resolution
  background(0);
  
  stroke(255);
  for(int i = 0;i < 2*radius+1;i++){
    for(int j = 0;j < 2*radius+1;j++){
      if((round(x) + radius) == i && (round(y) + radius) == j && sqrt(sq(round(x)) + sq(round(y))) < radius + 0.5){
        fill(0, 255, 0);
        xPointsT = append(xPointsT, i-radius);
        yPointsT = append(yPointsT, j-radius);
        xPointsHad = append(xPointsHad, i);
        yPointsHad = append(yPointsHad, j);
      }
      else{
        int fillVal = 0;
        for(int k = 0; k < xPoints.length;k++){
          if(round(xPoints[k])+radius == i && round(yPoints[k])+radius == j){
            fillVal += 64;
          }
        }
        fill(0, 0, fillVal);
        if(fillVal == 0){
          for(int k = 0; k < xPointsHad.length;k++){
            if(round(xPointsHad[k]) == i && round(yPointsHad[k]) == j){
              fill(128, 0, 0);
            }
          }
        }
      }
      rect(i * tileSize, j * tileSize, tileSize, tileSize);
    }
  }
  
  strokeWeight(3);
  stroke(0, 255, 255, 64);
  for(int i = 0;i < xPoints.length;i++){
    line((float(radius)+0.5) * tileSize, (float(radius)+0.5) * tileSize, (float(radius)+0.5+xPoints[i]) * tileSize, (float(radius)+0.5+yPoints[i]) * tileSize);
  }
  strokeWeight(1);
  
  fill(255, 255, 0);
  ellipse((x + radius + 0.5) * tileSize, (y + radius + 0.5) * tileSize, 10, 10);
}

void setPixel(float _x, float _y){
  for(int i = 0; i < xPoints.length;i++){
    if(_x == xPoints[i] && _y == yPoints[i]){
      return;
    }
  }
  for(int i = 0; i < xPointsT.length;i++){
    if(_x == xPointsT[i] && _y == yPointsT[i]){
      return;
    }
  }
  
  xPointsT = append(xPointsT, _x);
  yPointsT = append(yPointsT, _y);
}
Run Code Online (Sandbox Code Playgroud)

除了忽略不在圆圈中的图块的主要区别之外，我还更改了将坐标存储在两个数组中而不是字符串中，因为当点数少于半径 + 1 时，我使用代码来拉伸它们，所以我不必在 C64 的 RAM 中存储多个不同大小的圆，因此它满足我的主要要求：它应该填充每个图块，并且应该通过忽略光线末端的一些点来缩小规模。如果有效的话？呃……可能有更好的解决方案，用更少的光线填充圆圈，但我不太关心。不过，如果您有想法，最好能告诉我，否则这个问题就解决了。

编辑：我忘了添加图片。不要混淆，我在发布代码后修改了代码，这样您也可以看到圆圈上的蓝色瓷砖。

实心圆

归档时间：

查看次数：

285 次

最近记录：

5 年，6 月 前
相关归档
什么是尾部呼叫优化？ 765
检测树结构之间的差异 72
根据使用频率随机生成字母？ 10
在扩展字符串中查找第k个元素 10
使用LIFO实现FIFO 9
从硬盘中排序巨大的整数 8
我是否可以始终将仅可变算法转换为单一分配并仍然有效？ 8
通缉:工作Bose-Hibbard排序实现最好用C语言 6
如何计算知道半径和中心点的圆上的点 4
如何使用NSNumbers进行数学运算 0
难疑归档
你如何获得JavaScript的时间戳？ 3844
如何删除远程标签？ 3121
是否可以将CSS应用于角色的一半？ 2717
什么是尾递归？ 1602
抽象函数和虚函数有什么区别？ 1526
没有指定分支的"git push"的默认行为 1339
如何使用INER JOIN与SQL Server删除？ 1181
Visual Studio中的构建解决方案,重建解决方案和清洁解决方案之间的区别？ 1081
如何将命令行参数传递给rake任务 1065
如何将本地jar文件添加到Maven项目？ 1053