Jak napisać algorytm, który poprawnie wypełni okrąg liniami od środka?
Obecnie staram się napisać kod do obliczania części ekranu, które widzisz i tych, którzy nie mogą z powodu obiektów blokujących światło w 2d, jak w Among Us:
Kod powinien działać na procesorze o bardzo niskich specyfikacjach (przynajmniej w 2020 r.), C64. Na tak prostym procesorze nie jest możliwe wykonanie tak złożonej matematyki wystarczająco szybko dla gry, więc wpadłem na pomysł: przede wszystkim tworzę wszystko w oparciu o kafelki, co ułatwia przetwarzanie, a także oznacza, że mogę po prostu zmienić całą znaki lub ich kolorowe komórki. Następnie po prostu piszę kod dla komputera PC w Processing (jest to język kodowania podobny do Java, ale łatwiejszy w użyciu), aby obliczyć, jak poruszałyby się promienie światła (poniższa grafika powinna uczynić to bardziej zrozumiałym), najpierw tylko z prostokątem (i pojedynczy kwadrant):
Następnie napisałem trochę brudnego kodu asemblera, aby używać zapisanych współrzędnych, aby po prostu wypełniać kafelki odwróconym znakiem w oparciu o numer promienia aktualnie rysowanego na promieniu, dopóki nie uderzą w obiekt (/ kafelek, który chce wypełnić nie odwrócony, a nie spacja), a następnie po prostu przejdź do następnego promienia. Zmniejszyłem promień do 7, więc zajmuje tylko 256 bajtów, przydatne dla ASM. I to całkowicie zadziałało, byłem w stanie naprawić każdy błąd, a wynik był imponujący, ponieważ musiałem dodać instrukcje pauzy lub wszystko działało tak szybko, że nic nie było widać.
Po tym zadziałało, wypróbowałem to z kółkiem, ustawiając punkty za pomocą tego kodu:
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);
}
Wcześniej korzystałem z algorytmu okręgu Bresenham, ale to nie do końca działało, więc wypróbowałem prostszy sposób. Więc ...
Wszystkie zaznaczone czarne płytki nigdy nie zostaną trafione przez żadne światło, co jest dość dużym problemem, ponieważ nie miałoby to większego sensu w grze, w której po prostu nie widać tych płytek. Kod, którego użyłem, napisany w Processing , to:
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);
}
(Instrukcje uzyskania prostokąta znajdują się w kodzie) Te wspomniane kafelki wydają się nigdy nie trafiać, ponieważ promienie na nich po prostu przeskakują nad nimi, ale co mogę zrobić, aby temu zapobiec? Możesz zmniejszyć interpolPos + = x; uderzać więcej płytek, ponieważ w ten sposób twoje kroki są mniejsze, ale to marnuje trochę miejsca, więc nie uważam, że to dobre rozwiązanie. Najlepiej byłoby po prostu zmniejszyć liczbę rysowanych współrzędnych, aby uzyskać mniejszą wizję. Czy ktoś ma dobry pomysł, jak to zrobić?
Odpowiedzi
Wybrałeś niewłaściwą metodę wyszukiwania wszystkich dotkniętych komórek - zamiast metody opartej na punktach, w której potrzebujesz podejścia opartego na komórkach (kwadratach) - promień przecina prostokąt, a nie punkt.
Jest artykuł Amanatides i Woo „A Fast Voxel Traversal Algorithm for Ray Tracing” dla 2D.
Praktyczna realizacja .
Przykład:
Przykład szybkiego śledzenia. Promienie emitowane z lewego górnego rogu przechodzą do niebieskich punktów. Jeśli promień napotka przeszkodę z czarnych komórek, zatrzymuje się. Różowe komórki są oświetlone promieniami, szare - nie.
Okay, znalazłem coś, co działało dla mnie w mojej sytuacji: po prostu użyłem części, która całkowicie działa (prostokąt), a następnie po prostu utworzyłem okrąg, ignorując każde uderzenie płytki, które jest dalej od źródła światła, a następnie promień + 0,5, bo bez + .5 koło wygląda dziwnie. Możesz spróbować samemu, oto kod:
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);
}
Oprócz głównej różnicy w ignorowaniu kafelków, które nie są w okręgu, zmieniłem też, że przechowuję współrzędne nie w łańcuchu, ale w dwóch tablicach, ponieważ wtedy używam kodu, aby je rozciągnąć, gdy jest mniej niż promień + 1 punktów, więc Nie muszę przechowywać wielu kręgów o różnych rozmiarach w pamięci RAM C64, więc spełnia moje główne wymagania: powinien wypełniać każdy kafelek i powinien być skalowany w dół, ignorując niektóre punkty na końcu promieni. A czy jest skuteczny? Uh ... mogłoby być lepsze rozwiązanie, które wypełni krąg mniejszą liczbą promieni, ale nie obchodzi mnie to zbytnio. Mimo wszystko, jeśli masz pomysł, byłoby miło, gdybyś mógł mi powiedzieć, ale w przeciwnym razie to pytanie jest rozwiązane.
Edycja: zapomniałem dodać zdjęcie. Nie daj się zmylić, zmodyfikowałem kod po wysłaniu go, abyś mógł również zobaczyć niebieskie kafelki na kółku.
