Interactive Raycaster For the Commodore 64 Under 256 Bytes 143
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."
(oblig) Better late than never (Score:4, Funny)
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.
Re:(oblig) Better late than never (Score:5, Interesting)
Had the software been around when I used a C64 (when they were the state of the art) . .
What do you mean? C64 still is state of the art . . . for 1982.
On the other hand, a clever hack borders on being timeless - for example and inspiration if nothing else.
Certainly in a time of ever greater bloatware it can border on mind-blowing to consider what people used to do, and some still do, in handfuls or hundreds of bytes: The Puzzle [folklore.org]
Visual Transistor-level Simulation of the 6502 CPU [visual6502.org]
Re: (Score:1)
Zip? (Score:5, Funny)
The source code is zipped. For a 254 byte program. This just tickles me for some reason.
Re:Zip? (Score:5, Funny)
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)
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 ...
Re: (Score:2)
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.
Re: (Score:3)
Re: (Score:3)
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!
Re: (Score:3)
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
Re: (Score:2)
Re: (Score:3)
And the lameness filter prevents it from being posted here. Aptly named.
Bad link in summary (Score:2)
The vimeo link leads to this article.
Re:Bad link in summary (Score:5, Funny)
kudos (Score:5, Informative)
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].
Re: (Score:2)
Heh, the more things change...
Re: (Score:3)
I was hoping for the story of Mel, a real programmer [utah.edu].
On the article, it's fantastic. It puts me in mind of First & Third almost FORTH and the recent Fixing E.T. hack.
Vimeo, Vimeo, wherefore art though, Vimeo? (Score:4, Informative)
Dunno if the link was bad for anyone else, but here's the actual vimeo link [vimeo.com].
Re: (Score:2)
What is that font the C64 uses and where can I get it?
Re: (Score:2)
http://dl.dropbox.com/u/144888/wordpress/2011-03-16-commodore/c64.ttf [dropbox.com]
Re: (Score:2)
Thanking you!
Re: (Score:1)
You might want to (re-)read the license for that file...
You MAY NOT: sell this font; include/redistribute this font in any font collection regardless of pricing; provide the font for direct download from any web site.
You MAY: link to "http://style64.org/c64-truetype [style64.org]" in order for others to download and install the font;...
Re: (Score:2)
Dude, it's right there in your ROM.
HP Printer Driver Developers Take Note (Score:5, Insightful)
Re: (Score:1)
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.
Re: (Score:2)
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.
Re: (Score:2)
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.
Re:HP Printer Driver Developers Take Note (Score:5, Informative)
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)
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!
Troll? (Score:2)
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
Re: (Score:2)
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.
Re: (Score:1)
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.
Re: (Score:2)
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.
Re: (Score:1)
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
Re: (Score:2)
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
Re: (Score:2)
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.
Re: (Score:2)
Re: (Score:2)
Why?
Re: (Score:2)
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.
Re: (Score:2)
Re: (Score:2)
Really? The Postscript printers I've used, network and local, have all required drivers. Maybe this is a stupid question, but how do you control duplex or not, color or B/W, which paper source, etc if you don't have a driver for the printer?
A PPD [wikipedia.org], a text file which describes the printer's capabilities, and the commands to send to change various options.
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
The point is that the OS comes with the Postscript driver, as well as PPD support. They'll never become obsolete and will always be supported by new versions of the OS.
Re: (Score:2)
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!
Re: (Score:3)
Uses two undocumented / illegal instructions (Score:5, Interesting)
It's interesting to note that the code uses two "undocumented" 6510 instructions:
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.)
Re: (Score:2)
The alternative version (1bir-alt.prg/s) uses no illegal opcodes at all. :-)
Re: (Score:2)
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)
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.
Re: (Score:2)
The reason for this is simple - the instruction decoder is using a bunch of logic gates to figure out how to drive the various
Correct link for Vimeo video (Score:2)
The Vimeo link in the story somehow became broken, the correct link is as follows:
http://vimeo.com/66004524 [vimeo.com]
Good Training for embedded systems (Score:4, Insightful)
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.
Re: (Score:3)
Re: (Score:3)
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
Re: (Score:2)
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.
Only 254 bytes? (Score:1)
Re: (Score:2)
Or HALO
http://members.shaw.ca/jeffv/halo2600.html [members.shaw.ca]
Will this run . . . (Score:4, Funny)
Will this run on my VIC-20?
Otherwise, meh.
Re:Will this run . . . (Score:5, Interesting)
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.
Re: (Score:2)
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.
Re: (Score:2)
Re: (Score:2)
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)
My 6502 is not completely lost.
Here is how to optimize the code a little bit:
Replace:
with:
This saves 2 bytes and a few cycles.
Re:Optimization (Score:4, Funny)
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)
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:
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.
Re: (Score:2)
Holy shit.
I just lost my geek card!
Or, 2MHz 6809 with full 3d Game (Score:2, Interesting)
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
Other creative uses of ROM data? (Score:1)
Re: (Score:3)
Yars Revenge used its own game code as pseudorandom data to animate the neutral zone.
Awesome! (Score:1)
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...)
Re: (Score:1)
NEVAR!!!!
Re: (Score:1)
Page 0. 'Nuf said.
4 KB expansion card (for 1540/1). 'Nuf said.
MC reset switch. 'Nuf said.
Phonome-based, wire-wrapped, GP256 speech-synth for the IO port. 'Nuf said.
But an Amiga was so far beyond, just a few short years later, that it is stupid to even consider the C64 worthy of anything at all. 'Nuf said.
Re:OMFG !! (Score:5, Insightful)
The C64 is worthy of fun.
Re: (Score:2)
For those of us under 40 years old, there is quite a lot more to be said. I have no idea what half of what you said even stands for.
Page 0
1540/1
MC reset = Master Control?
Phonome-based
Re:Real-work problem? (Score:5, Insightful)
Re:Real-work problem? (Score:5, Insightful)
I work with a health IT company that's trying to give doctors better tools to solve and treat disease. Our project could improve the lives of lots of folks, and its quite difficult to find talented technical folks to join the team.
I appreciate this is a cool hobby project, I just wish the guy would use his not inconsiderable talents to work on something that has a more obvious real-world payoff (unless this is all a hologram running on 4x10^16 Commadore 64s).
I got an idea.Pay him to do it. Your company works for money.
You wouldn't be working for one of the two dozen firms doing mobile apps for connecting doctors to patients, looking for funding, explaining how you work "with" and not "for"?
Re: Real-work problem? (Score:5, Insightful)
Re: (Score:2)
I think it's a necessity to have fun.
Yes, life can be hard, cruel and short, but those are all reasons to enjoy it anytime you have the possibility.
Re: (Score:2)
I got an idea.Pay him to do it. Your company works for money.
Heh. Money well spent on Health IT innovations.
-
sorry, spilt my coffee.
Re:Real-work problem? (Score:5, Funny)
I work with an advanced robotics research firm that's trying to take humans out of fragile, disease-ridden bodies and put them in immortal robot bodies. Our project would allow humanity to transcend mortal existence, and it's quite difficult to find talented technical folks to join the team.
I appreciate your cool hobby project, I just wish you would use your not inconsiderable talents to work on something that has a more obvious long-term payoff.
Re:Real-work problem? (Score:5, Interesting)
As a bioinformatician who's trying to give researchers better tools to identify disease, whose projects could also improve the lives of lots of folks: this is not that kind of programming. Demoscene programmers are generally hired by graphics companies and embedded systems development, where their formidable optimization abilities actually get put to use; those skills are not transferable to general high-performance computing. You'll have to keep hiring out of the general CS grad pool.
Re:Real-work problem? (Score:5, Insightful)
Actually the skills do transfer. The techniques of code optimization are many and universal. Which ones constitute acceptable use depends on the application (i.e. mathematical approximations are not always OK). From what I keep reading, HPC focuses a lot on matrix math - an area where some tricks can help a lot without affecting the results. I was manipulating 1GB 3d data sets interactively on a machine with 128M of RAM back in the day, and I suspect the technique has not gone mainstream yet.
Re: (Score:3)
Which ones constitute acceptable use [...]
And that's the trick. These people focus predominantly on mathematical approximations, extreme memory limitations, and knowing the ins-and-outs of the CPU itself, or the API they're using if it's a PC demo. All C64 demos are programmed in assembly. So while optimization is common to both fields, the level of detail is much too tight. In demo programming, effects are chosen because they optimize well. That doesn't fit with matrix programming or stats where accurately capturing an algorithm is the top priorit
Re: (Score:2)
Even if a demoscener did, for example, rewrite BLAST, the result would be completely unmaintainable
So same as it is now?
Your comments about exact calculations in this context strike me as kind of funny. The whole reason BLAST exists is because it replaces an expensive search for an optimal match with a heuristic method. It is at its core cheating to optimize a process that wasn't running fast enough. And if you take a look at how the original Smith–Waterman algorithm [wikipedia.org] has been sped up, you'll see that clever ways to cut the code down so it will run on specialized hardware are exactly what people
Re: (Score:3)
Up to a point, I agree with you—I've even implemented some optimizations of Smith-Waterman myself, so I know how bad it can get. The thing is, to fully maximize the kinds of cheating that you typically see in demos, you usually have to sacrifice the flexibility of the algorithm itself. A lot of the genius in low-power C64 and Amiga demos comes from precalculating data and constraining the perspectives from which the image on screen is shown; they're illusions. While a demoscene programmer may be excel
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:1)
Re:Real-work problem? (Score:5, Insightful)
Can't find talented technical folks to join the team, or can't find talented technical folks to join the team for well below market wages?
Usually when people say one, they really mean the other.
Re: (Score:3)
I work with a health IT company that's trying to give doctors better tools to solve and treat disease.
That's cool. I'm between jobs right now, so I have a lot of time on my hands. But the bright side is that just a few dollars from my unemployment check will buy a whole bunch of eggs, so I'm cool.
Say, why don't you tell me where you live, and I'll come over and we'll talk about that disease treating thingie you're interested in.
Re: (Score:3)
Hang on there. Why are you using your talents on a project that may save 1000s when you could be working in vaccination projects that could save 10s of 1000s? Wait! Forget that. You and those time wasting vaccination workers should be focused on biotechnology that could create crops to feed millions world wide!
Hold it! Scratch that. Global warming will end up destroying the entire planet. Get those lay-about biotech-crop workers on that!
Wait! Heat death of the universe. Only billions of years away and effec
Re:Real-work problem? (Score:5, Insightful)
Do you visit model railroad clubs and chastise them for playing with toys when there's so much real freight to be moved?
Re: (Score:3)
How do you even know what he is using his talents for at his day job? This type of project is
fun, allows a programmers to relax, reduce stress, and unwind but also allows them to hone
their skills so that there actually are "talented technical folks" for you to hire. I have yet to
meet a great programmer that doesn't do this sort of thing in their spare time and therefore
I honestly believe that eliminating this sort of behavior would actually reduce your ability to
hire qualified candidates.
Re: (Score:1)
> I work with a health IT company that's trying to give doctors better tools to solve and treat disease. Our project could improve the lives of lots of folks, and its quite difficult to find talented technical folks to join the team.
My most beloved word in the dictionary is "freedom". People are, today, still free to write stuff for fun if they want to for the C64.
My worst nightmare would be a world in which, in the name of morality, everybody was forced to work on something with "Real-World payoff" [TM
Re: (Score:2)
I appreciate this is a cool hobby project, I just wish the guy would use his not inconsiderable talents to work on something that has a more obvious real-world payoff
So people need to work on productive stuff that will save lives and treat disease, 24/7. They can't go to the movies, they can't go to the park, they can't take a break. The MUST always be doing something productive? You know, stuff like this is the way some people take a break from their other work. Maybe they enjoy solving problems, or doing something different sometimes. Maybe this person learned something from this?
Everyone can't be solving hard problems all the time.
Re: (Score:2)
Since you said company, I suspect it plans to turn a profit on this. Either convert to a non-profit and ask him to contribute or send him paying job offer.
Re: (Score:2)
Actually, a lot of the really talented people go to finance.
Whether they help humanity on the whole is debatable.
Re: (Score:2)
Next version is coming up soon, with more features than you actually mentioned in your post. :-) (It will not be under 256 bytes, though). This was, as you said, made to prove that it can be done under 256 bytes. Therefore, the size limit does not really allow to add many more features than there are now (although it is still possible to add small improvements here and there, of course). Lastly, this does not utilize any LUT, except for the usual sine/cosine tables.