Line(x1,y1,x2,y2)

[Sinus]

Это правда что в Spectrum Expert (1, 2) была самая быстрая процедура рисования линии?

Если у кого-нибудь есть быстрее, то поделитесь кодом плиз.
(естественно, что установка точки включается в рисование линии)

[drbars]

Это правда что в Spectrum Expert (1, 2) была самая быстрая процедура рисования линии?

Если у кого-нибудь есть быстрее, то поделитесь кодом плиз.
(естественно, что установка точки включается в рисование линии)

Самая быстрая процедура линии написана Alex Raider'ом. Исходники лежат в архиве ZX Open Source http://opensourcezx.untergrund.net/e_misc-alex_raider_misc_src.html

[Sinus]

Кстати вот, линии Alex Raider'a и которая в Spectrum Expert'e по скорости и алгоритму работа почти одинаковые (около 9 линий во фрейм), однако та которая в Expert-e меньше размером.

[elfh]

ээээ! ты что, в экспертовской генерится огромная процедура отрисовки! а у рэйдера нет. правда, у него чуть медленнее, самую малость.

[Sinus]

ну, учитывая что я час назад сделал две тестовые проги и посчитал их размер (размер самих процедур отрисовки и генерации табличек + размер данных которые эти генерилки генерят) + сделал приблизительный замер скорости (по бордюру), то я уверен в том что говорю.

могу отправить SCL файл с этим всем добром

[psndcj]

ELPH - ну не такая уж и огромная...

[himik]

Кстати вот, линии Alex Raider'a и которая в Spectrum Expert'e по скорости и алгоритму работа почти одинаковые (около 9 линий во фрейм), однако та которая в Expert-e меньше размером.

вопрос по теме, каких линий?

У нас КИМ написал процедуру, которая, если мне память не изменяет, рисовала 7,5 диагоналей спектрума во фрейм...

[Vitamin]

Нашел процедуру авторства Unwinder. Юзаю сам. Весьма быстро и хорошо. Требует 4кб памяти под таблицу и вызов MAK_PLO перед рисованием (заполнение таблицы)



;-----------------------------------------
LINE_R LD (STACK+1),SP ;ПРОЦЕДУРА РИСОВАНИЯ ЛИНИИ
DI
LD A,L ;В HL И DE НАХОДЯТСЯ КООРДИНАТЫ ТОЧЕК
CP E
JR NC,NO_EXCH
EX DE,HL
LD A,L
NO_EXCH: SUB E
LD C,A
LD A,H
SUB D
JR C,DOWN_UP
UP_DOWN: LD B,A ;РИСУЕМ ЛИНИЮ СВЕРХУ ВНИЗ
LD H,58 ;LIN_ARR/512+2
LD L,D
JP MISS
;-----------------------------------------
DOWN_UP: NEG ;РИСУЕМ ЛИНИЮ СНИЗУ ВВЕРХ
LD B,A
LD H,59 ;LIN_ARR/512+3
LD A,191
SUB D
LD L,A
MISS: ADD HL,HL
LD SP,HL
LD H,'LIN_ARR
LD L,D
LD A,(HL)
INC H
LD D,(HL)
INC H
LD L,E
ADD A,(HL)
LD E,A
INC H
LD L,(HL)
EX DE,HL
LD A,B
CP C
JR NC,VERTIC
HORIZON: DEFB 221 ;ГОРИЗОНТАЛЬНАЯ ЛИНИЯ (DX>DY)
LD L,A
DEFB 221
LD H,C
LD B,C
LD C,E
LD A,B
SRL A
JR Z,END_LIN
EX AF,AF'
HORIZ0: LD A,(HL)
OR C
LD (HL),A
EX AF,AF'
DEFB 221
SUB L
JR NC,HORIZ2
DEFB 221
ADD A,H
POP DE
ADD HL,DE
HORIZ2: EX AF,AF'
RRC C
JR NC,HORIZ1
INC L
HORIZ1: DJNZ HORIZ0
END_LIN: LD A,(HL)
OR C
LD (HL),A
STACK: LD SP,0
EI
RET
;-----------------------------------------
VERTIC: DEFB 221 ;ВЕРТИКАЛЬНАЯ ЛИНИЯ (DY>DX)
LD H,A
DEFB 221
LD L,C
LD C,E
SRL A
JR Z,END_LIN
EX AF,AF'
VERT0: LD A,(HL)
OR C
LD (HL),A
EX AF,AF'
DEFB 221
SUB L
JR NC,VERT1
DEFB 221
ADD A,H
RRC C
JR NC,VERT1
INC L
VERT1: EX AF,AF'
POP DE
ADD HL,DE
DJNZ VERT0
JP END_LIN
;-----------------------------------------
DEFB " * MEGA FAST LINE V1.0 BY UNWINDER'95
;-----------------------------------------
NEXT_DE: INC D
LD A,D
AND 7
RET NZ
LD A,E
ADD A,32
LD E,A
RET C
LD A,D
SUB 8
LD D,A
RET
;-----------------------------------------
MAK_PLO: LD HL,LIN_ARR
LD DE,16384+32768
LD B,192
MAK_PL0: LD (HL),E
INC H
LD (HL),D
DEC H
INC L
CALL NEXT_DE
DJNZ MAK_PL0
LD HL,LIN_ARR+1023
LD A,1
MAK_PL1: LD (HL),A
RLCA
DEC L
DJNZ MAK_PL1
DEC H
LD A,31
MAK_PL2: LD B,8
MAK_PL3: LD (HL),A
DEC L
DJNZ MAK_PL3
DEC A
JP P,MAK_PL2
MAK_LIN: LD IX,LIN_ARR+1024
LD HL,16384+32768
LD B,191
MAK_LI0: LD E,L
LD D,H
EX DE,HL
CALL NEXT_DE
EX DE,HL
AND A
SBC HL,DE
LD (IX),L
INC IX
LD (IX),H
INC IX
ADD HL,DE
DJNZ MAK_LI0
LD IX,LIN_ARR+1024+512
LD HL,22528-31+32768
LD B,191
MAK_LI1: LD E,L
LD D,H
CALL PREV_HL
AND A
SBC HL,DE
LD (IX),L
INC IX
LD (IX),H
INC IX
ADD HL,DE
DJNZ MAK_LI1
RET
;-----------------------------------------
PREV_HL: DEC H
LD A,H
AND 7
CP 7
RET NZ
LD A,L
SUB 32
LD L,A
RET C
LD A,H
ADD A,8
LD H,A
RET
;-----------------------------------------
LIN_ARR EQU 32768-4096

[Sinus]

himik, рандомных :) в начале фрейма рандомайзер инитится одинаковым числом, чтоб линии не прыгали.

Vitamin, сенькс, вставлю в тестилку и посмотрю по скорости.

[himik]

himik, рандомных :) в начале фрейма рандомайзер инитится одинаковым числом, чтоб линии не прыгали.

дык это на мой взгляд не корректный тест... В диагоналях то точнее будет, ведь она:
1. самая длинная линия
2. самая сложная в рисовании

Добавлено через 3 минуты

Нашел процедуру авторства Unwinder. Юзаю сам. Весьма быстро и хорошо. Требует 4кб памяти под таблицу и вызов MAK_PLO перед рисованием (заполнение таблицы)



ой сдается мне, что по нынешним меркам это мега тормозная процедура...
"весьма быстро" относительно чего?

Давайте приводить тесты в у.е. :) т.е. в диагоналях. Сколько диагоналей за фрейм успевает нарисовать.
Также можно приводить пример вертикали, горизонтали и т.п.

[Vitamin]

ой сдается мне, что по нынешним меркам это мега тормозная процедура...
На такие мысли навел год в строке копирайта?

Я вот жду результатов тестирования тов. Sinus

[GriV]

дык это на мой взгляд не корректный тест... В диагоналях то точнее будет, ведь она:
1. самая длинная линия
2. самая сложная в рисовании

Не очень верно

Оффтоп, но может кто забыл какие глюки были в 3dMark'03? Там использовался простой подгон под тест и в результате бенчмарк вырастал за ни за что в 1,5 раза %)

Это я к чему: если в процедуре прорисовки будет отдельная процедура которая рисует диагональные линии то такой способ вызовет эээ не совсем адекватную оценку. Там что Sinus правильно говорит, надо делать рандомный тест. Я ещё более объективно быть может использовать такой тест - в течение скажем секунды рандомные линии, потом в течении секунды вертикали, потом горизонтали, потом диагонали. В конце выводить результаты по всем четырём тестам, в принципе вполне возможно рисовать вертикальные/горизонтальные линии отдельной процедурой (так же как диагонали на 45 градусов и/или на весь экран). Принципиально тест не изменится, а вот результат станет более точным.

[himik]

ну я выше где-то и написал, что давайте проведем тесты по нескольким критериям, вертикаль, горизонталь, диагональ, ну и рандом.
Просто интересно узнать результат.

[GriV]

Додумал сейчас... надо бы ещё проверять качество линии %) мало ли какая ушлебанская процедура попадётся :-D она быть может просто будет делать RET зато будет как быстро работать!!! :-)

[himik]

хотя может быть и логичнее было-бы взять для основы теста некую готовую таблицу координат, в которой уже прорисованы несколько готовых линий, используя все направления и длины. Вот тогда и можно просто вычеслить, какая процедура рисования обрабатывает это быстрее, т.е. занимает меньше времени на вывод полной картинки из координат.
ИМХО логичнее, и рэндомность исключаем.

[GriV]

Вот ещё что подумал, там ведь дробночисленная арифметика используется - я имею в виду приращения по X и по Y для прорисовки линий. В таболичном методе, которыми очевидно пользуются быстрые процедуры очевидно это арифметика присутствует, хоть и в неявном виде. И в зависимости от того как работает счётчик переполнения будет меняться алгоритм увеличения координаты по X и по Y - это может быть округление в сторону меньшего целого, в сторону большего целого и классическое округление (от 0,5). В зависимости от этого форма линии в целом может меняться!!!
Потому имхо если уж делать тест, то самой точной должна быть признана линия, которая использует последний критерий переполнения (классическое округление). И ещё, встречались некоторые процедуры, которые в целях увеличения быстродействия рисовали линии с пустыми местами (т.е. линия имела разрыв, как пунктир).

[himik]

ну, я думаю тестировать необходимо полноценные процедуры, которые рисуют сплошные линии :)

[psndcj]

еще корректнее наверно будет считать не сколько линий за фрейм - а рисовать скажем с сотню линий и считать количество затраченных фреймов...

[Lethargeek]

хотя может быть и логичнее было-бы взять для основы теста некую готовую таблицу координат, в которой уже прорисованы несколько готовых линий, используя все направления и длины. Вот тогда и можно просто вычеслить, какая процедура рисования обрабатывает это быстрее, т.е. занимает меньше времени на вывод полной картинки из координат.
ИМХО логичнее, и рэндомность исключаем.
Просто надо "среднее количество тактов на пиксель в основном цикле" проинтегрировать по всем возможным углам :v2_finge:

[GriV]

ну есть стандартные критерии оценки производительности графической подсистемы %) например в килопикселях или в мегалиниях :-) шутко :-) количество линий - вот главная оценка.

Оценивать естественно надо не за фрейм а за больший промежуток времени
кроме того, я уже выше написал что на самом деле две линии нарисованные разными процедурами могут весьма отличаться, потому обязательно надо проверять качество.

[Lethargeek]

имхо если уж делать тест, то самой точной должна быть признана линия, которая использует последний критерий переполнения (классическое округление).
Достаточно поменять начальное приращение, проверки в цикле все равно выгоднее делать по переполнению.


количество линий - вот главная оценка.
ПИКСЕЛЕЙ!! :mad: Что такое "количество линий"? Что такое "линия"?

Хотя маньяки могут начать подсчитывать прямо сейчас: на спектрумовском экране возможны всего-то (256x192)*(256x192)=2415919104 различных комбинаций координат концов отрезка... выбрали критерий округления - и вперед, с песней! :v2_laugh: Особо продвинутые могут добавить предварительные проверки для отбрасывания симметричных и сдвинутых отрезков. :v2_lol:

[Vitamin]

(256x192)*(256x192)=2415919104
В два раза больше. Ибо от перемены координат отрезка различаются такты на рисование линии (проверка-перестановка требует тактов)

[Lethargeek]

В два раза больше. Ибо от перемены координат отрезка различаются такты на рисование линии (проверка-перестановка требует тактов)
Не "в два раза больше", а именно столько, сколько я написал, как раз с учетом проверки-перестановки (а то было бы в два раза меньше).

[Vitamin]

"в два раза больше", а именно столько, сколько я написал, как раз с учетом проверки-перестановки (а то было бы в два раза меньше).
А, точно. Каждый конец линии же по всему экрану проходит. Ну все равно дофига. Даже если под эмулем под супертурбой мерять много времени уйдет

[Lethargeek]

Ну все равно дофига. Даже если под эмулем под супертурбой мерять много времени уйдет
Дык я предлагал исключительно для маньяков. ;)
Хотя, если "эмуль" ничего, кроме Z80, не делает...

[moroz1999]

сферические кони в вакууме.

[Lethargeek]

сферические кони в вакууме.
Что именно?

[ZEK]

Что именно?
Единица измерения бенчмарка - типа производительность 250 вакумных лошадок :D

[Lethargeek]

Единица измерения бенчмарка - типа производительность 250 вакумных лошадок
А что не так? Единица измерения - количество тактов Z80 на выполнение теста. Причем выборка для теста даже не просто "репрезентативная", а вообще стопроцентная. :p

[Lethargeek]

В принципе количество отрезков даже в полном тесте можно сократить до разумных пределов - сдвинуть один из концов в ноль и просчитать в каждом квадранте (итого 256x192x4), причем весовой коэффициент - площадь прямоугольника с диагональю от конца отрезка до дальнего угла квадранта. Для полной точности еще внести коррективы на пересечение четного либо нечетного количества знакомест по горизонтали (x2) и вертикали (x2) с возможным пересечением одного или обоих сегментов (x1...x3), с соотв-ей разбивкой весов. Итого понадобится менее 2,4 млн отрезков. ;)

[moroz1999]

про сферических коней я упомянул потому, что на 99% уверен, что после двух страниц обсуждений методик тестирования до самого тестирования дело так и не дойдет :)

[research]

угу.
Дарк настрочил процедуру (которая в эксперте), но у него небыло времени ее вылизать. Там можно было еще тактов отбить чутка.
Тестить бесполезно т.к. линии до 45 градусов и после 45 градусов рисуются разными процедурками и жрут разное число тактов. Надо брать ту, которая лучше и проще в прогу страивается и ставить. А так если по неделе рассуждать, никакого кода так и не будет :)

[Lethargeek]

Тестить бесполезно т.к. линии до 45 градусов и после 45 градусов рисуются разными процедурками и жрут разное число тактов.
Почему "бесполезно"? ;) Ежу понятно, что "разные процедурки" (вообще-то это разные ветки одной процедуры), ну дык интересует средневзвешенная эффективность в общем случае. Которая однозначно определяется тестом.

[research]

давайте еще на 4 страницы минимум устроим выяснение критериев тестирования объективного теста, а так же теста при условиях приближенных к реальным ;-)

[ALKO]

Поделитесь,пожалуйста, асмовской процедурой рисования линии.

---------- Post added at 16:14 ---------- Previous post was at 14:46 ----------

Всё, спасибо за внимание.
Нашёл тут http://zxpress.ru/article.php?id=7388

---------- Post added at 16:16 ---------- Previous post was at 16:14 ----------

Ещё интересен момент, как векторную анимацию обновлять без мерцания ?

---------- Post added at 16:28 ---------- Previous post was at 16:16 ----------

Хммм.... та процедура по скорости мало чем отличается от бэйсикового DRAW

[newart]

Ещё интересен момент, как векторную анимацию обновлять без мерцания ?
Используй буфер. Что замедлит работу еще больше... на 128-к с этим не так печально.

[ALKO]

Используй буфер. Что замедлит работу еще больше...
Я так полагаю нужно изменить процедуру GET_ADR
LD A,#BF - это типа старший разряд указателя на адрес ?
Что конкретно изменить, что б отрисовывало например по адресу 40000 ?

[newart]

Что конкретно изменить, что б отрисовывало например по адресу 40000 ?
Адрес делай кратным 256.

[Andrew771]

Нашел процедуру авторства Unwinder. Юзаю сам. Весьма быстро и хорошо. Требует 4кб памяти под таблицу и вызов MAK_PLO перед рисованием (заполнение таблицы)
Чё-та она у меня не работает, почему-то таблицу заполняет на 1917 байт только (число-то ого-го какое, Великий Октябрь!) вместо 4к. Что я не так сделал? (см.файл)

[denpopov]

Что я не так сделал? (см.файл)
Зачем тебе такие адреса?
LD DE,16384+32768

[Andrew771]

Автора Unwinderа надо трясти, не ошибся ли он, таблица начинается с адреса 32768-4096. Или Vitaminа. А то теперь самому ковырять весь код - проще заново написать.

Блин, ну почему сразу не дают работоспособные процедуры без танцев с бубном. То же самое - часто невозможно пользоваться процедурами из прессы, т.к. там или ошибки, или многие сокращения.

[denpopov]

А какие симптомы вообще? Сбрасывается прога, или рисует неверно?

У меня есть две другие процедуры, но явно не быстрые, одна Zombusters Crew, вторая - BeerManZ (использовалась в Bizarre Constructions). Если нужны, поищу и выложу.

[Andrew771]

А какие симптомы вообще? Сбрасывается прога, или рисует неверно?
Сначала заполняется таблица, но не на 4к, а на 1917 байт. Потом ничего на экране не появляется, выход в Бейсик корректный.


У меня есть две другие процедуры, но явно не быстрые, одна Zombusters Crew, вторая - BeerManZ (использовалась в Bizarre Constructions). Если нужны, поищу и выложу.
я вообще бы хотел процедуру рисования линии с минимальным объемом используемой памяти, но не очень медленную. Даже 4к расточительно. Для игр планирую.

---------- Post added at 09:32 ---------- Previous post was at 09:31 ----------

А Брезенхема кто-нить реализовал без таблиц?

[denpopov]

Лови, 146 байт, только точка рисуется как атрибутики:)




device zxspectrum128
ORG #6000
begin
; * parameters :
; - DE : coordinates of the 1st point
; - HL : coordinates of the 2nd point
out(#fe),a
ld de,0
ld hl,#1f17
call Line

;убрать остатки кода до Line
ld a,b,b,c,c,a
push bc
exx
pop de
ld l,d,h,0
add hl,hl
add hl,hl
add hl,hl
add hl,hl
add hl,hl
ld d,#58
add hl,de
ld(hl),16;plot with color
exx
;ld a,16,(#5800+#17*#20+#1f),a
stu: jr stu

Line:
ld A,D
sub H
jr NC,dxpositive ;delta_x > 0
DXNegative:
neg
dxpositive:
ld B,A ;B <- |delta_x|
ld A,E
sub L
jr NC,dypositive ;delta_y > 0
DYNegative:
neg
dypositive:
sub B ;|delta_y|
push AF
jr C,DeltaX ;|delta_x| > |delta_y|
DeltaY:
ld A,H ;if |delta_x| < |delta_y| then
ld H,L ;then values x and y are swapped
ld L,A ;so the loop will always be performed on the
ld A,D ;x value. A flag must be set to
ld D,E ;remind that data must be drawn (y,x)
ld E,A ;instead of (x,y)
DeltaX:
ld A,D
sub H
jr NC,TestDY ;x1 < x2
TestDX:
ex DE,HL
TestDY:
ld A,E
sub L
ld A,$01
jr NC,StoreA
neg ;y1 > y2 : in case2 the 'y' variable
StoreA:
ld (Way+1),A;ld (Way),A
InitLine:
ld B,H
ld C,L
ld A,E
sub L
jr NC,EndInit
ld A,L
ld L,E
ld E,A
EndInit:
ld A,E
sub L
rla
ld L,A ;value to add in case1 (d < 0)
add A,H
sub D
ld E,A ;'d' variable is initialised
add A,H
sub D
ld H,A ;value to add in case2 (d >= 0)
Loop:
ld A,B
sub D
jr NC,EndLine ;the line is completely drawn.
pop AF
bit 7,A
push AF

push AF
push BC
jr Z,DrawPoint
ld A,B
ld B,C
ld C,A
DrawPoint:
; CALL PointOn
push bc
exx
pop de
ld l,d,h,0
add hl,hl
add hl,hl
add hl,hl
add hl,hl
add hl,hl
ld d,#58
add hl,de
ld(hl),8;plot with color
exx

pop BC
pop AF
TestD:
bit 7,E
jr NZ,Case1
Case2: ;d >= 0
ld A,E
add A,H
ld E,A
Way:
ld A,0;ld A,(Way)
add A,C
ld C,A
jr EndLoop
Case1: ;d < 0
ld A,E
add A,L
ld E,A
EndLoop:
inc B
jr Loop
EndLine:
pop AF ;MUST NOT BE REMOVED
ret
;PointOn:
; ret

end
display /d,end-begin
savesna "brez.sna",begin



---------- Post added at 10:49 ---------- Previous post was at 10:45 ----------

И по vitamin.txt:
убери из MAK_PLO 16384+32768 +32768, потому что рисование происходит в страничку

[Andrew771]

Спасиб огромное, denpopov, и твоя, и Витаминная заработали! Пошел думать дальше над новым супер-пупер проектом :)

---------- Post added at 10:42 ---------- Previous post was at 10:01 ----------

Йех, блин, запустил процедурку для 255 линий, рисовала пару-тройку секунд. Векторную графику в игре не замутишь. :(

[denpopov]

Векторную графику в игре не замутишь.

смотря то, что ты хочешь. Вот еще от BeermanZ, слегка модифицированная:


PIX_TAB EQU #7C00
device zxspectrum128

ORG #6000
begin
CALL INIT
;HL=XY,BC=YX
ld BC,#bfff;bf
MAIN EI:HALT
LD A,0:OUT (#FE),A
push bc
LD HL,#0000
CALL DRAW
LD A,2:OUT (#FE),A
pop bc:dec c:jr z, wkey
jp MAIN
wkey
LD A,#7F:IN A,(#FE)
RRA:JR C,wkey;MAIN
EXX:LD HL,#2758:EXX
RET

;-------------------------------
DRAW LD (TEK_POI+1),HL,E,H
LD H,high PIX_TAB,A,(HL);[
INC H:LD D,(HL):INC H
LD L,E:OR (HL):LD E,A
INC H:LD A,(DE):OR (HL)
LD (DE),A

LD HL,(TEK_POI+1),DE,#FFFF
LD A,H:SUB C:JR NC,$+6
NEG:LD E,1,C,A
LD A,L:SUB B:JR NC,$+6
NEG:LD D,1,B,A
LD A,C:CP B:JR NC,L24C4
LD L,C:PUSH DE:XOR A
LD E,A:JR L24CB
L24C4 OR C:RET Z:LD L,B,B,C
PUSH DE:LD D,0
L24CB LD H,B,A,B
RRA
L24CE ADD A,L:JR C,L24D4
CP H:JR C,L24DB
L24D4 SUB H:LD C,A
EXX:POP BC:PUSH BC
JR TEK_POI
L24DB LD C,A:PUSH DE
EXX:POP BC
TEK_POI LD HL,0,A,C
ADD A,H
LD H,A,A,B
ADD A,L:LD L,A
LD (TEK_POI+1),HL

LD E,H,H,high PIX_TAB;[
LD A,(HL):INC H
LD D,(HL):INC H
LD L,E:OR (HL)
LD E,A:INC H
LD A,(DE):OR (HL):LD (DE),A
EXX:LD A,C:DJNZ L24CE
POP DE
RETURN RET
;ANY RET

INIT LD DE,#4000,L,E,BC,#8000;#C000
ILP1 LD H,high PIX_TAB,(HL),E:INC H;[
LD (HL),D:INC H
LD (HL),C:INC H
LD (HL),B
CALL DOWN_DE;,DOWN_DE
RRC B;,B
LD A,C:ADC A,0:LD C,A
INC L:JR NZ,ILP1
; LD HL,PIX_TAB+96;256+96
;ILP2 LD (HL),0:INC L:JR NZ,ILP2
RET
;-------------------------------
DOWN_DE INC D:LD A,D:AND 7:RET NZ
LD A,E:ADD A,32:LD E,A:RET C
LD A,D:SUB 8:LD D,A:RET
end
display /d,end-begin
savesna "DRAW02.sna",begin

[Andrew771]

смотря то, что ты хочешь
Допустим, на экране одновременно 50 непрозрачных объемных тел из граней (без закрашивания), расположенные на разных расстояниях, которые могут перекрывать друг друга :)

[denpopov]

на экране одновременно 50 непрозрачных объемных тел из граней (без закрашивания), расположенные на разных расстояниях, которые могут перекрывать друг друга

Если это игра, то затея очень крутая. либо готовые спрайты хранить и выводить, либо я не знаю тогда..

[Andrew771]

Если это игра, то затея очень крутая.
Вот типа того, игра Sky Ranger: http://www.worldofspectrum.org/infoseekid.cgi?id=0004557
Там много параллелепипедов из линий (проволочная графика), и всё работает приемлемо по скорости.

[denpopov]

Там много параллелепипедов из линий (проволочная графика)

Вертикальные линии можно по-другому строить.

[Andrew771]

Вертикальные линии можно по-другому строить.
ну а диагоналек там тоже много.

---------- Post added at 13:16 ---------- Previous post was at 13:02 ----------


либо готовые спрайты хранить
кстати, можно сделать спрайты линий, диагонали на весь экран, ограниченный набор углов, может достаточно. А длину в процессе обрезать. :)

---------- Post added at 13:27 ---------- Previous post was at 13:16 ----------

А еще придумал алгоритм для линии, можь это уже изобретенный велосипед.
Линия же на экране всегда состоит из коротких прямых горизонтальных или вертикальных линий одинаковой длины. Так вот:
- находим длину одной такой маленькой линии (d=y2-y1/x2-x1);
- находим, из горизонтальных или вертикальных будет состоять наша итоговая линия (что больше, x2-x1 или y2-y1);
- затем наращиваем по одной координате на 1 пиксель, а по другой выводим эту маленькую линию. Повторять этот пункт, пока не дойдем до конечной точки.

[Lethargeek]

Линия же на экране всегда состоит из коротких прямых горизонтальных или вертикальных линий одинаковой длины
одинаковой в вещественном выражении, а вот в целых числах на экране - неодинаковой

[Andrew771]

одинаковой в вещественном выражении, а вот в целых числах на экране - неодинаковой
Можно тогда какую-нить поправочную единицу ввести на некоторое количество отрезочков, один из них будет покороче или длиннее на 1 пиксель. Она будет определяться при первом и единственном делении для нахождения длины отрезка.

[NovaStorm]

поправочную единицу ввести
Ну Брезенхэм и получается =)

[Andrew771]

Ну Брезенхэм и получается =)
почти. Там на каждой точке проверяем, нужно ли прибавить 1, а тут мы будем это делать только после отрезка.

[Destr]

А еще придумал алгоритм для линии, можь это уже изобретенный велосипед...
Лет 10 назад пробовал такое делать (проект "Линейка").
Получилось что для того чтоб рисовалось быстрей чем другие алгоритмы - нужно прорву памяти под таблички со всеми значениями, иначе медленно.
Ну а уж если есть свободная память, то лучше юзать процедуру из Spectrum Expert.

[tiboh]

На форуме выкладывали ещё одну быструю и относительно короткую процедуру рисования линии, без таблиц. Из недостатков: не умеет рисовать по XOR.

[Lethargeek]

почти. Там на каждой точке проверяем, нужно ли прибавить 1, а тут мы будем это делать только после отрезка.
но отрезок тоже циклом с проверкой рисовать надо (и получается в итоге всё тоже самое))
либо прорву памяти под рисование отрезков любой длины и с любой начальной позиции

что реально сэкономить для брезенхэма - выкинуть лишнюю проверку после ступеньки

[Andrew771]

но отрезок тоже циклом с проверкой рисовать надо (и получается в итоге всё тоже самое))
отрезок либо вертикальный, либо горизонтальный, проверка только счетчика цикла. А координату каждой точки заново высчитывать не надо, только прибавлять/отнимать адрес на экране для столбца или бит для строки. В общем, надо пробовать в реале. Но Destr говорит, что уже попробовал :)

[Lethargeek]

отрезок либо вертикальный, либо горизонтальный, проверка только счетчика цикла
говорю же, то же самое получается - вместо проверки на ступеньку проверка счётчика :p

[Andrew771]

вместо проверки на ступеньку проверка счётчика
это равнозначно по быстродействию?

[Lethargeek]

да почти, add+jump против djnz, но это еще без учёта перезагрузок

[shurik-ua]

Небольшое чтиво в тему - описано как избавиться от ветвления в алгоритме Брезенхейма - ну и просто интересная книжка.

[Titus]

Небольшое чтиво в тему - описано как избавиться от ветвления в алгоритме Брезенхейма

Для Спектрума это в чистом виде не очень подходит ввиду большой разрядности констант для сохранения формы линии идентичной стандартной.
А в упрощенном виде это и так (я надеюсь) все, кому не лень пробовали (во всяком случае я), хотя излом линии получался нестандартным, с некоторыми погрешностями.

[shurik-ua]

тут в начале темы спорили как же лучше тестировать скорость рисования линии - как вариант можно сделать как здесь:

http://www.youtube.com

Даже исходники есть :

[Destr]

Други, подмогните!
Не могу сообразить как рассчитать шаг линии на один пиксел за раз.
Т.е. не накапливая err.
Делаю так (для 0 октанта):
dx = x - xcnt
dy = y - ycnt
err = dx / dy - dy
x = x - 1
If err < 0
y = y - 1
EndIf

Но работает как-то криво:

[shurik-ua]

function line(x0, x1, y0, y1)
int deltax := abs(x1 - x0)
int deltay := abs(y1 - y0)
real error := 0
real deltaerr := deltay / deltax
int y := y0
for x from x0 to x1
plot(x,y)
error := error + deltaerr
if error >= 0.5
y := y - 1
error := error - 1.0

[Destr]

function line(x0, x1, y0, y1)
Это из википедии.
Пробовал.
Тоже лажа получается (ведь error сохрнанять не получится).

[shurik-ua]

вот по пунктам как я понимаю:
1. вычисляем dХ и dY
2. определяем которая из них (дельт) больше - например dy
3. переменная err - на входе цикла равна 0
4. делаем цикл на столько итераций сколько в бОльшей дельте for n=0 to (y-1)
5. ставим точку и увеличиваем ту координату, дельта которой больше - y=y+1
6. err = err + dx - прибавляем меньшую дельту к переменной
7. if err > dy then err = err-dy:x=x+1: end if;

[Destr]

вот по пунктам как я понимаю:
Да не пойдёт.
В общем дело так: Есть спрайт (координаты x1,y1 в пикселах).
Есть точка назначения (x2, y2 тоже в пикселах).
Нужна подпрограмма которая сдвигает координаты спрайта (x1,y1) на один шаг (пиксель) в желаемом направлении (x2,y2).
Хранить err не вариант (ведь целевые координаты могут менятся, а спрайт всё равно должен двигатся к точке назначения).
Процедура каждый раз должна вычислять что и как прибавлять.
Т.е. сохранять err никак не полезно (ибо если коорд. изменились то прошлое значение неактуально).
Конечно можно каждый раз рассчитывать всю линию полностью, но сдвигать координаты только один раз, но мне это кажется жутким ламерством и заставить себя так сделать не могу.

[shurik-ua]

Т.е. сохранять err никак не полезно (ибо если коорд. изменились то прошлое значение неактуально).
всё то же самое - но вместо цикла ты определяешь какая координата точно увеличится исходя из вычисления бОльшей дельты - тогда переменную err заводить не надо.

я так понял это в игре самонаведение какое-то ?

[Destr]

всё то же самое - но вместо цикла ты определяешь какая координата точно увеличится исходя из вычисления бОльшей дельты - тогда переменную err заводить не надо.
Вот и не могу сообразить как её вычислять.

я так понял это в игре самонаведение какое-то ?
Да, это для кота (метла ведь должна его гонять)

[shurik-ua]

Да, это для кота (метла ведь должна его гонять)
а что за игра ?

[Destr]

а что за игра ?
http://zx-pk.ru/showthread.php?t=25304

[shurik-ua]

тогда алгоритм нужно изменить - всё как я писал только алгоритм вернёт сколько и каких координат нужно увеличить - то есть на пункте 7 делаем выход из цикла и имеем n - это кол-во приращений координаты с большей дельтой, а координата с меньшей дельтой увеличится на 1.

---------- Post added at 20:28 ---------- Previous post was at 20:22 ----------

упд
для прямых линий будет работать криво - нужно выделять заранее кол-во итераций алгоритма - например 3-4 - и после работы координаты будут изменены по направлению к цели

[Destr]

для прямых линий будет работать криво - нужно выделять заранее кол-во итераций алгоритма - например 3-4 - и после работы координаты будут изменены по направлению к цели
Можешь в псевдо-коде накидать?

[shurik-ua]

а координаты изменяются каждый фрейм ?

[Destr]

а координаты изменяются каждый фрейм ?
Необязательно.
Метла может быть занята подметанием (т.е. другая процедура изменения), может стремится к коту, может ждать пока он приземлится (когда шуганула и кот полетел), может прервать преследование (если кота схватила собака). В общем условий дофига, но когда преследует - то каждый фрейм меняется (пока что так думаю, возможно будет слишком быстро, придётся замедлять, или слишком медленно - придётся менять два раза например.)

[shurik-ua]

примерно так:


var1 = 4 - некая глобальная переменная которая устанавливается 1 раз в начале игры для отладки - в релизе заменить константой
var2 = 0 - тут просто глобальная переменная
call user_input_and_get_cat_coords - опрашиваем кнопки и меняем координаты кота - к примеру каждый фрейм
call metla_AI
ret

metla_AI:
var2=var2+1
if var2 <> var1 then exit
var2=0
dx=x0-x1
dy=y0-y1
err=0
x=0,y=0
;дальше опишу для случая если dy больше dx - если меньше то такая же ветка но поменять местами x и y
for n=1 to var1 ;выделяем 4 итерации для алгоритма брезенхейма
inc(y)
err = err+dx
if err >= dy then
err=err-dy
inc(x)
end if
next n
result x0+x,y0+y


то есть мы даём алгоритму столько итераций - сколько фреймов метла бездействовала.

[Destr]

то есть мы даём алгоритму столько итераций - сколько фреймов метла бездействовала.
Если var1 = 4 (или 3, или ещё как) то в общем-то работает.
Но если var1=1 (т.е нужно сделать один шаг) то лажает.
Надо придумать что-то другое, брезенхем тут видимо не поможет.
Как-то вычислить шаг по у и по x для одного передвижения.
Собственно для случая dx>dy шаг по х равен 1, а у надо как то узнать уменьшать или нет. Не могу только понять как именно, блин, тяжкое это дело математика.

[shurik-ua]

для случая dx>dy


for n=1 to var1 ;выделяем 4 итерации для алгоритма брезенхейма
inc(x)
err = err+dy
if err >= dx then
err=err-dx
inc(y)
end if
next n
result x0+x,y0+y

но это только для одной четрерти )) - для остальных четвертей нужно одну из координат увеличивать а другую уменьшать - ну и в пределах каждой четверти у алгоритма две ветки.


Но если var1=1 (т.е нужно сделать один шаг) то лажает.
var1 и не нужно делать 1 - собственно ради этого всё и затевалось )

[Destr]

но это только для одной четрерти )) - для остальных четвертей нужно одну из координат увеличивать а другую уменьшать - ну и в пределах каждой четверти у алгоритма две ветки.
Да знаю я, писал линию.

var1 и не нужно делать 1 - собственно ради этого всё и затевалось )
Нужно чтоб шаг можно было делать 1 пиксель.
Т.е не 4 итерации а 1.
Но для брезенхема нужно сохранять err иначе лажа.
Значит не подходит.
Как ещё можно высчитать этот чёртов шаг?

[shurik-ua]

Как ещё можно высчитать этот чёртов шаг?
никак - потому что за 1 приращение Y ты нигде не сохранишь 0.5 приращения к Х.
объясни лучше зачем стремиться чтоб var1 был 1 - он при значениях 2-8 будет проявлять себя практически одинаково. при больших значениях 20-50 уже будет видна ступенчатость в движении.

[Destr]

объясни лучше зачем стремиться чтоб var1 был 1
Потому что на основе этой процедуры (стремление к целевой точке) будет не только метла двигатся (которая ещё туда-сюда сойдёт если по 2-3 пиксела шаг), но и ещё куча других действий (не столь явных, но там уже надо шаг - по пикселу. Или один пиксел по x или один по y или и то и другое - т.е. диагональ)
Надо что-то придумать, согласен даже на всякие деления-умножения, но процедура возможна (если бы знал как - то не спрашивал бы, поэтому и надеюсь что кто-нибудь подкованый в математике подскажет что надо на что поделить чтоб получить этот самый k и как его интерпретировать чтоб сдвинуть в нужную сторону)

[Destr]

Ну и еще придется хранить дробную часть в координате.
Дробные части у координат есть.

Если хочется побыстрее то можно составить округленную, скажем до 8, табличку с единичными смещениями. Все зависит от количества тактов свободных, на крайняк можно и по 8 направления двигаться.
Так расскажи как это?
Тактов как всегда мало, но не думаю что тут надо что-то запредельное... Тысчонок 2-3 я думаю хватит за глаза и за уши.

[Destr]

Мог немного ошибиться, проверял на нескольких рандомных значения, полную обвязку поленился ( уже не интересно)
Набросал тестовую прогу (во вложении).
Левым и правым синклер-джойстиком можно погонять точки по экрану.
0 - точка стремится к цели
Пробел - очистить экран от следов (без потери координат).

Вроде как стремится бежать куда надо, но как-то криво.
Или это я лажанулся?
Исходник тоже в архиве, но если лень смотреть то кусок кода который вычисляет приращение:


STEP EQU 4
LD BC,(COOR1),DE,(COOR2):CALL VECTOR
LD H,STEP:CALL MULS ; dY
PUSH HL
LD H,STEP,E,C:CALL MULS ; dX
LD BC,(COOR1)
LD A,B:ADD A,H:LD B,A
POP HL
LD A,C:ADD A,H:LD C,A
LD (COOR1),BC
.....
MULS ; HL=H*E (+-)
LD L,0,D,L,A,H:XOR E:EXA
LD A,H:NEG:JP M,$+4:LD H,A
LD A,E:NEG:JP M,$+4:LD E,A
DUP 8:ADD HL,HL:JR NC,$+3:ADD HL,DE:EDUP
EXA:RET P:EX DE,HL:LD L,H
SBC HL,DE:RET

[jerri]

Destr, у тебя если dx или dy = 0 то улетает не туда

[Destr]

Destr, у тебя если dx или dy = 0 то улетает не туда
Ну дык...
Как это пофиксить?
Или может неправильно табличка генерится (я-то sjasm компилю, а писано изначально на чём-то другом вроде. a80 было расширение).

---------- Post added at 11:28 ---------- Previous post was at 10:13 ----------

Тэкс, процедуру krt17, вроде заставил работать (забыл поначалу учитывать дробную часть).
Премного благодарен!

[Destr]

Там sjasm только, я других не знаю в которых ула встроена. Улетало не туда потому как 128 это не -128 для этого есть старший байт он только для знака добавлен. Можно уменьшить точность до 64, либо учитывать оба байта.
Ну я уже прикрутил как есть.
Вроде работает (во вложении кот и метла, управление курсором)

[shurik-ua]

Ну я уже прикрутил как есть.
фиолетовый бордер - это процедура от krt17 ?

[Destr]

Там всего 470 тактов максимум
Вроде 1500 на пике (вместе с умножениями).

[Reobne]

Кому нибудь тоже показалось, что начиная с поста#66 (http://zx-pk.ru/showpost.php?p=829522&postcount=66) надо-бы перенести в другую тему, например: "ИИ. Расчёт преследования по кратчайшей прямой."?

[Destr]

Кому нибудь тоже показалось
Я размышлял куда запостить, но всё-таки решил сюда. Ведь как не крути - а это именно линия (линия следования) из x1y1 в x2y2.
Мало-ли поможет кому-то.
А для ИИ вообще надо отдельную тему в главном отделе.
Ну рядом с Программирование например завести ИИ на спектруме.
Тогда да, там подраздел как ты сказал (Расчёт преследования по кратчайшей прямой)
Кто-то ещё что-то выложит (в другую тему).
Да и вообще с форума посты на эту тему собрать и рассортировать.
Но это моё ихмо, если надо - пущай переносят куда посчитают нужным.

[tiboh]

Нашёл процедуру рисования линии (в формате ALASM) от KIM/Rain Group Inc/Power of Sound. Создана на основе процедуры Dark/X-Trade.

[Destr]

Нашёл процедуру рисования линии (в формате ALASM) от KIM/Rain Group Inc/Power of Sound. Создана на основе процедуры Dark/X-Trade.
По случаю перепробовал приведённые в ветке линии - эта вроде самая быстрая (тестил #0000-#BFFF, вроде вполне себе средний вариант, и не горизонт и не вертикаль и не 45).

[Shiny]

Нашёл процедуру рисования линии (в формате ALASM) от KIM/Rain Group Inc/Power of Sound. Создана на основе процедуры Dark/X-Trade.

мог бы и перевести в приличный формат

[Lethargeek]

По случаю перепробовал приведённые в ветке линии - эта вроде самая быстрая
и это ты еще в другую ветку (https://zx-pk.ru/threads/11661-o-risovanii-pryamykh.html?p=986444&viewfull=1#post986444) не заглянул ;)


(тестил #0000-#BFFF, вроде вполне себе средний вариант, и не горизонт и не вертикаль и не 45).
~11500 на диагональ, для ~6 кб не особо (хоть и быстрей оригинала spectrum expert)

- - - Добавлено - - -


мог бы и перевести в приличный формат
чтобы собиралось в ужасме, нужно заменить в трёх местах апостроф на HIGH
или это моя версия устарела?

[Destr]

и это ты еще в другую ветку не заглянул
Заглянул, а что толку без исходников?
Потестить не потестишь, а уж юзать тем более (подбирал процедурку пошустрей именно чтоб применить, просто результаты тестирования на всяк случай озвучил).

[Lethargeek]

Потестить не потестишь, а уж юзать тем более
вот как раз как минимум потестить там можно
допилить сырцы пока некогда :(

[Bedazzle]

мог бы и перевести в приличный формат

Кстати, а как наиболее безгеморройно вытаскивать аласмовые сырцы, чтобы к примеру, далее попробовать перетянуть под ужасм?

[Black Cat / Era CG]

Кстати, а как наиболее безгеморройно вытаскивать аласмовые сырцы, чтобы к примеру, далее попробовать перетянуть под ужасм?
Либо на спеке под BestView, либо плагином для TC на PC.

[Shiny]

Кстати, а как наиболее безгеморройно вытаскивать аласмовые сырцы, чтобы к примеру, далее попробовать перетянуть под ужасм?

я впихнул архив, который выложил tiboh в .trd и вытащил Far'ом с плагинами. Как безгеморройно? Не знаю, синтаксис аласм придуман ушибленным программистом. Наверное, ручками.

[Dart Alver]

Кстати, а как наиболее безгеморройно вытаскивать аласмовые сырцы, чтобы к примеру, далее попробовать перетянуть под ужасм?
Я самим аласмом в текст конвертил а потом плагином для MC вытаскивал. А с появлением Xpeccy теперь можно прямо в эмуляторе с образины тырдиска на хост перекидывать.

[NEO SPECTRUMAN]

А с появлением Xpeccy теперь можно прямо в эмуляторе с образины тырдиска на хост перекидывать.
по моему такое вполне умел emuzwin

[Dart Alver]

по моему такое вполне умел emuzwin
Вполне возможно, я не пользовал. Под линем у меня пока Xpeccy рулит. ))

[Destr]

По случаю перепробовал приведённые в ветке линии - эта вроде самая быстрая (тестил #0000-#BFFF, вроде вполне себе средний вариант, и не горизонт и не вертикаль и не 45).
Вот по-прежнему эта как-бы (из доступных) самое TRUE, а вот такую-же но черезстрочную кто-нить пробовал?