Mile
Zero

I spend a lot of time at work straddling four programming languages: PHP, SQL, JavaScript, and ActionScript. Many of our projects use at least three of these, if not all four. Yet while there's certainly some degree of domain-specific knowledge in each, there's more technique shared between them, floating off in the indefinite space of "software engineering."

Granted, I didn't study computer science in college. I had done some programming before and didn't really want anything to do with it professionally--I wanted to work for the Travel Channel! So when I fell into doing data journalism for CQ, a job that's halfway between storytelling and interactive coding, I knew there were skills where I was probably behind. And now that I feel like I'm relatively up to speed on the languages themselves, I want to catch back up on some of what I missed, starting with various low-level data structures.

The result is Typedefs, a simple blog where, in each entry, I pick an item from Wikipedia's list of data structures, implement it in JavaScript, and then explain how I did it and provide a quick demonstration. So far, I've done linked lists (the old classic), AA trees, and heaps. Next I want to try a chunk-based file, like PNG, and also a trie or bloom filter for text lookup.

I can already tell that working through these examples has been good for me--not because I expect to implement a lot of AA trees, because in my experience that's pretty rare, but because building these structures gives me a better understanding of how languages actually work, and a wider range of algorithms for solving other problems. The mechanics of a heap, for example, define a set of interesting ways to use arrays for storage and processing. AA trees really force you to examine the implications of pass-by-reference and pass-by-value. Linked lists are always a good experiment in miniature API design. As bite-sized, highly-technical exercises, they give me a chance to stretch my skills without having to build a full-sized JavaScript application.

These posts are also intended to leverage a truism: that the best way to learn is to teach someone else. By writing the blog as a teaching tool for other people, it forces me to organize my thoughts into a logical, coherent narrative: what are the foundations of this structure? What's it actually doing during this algorithm? Why is this useful? When the goal is to educate, I can't just get away with refactoring someone else's example. I need to know how and why it's built that way--and that knowledge is probably more useful than the example itself.

Here's what I've learned from releasing Underground to the Android Market:

• Mobile software is like blogging. Both have a direct relationship between good will and update frequency. People love updates. Every time I upload a new version, there's a spike of new downloads and positive comments, probably because it kicks Underground back up to the top of the Market listings where people can find it. If I were doing this for money, the lesson would be clear: update often with small tweaks. Indeed, Android's no-approval update process makes this a lot more feasible.
• Code for yourself, it'll find an audience. Not a large audience, but one that's remarkably vocal. It's self-selecting, sure, but the comments for Underground in the Market have been largely positive, with several glowing reviews and people who like it enough to e-mail me. Some, in fact, who maybe feel they should e-mail me a little too much. In no small part, this is just a factor of scale: centralized distribution has its downsides, but the sheer reach of it is impressive.
• Java is exactly as annoying as I remember. When I was in high school, I learned a little bit of Java--enough to think that it was a language designed by uptight Computer Science professors to make even small tasks many times more complicated than they needed to be. Years later and with a bit more experience, my opinion hasn't changed noticeably. Checked exceptions (those that require a try/catch block) may be the most annoying innovation of the last twenty years, but if you're used to dynamic languages (and what web worker isn't?), it'll be the ridiculous InterfaceListener abstract classes, lack of first-class functions, and overzealous static typing that'll really drive you nuts. I can be productive in Java, but I never stop feeling like I'm typing three times as much as I would in PHP or ActionScript.
• Open source means education. Underground isn't incredibly complicated, but it has a couple of neat tricks up its sleeve--mostly in the code for capturing the home button and querying the package manager. It's unlikely I would have been able to figure these out if I hadn't had most of the Android source tree available to me, including the built-in launcher. And in turn, while nobody else has submitted any patches to Underground's code repository, I've had several people write to say that they appreciated being able to read through my code and learn from it. With that in mind, I spent about an hour last commit adding extensive comments. From my perspective, open source is only partly about getting outside input. It's more about leaving the process out there, encouraging transparency, and lowering the barrier of entry--increasing generativity, in other words.
• Seriously, people, e-mailing me once is flattering. Ten times starts to get a little creepy.
• The Android UI toolkit is relatively painless. I did almost no work to transition Underground to high-dpi devices, and it scaled beautifully (the use of device-independent pixels for layout is highly recommended). Being able to build a custom dialog box using the same tools as everything else, then just inflating it and throwing it into the AlertDialog Builder, is pretty cool. For a while, I had some builds that incorporated much more complex UI ideas--some fancy designs submitted by a user that added some graphical touches, including a frame around the main list. I was impressed by how simple it was--particularly the PreferenceScreen built-in class, which handles both preference getting/setting and look-and-feel for you. And while I'm not a huge fan of XML files, using them for layout also means that when you shelve large chunks of the design (as I eventually did), you can just comment those sections out. In a lot of ways (as with the rest of Android's design), it reminds me of the best parts of web programming translated onto a native platform.

Overall, I've really enjoyed learning the platform and joining the community. I did some other hobby work on Android the other week (wrote a Locale plug-in for detecting headphones and started a utility/plug-in for launching arbitrary custom Intents), and I think it's lived up to my initial impressions of a smart, interesting API design. That said, now that Underground's in decent shape (most of the requested features have been added), I'm taking a break from Android coding for a while to give my hands a rest and concentrate on other hobbies. When I get the urge again, I'm thinking about contributing to the official NPR client--it's not a particularly good citizen on Android, and I think it'd be a good way to get involved with other digital journalists.

Again, click in the window and press space to begin playing. This time, I've added player controls: arrow keys steer and move forward, A jumps and double-jumps, and holding Z while jumping will switch from strafing to turning. Press space again when you're done, to pause rendering and keep it from hammering the CPU.

This time, the landscape is made up of 16 procedurally-generated tiles, each colored differently so you can tell between them. I apologize if there's a pause while you load the page--the noise functions I'm using tend to lock Flash for about two seconds on my machine. There's also some primitive gravity operating on the stars that you can see at the beginning.

I'd been thinking about various game-related uses for this while working on it, and the frontrunner was a kind of "jetpack delivery service" that combined Tribes with Crazy Taxi--hence the control scheme. The problem is that A) it would require an enormous landscape, and B) I'm not really sure how to balance it. For a game like that, players need to enjoy the process of movement itself, while still being limited in ways that don't have a steep frustration curve. You could do it with platforming, but I'm not really sure this engine is well-suited for that kind of thing. More importantly, implementing it well would require building levels by hand, a process for which I probably don't have the tools or temperament.

It occurred to me tonight that a better setting might be underwater--like Seaquest, without the annoying dolphin voice. That would be ideal for use with procedural height and texture maps. It'd be a natural fit for the look of a voxel engine, while still providing a good excuse for fog. It'd be kind of a neat change from the usual genres. And it would bypass one of the pitfalls of doing a first-person game in Flash, which is that mouselook is expected but not really possible due to limitations of the plugin. So I'm going to fork the code and start playing with a different control scheme, as well as a different method of generating the heightmaps that provides a bit more natural variation.

Behold, the mighty voxel terrain engine:

Click on the Flash window to give it focus, then press space to start/stop the animation thread. The two numbers at the top are the framerate and the level-of-detail (LOD) constant. You can adjust the LOD, and thus the framerate, by pressing the [ and ] keys. The ' key cycles through three post-processing options: poor-man's light bloom, simulated drunkenness, and none.

I've been working on this in my spare time for a couple of days now, just as a kind of mental exercise. Also, the techniques that I figure out on problems like this could be useful for work--I'd love to do a scatter plot or density map of the US using this kind of approach. Finally, it's a chance to get back to the kind of frame buffer-centric graphics hacking that I used to do.

So why voxels? Well, for one thing, they're easy to debug. An engine like this works by casting rays out from the viewpoint for each pixel of the display, stopping when they intersect the landscape, and drawing a texture point at that position. The heightmaps are pulled straight from images that I can make in Photoshop (thus keeping my toolset fast and simple). There aren't any BSP trees or polygon normals to compute (usually). Voxel engines may have fallen out of popularity with professionals because they can't be easily hardware accelerated (although some coders hope that will change), but they have relatively few points of failure and mistakes tend to be pretty obvious.

Getting this to work was easy. Getting it to run at 30fps or more was a bit harder. A few notes:

• Actionscript 3 is a surprisingly fast language with a nice built-in graphical library, but its methods for working directly with framebuffers are very limited. In C, I would have loaded the map data into an array and run through it with pointers, poking values into screen memory as I went. Actionscript, being a managed language, has no pointers, and its arrays kept giving me fits. When I did get the code running using data structures, it was often too slow, because the code had to be more complex (to add bounds-checking, casting, dereferencing, and index-manipulation). In the end, I went back to doing data retrieval using BitmapData.getPixel(). In comparison to array operations, getPixel offers two nice features: it fails gracefully when my rays overshoot the map, and it accepts floating point values. The end result is actually faster, even though getPixel itself is almost twice as slow as simple array lookup. As always, avoid premature optimization.
• Likewise, I tried a lot of different methods to see if I could beat setPixel(), without any success. It's odd, but there doesn't seem to be any speed advantage to populating a ByteArray and then copying it into the BitmapData, either for the entire frame or for each column. And the bookkeeping's a lot easier this way.
• You may notice that there's not much penalty for opening the SWF at full size. This is counterintuitive: voxels don't scale to high resolutions well, since they have to cast a ray for each pixel of the screen buffer. So figuring that it was always going to be pretty blocky anyway, this version renders internally to a 320x240 bitmap, then uses Flash's native scaling bring it up in size.
• In fact, generally speaking, I try to write for the parts of the Flash API that are clearly implemented in native code. It just makes sense to let the VM do the heavy lifting. In this case, bitmap scaling and copying is very fast, and the blur filter is optimized for powers of 2. Put an 8-pixel blur on a 50% transparent bitmap copy, and voila! instant bloom effect with practically no performance penalty.
• Actionscript may not have pointers, but some of the same rules apply. For example, property lookup on an object (dereferencing, if you will) is a lot slower than making a local reference variable. Also, creating objects (allocating memory) is expensive. I got a pretty significant boost early on by switching from "ray.x" to "rayX" for casting, initializing variables outside of loops, and storing references to object properties (particularly those behind two or three dot operators) whenever possible.
• Most of the program is spent in a single loop, incrementing rays and checking for intersections with the landscape, so that's where optimization was really needed. I spent some time tweaking the operations there, but by far the most effective addition was LOD: effectively, lowering the accuracy of the ray as it gets farther from the viewpoint. Implementing level-of-detail alone was responsible for a 400% speed increase. It works by increasing the casting distance each time through the loop. To get a logarithmic increase, the increase is equal to the ray's length shifted to the right by a set number of places. When you change the LOD above using the [] keys, you're changing the amount of the bitshift. At 10, the ray is accurate out to 1024 units (which is the maximum view distance). On my laptop with the debug player, setting it to 7 (meaning that detail drop-off begins at 256 units) seems to be a good tradeoff between speed and accuracy. A setting of 5 or 6 is faster but with visible jumpiness. Below 5, some wacky (but fun) behavior emerges.
• Another increase comes from being smart about the ray behavior. I render each column of pixels from the bottom up. Since the heightmap can only contain one height value, any given pixel's ray will never intersect the map in less distance than the pixels under it, so it can continue from the same X and Y coordinates as the previous ray, adjusted to a new height and vertical angle. Also, once a ray hits nothing but sky, all rays above it will do the same--so there's no need to bother with them.

Although it's simple, coding this was a lot of fun. The next goals are to add support for tiled heightmaps (for building bigger worlds), multiple landscape textures, and sprites. If the framerate would support it, I'd put a second, inverted landscape on the "ceiling" for creating more complicated structures. One thing I didn't anticipate was how much I like the look of the bold colors and gradients in the current "programmer art" texture--maybe that's a look I'd like to preserve. And of course, somewhere along the line, I'll have to figure out what I'm doing with it. Any ideas?

Against my better judgement, I've started working with JavaScript at work. It's a huge mistake, because learning new technical skills in a department that's weak in them is suspiciously like forming a debilitating drug habit: first you're just creating some tabs, then you work out how to stripe alternating rows in financial tables, and before you know it you've been assigned to build a searchable front-end for the video database. I specifically wanted to not be a programmer when I went into higher education, and look where that got me. But there doesn't seem to be any way around it, particularly after learning Flash--and Flash was itself unavoidable, since I strongly believe in using the right medium for the message, and CQ.com's messages happen to be very data-heavy and in need of visualization.

In any case, I'm conflicted. I actually really like JavaScript solely as a language. When I go to write something quickly in Visual Basic or Python now, I find myself missing features like dynamic objects (where objects can add properties and methods during runtime), long lambda functions (which are created in the middle of other code, for things like callbacks), and first-class functions (not everything has to be wrapped in a class, and functions can be passed around as objects). I feel like I finally get why people are so enthusiastic about LISP and Scheme, where a lot of these features originated: it makes for a very expressive, flexible language.

But using JavaScript means writing for the web browser, which means writing for the Document Object Model (DOM), which is a dreadful affair. I apologize for writing that, since it's rehashing something that everyone knows, but it's absolutely true. Even using a library like JQuery, thus eliminating some of the frustration of cross-browser incompatibility, cannot make this enjoyable. It's all the pain of writing a web page, compounded by rewriting it dynamically through a set of clumsy, half-blind interfaces, hopefully without breaking anything beyond recognition. JQuery doesn't solve that problem. It makes it slightly less annoying, at the cost of forcing coders to type "$()" about a million times, at which point I might as well be using LISP anyway.

In order to see how nice JavaScript could be, I think you have to write something in ActionScript, where an actual API library is provided for things like UI elements, file access, events, and graphics. Freed from having to use the HTML DOM as a layer for presentation and interaction (something for which it was arguably never designed), it's actually possible to get into a rhythm and discover the good parts of JavaScript/ActionScript/ECMAScript. It's a real wake-up call--with the downside that it makes going back to the browser even more depressing.

Flash has a bad rep in the tech press. It resurfaces whenever Adobe updates the player plugin, which is the only part they actually control anymore, or when the discussion turns to Flash content on mobile platforms. And it's not wholly inaccurate, but it's way out of proportion to what Flash deserves, and what it achieved.

You don't have to tell me that Flash has flaws. It's a pain to deep-link, particularly since it has no access to the browser's address bar--doing it requires adding extra Javascript to the page. The plugins on anything other than Win32 can be cumbersome, slow system-hogs. And yes, there are a lot of annoying Flash ads out there (although that's certainly not Adobe's fault).

But all this pales in comparison to what they've accomplished with Flash. If nothing else, look at it pragmatically: in only a few years, using a platform that started out with far less functionality, Flash basically took over the rich Internet application space. Java applets have been left to languish in backwaters like the Facebook photo uploader (the Flash plugin's comparatively quick startup and tiny download size no doubt has a lot to do with it). Javascript/HTML support for video and canvas drawing is still limited--without Flash, the Internet video sea change probably wouldn't have happened.

And in the meantime, the technical aspects really can't be set aside. Flash started out as a tool for doing frame-based animation, and a lot of its features still exist on that basis. But ActionScript, the Javascript variant that runs Flash's interactive components, has gotten more and more sophisticated, especially after it was revamped into a fully object-oriented language with Flash 9. At this point, despite accusations of sluggishness, it's still fast enough that the Tamarin VM Adobe created will be folded into Firefox for executing Javascript, and it competes favorably with the new engines powering Chrome and Safari.

There's a common criticism that the kinds of things done in Flash could also be done in Javascript without the proprietary plugin. But speaking as a web multimedia producer, the problem with that approach is that it would require me to use Javascript, which means diving into the vast sea of browser incompatibilities (or, more likely, relying on a browser framework like jQuery). And even then, support for custom drawing or multimedia is strictly limited. What Flash brings to the table is a reasonably well-written API for performing those kinds of functions, backed up with a reliable level of cross-browser performance. Eventually, browsers may catch up to that. But right now, if I want to do rich interaction with no headaches, my best option is probably Flash (or Silverlight, but it's not widespread enough yet).

Even so: let's pretend that YouTube, decent APIs, and speed aren't important to us. What's Flash got going for it? As XKCD pointed out, it spawned a tiny renaissance in simple, fun, 2D gaming. As a tool for making everything from the sadly-departed Scrabulous to Alien Hominid, Flash provided a slick platform allowing artists and novice designers to experiment and get exposure. It's done for 2D what Duke3D and Doom did for the mod scene. Say what you like about it, if you love retrogaming, Flash deserves some credit for its recent success.

Thee examples of why scripting is an essential part of a "smart" phone:

Example 1: Belle recently switched to Sprint and got an Instinct, of which she will extol the virtues to anyone who will listen. Seems like a nice enough phone to me. But it doesn't rotate photos, so she has to hold the camera the right way when adding images to contacts. We didn't figure this out until after she'd gotten a picture she liked.

My phone also does not rotate photos--as a "business" phone, Nokia treats the camera in the E51 as an afterthought. I can rotate them while viewing, but it's not a permanent change. But since I'd already run into another limitation (the inability to resize photos), I'd taken a half-hour to write a Python script that rotates and resizes images, most of which was spent learning Python's syntax (dear Nokia: ECMAscript variant, please?). So Belle sent me the file via Bluetooth, I ran it through the script, and sent it back. Now she can see a truly dismaying (but correctly-oriented) picture of my face when I call her.

Example 2: A while back I wrote that life for colorblind people often doesn't come up roses (monochromatic ones, even). Why, I wondered, couldn't you use a phone camera to identify colors? Well, you can. I wrote a script called Color Dog that opens up a viewfinder, paints a little rectangle in the center, and displays the average RGB values for pixels in that square.

Example 3: The last call for me on my old phone was that I couldn't easily record calls from it--there's no headphone jack on a RAZR, and taping via Bluetooth is no fun at all. The E51 does have a jack for various audio attachments (for some reason, Nokia calls these 'enhancements') and can even discriminate between inputs and outputs, so I could continue to talk into the phone while taping the conversation through the jack. It's even got a decent voice recorder that can run during calls, for up to an hour (memory permitting).

But let's say I'm paranoid, or I'm forgetful, or I'm being targeted by obscene phone calls. For whatever reason, I want all my calls taped, automatically, and filed under the date and time they were made. That's probably only 40 lines of code, if that--a phone status callback, a basic UI screen, and a function for starting the recording with timestamped filenames. I haven't written this. Yet. This and my idea for an app that responds to SMS with a link to the phone's latitude and longitude on Google Maps (for people who lose their phones regularly) are at the top of my list.

None of these examples are things that any smartphone--or even most camera phones--couldn't do. But they are things that most smartphones don't do. And that difference between "could" and "does" is the important point here.

Is it possible that someone could write an app on another smartphone that would permanently resize and rotate a user's photos, or help identify color values, or automatically tape calls? Sure--even in a walled garden this is possible, although technical issues (limitations on access to filesystem, background processes, or low-level hardware) could make it more difficult. But for example two it's fairly unlikely, and example three much more so, for reasons involving both barrier to entry and (in the latter case) legal liability issues.

However, on a platform that's not walled off, I can freely write these kinds of little scripts to address those problems or add capabilities. And then I can share them with other people, who can just run them, or they can tinker with them and make them better (here you go: ImageTool.py and ColorDog.py). I don't have any problems with walled gardens for buying apps, if that's your thing. But as far as I'm concerned, it's not really a smartphone--a truly adaptable, innovative device--unless it also offers the option of tweaking it on the go this way. It needs to be the equivalent of a digital swiss army knife: if you're going to carry around a Turing machine in your pocket, why settle for anything less?

I understand the desire to get a platform-independent language onto mobile devices. But I have to ask, now that I'm messing with it--who exactly thought it would be a good idea to put Python, a language that describes its program blocks using indentation, onto Symbian phones, most of which have a screen that's less than 2 inches across?

FlashDevelop is a donationware IDE for Adobe's now-open source Flex framework--basically Flash for programmers instead of animators. Between the two, you can make Flash-based software for free now, which is kind of a big deal. Maybe everyone already knew this, but I was surprised by it. Pleased, granted, but still surprised.

At this point Flash seems to have achieved what Java wanted to be: a slick, machine-portable, Internet-aware programming language with an unbelievable level of market penetration. It also has the advantage of a runtime that's very small compared to a JRE. Java has managed to achieve a valid niche as a server-side technology, but it's not much of a force on the consumer side any more.

But the weakness of Flash has been cost for the development tools, as far as I have been concerned, and I'm sure lots of other people feel the same way. You can develop Java for free, and you don't have to use a command line any more. You can get a limited copy of Visual Studio (pick your variant) for the price of a download. But Flash is what, $600 nowadays? Even Flex Builder is at least a couple hundred bucks. Moreover, Flash (the app, not the API) is truly terrible for programming, what with that weird floating psuedo-window and its continued dependence on the timeline.

Which leads me inescapably, knowing people as I do, to the conclusion that a great deal of Flash's popularity has been built on pirated copies of the software. So it was probably only a matter of time before Adobe decided to open the software up with a free/cheap version, simply reserving some of the goodies (bonus UI components, for example) for paying customers. Which is, as far as I can tell, exactly what they've done.

Anyway, the politics of it aside, you can make Flash for free now. This is a very good thing. I'm guessing they'll screw it up any day now.

My Internet claim to fame, before I started plastering my name all over this mountain of wandering ASCII, was as a coder in a very small corner of the PocketPC gaming market. Quake had just been ported to Microsoft's first usable mobile operating system, which was a big win, but I couldn't run it. At the time, PocketPCs were much more powerful than the Palm device where I'd started, but they were also much more expensive. To save money, some OEMs were making using cheap greyscale screens instead of the color versions that were more common. Greyscale was actually an advantage for some users, because the battery life was longer, but it used a 4-bit screen depth (like the original Gameboy) instead of 16-bit color. As a result, applications that weren't written to handle the lower scale would overwrite video memory with four times as much information, all incorrectly formatted, and the device would crash.

I was just a student, so I had to dip my toes into the WinCE market with one of the lower-end devices from an eBay auction. And while I was content to grin and bear it when the best commercial games would only run on color devices, Quake was open source. So I got a copy of the compiler and started mangling the video code until I created a version that would run on both devices. The conversion was tricker than I had initially figured (the buffer was actually addressed in landscape mode, so I had to write non-adjacent pixels to each byte when in portrait), but I managed to blunder through. It wasn't perfect (I had a bug in my lookup tables, and very bright colors would turn black), but it was a hit in the small community of users who used the same devices. I followed up with a replacement for the PocketPCs game .dll (which told software where to locate video memory and directly access the buttons) that would automatically convert color games to greyscale, even if the author hadn't done any work, by creating a virtual color screen and converting from there.

I could do all of this, even though I didn't (and still don't, really) know anything about the Windows API, because Windows CE would give considerable leeway to programmers. If you wanted something onscreen fast, you didn't waste your time trying to get the OS to draw it for you. You grabbed the screen memory and wrote the bytes yourself. This was a low-level hackability that the PocketPC shared with Palm, although the latter was even more primitive (and therefore even more fun to code on). PocketPC does, after all, have several great modern features--multitasking, protected memory, error collection--that always felt like they were in my way. On a Palm, the OS was laid open. You could ignore the proper way to code, disrespect the other programs, and have your game largely take over the machine. As a user, it was an often unsatisfying platform, but as a programmer it was a blast.

The reason I started to think about this was because there's word that the Apple iPhone won't be able to run third-party software. Well, that's not entirely true. I expect that a few months after it's out on the open market, or as open as a $500-with-expensive-contract phone can be, someone will have hacked it open. Eventually, you will be able to play Quake on it--everything plays Quake or Doom, given time, even if no-one could ever imagine such a thing being useful or enjoyable. At this point I think the port just spawns on its own, no coders required, after a set gestation period. But what you probably won't be able to do is break into the system guts like I did. Maybe that's a good thing, from a modern perspective--should kids really be learning about addressable video memory at this point, instead of real APIs like Core and DirectX (which will eventually come to Windows Mobile, mark my words). No doubt those kinds of programming environments are more powerful. I guess I just wonder if they're any fun.

I read a theory once that British programmers became dominant during early days of computer gaming because they learned on terrible little machines (the BBC Micro, I think) that were nevertheless easy to hack. For the last ten years or so, coding on a portable computer has been like a time machine back to a simpler era. For a certain kind of person, like me or maybe the guy who wrote a GTA game for NES, there's a powerful appeal in that simplicity. But it looks like PDAs and cell phones are no longer a destination for that kind of ground-level coding. We're either going to have to go to even simpler devices (wristwatches? digital cameras?) or to emulation for a retrocomputing fix. As our present moves into the future, our past keeps pace with it.