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

40 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