Wie kann man einen Algorithmus schreiben, um einen Kreis mit Linien von der Mitte aus richtig zu füllen?
Derzeit versuche ich, Code für die Berechnung der Teile des Bildschirms zu schreiben, die Sie sehen können, und derjenigen, die dies aufgrund von Objekten, die das Licht in 2D blockieren, nicht können, wie in Among Us:
Der Code sollte auf einem Prozessor mit sehr niedrigen Spezifikationen (zumindest im Jahr 2020), dem C64, ausgeführt werden. Auf einer so einfachen CPU ist es nicht möglich, so komplexe Berechnungen für ein Spiel schnell genug durchzuführen. Deshalb kam mir die Idee: Zunächst mache ich alles kachelbasiert, was die Verarbeitung erleichtert und auch bedeutet, dass ich einfach das Ganze ändern kann Zeichen oder ihre Farbzellen. Dann schreibe ich einfach Code für den PC in Processing (das ist eine Java-ähnliche Codierungssprache, aber einfacher zu verwenden), um zu berechnen, wie sich Lichtstrahlen bewegen würden (die folgende Grafik sollte dies verständlicher machen), zuerst nur mit einem Rechteck (und einem einzelner Quadrant):
Dann schrieb ich einen völlig unordentlichen Assembler-Code für die Verwendung der aufgezeichneten Koordinaten, um die Kacheln weiterhin mit einem invertierten Zeichen zu füllen, basierend auf der Nummer des Strahls, der gerade auf dem Strahl gezeichnet wird, bis sie auf ein Objekt treffen (/ die Kachel, die gefüllt werden soll, ist nicht invertiert und kein Leerzeichen) und dann einfach zum nächsten Strahl gehen. Ich habe den Radius auf 7 reduziert, sodass er nur 256 Bytes benötigt, was für ASM nützlich ist. Und das hat total funktioniert, ich konnte jeden einzelnen Fehler beheben und das Ergebnis war ziemlich beeindruckend, da ich Pausenanweisungen hinzufügen musste oder alles so schnell lief, dass man nichts sehen konnte.
Nachdem das funktioniert hat, habe ich es mit einem Kreis versucht und die Punkte mit diesem Code gesetzt:
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);
}
Ich habe zuvor den Bresenham-Kreisalgorithmus verwendet, aber das hat nicht ganz funktioniert, also habe ich es auf einfachere Weise versucht. Damit ...
Alle markierten schwarzen Kacheln werden nie von Licht getroffen, was ein ziemlich großes Problem ist, da es in einem Spiel nicht viel Sinn macht, diese Kacheln einfach nicht zu sehen. Der Code, den ich in Processing geschrieben habe , lautet:
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);
}
(Anweisungen zum Abrufen des Rechtecks finden Sie im Code.) Diese genannten Kacheln scheinen nie getroffen zu werden, da die Strahlen auf ihnen nur über sie springen. Aber was kann ich tun, um dies zu verhindern? Sie können interpolPos + = x verringern; mehr Kacheln zu treffen, weil auf diese Weise Ihre Schritte kleiner sind, aber das verschwendet ziemlich viel Platz, also denke ich nicht, dass das eine gute Lösung ist. Im Idealfall können Sie auch die Anzahl der von Ihnen gezeichneten Koordinaten verringern, um eine kleinere Sicht zu erhalten. Hat jemand eine gute Idee, wie das geht?
Antworten
Sie haben eine falsche Methode gewählt, um alle berührten Zellen zu finden. Anstelle einer punktbasierten Methode benötigen Sie einen zellbasierten (quadratischen) Ansatz. Der Strahl schneidet eher ein Rechteck als einen Punkt.
Es gibt einen Artikel von Amanatides und Woo "Ein schneller Voxel-Traversal-Algorithmus für Ray Tracing" für 2D.
Praktische Umsetzung .
Beispiel:
Beispiel für eine schnelle Nachverfolgung. Von der linken oberen Ecke emittierte Strahlen gehen zu blauen Punkten. Wenn der Strahl auf ein Hindernis für schwarze Blutkörperchen trifft, stoppt er. Rosa Zellen werden durch Strahlen beleuchtet, graue nicht.
Okay, ich habe etwas gefunden, das in meiner Situation für mich funktioniert hat: Ich habe nur den Teil verwendet, der vollständig funktioniert (das Rechteck) und dann einfach einen Kreis daraus gemacht, indem ich jeden Kacheltreffer ignoriert habe, der weiter von der Lichtquelle entfernt ist als der Radius + 0,5, denn ohne + .5 sieht der Kreis komisch aus. Sie können es selbst versuchen, hier ist der 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);
}
Neben dem Hauptunterschied, Kacheln zu ignorieren, die sich nicht im Kreis befinden, habe ich auch geändert, dass ich die Koordinaten nicht in einem String, sondern in zwei Arrays speichere, da ich sie dann mithilfe von Code strecke, wenn weniger als Radius + 1 Punkte vorhanden sind Ich muss nicht mehrere Kreise mit unterschiedlichen Größen im RAM des C64 speichern, daher erfüllt es meine Hauptanforderungen: Es sollte jede Kachel füllen und durch Ignorieren einiger Punkte am Ende der Strahlen verkleinert werden können. Und ist es effizient? Äh ... es könnte eine bessere Lösung geben, die den Kreis mit weniger Strahlen füllt, aber es ist mir egal. Wenn Sie eine Idee haben, wäre es schön, wenn Sie es mir sagen könnten, aber ansonsten ist diese Frage gelöst.
Bearbeiten: Ich habe vergessen, ein Bild hinzuzufügen. Seien Sie nicht verwirrt, ich habe den Code nach dem Posten geändert, damit Sie auch die blauen Kacheln auf dem Kreis sehen können.
