Comment pouvez-vous écrire un algorithme pour remplir correctement un cercle en utilisant des lignes du centre?
Actuellement, j'essaie d'écrire du code pour calculer les parties de l'écran que vous pouvez voir et celles qui ne le peuvent pas à cause des objets qui bloquent la lumière en 2D, comme dans Among Us:
Le code devrait fonctionner sur un processeur aux spécifications très faibles (au moins en 2020), le C64. Sur un processeur aussi simple, il n'est pas possible de faire des calculs aussi complexes assez rapidement pour un jeu, alors j'ai eu une idée: tout d'abord, je fais tout basé sur des tuiles, ce qui facilite le traitement et signifie également que je peux simplement changer entièrement caractères ou leurs cellules de couleur. Ensuite, j'écris simplement du code pour le PC en traitement (c'est un langage de codage similaire à Java mais plus facile à utiliser) pour calculer comment les rayons de lumière se déplaceraient (le graphique suivant devrait rendre cela plus compréhensible), d'abord avec un rectangle (et un quadrant unique):
Ensuite, j'ai écrit un code d'assembleur complètement désordonné pour utiliser les coordonnées enregistrées pour continuer simplement à remplir les tuiles avec un caractère inversé en fonction du numéro du rayon actuellement dessiné sur le rayon jusqu'à ce qu'ils touchent un objet (/ la tuile qu'il veut remplir est pas inversé et pas un espace) puis passez simplement au rayon suivant. J'ai réduit le rayon à 7 donc cela ne prend que 256 octets, utile pour ASM. Et cela a totalement fonctionné, j'ai pu corriger chaque bogue et le résultat était assez impressionnant, car j'avais besoin d'ajouter des instructions de pause ou tout fonctionnait si vite que vous ne pouviez rien voir.
Après cela, je l'ai essayé avec un cercle, en définissant les points en utilisant ce code:
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);
}
J'utilisais auparavant l'algorithme du cercle de Bresenham mais cela ne fonctionnait pas tout à fait, alors j'ai essayé un moyen plus simple. Alors ...
Toutes les tuiles noires marquées ne sont jamais touchées par la lumière, ce qui est un gros problème, car cela n'aurait pas beaucoup de sens dans un jeu que vous ne puissiez tout simplement pas voir ces tuiles. Le code que j'ai utilisé, écrit dans Processing , est:
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);
}
(Les instructions pour obtenir le rectangle sont dans le code) Ces tuiles mentionnées semblent ne jamais être touchées parce que les rayons sur elles sautent juste dessus, mais que puis-je faire pour éviter cela? Vous pouvez diminuer interpolPos + = x; frapper plus de tuiles parce que de cette façon vos pas sont plus petits, mais cela gaspille beaucoup d'espace, donc je ne pense pas que ce soit une bonne solution. Idéalement, vous pouvez également simplement réduire le nombre de coordonnées que vous dessinez pour obtenir une vision plus petite. Quelqu'un a-t-il une bonne idée de la façon de procéder?
Réponses
Vous avez choisi une mauvaise méthode pour trouver toutes les cellules touchées - au lieu d'une méthode basée sur des points, vous avez besoin d'une approche basée sur des cellules (carrés) - le rayon coupe un rectangle plutôt qu'un point.
Il y a un article d'Amanatides et Woo "Un algorithme de traversée rapide de Voxel pour le Ray Tracing" pour 2D.
Mise en œuvre pratique .
Exemple:
Exemple de traçage rapide. Les rayons émis par le coin supérieur gauche vont aux points bleus. Si le rayon rencontre l'obstacle de la cellule noire, il s'arrête. Les cellules roses sont éclairées par les rayons, les grises ne le sont pas.
D'accord, j'ai trouvé quelque chose qui a fonctionné pour moi dans ma situation: j'ai juste utilisé la partie qui fonctionne totalement (le rectangle) et ensuite juste faire un cercle en ignorant chaque tuile frappée qui est plus éloignée de la source de lumière puis le rayon + 0,5, parce que sans + .5 le cercle semble bizarre. Vous pouvez l'essayer vous-même, voici le code:
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);
}
Outre la principale différence d'ignorer les tuiles qui ne sont pas dans le cercle, j'ai également changé que je stockais les coordonnées non pas dans une chaîne mais dans deux tableaux, car j'utilise ensuite du code pour les étirer lorsqu'il y a moins de rayon + 1 points, donc Je n'ai pas besoin de stocker plusieurs cercles de tailles différentes dans la RAM du C64, donc cela répond à mes principales exigences: il devrait remplir chaque tuile et il devrait être downscalable en ignorant certains points à la fin des rayons. Et est-ce efficace? Euh ... il pourrait y avoir une meilleure solution qui remplit le cercle avec moins de rayons, mais je m'en fiche. Pourtant, si vous avez une idée, ce serait bien si vous pouviez me le dire, mais sinon cette question est résolue.
Edit: j'ai oublié d'ajouter une image. Ne soyez pas confus, j'ai modifié le code après l'avoir publié afin que vous puissiez également voir les tuiles bleues sur le cercle.
