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
  add a,e
  rra
  ld l,a
  ld a,h
  add a,d
  rra
  ld h,a

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

  or a
  sbc hl,de
  jr z,EXIT
  add hl,de

  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
  add a,e
  rra
  ld e,a
  ld a,h
  add a,d
  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

68 comments:

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

    ReplyDelete
  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, :)

    ReplyDelete
  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?

    ReplyDelete
    Replies
    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.

      Delete
  4. i adore perusing this article so beautiful!!great work! learn more

    ReplyDelete
  5. This comment has been removed by the author.

    ReplyDelete
  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

    ReplyDelete
  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/

    ReplyDelete
  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.

    ReplyDelete
  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

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

    ReplyDelete
  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.

    ReplyDelete
  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

    ReplyDelete
  13. 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.

    ReplyDelete
  14. 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

    ReplyDelete
  15. 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

    ReplyDelete
  16. 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.

    ReplyDelete
  17. 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.

    ReplyDelete
  18. 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.

    Security Guard License
    Ontario Security License
    Security License Ontario
    Security License

    Thank you..

    ReplyDelete
  19. 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

    ReplyDelete
  20. 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

    ReplyDelete
  21. 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

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

    ReplyDelete
  23. 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

    ReplyDelete
  24. 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

    ReplyDelete
  25. 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

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

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

    ReplyDelete
  28. 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

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

    ReplyDelete
  30. 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

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

    ReplyDelete
  32. 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

    ;steady time optimisation
    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

    ReplyDelete
  33. 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

    ReplyDelete
  34. 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

    ReplyDelete
  35. 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.

    ReplyDelete
  36. 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. 메이저놀이터

    ReplyDelete
  37. 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

    ReplyDelete
  38. 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

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

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

    ReplyDelete
  41. À 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

    ReplyDelete
  42. 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.

    ReplyDelete