Como você pode escrever um algoritmo para preencher corretamente um círculo usando linhas do centro?
Atualmente tento escrever um código para calcular as partes da tela que você pode ver e aquelas que não podem por causa de objetos que bloqueiam a luz em 2d, como em Entre nós:
O código deve ser executado em um processador com especificações muito baixas (pelo menos em 2020), o C64. Em uma CPU tão simples não é possível fazer uma matemática tão complexa rápido o suficiente para um jogo, então eu tive uma ideia: Primeiro de tudo, eu faço tudo baseado em blocos, o que torna o processamento mais fácil e também significa que eu posso apenas mudar todo caracteres ou suas células coloridas. Então, eu apenas escrevo o código para o PC em Processing (que é uma linguagem de codificação semelhante a Java, mas mais fácil de usar) para calcular como os raios de luz se moveriam (o gráfico a seguir deve tornar isso mais compreensível), primeiro apenas com um retângulo (e um quadrante único):
Então eu escrevi um código assembler completamente confuso para usar as coordenadas gravadas para apenas continuar enchendo os ladrilhos com um caractere invertido com base no número do raio atualmente sendo desenhado no raio até atingir um objeto (/ o ladrilho que ele deseja preencher é não invertido e não um espaço) e então vá para o próximo raio. Reduzi o raio para 7 para ocupar apenas 256 bytes, útil para ASM. E funcionou totalmente, consegui consertar todos os bugs e o resultado foi impressionante, já que precisava adicionar instruções de pausa ou tudo rodava tão rápido que você não conseguia ver nada.
Depois que funcionou, tentei com um círculo, definindo os pontos usando este código:
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);
}
Eu usei anteriormente o algoritmo do círculo de Bresenham, mas não funcionou muito bem, então tentei uma maneira mais simples. Então ...
Todas as peças pretas marcadas nunca são atingidas por nenhuma luz, o que é um grande problema, porque não faria muito sentido em um jogo que você simplesmente não pudesse ver essas peças. O código que usei, escrito em 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);
}
(As instruções para obter o retângulo estão no código) Esses blocos mencionados parecem nunca ser atingidos porque os raios neles simplesmente saltam sobre eles, mas o que posso fazer para evitar isso? Você pode diminuir interpolPos + = x; para acertar mais ladrilhos porque assim seus passos são menores, mas isso desperdiça bastante espaço, então não acho que seja uma boa solução. Idealmente, você também pode diminuir o número de coordenadas que desenha para obter uma visão menor. Alguém tem uma boa ideia de como fazer isso?
Respostas
Você escolheu o método errado para encontrar todas as células tocadas - em vez do método baseado em pontos, você precisa de uma abordagem baseada em células (quadrados) - o raio intercepta o retângulo ao invés do ponto.
Há um artigo de Amanatides e Woo "A Fast Voxel Traversal Algorithm for Ray Tracing" para 2D.
Implementação prática .
Exemplo:
Exemplo de rastreamento rápido. Os raios emitidos do canto superior esquerdo vão para pontos azuis. Se o raio encontrar o obstáculo das células negras, ele para. As células rosa são iluminadas por raios, as cinzas não.
Ok, encontrei algo que funcionou para mim na minha situação: acabei de usar a parte que funciona totalmente (o retângulo) e, em seguida, apenas fazer um círculo, ignorando cada batimento de ladrilho que está mais longe da fonte de luz, em seguida, o raio + 0,5, porque sem + .5 o círculo parece estranho. Você pode tentar você mesmo, este é o código:
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);
}
Além da principal diferença para ignorar blocos que não estão no círculo, também mudei para armazenar as coordenadas não em uma String, mas em duas matrizes, porque então eu uso o código para esticá-los quando há menos de raio + 1 pontos, então Não preciso armazenar vários círculos com tamanhos diferentes na RAM do C64, portanto, atende aos meus requisitos principais: deve preencher todos os ladrilhos e deve ser redimensionável ignorando alguns pontos no final dos raios. E se é eficiente? Uh ... poderia haver uma solução melhor que preencha o círculo com menos raios, mas eu não me importo muito. Ainda assim, se você tem uma ideia, seria bom se você pudesse me dizer, mas caso contrário esta questão está resolvida.
Edit: Esqueci de adicionar uma foto. Não se confunda, eu modifiquei o código depois de postá-lo para que você também possa ver os blocos azuis no círculo.
