¿Cómo se puede escribir un algoritmo para rellenar correctamente un círculo usando líneas desde el centro?
Actualmente intento escribir código para calcular las partes de la pantalla que puedes ver y las que no pueden debido a objetos que bloquean la luz en 2d, como en Among Us:
El código debería ejecutarse en un procesador con especificaciones muy bajas (al menos en 2020), el C64. En una CPU tan simple no es posible hacer matemáticas tan complejas lo suficientemente rápido para un juego, así que se me ocurrió una idea: en primer lugar, hago todo basado en mosaicos, eso facilita el procesamiento y también significa que puedo cambiar todo caracteres o sus celdas de color. Luego escribo código para la PC en Processing (que es un lenguaje de codificación similar a Java pero más fácil de usar) para calcular cómo se moverían los rayos de luz (el siguiente gráfico debería hacer eso más comprensible), primero solo con un rectángulo (y un cuadrante único):
Luego escribí un código de ensamblador completamente desordenado para usar las coordenadas grabadas para seguir llenando los mosaicos con un carácter invertido según el número del rayo que se dibuja actualmente en el rayo hasta que golpean un objeto (/ el mosaico que quiere llenar es no invertido y no un espacio) y luego simplemente pasar al siguiente rayo. Reduje el radio a 7, por lo que solo ocupa 256 bytes, útil para ASM. Y eso funcionó totalmente, pude corregir cada error y el resultado fue bastante impresionante, ya que necesitaba agregar declaraciones de pausa o todo corría tan rápido que no se podía ver nada.
Después de que funcionó, lo probé con un círculo, estableciendo los puntos 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);
}
Anteriormente usé el algoritmo de círculo de Bresenham, pero no funcionó del todo, así que probé una forma más simple. Entonces ...
Todas las fichas negras marcadas nunca reciben luz, lo cual es un problema bastante grande, porque no tendría mucho sentido en un juego que simplemente no puedas ver esas fichas. El código que utilicé, escrito en Processing , es:
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);
}
(Las instrucciones para obtener el rectángulo están en el código) Parece que los mosaicos mencionados nunca se golpean porque los rayos en ellos simplemente saltan sobre ellos, pero ¿qué puedo hacer para evitar eso? Puede disminuir interpolPos + = x; golpear más fichas porque de esa manera sus pasos son más pequeños, pero eso desperdicia bastante espacio, así que no creo que sea una buena solución. Idealmente, también podría disminuir la cantidad de coordenadas que dibuja para obtener una visión más pequeña. ¿Alguien tiene una buena idea de cómo hacer eso?
Respuestas
Ha elegido un método incorrecto para encontrar todas las celdas tocadas; en lugar de la forma basada en puntos, necesita un enfoque basado en celdas (cuadrados): el rayo interseca el rectángulo en lugar de un punto.
Hay un artículo de Amanatides y Woo "A Fast Voxel Traversal Algorithm for Ray Tracing" para 2D.
Implementación práctica .
Ejemplo:
Ejemplo de rastreo rápido. Los rayos emitidos desde la esquina superior izquierda van a puntos azules. Si el rayo se encuentra con un obstáculo de células negras, se detiene. Las células rosadas están iluminadas por rayos, las grises no.
De acuerdo, encontré algo que funcionó para mí en mi situación: solo usé la parte que funciona totalmente (el rectángulo) y luego lo hice un círculo ignorando cada golpe de mosaico que está más lejos de la fuente de luz y luego el radio + 0.5, porque sin + .5 el círculo se ve extraño. Puede probarlo usted mismo, aquí está el 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);
}
Además de la principal diferencia de ignorar los mosaicos que no están en el círculo, también cambié que almaceno las coordenadas no en una Cadena sino en dos matrices, porque luego uso código para estirarlas cuando hay menos puntos de radio + 1, entonces No tengo que almacenar varios círculos con diferentes tamaños en la RAM del C64, por lo que cumple con mis requisitos principales: debe llenar todos los mosaicos y debe poder reducirse ignorando algunos puntos al final de los rayos. ¿Y si es eficiente? Uh ... podría haber una solución mejor que llene el círculo con menos rayos, pero no me importa demasiado. Aún así, si tiene una idea, sería bueno que me lo dijera, pero de lo contrario esta pregunta está resuelta.
Editar: Olvidé agregar una imagen. No se confunda, modifiqué el código después de publicarlo para que también pueda ver los mosaicos azules en el círculo.
