На Mastodon есть полузаглохший канал BBC Microbot, на котором публикуют разные программы на BBC BASIC. Для начинающих программа покажется сложной - я уже писал об этом. Полгода у меня валялась в папке одна программа, с которой я собирался разобраться. Прошло примерно три часа диалога с Яндексом, чтобы разобраться с принципом работы. Исходник:
https://bbcmic.ro/?t=dvf4r
10 MODE4:C=0:@%!4=8:@%!12=-8:Q%=@%+4:FORS%=0TO1023STEP8:FORR%=0TO1279STEP8:X%=R%:Y%=S%:MOVEX%,Y%
20 FORD%=C-3TOC:B%=D%*4AND12:V%=X%+@%!B%:W%=Y%+Q%!B%:IFPOINT(V%,W%)NEXT,,:VDU5,21
30 D%=HIMEM:NEXTD%:X%=V%:Y%=W%:DRAWX%,Y%:C=C+.125:GOTO20
Диалог был таким:
- разбери алгоритм программы, вот текст
- молчок
разбил на пробелы, скинул текст, задал вопрос
- ооооо, это круто! вот алгоритм.
- картинка не похожа на оригинал, вот ссылка.
- хммм, пошарил по докам, вот вариант.
- какое значение выдаст POINT(), если координаты вышли за диапазон экран.
- упс, сейчас разберусь.
Получил исходник на Си, скомпилировал, запустил, получил картинку формата .pgm, но так и не смог посмотреть. Вот оно:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <math.h>
#define WIDTH 1280
#define HEIGHT 1024
static uint8_t screen[HEIGHT][WIDTH];
/*
* BBC BASIC POINT(x,y):
* Returns -1 (blocked) for off-screen coordinates.
* Returns 0 (free) for on-screen empty pixels.
* Returns 1 (blocked) for on-screen drawn pixels.
*/
static int point(int x, int y)
{
if (x < 0 || x >= WIDTH || y < 0 || y >= HEIGHT)
return -1; /* off-screen = blocked */
return screen[y][x];
}
/* Bresenham line */
static void draw_line(int x0, int y0, int x1, int y1)
{
int dx = abs(x1 - x0), sx = x0 < x1 ? 1 : -1;
int dy = -abs(y1 - y0), sy = y0 < y1 ? 1 : -1;
int err = dx + dy, e2;
for (;;) {
if (x0 >= 0 && x0 < WIDTH && y0 >= 0 && y0 < HEIGHT)
screen[y0][x0] = 1;
if (x0 == x1 && y0 == y1) break;
e2 = 2 * err;
if (e2 >= dy) { err += dy; x0 += sx; }
if (e2 <= dx) { err += dx; y0 += sy; }
}
}
/*
* @% defaults to &90A = 2314 in BBC BASIC II.
* Program writes 8 to addr @%+4 = 2318, -8 to addr @%+12 = 2326.
* Addresses @%+0 = 2314, @%+8 = 2322, @%+16 = 2330 are in cleared
* user workspace (zeroed after boot), so all read back as 0.
*
* Direction table (B% = 0,4,8,12):
* B%=0: dx=0, dy=8 -> UP
* B%=4: dx=8, dy=0 -> RIGHT
* B%=8: dx=0, dy=-8 -> DOWN
* B%=12: dx=-8, dy=0 -> LEFT
*/
static const int dx[4] = { 0, 8, 0, -8 };
static const int dy[4] = { 8, 0, -8, 0 };
static int b_from_d(int d) { return (d * 4) & 12; }
/* Truncation toward zero, matching BBC BASIC INT() */
static int trunc_int(double v) { return (int)v; }
static int floor_int(double v) { return (int)floor(v); }
int main(void)
{
memset(screen, 0, sizeof(screen));
double C = 0.0;
int lines = 0;
for (int S = 0; S < 1024; S += 8) {
for (int R = 0; R < 1280; R += 8) {
int X = R, Y = S;
/* FOR D%=C-3 TO C: try 3-4 directions */
int d_start = trunc_int(C - 3.0);
int d_last = floor_int(C);
int found = 0, V = 0, W = 0;
for (int D = d_start; D <= d_last; D++) {
int B = b_from_d(D) / 4;
V = X + dx[B];
W = Y + dy[B];
if (point(V, W) == 0) { found = 1; break; }
}
if (!found) continue;
/* Draw spiral */
while (lines < 200000) {
d_start = trunc_int(C - 3.0);
d_last = floor_int(C);
found = 0;
for (int D = d_start; D <= d_last; D++) {
int B = b_from_d(D) / 4;
V = X + dx[B];
W = Y + dy[B];
if (point(V, W) == 0) { found = 1; break; }
}
if (!found) break;
draw_line(X, Y, V, W);
X = V; Y = W;
lines++;
C += 0.125;
}
}
}
long px = 0;
for (int y = 0; y < HEIGHT; y++)
for (int x = 0; x < WIDTH; x++)
if (screen[y][x]) px++;
printf("Lines: %d, Pixels: %ld\n", lines, px);
FILE *f = fopen("spiral.pgm", "wb");
if (f) {
fprintf(f, "P5\n%d %d\n255\n", WIDTH, HEIGHT);
for (int y = HEIGHT - 1; y >= 0; y--)
fwrite(screen[y], 1, WIDTH, f);
fclose(f);
printf("Saved spiral.pgm\n");
}
return 0;
}
Переписал код на PureBasic и получил хер пойми что. Исправил опечатки и картинка готова:
Dim dx(4)
Dim dy(4)
dx(0)=0
dx(1)=8/2
dx(2)=0
dx(3)=-8/2
dy(0)=8/2
dy(1)=0
dy(2)=-8/2
dy(3)=0
Procedure b_from_d(d)
ProcedureReturn (d * 4) & 12
EndProcedure
Procedure pt(x,y)
If (x < 0) Or (x >= 1280) Or (y < 0) Or (y >= 1024)
ProcedureReturn -1; /* off-screen = blocked */
EndIf
ProcedureReturn Point(x,y)
EndProcedure
If OpenWindow(0, 0, 0, 1280,1024, "BBC maze", #PB_Window_SystemMenu | #PB_Window_ScreenCentered)
CanvasGadget(0, 0, 0, 1280, 1024)
c.f=0
lines=0
If StartDrawing(CanvasOutput(0))
Box(0,0,1280,1024,0)
For S = 0 To 1024 Step 4
For R = 0 To 1280 Step 4
X = R
Y = S
d_start =Int(C - 3)
d_last =Int(C)
found = 0
V = 0
W = 0;
For D = d_start To d_last
B = b_from_d(D) / 4;
V = X + dx(B)
W = Y + dy(B)
If Pt(V, W) = 0
found = 1
Break 1
EndIf
Next D
; If Not found
; Continue
; EndIf
If Not found
Goto cont
EndIf
;/* Draw spiral */
While lines < 200000
d_start = Int(C - 3);
d_last = Int(C) ;
found = 0;
For D = d_start To d_last
B = b_from_d(D) / 4;
V = X + dx(B)
W = Y + dy(B)
If Pt(V, W) = 0
found = 1
Break
EndIf
Next d
If Not found
Break;
EndIf
LineXY(X, Y, V, W,$FFFFFF)
X = V
Y = W;
lines+1
C +0.125;
Wend
cont:
Next R
Next S
StopDrawing()
EndIf
Repeat
Event = WaitWindowEvent()
Until Event = #PB_Event_CloseWindow
EndIf
Оставлю кусок лога, который хоть что-то объясняет:
Что рисует программа
Программа заполняет экран спиралевидным узором — прямоугольными спиралями, которые выходят за границы экрана и возвращаются обратно, постепенно заполняя всё доступное пространство.
Разбор по строкам
Строка 10 — инициализация
10 MODE4:C=0:@%!4=8:@%!12=-8:Q%=@%+4:
FORS%=0TO1023STEP8:FORR%=0TO1279STEP8:
X%=R%:Y%=S%:MOVEX%,Y%
MODE 4 — графический режим 320×256, 2 цвета. Но в BBC Micro логические графические координаты всегда 0–1279 (X) × 0–1023 (Y), независимо от режима. Начало координат — в нижнем левом углу.
C=0 — счётчик направления (вещественный, увеличивается на 0.125 за шаг).
Таблица направлений через @%: это самый хитрый приём программы. @% в BBC BASIC — это специальная целочисленная переменная для форматирования вывода, по умолчанию равна 0. Программа использует её значение (0) как базовый адрес и записывает направления прямо в нулевую страницу памяти:
@%!4=8 — записывает 32-битное значение 8 по абсолютному адресу 4
@%!12=-8 — записывает -8 по абсолютному адресу 12
Q%=@%+4=4 — указатель со сдвигом для Y-компонент
Получается таблица из четырёх направлений (по 8 пикселей), где X-компоненты читаются из @%!B%, а Y-компоненты — из Q%!B% (тот же массив, но со сдвигом на 4 байта):
B% @%!B% (dx) Q%!B% (dy) Направление
0 0 8 Вверх
4 8 0 Вправо
8 0 -8 Вниз
12 -8 0 Влево
Программа рассчитывает, что по адресам 0, 8 и 16 в нулевой странице уже лежат нули — что на BBC Micro так и есть.
Вложенные циклы: S% (Y) от 0 до 1023 с шагом 8, R% (X) от 0 до 1279 с шагом 8 — программа сканирует экран по сетке 8×8 пикселей. Для каждой точки выполняется MOVE X%,Y% — перемещение графического курсора.
Строка 20 — поиск свободного направления
basic
20 FORD%=C-3TOC:B%=D%*4AND12:V%=X%+@%!B%:W%=Y%+Q%!B%:
IFPOINT(V%,W%)NEXT,,:VDU5,21
FOR D%=C-3 TO C — цикл по 4 значениям D%. Но по факту проверяется только первое значение (доказательство ниже).
B%=D%*4 AND 12 — отображение D% на индекс таблицы направлений {0, 4, 8, 12} с циклическим повторением каждые 4 значения. Благодаря AND 12 отрицательные значения D% тоже корректно замыкаются:
D% D%×4 AND 12 B% Направление
-3 -12 4 4 Вправо
-2 -8 8 8 Вниз
-1 -4 12 12 Влево
0 0 0 0 Вверх
1 4 4 4 Вправо
... ... ... ... (цикл)
V%=X%+@%!B% и W%=Y%+Q%!B% — координаты следующей точки: текущая позиция плюс вектор направления.
IF POINT(V%,W%) NEXT,, — ключевая проверка. POINT(V%,W%) возвращает 1, если пиксель уже нарисован, и 0, если нет:
Пиксель нарисован → выполняется NEXT,, — закрывает два внутренних цикла (D% и R%), перескакивает к следующей точке сетки. Программа сдаётся на этой позиции.
Пиксель свободен → IF ложен, весь остаток строки пропускается, выполнение переходит к строке 30.
В BBC BASIC IF без THEN делает всю оставшуюся часть строки условной. Поэтому :VDU5,21 — это мёртвый код: если POINT истинен, NEXT,, уходит на другую итерацию до того, как VDU5,21 успеет выполниться; если POINT ложен, вся строка пропускается. VDU 5,21 не выполняется ни в одном случае.
Строка 30 — рисование и цикл
30 D%=HIMEM:NEXTD%:X%=V%:Y%=W%:DRAWX%,Y%:C=C+.125:GOTO20
D%=HIMEM — присваивает D% очень большое значение (HIMEM — верхняя граница памяти), чтобы принудительно выйти из цикла FOR D%.
NEXT D% — закрывает цикл D% (значение уже за пределами диапазона).
X%=V%:Y%=W% — обновляет текущую позицию на найденную свободную точку.
DRAW X%,Y% — рисует линию от предыдущей позиции к новой.
C=C+.125 — сдвигает счётчик направления.
GOTO 20 — возвращается к началу цикла D%, начиная новый виток рисования с обновлённой позицией и новым C.
Алгоритм в целом
Программа обходит экран по сетке 8×8 пикселей (строка за строкой).
В каждой точке пробует одно направление (определяемое счётчиком C).
Если целевая точка свободна — рисует туда линию, увеличивает C на 0.125 и продолжает рисование уже из новой позиции.
Если целевая точка занята — переходит к следующей точке сетки.
Счётчик C медленно вращает предпочтительное направление: при использовании усечения к нулю (как в BBC BASIC) получается цикл Вправо×1 → Вниз×8 → Влево×8 → Вверх×16 → Вправо×8 → .... Направление «Вверх» получает 16 шагов вместо 8 из-за асимметрии усечения отрицательных и положительных чисел к нулю.
Результат — прямоугольные спирали. Первая спираль начинается из (0,0), идёт вправо 1 шаг, потом вниз 8 шагов (за нижний край экрана), влево 8 шагов (за левый край), вверх 16 шагов (возвращаясь на экран), и так далее. Когда спираль упирается в нарисованные пиксели, программа переходит к следующей точке сетки и начинает новую спираль.
С учетом измененной программы можно разобраться в принципе работы.
Комментарии
Отправить комментарий