中心からの線を使用して円を適切に塗りつぶすアルゴリズムをどのように作成できますか？
現在、私はあなたが見ることができる画面の部分と、2Dで光を遮るオブジェクトのために見ることができない人々を計算するためのコードを書こうとしています。
コードは、スペックが非常に低いプロセッサ（少なくとも2020年）であるC64で実行する必要があります。このような単純なCPUでは、ゲームに十分な速度で複雑な計算を行うことはできないため、私はアイデアを思いつきました。まず、すべてをタイルベースにすることで、処理が簡単になり、全体を変更できるようになります。文字またはそのカラーセル。次に、ProcessingでPC用のコード（Javaに似ていますが使いやすいコーディング言語）を記述して、光線がどのように移動するかを計算します（次の図はそれをより理解しやすくする必要があります）。最初は長方形（および単一象限）：
次に、記録された座標を使用して、オブジェクトに当たるまで光線に現在描画されている光線の数に基づいて、タイルを反転文字で塗りつぶし続けるための完全に厄介なアセンブラコードを作成しました（/塗りつぶしたいタイルは反転せず、スペースではありません）、次の光線に移動します。半径を7に減らしたので、ASMに役立つ256バイトしかかかりません。そしてそれは完全に機能し、すべてのバグを修正することができ、一時停止ステートメントを追加する必要があったか、すべてが非常に高速で実行されて何も表示されなかったため、結果は非常に印象的でした。
それがうまくいった後、私はこのコードを使用してポイントを設定し、円でそれを試しました：
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を減らすことができます。ステップが小さいので、より多くのタイルをヒットしますが、それはかなりのスペースを浪費するので、それは良い解決策ではないと思います。理想的には、描画する座標の数を減らして、ビジョンを小さくすることもできます。誰かがそれを行う方法について良い考えがありますか？
回答
タッチされたすべてのセルを見つけるために間違った方法を選択しました-セル（正方形）ベースのアプローチが必要なポイントベースの方法の代わりに-光線はポイントではなく長方形と交差します。
2D用のAmanatidesandWoo「レイトレーシング用の高速ボクセルトラバーサルアルゴリズム」の記事があります。
実用的な実装。
例：
クイックメイドのトレース例。左上隅から放出された光線は青い点に行きます。光線が黒い細胞の障害物にぶつかると、停止します。ピンクのセルは光線で照らされますが、灰色のセルはそうではありません。
さて、私は自分の状況でうまくいくものを見つけました：完全に機能する部分（長方形）を使用し、光源から半径+ 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);
}
円にないタイルを無視する主な違いに加えて、座標を文字列ではなく2つの配列に格納するように変更しました。これは、半径+1ポイントより少ない場合にコードを使用してタイルを引き伸ばすためです。サイズの異なる複数の円をC64のRAMに保存する必要がないため、主な要件を満たしています。すべてのタイルを埋め、光線の端のいくつかのポイントを無視してダウンスケーリングできる必要があります。そして、効率的ですか？ええと...より少ない光線で円を埋めるより良い解決策があるかもしれませんが、私はあまり気にしません。それでも、アイデアがあれば教えていただければ幸いですが、それ以外の場合はこの質問は解決されます。
編集：写真を追加するのを忘れました。混乱しないでください。投稿後にコードを変更して、円の青いタイルも表示されるようにしました。
