Forgot your password?
typodupeerror
Software Graphics

Interactive Raycaster For the Commodore 64 Under 256 Bytes 143

Posted by Soulskill
from the most-useful-software-I've-seen-this-month dept.
New submitter Wisdom writes "1bir (1 Block Interactive Raycaster) is a simple ray casting engine implemented only in 254 bytes to run on a stock, unexpanded Commodore 64. The name comes from the fact that on a C64 floppy disk, 1 block is equivalent to 254 bytes stored on a disk sector. In 254 bytes, 1bir sets up the screen for drawing, creates sine and cosine tables for 256 brads based on a simple approximation, casts rays into a 2D map that lives inside the C64 KERNAL ROM, renders the screen in coordination with KERNAL, evaluates 8-way joystick input and detects collision against walls. The ray casting core employs a brute force algorithm to determine visible walls, while the mapping portion supports both open-ended (infinitely looped) and traditional, closed maps. The source code in 6502 assembly is available, with extensive comments. A YouTube video showcases 1bir in a detailed manner with both kind of maps and more information, while a Vimeo video presents a shorter demonstration."
This discussion has been archived. No new comments can be posted.

Interactive Raycaster For the Commodore 64 Under 256 Bytes

Comments Filter:
  • by jeffmeden (135043) on Wednesday May 15, 2013 @04:26PM (#43734867) Homepage Journal

    Good thing it only took him 30 years of development to come up with this. Had the software been around when I used a C64 (when they were the state of the art) I would probably still be looping around inside those maps.

  • Zip? (Score:5, Funny)

    by ZahrGnosis (66741) on Wednesday May 15, 2013 @04:29PM (#43734891) Homepage

    The source code is zipped. For a 254 byte program. This just tickles me for some reason.

    • Re:Zip? (Score:5, Funny)

      by jeffmeden (135043) on Wednesday May 15, 2013 @04:46PM (#43735027) Homepage Journal

      The source code is zipped. For a 254 byte program. This just tickles me for some reason.

      When you have a 300 baud modem on your C64 and Delphi Online charges by the minute, every last byte adds up!

      • Re:Zip? (Score:5, Interesting)

        by tgd (2822) on Wednesday May 15, 2013 @05:07PM (#43735201)

        The source code is zipped. For a 254 byte program. This just tickles me for some reason.

        When you have a 300 baud modem on your C64 and Delphi Online charges by the minute, every last byte adds up!

        The funny thing is, back then the handy thing about 300 baud was there was no need to pipe things to more -- you could just cat a file and read it as it downloaded ...

        Stupid 1200 baud modems messed that all up ...

      • by Sloppy (14984)

        But doesn't Punter protocol upload in 256 byte blocks anyway?

        On no: the horror. I don't remember for sure! When did that happen? In 1985 I so would have schooled you. Look at me now; how sad.

    • by jandrese (485)
      The worst part is that zip actually increased the size of the programs by a few bytes. It was counterproductive here, although it did help shrink that relatively gigantic disk image.
      • by greg1104 (461138)

        The worst part is that zip actually increased the size of the programs by a few bytes.

        Of course it did. If it was possible to compress the program usefully and distribute a smaller version, he would have done that too!

      • The worst part is that zip actually increased the size of the programs by a few bytes. It was counterproductive here, although it did help shrink that relatively gigantic disk image.

        I thought no way, I had to see for myself. The zipped file crescent-1bir-src.zip is 8K, the three file files
        the zip contains add up to 25K so 1/3 it's original size. Your thinking of graphics files.

        If a file is already compressed (ie: graphics, zip) they can't get any smaller, another compression program
        will only increase it's size. Source code is text only and very compressible; all of your modem compression
        schemes to increase speeds are based on text only.

        The JSTOR files Aaron Swartz uploaded were 36 Gigs

        • by jandrese (485)
          I was talking about the binaries, not the source. The binaries are 256 bytes, as was mentioned in the writeup, but "compressed" they ended up around 260 bytes or so.
    • And the lameness filter prevents it from being posted here. Aptly named.

  • The vimeo link leads to this article.

  • kudos (Score:5, Informative)

    by excelsior_gr (969383) on Wednesday May 15, 2013 @04:30PM (#43734899)

    It is nice to see that in this world of plenty (at least as far as system memory and CPU speed goes) some people find joy in efficiency; and they go so far as to pull something like that off, just for the fun of it. Needless to say, the dude that did this is a real programmer [pbm.com].

  • by Anonymous Coward on Wednesday May 15, 2013 @04:31PM (#43734905)

    Dunno if the link was bad for anyone else, but here's the actual vimeo link [vimeo.com].

  • by parlancex (1322105) on Wednesday May 15, 2013 @04:31PM (#43734907)
    The next time you churn your next 500MB printer driver think about programs like this. Think long and hard.
    • by Anonymous Coward

      i would personally love to cause hours of greif and anguish to those who create hp printer drivers.

      for they have costed me days in troulbe shooting and reinstalling their bloated drivers and software.

      • Their Linux drivers are quite slim on the other hand, install easily and work beautifully.
        Every feature on every device works through the standard mechanisms too.

      • by Sloppy (14984)

        By misspelling "grief" you defied the adaptive Huffman table's expected distribution, thereby wasting memory. You're lucky this is a C64 story where memory is abundant, because if you had posted this in a VIC-20 story (where every single byte truly counts) I would have called you Not Worthy.

    • by Solandri (704621) on Wednesday May 15, 2013 @05:07PM (#43735205)
      The printer driver itself wasn't 500 MB. What happened was that some manager at HP decided tech support was wasting too much time (money) instructing people on how to navigate their byzantine support website to find and download the correct drivers for their printer. So they glommed the drivers for all of their printers into one big binary and told people to just download that.

      IMHO the real lesson from the HP printer drive fiasco is that if it's quicker and easier to find something on your website by doing a Google search for it, you need to redesign your website. HP eventually did that, and their site now lets you just type the printer's name and it'll take you directly to its download page.
      • Re: (Score:2, Troll)

        by drinkypoo (153816)

        The printer driver itself wasn't 500 MB. [...] IMHO the real lesson from the HP printer drive fiasco is that if it's quicker and easier to find something on your website by doing a Google search for it, you need to redesign your website. HP eventually did that, and their site now lets you just type the printer's name and it'll take you directly to its download page.

        ...where you can download a 150MB printer driver. Progress!

        • I own HP printers and scanners, I know what I am saying is a fact. HP printer drivers are still stupidly oversized. If you're using a real printer that speaks a real language you don't even need a driver, just the PPD, and that is actually provided for some models. But for their more primitive printers (like personal laserwriters, which for the most part don't even speak PCL) you need to download a massive driver that probably won't work on the next version of Windows. I've owned several HP printers specifi

    • If you are complaining about HP printer drivers, I think I can just about assure you that you haven't seen the bottom of the barrel - not by a long shot.

    • by tgd (2822)

      The next time you churn your next 500MB printer driver think about programs like this. Think long and hard.

      God, I hope you're not a programmer.

      • Why, yes I am! I've written home-brew Xbox games that included graphics and animations, sounds and music(<10MB), and reasonably complicated network software that runs as a service on many of my servers at work (<100KB). I've dabbled in writing demo code as well writing a complex synthesizer with DSP effects and tons of music content in 64kb.

        If you're actually defending the need to ship printer drivers literally over 500MB I would really love to hear your logic.

        • by tgd (2822)

          Why, yes I am! I've written home-brew Xbox games that included graphics and animations, sounds and music(<10MB), and reasonably complicated network software that runs as a service on many of my servers at work (<100KB). I've dabbled in writing demo code as well writing a complex synthesizer with DSP effects and tons of music content in 64kb.

          If you're actually defending the need to ship printer drivers literally over 500MB I would really love to hear your logic.

          No, I'm attacking your suggestion that a simple raycaster projecting a map of data that already exists in ROM being simple (it is -- it'd be a couple hundred lines of any code, no matter now little effort you put into making it compact) equates in any form with any software that actually has to meet external requirements. The suggestion is just ignorant, and karma-whoring.

          Its as stupid as looking at a cleverly made multicolor building a 5 year old throws together with legos and suggesting that the next time

          • Here I go feeding the trolls...

            So just so I can get this right, a printer driver is so complex a feat of engineering it is analogous to a skyscraper? A printer driver takes input data in the form of text, fonts, and images, formatting, and translates it into a format compatible with the printer in question. Entire operating systems have been written in less than 1/10th the size of some of HP's modern shipping print drivers. I never said it has to be 254 bytes, but the current level of bloat is absolutely in

            • by tgd (2822)

              Here I go feeding the trolls...

              No, here you go being a troll.

              If you reread my post, I even said the print driver is small. Most don't take any code, in modern systems.

              The stuff that turns a printer driver into a product that a company can ship adds the rest. Its okay, go back and read my post. I gave some examples.

              If you're still confused after re-reading it, I doubt anyone is going to be able to make you understand.

              • I'm afraid you're still an idiot, because "the stuff that turns the driver into a product" should still also be no greater than a few MB tops, even with stupid sounds, images and animations included for the printer status.
      • Why?

        • by tgd (2822)

          Why?

          Because I'd fire pretty damn quickly any programmer that doesn't understand product requirements. In fact, I have on a number of occasions.

    • by jandrese (485)
      I will never buy a non-Postscript printer ever again. Postscript printers mean you never have to mess with drivers, especially network Postscript printers.
    • After thinking a long time I decided that I would be impressed if he could implement the print driver to run on a commodore 64!

      • Then you should be impressed [blip.tv]. If you seriously are a developer who writes printer software for HP you are bad and you should feel bad.
  • by Myria (562655) on Wednesday May 15, 2013 @04:35PM (#43734937)

    It's interesting to note that the code uses two "undocumented" 6510 instructions:

    lax $91
    anc #$00 ; clears carry for sinadd below

    These instructions are undefined; they work by taking advantage of the internal CPU architecture to execute a hybrid of other legal opcodes. A lot of other older processors have such behavior, such as the Z80. Even the 8086 had a bit of this: "pop cs" and the second encoding of "sar" come to mind. (The 8086's "pop cs" was stolen by the 286 to mean an escape to a second opcode page.)

    • by Wisdom (4414)

      The alternative version (1bir-alt.prg/s) uses no illegal opcodes at all. :-)

    • It is not uncommon to find programs utilizing the MOS 6052 instruction set doing the same thing.
      This is why if you write a Nintendo NES emulator exactly to spec some games might not work because they use undocumented instructions that work on the real hardware but need to be specifically implemented in software.
    • Correcting myself (Score:4, Insightful)

      by Myria (562655) on Wednesday May 15, 2013 @05:15PM (#43735285)

      and the second encoding of "sar" come to mind

      Sorry, but it's "SHL" that has a duplicate encoding on x86. There are four slots for non-rotating shift instructions in "group 2": 4=SHL, 5=SHR, 6=???, 7=SAR. The /6 variant looks like it ought to be "SAL", and it is. However, unsigned left shifting is equivalent to signed left shifting, and thus the two opcodes end up doing the same thing. The original 8086 happy processed this instruction as a signed left shift because of how it interpreted the opcode bits, but that's the same as an unsigned left shift.

      This was retained in modern processors, whereas "pop cs" was not.

    • by tlhIngan (30335)

      These instructions are undefined; they work by taking advantage of the internal CPU architecture to execute a hybrid of other legal opcodes. A lot of other older processors have such behavior, such as the Z80. Even the 8086 had a bit of this: "pop cs" and the second encoding of "sar" come to mind. (The 8086's "pop cs" was stolen by the 286 to mean an escape to a second opcode page.)

      The reason for this is simple - the instruction decoder is using a bunch of logic gates to figure out how to drive the various

  • The Vimeo link in the story somehow became broken, the correct link is as follows:

    http://vimeo.com/66004524 [vimeo.com]

  • by localman57 (1340533) on Wednesday May 15, 2013 @04:52PM (#43735075)
    Projects like this are a great way to train new engineers for small embedded systems. There is a lot of work out there on 8-bit systems with a couple k of program space and a few hundred bytes of ram. At my place we actively collect books that targeted advanced computer programming techniques in the early 80's, because they line up good with the resources we typically have on a microcontroller that costs $1.27 now .

    For example, given a 128x96 black and white LCD, create an algorithm that will draw a line between any two points. Oh, and you can only use integer math, and we'd prefer it if you kept division operations to a minimum, because we have to do division through a software library call...

    The old-timers did that stuff in their spare time 30 years ago.
    • No need [wikipedia.org] to create one.
      • by greg1104 (461138)

        Line drawing can have a lot of complexity to it beyond just picking the best of the usual approaches. A simple implemtnation of Bresenham's line algorithm may or may not be optimal given the system's other constraints. One common change is to recognize that horizontal and vertical lines are both common enough that they should get their own optimized code paths. If it's possible the code might run on a grey scale display one day, you might code in a way that later allows anti-aliasing. On a computer like

    • by tibit (1762298)

      Division operations for line drawing? Ever heard of Bresenham's algorithm? It can be further tweaked based on the organization of the frame buffer.

      There are many state-of-the-art designs that are memory constrained. Parallax's Propeller has 512 32-bit words for high-speed cog memory. Their new Propeller II adds a third memory space (besides cog and hub memories), but the basic 512 word limit remains unchanged. XMOS XS1 architecture has 64 kbytes of RAM shared between code and data for a multi-core CPU tile.

  • Wow... perhaps there is some hope for Doom 2600 [wikia.com] after all...
  • by hduff (570443) <{moc.liamg} {ta} {ffudtyoh}> on Wednesday May 15, 2013 @05:42PM (#43735511) Homepage Journal

    Will this run on my VIC-20?

    Otherwise, meh.

    • by Wisdom (4414) on Wednesday May 15, 2013 @06:09PM (#43735771) Homepage

      It is quite possible that it will run on VIC20, but it will probably need some modification to the actual render code (I do not have a VIC20, so I am not sure). Other than that, it should work, as RAM usage is minimal (just needs 320 bytes for sine/cosine tables, ZeroPage and the 1K video RAM).

      Nevertheless, I will include it in the next release. Thanks for the idea.

      • by greg1104 (461138)

        The VIC20 doesn't have a bitmapped display mode. To show graphics you have to redefine the character set. The usual solution to that limitation was to throw RAM at the problem of holding the character definitions. I suspect it will be a lot more complicated than the C64 for the sort of code you're running.

    • by StarWreck (695075)
      I would bet it would run on the VIC-20. Maybe not the .C64 disk image but the source code. VIC-20 had only 5K RAM but it had a full 6502 CPU. Although they have entirely different video chips.
      • by greg1104 (461138)

        The VIC-20 was named for its VIC display chip [wikipedia.org]. It uses character definitions instead of bits, which means code for it is unique to running on VIC-based systems. There's a completely different video chip in the C64, they're not at all alike.

  • Optimization (Score:5, Interesting)

    by eulernet (1132389) on Wednesday May 15, 2013 @06:00PM (#43735691)

    My 6502 is not completely lost.
    Here is how to optimize the code a little bit:

    Replace:

    loop_stepadd
                            lda stepx,x ; & y
                            ora #$7f ; sign extend 8 bit step value to 16 bit
                            bmi *+4
                            lda #$00
                            pha ;clc
                            lda stepx,x ; & y
                            adc rayposx,x ; & y
                            sta rayposx,x ; & y
                            pla

    with:

    loop_stepadd ;clc
                            lda stepx,x ; & y
                            adc rayposx,x ; & y
                            sta rayposx,x ; & y
                            lda stepx,x ; & y
                            ora #$7f ; sign extend 8 bit step value to 16 bit
                            bmi *+4
                            lda #$00

    This saves 2 bytes and a few cycles.

    • by Wisdom (4414) on Wednesday May 15, 2013 @06:37PM (#43735989) Homepage

      Well spotted, I missed that one out. :-) Usual problem of looking at the same thing for so long, now it perplexes me how I missed such an easy one. :-)

      • Re:Optimization (Score:5, Interesting)

        by eulernet (1132389) on Wednesday May 15, 2013 @09:06PM (#43737017)

        Well, it was not obvious.

        I originally wanted to optimize the sign extend using some carry tricks, like asl/lda #0/sbc #0, but realized that it was unnecessary.
        In fact, you can improve it even more, as follows:

        lda stepx,x ; & y
                                bpl *+4
                                dec rayposxh,x
                                adc rayposx,x
                                sta rayposx,x
                                bcc *+4
                                inc rayposxh,x

        Saving 6 bytes !

        This trick is mentioned here:
        http://forum.6502.org/viewtopic.php?p=5262 [6502.org]

        BTW, your tsx/txs trick is really horrible, it forces the stack at the bottom of $100.

  • by Anonymous Coward

    This was done a decade ago for the Color Computer (6809). A self-modifying 3d engine in ~256 bytes was turned into a full "doom" style 3d game.

    http://members.optusnet.com.au/nickma/ProjectArchive/crasher.html

    With video!

    https://www.youtube.com/watch?v=jVFn_djQ6EY

  • I got a kick out of the use of bytes already in ROM as the map. I did something similar for an old DOS game of mine, Tunneler, where I used bytes taken from IBM PC ROM to replace the player's usual game view with a TV static/snow effect (simulated loss of signal). I grabbed bytes from an address in ROM that resulted in random-looking values interspersed with a few horizontal streaks. Know of any other games that made unusual use of ROM data?
    • by Hatta (162192)

      Yars Revenge used its own game code as pseudorandom data to animate the neutral zone.

  • Awesome! If only we could teleport today's knowledge back to 1983! =)

    I had been looking for a small demo to include with our Android .TAP-file renderer https://play.google.com/store/apps/details?id=co.kica.tapdancer [google.com], and this will be perfect! (Assuming it's free to distribute -- demos usually are but I'm attempting to clarify this...)

A sheet of paper is an ink-lined plane. -- Willard Espy, "An Almanac of Words at Play"

Working...