algorithm - 您如何编写算法以使用中心线正确填充圆?
问题描述
目前,我尝试编写代码来计算您可以看到的屏幕部分以及那些因为在 2d 中阻挡光线的物体而不能看到的部分,例如在我们当中:
代码应该在规格非常低的处理器(至少在 2020 年)C64 上运行。在如此简单的 CPU 上,不可能以足够快的速度为游戏完成如此复杂的数学运算,所以我想出了一个想法:首先,我将所有内容都基于 tile,这使得处理更容易,也意味着我可以改变整个字符或其颜色单元格。然后我只是在 Processing 中为 PC 编写代码(这是一种类似于 Java 但更易于使用的编码语言)来计算光线的移动方式(下图应该更容易理解),首先是一个矩形(和一个单象限):
然后我编写了一些完全混乱的汇编代码,用于使用记录的坐标,根据当前在射线上绘制的射线的数量,用倒置字符填充瓷砖,直到它们击中一个对象(/它想要填充的瓷砖是不是倒置也不是空格),然后转到下一条射线。我将半径减小到 7,所以它只占用 256 个字节,这对 ASM 很有用。这完全奏效了,我能够修复每一个错误,结果令人印象深刻,因为我需要添加暂停语句,否则一切都运行得太快以至于你什么都看不到。
之后,我尝试了一个圆圈,使用以下代码设置点:
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);
}
我以前使用过 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);
}
(获取矩形的说明在代码中)那些提到的瓷砖似乎永远不会被击中,因为它们上的光线只是跳过它们,但我能做些什么来防止这种情况发生?你可以减少 interpolPos+=x; 打更多的瓷砖,因为这样你的步数更小,但这会浪费相当多的空间,所以我认为这不是一个好的解决方案。理想情况下,您也可以减少绘制的坐标数以获得更小的视野。有谁知道如何做到这一点?
解决方案
推荐阅读
- android - android.net.wifi.STATE_CHANGE or android.net.wifi.supplicant.CONNECTION_CHANGE
- php - How can I run multiple Laravel commands simultaneously?
- java - 如何使用带有 SSL 的 httpclient 调用 SOAP Web 服务
- html - Is it valid HTML to have more than one label targetting an item?
- react-native - 面对“Devtools 与页面断开连接。重新加载页面后,Devtools 将自动重新连接。”
- c# - 如何更改 DataGridView 背景颜色/单元格颜色
- rust - 如何使用匹配处理 Rust 中的多个可变借用?
- python-3.x - 交叉()函数不起作用python3
- html - 角材料表 bg 颜色
- python-3.x - 找不到我制作的模块