## Sunday, 29 May 2016

### Divide and Conquer Line Algorithm for the ZX Spectrum

While attempting to write a game in 256 bytes I needed a routine to draw lines, but Bresenham's line algorithm weighs in at approx ~120 bytes. The only suitable alternative I'm aware of is recursive divide and conquer: divide a line into two smaller lines and call the draw routine with each in turn:

``````/* Draw a line from (ax,ay) to (bx,by) */

int draw ( ax, ay, bx, by )
{
int midx, midy;
midx = ( ax+bx ) / 2;
midy = ( ay+by ) / 2;
if ( midx != ax && midy != ay )
{
draw( midx, midy, ax, ay );
draw( bx, by, midx, midy );
plot( midx, midy );
}
}
``````

This is significantly smaller thank Bresenham's, 32 byte of Z80. However, there are a couple of compromises: it's slower and the lines aren't perfect because the rounding errors accumulate.

``````; draw lines using recursive divide and conquer
; from de = end1 (d = x-axis, e = y-axis)
; to   hl = end2 (h = x-axis, l = y-axis)

DRAW:
call PLOT

push hl

; calculate hl = centre pixel

ld a,l
rra
ld l,a
ld a,h
rra
ld h,a

; if de (end1) = hl (centre) then we're done

or a
sbc hl,de
jr z,EXIT

ex de,hl
call DRAW    ; de = centre, hl = end1
ex (sp),hl
ex de,hl
call DRAW    ; de = end2, hl = centre

ex de,hl
pop de
ret

EXIT:
pop hl
ret

; ---------------------------

; plot d = x-axis, e = y-axis

PLOT:
push hl
ld a,d
and 7
ld b,a
inc b
ld a,e
rra
scf
rra
or a
rra
ld l,a
xor e
and 248
xor e
ld h,a
ld a,l
xor d
and 7
xor d
rrca
rrca
rrca
ld l,a
ld a,1
PLOTBIT:
rrca
djnz PLOTBIT
or (hl)
ld (hl),a
pop hl
ret
``````

Alternatively the `de(end1) = hl(centre)` test can be replaced with a recursion depth count to create an even slower 28 byte routine:

``````; draw lines using recursive divide and conquer
; from de = end1 (d = x-axis, e = y-axis)
; to   hl = end2 (h = x-axis, l = y-axis)

DRAW:
ld c,8

DRAW2:
dec c
jr z,EXIT

push de

; calculate de = centre pixel

ld a,l
rra
ld e,a
ld a,h
rra
ld d,a

call DRAW2   ; de = centre, hl = end1
ex (sp),hl
call DRAW2   ; de = centre, hl = end2

call PLOT
ex de,hl
pop hl
EXIT:
inc c
ret
``````

1. Fantastic work! Thanks for sharing, if I had a ZX Spectrum, I'd definitely try this out. :)

2. Hi John,

Do you know where I can find an implementation of the Bresenham line drawing in Z80? I'm not too bothered about the size of the code, I'm just trying to understand how to do it correctly, :)

3. That PLOT: routine pretty much sums up why I never managed to learn machine code. It's easy to learn what all the instructions do on their own, but when they get put together, they just become a jumble.

You set the last three bits of the X co-ordinate and add one to it, for some reason. And then it gets really weird when you move on to the Y coordinate. I think "rra, scf, rra, or a, rra" might mean something like "divide by 8 then add 64" but when you Xor it with the number you first thought of, then And it with something else, and Xor it with the number you first thought of once again, my brain just turns to mush.

How does anyone follow all that, let alone understand it enough to write it?

1. Ah, I've just worked out that setting the last 3 bits and adding one is probably like rounding the X co-ordinate up to the next multiple of 8. Maybe that's something to do with the X axis having 8 pixels to each screen byte? Am I getting warmer?

Though if you're trying to use as few bytes as possible (to pack as much game as possible into a 16K Spectrum?) a simple CALL to ROM would only be 3 bytes. That's a lot less than all this "Round up and divide by the number you first thought of" stuff.

5. This comment has been removed by the author.

6. You there, this is really good post here. Thanks for taking the time to post such valuable information. antimalware service executable high disk usage win 10

7. This is extremely fascinating substance! I have completely delighted in perusing your focuses and have arrive at the conclusion that you are right about a number of them. https://freegrapi.com/

8. Hi,
Good job & thank you very much for the new information, i learned something new. Very well written. It was sooo good to read and usefull to improve knowledge. Who want to learn this information most helpful. One who wanted to learn this technology IT employees will always suggest you take data science course training bangalore. Because data science course in pune is one of the best that one can do while choosing the course.

9. I Got Job in my dream company with decent 12 Lacks Per Annum salary, I have learned this world most demanding course out there in the current IT Market from the Hkbk group of institutions experts who helped me a lot to achieve my dreams comes true. Really worth trying

10. Thank you for excellent article.Great information for new guy like antimalware service executable

11. Thanks for sharing useful information. I learned something new from your bog. Its very interesting and informative. keep updating. If you are looking for any Big Data related information, please visit our website Big Data training institute in Bangalore.

12. Get Computer Science Assignment Help online visit NeedAssignmentHelp provide the best computer science assignment 100% Trusted & Secure.24/7 Live Chat, On-time Delivery, Low Price. Order Now!

Computer Science Assignment Help

13. Nice post. Thanks for sharing! I want people to know just how good this information is in your article. It’s interesting content and Great work.
appium online training
appium training centres in chennai
best appium training institute in chennnai
apppium course
mobile appium in chennnai
mobile training in chennnai
appium training institute in chennnai

14. An impressive share! I have just forwarded this onto a co-worker who was conducting a little homework on this. And he in fact bought me lunch due to the fact that I stumbled upon it for him... lol. Read more So let me reword this.... Thanks for the meal!! But yeah, thanks for spending time to talk about this topic here on your website.

15. Thanks for all the tips mentioned in this article! it’s always good to read things you have heard before and are implementing, but from a different perspective, always pick up some extra bits of information. Visit@
QuickBooks Support
norton.com/setup

16. This facet of requests for market access, high-speed Internet notification to the trading platform can be capture with snapshots to keep track of all changes in the second. stock market

17. It is important for history coursework writing service students to seek History Essay Writing Services from a reputable history research paper service provider for their custom history paper writing help services.

18. The development of artificial intelligence (AI) has propelled more programming architects, information scientists, and different experts to investigate the plausibility of a vocation in machine learning. Notwithstanding, a few newcomers will in general spotlight a lot on hypothesis and insufficient on commonsense application. machine learning projects for final year In case you will succeed, you have to begin building machine learning projects in the near future.

Projects assist you with improving your applied ML skills rapidly while allowing you to investigate an intriguing point. Furthermore, you can include projects into your portfolio, making it simpler to get a vocation, discover cool profession openings, and Final Year Project Centers in Chennai even arrange a more significant compensation.

Data analytics is the study of dissecting crude data so as to make decisions about that data. Data analytics advances and procedures are generally utilized in business ventures to empower associations to settle on progressively Python Training in Chennai educated business choices. In the present worldwide commercial center, it isn't sufficient to assemble data and do the math; you should realize how to apply that data to genuine situations such that will affect conduct. In the program you will initially gain proficiency with the specialized skills, including R and Python dialects most usually utilized in data analytics programming and usage; Python Training in Chennai at that point center around the commonsense application, in view of genuine business issues in a scope of industry segments, for example, wellbeing, promoting and account.

19. Very interesting blog. Many blogs I see these days do not really provide anything that attracts others, but believe me the way you interact is literally awesome.You can also check my articles as well.

Thank you..

20. Keep it up and update more valuable information like this. If you need website designing and web development services in the best price in Delhi, visit Ogen Infosystem and get website in your budget as you need.
Website Designing Company

21. Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article. This article inspired me to read more. keep it up.
Data Science Course

22. Water bodies are the main source of transportation for international freight forwarding. Due to this, sea freight company in Delhi,
visit
Freight Forwarder in Vietnam
Shipping Company In India

23. Given below are some prominent benefits you can enjoy if you opt for data science training. data science course syllabus

24. I usually make video for youtube instead of such boring article and buy youtube likes from this site https://soclikes.com/, but it is your business

25. This is additionally a generally excellent post which I truly delighted in perusing. It isn't each day that I have the likelihood to see something like this..
data science course in noida

26. Good information you shared. keep posting.
data scientist training in aurangabad

27. This Blog is very useful and informative.
best data science courses

28. With endless books and articles coming up to offer entryway to bring in cash online field and confounding peruser much more on the real method of bringing in cash, data scientist course

29. As always your articles do inspire me. Every single detail you have posted was great.
data science courses in delhi

30. I read that Post and got it fine and informative. Please share more like that...
data science course in delhi

31. This is a great motivational article. In fact, I am happy with your good work. They publish very supportive data, really. Continue. Continue blogging. Hope you explore your next post
best data science course

32. Really Nice Information It's Very Helpful All courses Checkout Here.
data science course noida

33. We’ve been creating elegant digital printing for over 20 years. Right from the start of the digital printing revolution, in fact. In that time we have grown with you, our clients. And the thing is, like any important relationship check our website for more info custom stickers printing

34. Thanks for posting the best information and the blog is very informative.Data science course in Faridabad

35. also on WOS
PLOT:
push hl
ld a,e
rra
scf
rra
or a
rra
ld l,a
xor e
and 248
xor e
ld h,a
ld a,l
xor d
and 7
xor d
rrca
rrca
rrca
ld l,a

ld a,d ; 4t x %aaabbbbb
cpl ; 4t bit value is reversed bit 0 = pixel 7
and 7 ; 7t 000bbb
; a holds bit number as value 000bbb
rlca ; 4t
rlca ; 4t
rlca ; 4t bbb000
or 198 ; 7t %11bbb110
; exx ; 4t already holding ?!? or is it free at this point?
push hl ;11t
ld hl,bits+1 ;10t
ld (hl),a ; 7t
pop hl ;10t
; exx ; 4t
bits set 0,(hl) ; 8t 0xCB %11bbb110

pop hl
ret

36. sorry,
this one is a bit better STEADY timing optimised:

PLOT:
push hl ;11t

ld a,d ; 4t
cpl ; 4t
and 7 ; 7t

rlca ; 4t
rlca ; 4t
rlca ; 4t
or 198 ; 7t

ld hl,bits+1 ;10t
ld (hl),a ; 7t

ld a,e ; 4t
rra ; 4t
scf ; 4t
rra ; 4t

or a ; 4t
rra ; 4t
ld l,a ; 4t
xor e ; 4t
and 248 ; 7t

xor e ; 4t
ld h,a ; 4t
ld a,l ; 4t
xor d ; 4t
and 7 ; 7t

xor d ; 4t
rrca ; 4t
rrca ; 4t
rrca ; 4t
ld l,a ; 4t
bits:
set 0,(hl) ; 8t 0xCB %11bbb110

pop hl ;10t
ret ;10t

plottime equ 11+ 4+4+7 +4+4+4+7 +10+7 +4+4+4+4 +4+4+4+4+7 +4+4+4+4+4 +8 +10+10

37. Very Informative and interesting blog!  Primavera course online  Best primavera p6 training online

38. I see some amazingly important and kept up to length of your strength searching for in your on the site.
Best Digital Marketing Courses in Hyderabad

39. The CBD Oil Boxes are an important thing to trade cannabis oil in the market by performing it in the Cardboard or Kraft materials most maximum of the time. We are developing exceptional artwork for these custom product boxes. We at PACKAGINGPAPA, recognize the significance of press examples to explain our packaging abilities. therefore free individual kits are offered to our customers which include random box samples of our past done work.

40. This is the information I really wanted. I found it while searching to solve the problem I had been troubled with for several days, but thank you very much. 메이저놀이터

41. Super site! Custom Printing Service I am Loving it!! Will return once more, Im taking your food additionally, Thanks.Buy Packaging Boxes Buy Packaging Boxes

42. Technology is continuously updating at such a rapid speed that it seems it might be faster than light! To keep up with this extreme pace of development, you’ve got to stay learning the newest technology concepts. We will look at the most trending technologies to master. Learn about the top hottest skills to learn to get a job.
1) Data Science course in Delhi
2) Artificial Intelligence Course in Delhi
3) Machine Learning course in Delhi
4) Business Analytics courses in Delhi
5) Digital marketing course in Delhi
6) Full Stack Software Developer course in Delhi
7) Blockchain Developer
8) RPA
9) Video Editing
10) AWS

43. Thanks for posting the best information and the blog is very helpful.Data science course in Varanasi

44. bespoke packaging boxes At Bespoke Packaging UK we strongly believe in the interests of bespoke packaging, which has multiple benefits.

45. À quoi bon ne pas exposer les significations dites les journées dernieres par la chambre national? pour le moins on pourrait dialoguer selon les vrais taux casino licenses

46. Movie-watching websites that are more than movie-watching websites Because we are the number 1 free movie site in Thailand for a long time, including new movies, Thai movies, Western movies, Asian movies, we have all kinds of ways for you Including new series Full of all stories without interstitial ads to keep annoying anymore. One place sa-movie.com.

Android and IOS operating systems. Watch online movies, Thai movies, Western movies, Asian movies, Cartoon movies, Netflix Movie, Action Movies, Comedy Movies, Crime Movies, Drama Movies, Horror Movies, Adventure Movies, Crash Movies and still have many new movies to watch. You can watch for free anytime, anywhere 24 hours a day at see4k.com.

GangManga read manga, read manga, read manga online for free, fast loading, clear images in HD quality, all titles, anywhere, anytime, on mobile, tablet, computer. Android and IOS operating systems. Read top comics, action dramas, comedy, adventure, horror and manga. New coming every day to watch many more. Can be read for free anytime anywhere 24 hours a day at gangmanga.com..

It is no secret that football is among the most popular and widely watched sports. Everybody who likes football tries to find the best platform for free soccer streaming. So, what are the best free sports streaming sites? We are going to answer this question. On this page, you can find a detailed overview of the most widespread soccer streaming websites. Keep on reading and make the best choice for you live24th.me.

47. Gift Boxes, Gift Boxes Factory, Gift Boxes Wholesale, Gift Box Manufacturer Gift Boxes, Gift Boxes Factory, Gift Box Manufacturer Custom Printing Services co.uk is the fastest handmade service manufacturers of printed packaging box.eye lash boxes | eye lash boxes

48. Ertugrul ghazi game play free in mobile

49. Thanks for posting the best information and the blog is very helpful.digital marketing institute in hyderabad

50. Good information you shared. keep posting.
data science training in pune

51. It's an excellent article!!! Such a piece of wonderful information and I was getting more concept to your blog. Thanks for your great explanations.
AWS certification course in Chennai

52. A good blog always comes-up with new and exciting information and while reading I have felt that this blog really has all those qualities that qualify a blog to be a one.

53. Hello, I am one of the most impressed people in your article. 토토커뮤니티 I'm very curious about how you write such a good article. Are you an expert on this subject? I think so. Thank you again for allowing me to read these posts, and have a nice day today. Thank you.

54. Wow, amazing post! Really engaging, thank you.
data scientist course in aurangabad

55. I am taking pmp exam prep online. One of my friend told me that ppm global services providing online course where student get the best mentor and all the resource.

56. Such a great post I like it very much keep it up.
Tuck boxes Arkansas
Display boxes Arizona

57. I feel very grateful that I read this. It is very helpful and very informative and I really learned a lot from it.
Best Data Science courses in Hyderabad

58. Thanks for posting the best information and the blog is very important.data science institutes in hyderabad

59. This is one very interesting post. I like the way you write and I will bookmark your blog to my favorites.메이저놀이터

60. Nice information, valuable and excellent design, as share good stuff with good ideas and concepts.먹튀검증커뮤니티