Tiles Don't Generalize

For a couple months, I've been experimenting a bit with SVG during my free time to get a feel for how to use it cleanly on the web. In particular, I've been playing around with trying to create a little tile-based game using SVG and JavaScript.

The nice properties of grid-based tiles using an isometric or 3/4 perspective are well-known. As long as every object in the game fits exactly in a 1x1 grid cell, then everything works great. It's easy to figure out an order to draw the objects in order to ensure that nearer objects properly occlude further objects. You can stack objects within a grid and do other nice stuff too.

After seeing all those isometric-perspective computer games with characters running in-between grid tiles and with all manner of odd-shaped objects though, I assumed that the algorithms for choosing the order to draw objects in the isometric perspective generalized in some nice way. Of course, I realized that things couldn't generalize arbitrarily. If you allowed for arbitrary objects in arbitrary poses, then you'd end up with an arbitrary 3d scene drawn from an orthographic perspective. Then you'd need the full painter's algorithm with polygon chopping etc.

But, I assumed that if all objects were in non-overlapping axis-aligned bounding boxes, then I could figure out some way to order the objects without needing to chop any of them (since you can't really do this is SVG). In particular, I wanted the floor tiles and the objects to be all mixed up in the rendering code. But for the isometric perspective, it is possible to create degenerate examples where objects mutually occlude each other. So you can't generalize algorithms for the isometric perspective this way. In particular, my plan of having floor tiles and wall tiles, plus arbitrarily sized objects sitting on the floor tiles just wouldn't work.

In fact, the same thing happens with the three-quarter perspective as well (I've shifted the perspective a bit so that it's easier to see the depth of the objects).

So having arbitrarily sized objects that can stack on top of each other arbitrarily won't work. Having objects in non-overlapping axis-aligned bounding boxes where all the bounding boxes sit on the same plane, that seems to work ok. With the isometric perspective, it seems like it might be a little bit hard to get the right ordering of objects during drawing, but it seems doable at least. With the 3/4 perspective, everything works out well in that particular situation.

So basically, one way to get around this problem is to have a flat floor and use tiles to cover the floor as one layer, then on a second layer, you can have objects and walls and stuff that you can order separately. I imagine there are other cases that lead to an easy ordering of objects (perhaps if everything has a fixed height? or maybe in the 3/4 perspective, if you allow for only two levels: one for arbitrary height terrain and then another for things on top?), but I haven't really figured it out yet. Perhaps in reality, degenerate cases never really end up occuring, so you can just sort of hack in lots of special cases in the rendering engine to make sure all the objects are rendered in the right order.

Well, in any case, the point of this post is to show that tiles are trickier than I thought. They really don't generalize nicely, so you have to put a lot of thought into how to handle things once you allow for objects that don't fall exactly within grid boundaries.

Resolution Independence in Vista

I recently got a Thinkpad notebook that crams a 1400x1050 resolution onto a tiny screen. It's a great screen, but unfortunately everything ends up being a bit too small. If you have resolution independent applications, the increased resolution can be a real joy though because the text becomes so clear and easy on the eyes. Although previous versions of Windows had very limited support for resolution independence, things supposedly had improved quite a bit in Vista.

Unfortunately, things don't quite fit together that well. Just like earlier versions of Windows, you can increase the default font size in Vista. Unfortunately, this causes various glitches in things. For example, text no longer fits in the dialog boxes of Windows Media Player (I suspect that the Windows Media Player people must have written some custom dialog box code because I'm pretty sure the default dialog box code scaled things correctly even back during the Windows 95 days). And lots of fonts on web pages are specified in terms of pixel sizes, and their sizes don't get adjusted, so the text ends up being too small to see. Internet Explorer does have a zoom capability that redefines pixel sizes, but it also increases the size of the default font, which has already been increased, making things look too big.

Vista also has the option of simply scaling up all pixels to a larger size. Basically, Windows will fool legacy applications into thinking that the screen has a lower resolution, so that the applications render at a smaller size. This render is then scaled up to fill the larger resolution. Resolution independent applications, however, can render at the full resolution. Unfortunately, Adobe (Acrobat) Reader is considered a legacy application. Being able to read .pdf documents with crisper text is one of the main reasons I chose the high resolution screen, and you lose all those benefits if you render everything to a lower resolution and then scale it up. I imagine the same problem crops up in other applications as well. For example, Internet Explorer doesn't have strong support for vector drawing formats like SVG, so it's not possible to get high resolution graphics on web pages, so you have to live with scaled up versions of bitmaps instead.

Based on this experience, I imagine it will take another few years before it becomes practical to use Windows comfortably on a high resolution display. The new version of MacOS will supposedly have strong support for resolution independence, but I doubt that they've actually managed to solve the problem in a comprehensive manner. I think that doing resolution indepence right probably requires a larger rethinking of UI widgets and layout managers (basically, it will be the same technology needed to layout a single UI design on both tiny mobile device screens and large LCD monitors with needing lots of manual tweaking), but I haven't really heard much about research into that area by Apple, so I doubt they've hit the final solution yet.

Serializing Signals without Atomic Compare and Swap

So basically, the problem with event handlers in IE6 is that they might become interrupted by other event handlers, making synchronization difficult. What you want is a more traditional event driven model where only one event handler can execute at a time. Essentially, you want a scheme that serializes signals so that the event handlers execute sequentially. Unfortunately, since JavaScript comes with no synchronization primitives like atomic compare and swap, so doing this is messy.

So I think I've come up with a scheme that lets you wrap event handlers in a function that will test if other event handlers are executing at the same time. If they are, it will add itself to a queue to be executed later. There's various annoying synchronization issues involved though, so this is not as simple as it sounds.

Here's the pseudocode for the event wrapper function:

globals root, queue
if root == null
  root := true
  execute own handler
  root := null
  while !queue.empty()
    root := true
    queue.dispatch()
    root := null
else
  queue.add(self)

And here's the pseudocode for the queue methods:

queue.add(fn)
globals end, isClaims[], handlers[], queueLength
myend := end
while(true)
  if isClaimed[myend] != null
    myend++
    if myend >= queueLength
      myend := 0
    if myend == start
      error!
    continue
  isClaimed[myend] := true
  if handlers[myend] != null
    continue
  handlers[myend] := fn
  break
end := myend
 
queue.empty()
globals isClaimed[], start
return isClaimed[start]==null
 
queue.dispatch()
globals isClaimed[], handlers[], start, end, queueLength
if isClaimed[start] != null
  myend := end
  if myend == start
    myend++
    if myend >= queueLength
      myend := 0
    end := myend
  execute handlers[start]
  handlers[start] := null
  isClaimed[start] := null
  start ++
  if start >= queueLength
    start := 0

And here's how you could code it up in JavaScript. Basically, I define a handler function. You can then use the handler function to wrap your own event handlers before setting them to listen for events:

<script>
// Initialization script that creates the "handler" function for wrapping
// handlers
(function () {
  var SIZE = 100;                   // max number of simultaneous events
  var root = false;                 // boolean, indicating whether
                                    // event handler is the first one in a
                                    // chain or not
  var queue = new Array(SIZE);      // Event handlers to be executed later
  var thisQueue = new Array(SIZE);  // Corresponding this objects
  var isClaimed = new Array(SIZE);  // reserves a spot in queue
  var start = 0;                    // position in queue circular buffer
  var end   = 0;
 
  // Define the global handler wrapper function
  handler = function(eventHandler)
  {
    return function() {
        if (root == false) {
          root = true;
          eventHandler.call(this);
          root = false;
          while (isClaimed[start] != null)
          {
            root = true;
            if (isClaimed[start] != null) {
              var myend = end;
              if (myend == start) {
                myend++;
                if (myend >= SIZE) myend = 0;
                end = myend;
              }
              queue[start].call(thisQueue[start]);
              queue[start] = null;
              thisQueue[start] = null;
              isClaimed[start] = null;
              start++;
              if (start >= SIZE) start = 0;
            }
            root = false;
          }
        } else {
          var myend = end;
          while (true) {
            if (isClaimed[myend] != null) {
              myend++;
              if (myend >= SIZE) myend = 0;
              continue;
            }
            isClaimed[myend] = true;
            if (queue[myend] != null) continue;
            queue[myend] = eventHandler;
            thisQueue[myend] = this;
            break;
          }
          end = myend;
        }
      };
  }
})();  // Execute the initialization code
 
function loaded()
{
  alert('loaded ' + this.src);
}
 
var img1 = new Image();
var img2 = new Image();
img1.onload = handler(loaded);
img2.onload = handler(loaded);
img1.src = "test1.png";
img2.src = "test2.png";
alert('done')
</script>

Asynchronous Callbacks in IE6 JavaScript

Well, back in October, I noticed that Internet Explorer 6 had a few quirks with its usage of event handlers. JavaScript is single-threaded and does not contain any synchronization primitives. As a result, when JavaScript is embedded in a web browser, it is supposed to use an event-driven model: as events occur, they are put into a queue, and then a single thread removes events from the queue and executes handlers for them. Unfortunately, IE6 does not rigorously follow this model. Some of their callbacks follow a model used for interrupts or UNIX signals. Even if another piece of JavaScript code is being executed, the code can be interrupted by an asynchronous event, and the callback for that event will be run. When the event ends, the original code will resume. Unlike signals or interrupts though, IE6 allows these callbacks to interrupt other callbacks.

So, if you put the following code in a web page and run it in IE6, you will get three different dialog boxes showing up simultaneously:

<script>
function loaded()
{
  alert('loaded ' + this.src);
}
 
var img1 = new Image();
var img2 = new Image();
img1.onload = loaded;
img2.onload = loaded;
img1.src = "test1.png";
img2.src = "test2.png";
alert('done')
</script>

I believe this problem was corrected in Internet Explorer 7 because if you run the same code in IE7, you only get one dialog box showing up at a time.

In any case, I think I came up with a solution for this problem back in November, but I never got around to testing it until now. I'll put the code up in my next post.

JavaScript in IE is not Multithreaded

After coding up my mutex and experimenting with it, I've discovered that Internet Explorer isn't multi-threaded. Instead, it has something worse. Much, much worse.

In any case, here's my mutex code:

function Mutex(maxThreads)
{
 // This mutex is based on the paper "Tight Bounds for Shared Memory Symmetric
 // Mutual Exclusion Problems" by Eugene Styer and Gary L. Peterson.
 if (maxThreads < 2)
  alert('Mutex is configured incorrectly');
 this.waiting = new Array(maxThreads);
 this.locks = new Array(maxThreads);
 for (var n = 0; n < maxThreads; n++)
 {
  this.waiting[n] = null;
  this.locks[n] = null;
 }
 this.maxThreads = maxThreads;
 this.whoInCriticalSection = null;
 this.turn = null;
 this.get_visible = function(level, retry, me) {  // This is private
  if (level == -1)
  {
   this.waiting[0] = me;
   level = 0;
   retry = true;
  }
  else if (this.waiting[level] != me)
  {
   // Don't write if we can make progress
   if (this.turn != me)
   {
    if (retry)
    {
     // Assume mistake, once
     retry = false;
    }
    else
    {
     level = level + 1;
     retry = true;
    }
    // Make visible again
    this.waiting[level] = me;
   }
  }
  return [level, retry];
 }
 this.enter = function() {
  var me = new Object();  // generate a unique id for this thread
  var level = -1;
  var retry = false;
   while (true)
  {
   // See if lock is available, or if it assigned to me
   while (this.turn != null && this.turn != me)
   {
    var ret = this.get_visible(level, retry, me);
    level = ret[0];
    retry = ret[1];
   }
   this.turn = me;
   var locked;
   while (true)
   {
    // Try to get all locks
    for (var pos = 0; pos < this.maxThreads; pos++)
    {
     if (this.locks[pos] == null)
      this.locks[pos] = me;
    }
    // Do we have all the locks?
    locked = true;
    for (var pos = 0; pos < this.maxThreads; pos++)
    {
     if (this.locks[pos] != me)
      locked = false;
    }
    if (this.turn != me  locked) break;
   }
   if (this.turn != me)
   {
    // Lost, release locks
    for (var pos = 0; pos < this.maxThreads; pos++)
    {
     if (this.locks[pos] == me)
      this.locks[pos] = null;
    }
    var ret = this.get_visible(level, retry, me);
    level = ret[0];
    retry = ret[1];
   }
   else
   {
    break;
   }
  }
  // Acquired lock
  if (this.level > -1 && this.waiting[this.level] == me)
   this.waiting[this.level] = null;
  this.whoInCriticalSection = me;      // Save our id for later
 }
 this.leave = function() {
  var me = this.whoInCriticalSection;  // Get our saved id
  this.whoInCriticalSection = null;
  // Find ID of top waitier or 0 if nobody
  var next = null;
  for (var pos = this.maxThreads - 1; pos >= 0; pos--)
  {
   if (this.waiting[pos] != null) {
    alert('handoff');
    next = this.waiting[pos];
    break;
   }
  }
  // Let them continue, release locks
  this.turn = next;
  for (var pos = 0; pos < this.maxThreads; pos++)
  {
   if (this.locks[pos] == me)
    this.locks[pos] = null;
  }
 }
}

So back to the original point. In the end, JavaScript in Internet Explorer isn't multi-threaded. There's only one thread, but it can be interrupted by callbacks or signals, and the thread won't regain control until after the signal/callback handler completes.

So if you look at this chunk of JavaScript code

var image = new Image();
image.onload = function() {
 alert('a0');
 alert('a1');
 };
image.src = 'blank.gif';
alert('0');
alert('1');

you'll notice that the alerts you get are for a0, a1, 0, and then 1. The onload callback does not give up control back to the main thread until after it finishes giving its two alerts. This means that mutexes and critical sections can't be used in JavaScript because if one thread is inside a critical section and becomes interrupted, the other thread cannot yield to the other thread to let it exit its critical section. So basically, you can't use locks or critical sections or other standard programming techniques to protect important parts of code.

I don't know what the best way to fix this is. It's just messy...very, very messy.

JavaScript Mutexes 2

Actually, I started thinking some more about symmetric mutual exclusion, and I realize that I was actually mistaken. You don't actually need to use any randomization. Although in a real system, the only way to generate unique thread ids would be to use randomization, JavaScript does have one operation that is guaranteed to generate unique keys--just use new to create a new Object since new is atomic. You can then use this object as your thread id. And since it's an object, JavaScript will automatically take care of cleaning it away once you're finished with it.

So, in conclusion, JavaScript mutexes are possible if you use a shared memory symmetric mutual exclusion algorithm and if you are able to put a bound on the number of threads that may attempt to enter a mutex at any one time. This is the best approach to the problem. There are no unacceptable trade-offs that need to be taken into account (beyond the whole messiness of needing to implement your own mutexes in JavaScript in the first place).

Mutual Exclusion in JavaScript

I started reading up on some papers, and I've found that the type of mutual exclusion being attempted by Wallace in JavaScript is actually impossible. Totally anonymous mutual exclusion using atomic RW registers cannot be done.

That leaves two choice:

1. One can hand-out thread ids in advance (i.e. assign one to each possible callback) during a stage when one knows the code will have only one thread running

2. Use randomized mutual exclusion algorithms

Personally, I think option #1 is very hard to implement correctly, so option #2 is probably the most feasible. Basically, you randomly generate a thread id for yourself at any time (in fact, you can randomly generate a thread id every time you want to enter a mutex). Then, you can run a symmetric mutual exclusion protocol using atomic RW registers.

I found a paper that seems to give one such algorithm:

"Tight Bounds for Shared Memory Symmetric Mutual Exclusion Problems" by Eugene Styer and Gary L. Peterson.

JavaScript is Multi-Threaded

I was doing some JavaScript programming where I hooked a bunch of image onload() callbacks with functions that would generate alerts, when I noticed that various alerts were firing before I had finished hooking up all my callbacks. This caused me a lot of consternation. JavaScript does not come with any threading primitives. As such, it's very hard to do any synchronization. Yet clearly, my version of Internet Explorer was triggering these callbacks asynchronously, in threads other than my main thread, resulting in various race conditions in my code.

Firefox seems to use a more sensible model. It seems like it has only one JavaScript thread (much like the single UI thread in most GUI systems), and asynchronous events queue up and are only fired when your JavaScript thread isn't doing anything (of course, that's brings up the other problem of the fact that Firefox seems to discard events if too many get queued up--but at least that's easier to handle than race conditions).

I went looking around for various mutex code to solve this problem, but nothing seems quite right. Some Bruce Wallace person created a JavaScript version of mutex, but I don't have much confidence in it. First of all, he replaced a fixed size array from Lamport's Bakery algorithm with a Map. The whole point of the fixed size array was that you could perform atomic reads and writes on it--a reasonable assumption. Once you use a Map, you're assuming atomic adds, atomic removes, and atomic iteration, which are much larger assumptions. In any case, if you had an atomic add operation, then you wouldn't need to implement the Bakery algorithm because you could use atomic add to create a mutex. His assignment of thread ids also has a race condition in it. I suppose I could just assign a separate thread id to each callback in advance, thereby avoiding the race condition, but if I did that, then I wouldn't need this Map nonsense and I could use a fixed size array because I would know how many threads there are in advance.

Instead, I simply reshaped my code so as to minimize the race condition to an atomic increment instruction. It seems unsatisfactory though. Personally, I think JavaScript should not be multi-threaded, but if it is multi-threaded, they should at least supply something like Array atomic_add() and atomic_remove() methods so that users at least have the proper primitives available for building synchronization primitives. And I'm not sure whether JavaScript engines are themselves thread-safe. I know that Mozilla's Rhino claims that it is thread-safe (I vaguely remember them stating that get and put operations were atomic), but I don't know about the engines in FireFox and IE.

Update 2011-3-31: I was going through my blog stats for the first time, and I noticed that people seem to read this post occasionally. This is an old blog post, and I explore the situation in more detail in later blog posts. Actually, JavaScript is NOT multi-threaded. In IE6, you do get some weird non-sequential behaviour, but that's due to nested asynchronous callbacks.

Getting an SVG Bounding Box out of Batik

I was using CorelDRAW to create some GIFs using a script, but CorelDRAW 11 has a lousy GIF exporter, so I couldn't really get the output that I wanted. So, I thought I would export my CorelDRAW data to SVG, and use the Batik SVG libraries to export the data I wanted to GIF (using the GIF exporter I described in the previous post).

I did encounter a problem though in that CorelDRAW defined a page size on the SVG document, and the Batik transcoders always exported the entire page (instead of just the parts of the page that contained my image). If I removed the page information from the SVG document, then Batik would just export an image with a default size. What I needed was a way to get a bounding box on my image, which I could then pass to Batik as the export size.

When I searched on Google, all the information that I could find about creating bounding boxes involved creating UI objects to render into, which triggers Batik to calculate bounding box information. This seemed a little bit overly heavy to me, but by looking at how the Batik transcoders render their images, I was able to just reuse their rendering code to trigger a bounding box calculation without actually rendering to a UI.

The first step is to remove the page sizing information from the SVG document (otherwise, Batik will just use the page size as the bounding box). Just run this XSLT filter over it:


<?xml:namespace prefix = xsl />
<xsl:stylesheet version="1.0" svgns="http://www.w3.org/2000/svg" xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:output method="xml">

<xsl:template match="@*node()">
<xsl:copy>
<xsl:apply-templates select="@*node()">
</xsl:copy>
</xsl:template>

<!-- Remove width, height, and viewBox attributes (substitute different things in later on when we've calculated a bounding box) -->
<xsl:template match="svgns:svg/@height"></xsl:template>
<xsl:template match="svgns:svg/@width"></xsl:template>
<xsl:template match="svgns:svg/@viewBox"></xsl:template>

</xsl:stylesheet>

Then, you can take the resulting SVG code and feed it into Batik to calculate a bounding box like so:

String parser = XMLResourceDescriptor.getXMLParserClassName();
SAXSVGDocumentFactory f = new SAXSVGDocumentFactory(parser);
SVGDocument doc = (SVGDocument)f.createDocument(svg);
GVTBuilder builder = new GVTBuilder();
BridgeContext ctx;
ctx = new BridgeContext(new UserAgentAdapter());
GraphicsNode gvtRoot = builder.build(ctx, doc);
return gvtRoot.getSensitiveBounds();

You can then use the returned information to set the "viewBox," "height," and "width" attributes on the svg tag of the SVG file. When you then run the transformed SVG file through Batik, Batik will export the image with the bounding box set tightly around the contents.

-Ming

Exporting Transparent GIFs from Java

After spending a while trying to create paletted PNG files with transparency that work in Internet Explorer (after much trying, I couldn't coax ImageMagick to create such a file, though I was able to use GIMP to do it), I decided that GIFs were the only practical file format to be used. But it's hard to get a Java program to output GIF files.

Because of the whole patent licensing issue, there aren't really any good, full-featured, unencumbered GIF exporters for Java. But there are various good bits and pieces on the 'net, which can be pieced together to make something reasonable.

First, you need some code that can actually encode the GIF file. The US government has some code that can do this (offered as part of NIH's ImageJ). All you have to do is download ImageJ and grab their ij.io.GifEncoder class.

The ImageJ code only accepts paletted data as input though. Since most images are in 24-bit colour, you need to perform a colour reduction somehow. Fortunately, someone went and took the colour quantizer used in ImageMagick and rewrote it for use in Java. It uses an octree for its colour quantization, which is a technique described in much detail elsewhere on the Internet. The quantization code needs to be reworked a bit to properly handle transparent pixels, but fixing that isn't too much work. A more important fix though is that the code performs an unnecessary optimization to save memory, which results in poor quality quantization. In the constructor for Cube, it sets the tree depth to log_4 of max_colors. Instead, the tree depth should just be set to the maximum depth of 8. Although the original ImageMagick did limit the tree depth to log_4 of max_colors, they used another optimization elsewhere in the code to reduce the effect of that limitation.

Once you combine these two pieces of code together (you have to change some of the APIs to handle transparency and other things), then you end up with a very reasonable GIF exporter.

Firefox Should Stop Being So Smug About It's CSS Support

Because, honestly, Firefox is missing some fairly major CSS features. Notably, it's missing support for "inline-block." This problem has been known since 1999 (7 years ago!) and is listed as bug 9458, but the Mozilla people haven't been particularly inclined to fix it.

I think the problem is fairly important because it's the one CSS feature that allows for arbitrary nesting of inlines and blocks. Usually, you can put inlines in blocks and blocks in other blocks. Inline-block is the feature that lets you put blocks in inlines. This opens up a certain class of layouts that aren't otherwise possible.

Reading the bug description in bugzilla, it seems like Mozilla's Gecko rendering engine is fundamentally flawed and can't really handle this feature without a major rewrite. Internet Explorer handles inline-block well, so, in my opinion, IE has superior CSS compliance than Firefox.

Jakarta Commons CLI 1.0 Is Not Very Good

I wanted to do some quick command-line argument parsing in Java, so I grabbed the CLI component from Jakarta Commons and gave it a whirl. Unfortunately, this component is not very good. I fit it into a jar of about 28KB, which is not large but not that small either. The resulting command-line parser is able to identify various command-line arguments, but it isn't able to do more advanced parsing such as automatically converting arguments to integers (like jargs). It also isn't able to make use of Java annotation coolness (like args4j). It has a nice feature for automatically generating help messages, but the generated option list doesn't really match what the parsers will accept. For example, the help message will say that "-gui" is a valid option, but when using the PosixParser, the parser kept misreading the "-gui" as "-g" and rejecting it for some reason. I had to switch to the BasicParser to get it to do something reasonable.

Overall, it's nothing that I can't live with, but I was hoping for something a little better from Jakarta Commons. I think they should junk the multiple parsers, and just focus on a single more full-featured one.

Recording with Java Sound on the Macintosh

I was trying out my little Java VoIP application with a friend of mine who owned a Macintosh, and it didn't quite work right. Besides the whole dubious Java 5.0 support for the Macintosh, I couldn't open a TargetDataLine at 8000 kHz.

On PCs, you can record and playback audio at arbitrary sample rates. That's not the case on the Macintosh. After getting another friend to do some probing, I found that the Java sound system on Macintoshes can playback at arbitrary sample rates, but can only record at 44100 Hz. You can record at 8/16-bit depths, with (un)signed types, and at different endianness though, I think.

VoIP in Computer Games

About a year and a half ago, I started to become curious as to why there were so few computer games with VoIP support. It should be relatively easy, shouldn't it? You just grab an open source sound codec like Speex, throw in some sound code, add some network packet buffering code, mix, and voila--VoIP support. Unfortunately, I became distracted by something else and never got around to looking at the issue more deeply.

Just recently, I became curious again, so I decided to code up a small VoIP application. And, as expected, it did end up being fairly easy. I have to admit that I did waste a week going down the wrong path--I configured my sound card wrongly, resulting in a lot of feedback in the signal, so I spent a week examining algorithms for echo and feedback cancellation. But once I figured out what I was doing wrong, I was able to bang out a working little VoIP application in about a week.
The only part that wasn't really obvious (to someone who's been thinking about the problem for the past year) was the packet buffering code. Conceptually, it should be easy, you just store incoming packets somewhere and wait a few milliseconds before using them to compensate for packets coming in out of order and with jittered delay. But that leaves a lot of unresolved issues such as what should you do if you use up all the packets waiting for you? You can skip a packet (i.e. assume that they are lost) or skip a "heartbeat" (i.e. assume that you're consuming packets too quickly and wait for the packet to arrive). And what happens if you receive too many packets?

The scheme that I ended up using was to trigger everything based on the difference between the highest packet sequence number in the packet buffer and the next packet sequence number that the program is expecting. So whenever my program tries to grab the next packet, if the difference in sequence numbers is below a certain threshhold, then I skip a heartbeat; otherwise, I grab the next packet, skipping it if it hasn't arrived yet. If the difference in sequence numbers ever gets above a certain threshhold, then I advance the expected sequence number to get below the threshhold. I also had different threshholds for deciding when to adjust for clock-skew. Oddly enough, my sound card seemed to playback audio at a different sample rate than what I specified for some reason (it could quite well be my fault), so I put in some code for stretching incoming sound samples to take up more or less time. All of these threshholds should probably be adaptive somehow, but I couldn't be bothered, so I just set them to some default values.

Other than that, everything was pretty straight-forward. In Windows Java, the System.currentTimeMillis() method is very low-resolution, which caused my server to alternate between thinking it was very fast or very slow. Fortunately, newer versions of Java have a nanoTime() method, which provides a better high-resolution timer. I also had a bit of a problem with silence detection because my sound card didn't use 0 as a baseline. Sound samples seemed to center around -100 or so. I was able to get around this by taking the max and min sound samples of every chunk of sound, averaging them, and then exponentially averaging them with my previous estimate of what the baseline was. This seemed to work as an adaptive baseline. I'm not sure how to erect an adaptive silence detection algorithm on top of that though since I put a static algorithm there instead.

So the conclusion of all this is that VoIP support isn't included in more computer games due to laziness on the part of developers. It really is very easy to do. There may be some latency issues where computer game code is stealing so many CPU cycles that the VoIP code can't get CPU resources at regular enough intervals that it causes latency, but I'm sure it's something that game developers could work out with thread priorities and stuff like that.

Adding a Little Colour to Sine Waves

I've never really been much of a audio creation buff, but when I heard that Propellerhead were releasing their ReBirth audio program for free, I quickly downloaded it because I've always been curious as to what all the fuss was about. ReBirth is apparently an emulator of the TB-303, which is a piece of techno hardware from the 80s that could be used to generate weird instrument sounds and to sequence those sounds into some simple tracks. It also emulates some other pieces of hardware (namely some rhythm boxes). I actually found ReBirth to be really difficult to use and completely confusing, so I uninstalled it.

Fortunately, I also downloaded the free Rubberduck program from d-lusion, and it was quite fun and easy to use (not that I have sufficient talent to get the program to do anything that sounds good, but at least I can make those crappy sounds easily as opposed to with ReBirth). After playing with it for a while, I noticed that if I turned off all the filtering effects, I could still make some nice instrument sounds just by combining sine waves and square waves.

This was significant to me because I occasionally create little Java games, but it's hard to get any music into those games. Java includes support for MIDI output, and the full Java VM even comes with Roland sound patches for its instruments, but the existence of these patches isn't guaranteed, so you can't rely on them for game music. Instead, you have to supply game music via sound files, but then you need to generate these sound files somehow. I purchased some cheap music composition software, but it creates sound files by playing the music out through the computer sound card and recording it. Since my sound card is really cheap, the resulting sound files end up containing much too much noise to be useful. There are open-source programs that can take MIDI songs and output sound files directly, meaning you don't get any noise, but these programs all use sound patch sets of questionable legality, so I didn't want to use them. But if I could just make my own instrument sounds by combining some sine waves and square waves, then I could just create a program for converting MIDI songs into sound files myself without the problems of noise or legal encumbrances.

Unfortunately, once I wrote a program for combining sine waves and square waves in various ways, I realized that the sounds that my program was generating were puny and weak. Even the simple sine wave sound generated by d-lusion's Rubberduck was much fuller and colourful than the sine wave generated by my program.

The documentation for d-lusion's Rubberduck said that they pass their sound through a low-pass filter, but I thought I had turned all the filtering parameters off. Besides, a low-pass filter shouldn't really affect a sine wave. In any case, I'm really weak with signal processing, so I couldn't really design such a filter anyways.

Well, anyways, I was looking over the "Cookbook formulae for audio EQ biquad filter coefficients" document by Robert Bristow-Johnson which is, essentially, the dummies guide to creating various filters using digital feedback mechanisms. When I looked at what Rubberduck did to square waves (it rounded out the corners), I suspected that maybe I could just sort of randomly feedback things into itself and maybe get a similar effect.

So that's what I did:

y[n] = 0.8 * y[n-1] + 0.2 * x[n]

where x[n] is a sine or square wave and y[n] is the final sound output, and the result is exactly what I wanted. Whereas a simple sine wave is teeny and annoying, when you pass it through this filtering, you get a richer, rounder, more bloated sound. Of course, when you look at the raw wave form, it still looks like a sine wave, but I suspect that it's slightly reshaped so that you get some interesting side frequencies going on. I tried doing a spectral analysis, but I couldn't really interpret it (it looked consistent with a sine wave to me), but it sounds a lot different, so there must be some sort of subtle colouring there.

Of course, to get really interesting sounds, you need adjustable filters that allow you to get various cool effects, but I think I have pieces of code for making blip and bop noises for my Java games.

Computer Generation of Road Networks

For the past couple of days, I've been thinking of how to get a computer to automatically generate a city road network. I really have no idea what the best way to approach this is.

Doing a quick search through the Internet, there are computer techniques for automatically generating terrain, for simulating the growth and sprawl of cities, for simulating the growth of small neighbourhoods, and for simulating traffic on a road network, but only a few simulations for generating accurate road networks themselves. In fact, the simulations that do exist seem to focus on simulating lot use with the expectation that the road network just sort of "falls out."

I think the difficulty is that there isn't that much scientific use for simulating the development of road networks, so a lot of research hasn't gone into that area. Of course, the people who do research on urban sprawl really should do more research into road networks too because urban sprawl tends to be dependent on the location of existing highways etc. Anyways, the problem is also hard because road networks tend to be highly planned and need to take a lot of factors such as geography, cost, etc. into account during their evolution, so it's hard to get a computer to randomly generate this type of data.

Still, I wonder what it takes to build a road network generator. I imagine that an urban growth simulation model might actually be the wrong approach because it'll end up being too complex. I think a top-down approach that lays out some highways, throws down a coast-hugging road network near water, builds a grid patterned downtown, and a squiggly suburb area might actually be the easiest approach. Hmm.

Theoretical Underpinnings for Kids' Programming Tools 2

Y'know, yesterday I was fretting about the fact that without strong theoretical underpinnings, my programming website for kids would never become a useful tool. But there no reason for me to have such a crisis of confidence because, honestly, which of these people is most likely to make the best programming tool for kids:

A PhD from MIT who has been professionaly developing his patented educational programs for more than 10 years.

A Turing award winner who has spent decades studying user interactions with programming languages.

Me.

Obviously, my approach will be the best. :-)

Teaching about Loops

So I finally finished most of the artwork for the "if" section of my programming website for kids. It seems that the Java VM has improved a bit since I last used it. I'm finally getting consistent synchronization behaviour between when my applet running in a web broswer and my applet running stand-alone. And Swing now seems to support automatic text cut&paste with Windows applications (sigh, all of this could have been avoided if they used native widgets!).

And I'm now starting the section on loops. I've spent a few months thinking about this topic, but I'm still not sure about what the best approach is.

In traditional programming books about BASIC, the loop section would talk about FOR...NEXT loops:

FOR n=1 to 5
REM Stuff that happens 5 times
NEXT n

Unfortunately, the Javascript for loop is a little bit cryptic (especially since I haven't covered increment operators, the less-than operator, or the greater-than operator). Additionally, the convention for loops is that they start at 0. But, people are more comfortable with loops that start incrementing at 1 (like in BASIC). However, if I use 1-based loops throughout my examples, people might get confused when they later start working with normal code.

I suppose I could treat the syntax of the "for" loop as gobbledygook that should be treated as a black-box. This then reduces the number of concepts that need to be understood to work with loops.

Another alternative is that I could start with while loops. The advantage is that the word "while" actually means something, so it might be easier to understand. Unfortunately, there isn't all that much that one can do with a while loop without understanding the concept of sentry variables, which involves teaching 2 or 3 abstract concepts all at the same time.

I could teach the concept of the infinite loops first via "while(true)," but assuming that I don't teach boolean algebra beforehand (which I don't), then the whole command would need to be treated as a black-box, defeating the whole purpose of starting with the "while" loop in the first place. Then, I could follow that by teaching the concept of using "break" to break out of loops. This seems a little odd to me because no one else teaches loops in this way. Perhaps the "breaking out of loops" concept is simply too abstract a concept. But it does seem like a lot less work than discussing sentry variables and such.

Well, I don't know. For the past few months, I've been keen on the idea of starting with the while loop, but now I'm starting to come around to the idea of starting with infinite for loops. I'll have to ponder this some more.

Theoretical Underpinnings for Kids' Programming Tools

During the weekend, I happened to come across a cheap scanner for sale, and I grabbed one so I would have the tools to start working on my programmingbasics.org website again. This then inspired me to take another look at the tools available for teaching kids to program. It looks like the same stuff as always--Squeak, ToonTalk, and Logo. Of course, all of these tools have strong theoretical underpinnings describing interaction models, learning processes, etc., whereas my website simply focuses on recreating the programming environment available to me when I was a kid. I'm no longer confident that I'm taking the right approach any more. Will my website (assuming that I ever finish it) have the correct foundation for teaching kids to program? Should I take a more holistic approach to the site and try to provide a complete environment for "experimentation" as opposed to simply creating something that focuses solely on just programming? Hmm. Perhaps I'm being naive. Kids today associate computer with great graphics and sound. Creating an environment that focuses on programming and doesn't allow kids to immediately generate flashy animations might lose their interest too quickly.

When I learned programming, all computers were textual. In fact, I didn't even own a computer. I was fascinated by flowcharts and wrote my first computer program out on paper by hand. The books available for teaching kids to program focused on real languages and on real syntax issues. And that's what I wanted to learn when I read those books. That's why my website is based on Javascript and focuses on syntax. But maybe those old programming books for kids died out for a reason, and maybe that reason was that kids aren't interested in learning programming that way any more. I guess I'll have to think about it.

FBX File Format

Previously, I've complained about the U3D file format for having such an obscure encoding scheme that I felt it was impossible to read a U3D file without using the unreleased Intel U3D libraries that everyone else apparently uses to read and write this file format.

But after looking at some other 3d file formats, perhaps this isn't so unusual. For example, Kaydara's FBX file interchange format (now owned by Alias) doesn't even have a documented encoding format. As far as I can tell, the only way to read a FBX file is to use the provided SDK libraries. Personally, I can't imagine how you could call something an interchange file format if you don't actually describe what the file format is. But maybe I'm just not used to how things work with 3d graphics.

Oddly enough, the only light-weight 3d file format that seems to be well-documented is Microsoft's DirectX file format. Unfortunately, it's apparently no longer under active development.