Arabic Support in Java

So a few months back, I started working on an Arabic version of JavaScript, which required me to figure out how to write an Arabic Java program. To my surprise, Java actually has pretty lousy support for BIDI and Arabic.

Now, I always suspected that the old Sun severely understaffed its Java UI group and I always had this odd feeling that their UI programmers never actually programmed any real applications using their UI frameworks. The fact that Java, the major enterprise programming language of the last decade, still doesn't properly support Arabic even after all these years of development just tells you everything you need to know right there. IBM/eclipse, with its SWT UI framework for Java, has had proper Arabic support for a long time now. Instead of doing everything alone, why didn't Sun get help from others when developing Java? Why? Mind you, they rely heavily on proper OS support for Arabic while Java's Swing framework is designed in such a way that they have to reimplement Arabic support from scratch. And the Unicode character encoding was specifically designed so that text processing of Unicode is easy but the handling Unicode in a GUI is the most awfully complicated piece of code possible. But still, we're at Java 7 now, and they should have been able to get this basic piece of infrastructure supported by now.

It makes me wonder which programming languages computer science students are taught in the Arab world. It can't be Java. What's the point of learning a programming language that can't properly handle the input and display of your native language? I guess it must be C# or something.

Anyway, this is what I found. I was working in Windows in Java 6, so my observations may be specific to this combination.

In AWT, I tried setting the text direction using applyComponentOrientation(), but I could never get that thing to work. The text always stayed left-to-right using AWT widgets. In both AWT and Swing, there's a setLocale() method, but I have yet to figure out whether that method actually does anything. I suspect it doesn't do anything. So basically, I don't think there's any BIDI support in AWT. This is somewhat annoying because Windows has reasonable BIDI and Arabic support, so if Java simply passed on this text orientation information from AWT to Windows, then we could simply use AWT for our UIs, and everyone would be happy. Unfortunately, it doesn't.

In Swing, the applyComponentOrientation() method did seem to properly set the text orientation, so there's some good support for bi-directional text there. Unfortunately, for Arabic text, you also need support for text numeric shaping. Although some Arab nations use western number symbols (which, as you probably know, are called Arabic numerals, which makes things nice and confusing for everybody), most Arab nations have their own number symbols. Unicode, in its infinite wisdom, decided that these symbols will actually be encoded in character streams as western digits 0-9, but the UI will be responsible for automatically substituting in different number shapes when the characters are actually displayed. The Java graphics libraries actually have some support for numeric shaping when displaying text, but it's sort of broken. Java doesn't automatically extract region and locale information from the OS, so it defaults to guessing which numeric shapes it should use. If the string you're displaying starts with numbers, there's no initial context for the numeric shaper to use in guessing which number forms to use, so it will default to Western shapes. Also, the Java numeric shaper only reshapes numbers and forgets to reshape the decimal point and thousand separator. I tried a release candidate for Java 7, and this problem was still there. Does anybody at Sun/Oracle actually use their UI framework in real applications? Anyway, even this broken support for numeric shaping isn't actually enabled in Swing, so you can't display numbers in Arabic. In the Java 7 release candidate, programmers could manually enable Arabic numeric shaping in rich text widgets (i.e. JTextArea), but it wasn't clear whether that support was also added to other widgets like JButton or JLabel, etc. In any case, given the brokenness of Java numeric shaping, that isn't exactly a big win.

So in the end, if you want to build an Arabic GUI in Java, use SWT. Eclipse now has a free GUI builder available called Window Builder, and even though I didn't actually know any SWT, I was able to throw together a SWT GUI in a couple of hours with almost no work. GUI builders are awesome. Previously, I was always concerned that I would lose some flexibility in the code I could write, but the one in Eclipse is a real dream and saves a lot of time. I really should have paid money to buy one years ago.

Getting Type 1 Postscript Fonts from pdflatex

For the past several years, I've been using pdflatex to generate PDFs from my LaTeX, and it usually works like a charm. All modern versions of pdflatex correctly use type 1 (vector) postscript fonts and not type 3 (bitmap) fonts.

Just today, I was generating a PDF for a camera-ready, but whenever I looked at the list of fonts in the document, I kept seeing type 3 fonts there. I couldn't figure out where those type 3 fonts were coming from. I initially thought they might be from some figures, but that ended up not being the case. After playing with my document for a while, I discovered that the problem was that I was using some non-English characters, which was causing problems for LaTeX. Apparently my default installation of LaTeX had type 1 fonts that only covered the standard English character set (plus some accents). When I used characters like French guillemets quotation marks, LaTeX would need to use type 3 fonts because those were the only versions of the fonts with those characters. Using \usepackage[T1]{fontenc} did nothing since my LaTeX installation simply didn't have the necessary fonts.

Fortunately, there is a package called cm-super that seemed to contain the necessary fonts. I couldn't figure out how to coax my Fedora TexLive distribution to download this package, so I tried to grab it in Windows using MiKTeX. Unfortunately, the package is fairly large, and MiKTeX kept killing my computer while trying to download it. The download would start quickly, but gradually slow down to a crawl while my cpu utilization would go upwards. I suspected MiKTeX was doing something silly like storing the file in memory, but in a linearly expanding buffer of some sort. My Thinkpad X61t has always had heat problems, and running with high cpu usage for such long periods kept causing my laptop to overheat and die before the download would finish. Fortunately, I was able to download the packages plus some index files directly from a mirror, and get MiKTeX to load the package locally instead of from the Internet. Some people also needed to do the usual MiKTeX oddness to get things to work right afterwards.

But everything seemed to work ok once I had cm-super installed. My PDFs contained only type 1 fonts. I really don't have a strong understanding of why cm-super isn't included in my default LaTeX installation. Are the fonts too big? Is the quality of the fonts not as good as the default ones? I have no idea. But it looked ok to me, so I'm going with it.

How to Use Constructors and Do Inheritance Properly in JavaScript

With all my complaints about how difficult it is to find good documentation about how to do inheritance properly in JavaScript, I thought it might be useful to write a blog post about it, so then it would be easier (for me, at least) to find information about the topic.

Constructors

So, let's suppose you have a program, and you need to have a Student object. Students have a name and an array of courses that they are taking. The quickest way to create a Student object is to use the object literal syntax:

var student = { 
   name: 'Joe', 
   courses: [],
   addCourse: function(course) { courses.push(course); } 
};

If you need to create many Student objects, you can simply create a function that creates them for you:

function makeStudent(student_name) {
   return {
         name: student_name, 
         courses: [],
         addCourse: function(course) { courses.push(course); } 
      };
}
var student = makeStudent('Joe');

You can also use a constructor function, which essentially does the same thing:

function Student(student_name) {
   this.name = student_name;
   this.courses = [];
   this.addCourse = function(course) { courses.push(course); };
}
var joe = new Student('Joe');
var ann = new Student('Ann');
var sue = new Student('Sue');

There is a small problem with using constructors in this way. When you create many Student objects, the same name, courses, and addCourse properties show up in each Student. Everything still works, but it's not as efficient as it could be.

To make things more efficient, we need all the Student objects to share some properties instead of having separate, identical properties in each Student. For objects to share properties, we need to make use of JavaScript prototypes. In JavaScript, every object has a prototype object. When you read a property, JavaScript first looks if the property exists in the current object, if it doesn't, JavaScript then looks to see if the property exists in the chain of prototype objects. When you write to a property, the property is changed in the current object and not the prototype. Different Student objects can share the same prototype. Initially, all the properties of the prototype will appear as properties of the Student. As the Student objects change, they will get their own versions of the properties.

What all this amounts to is that prototypes are useful for describing the initial, "prototypical" view of what a certain type of object should look like. Over time, objects will change and stray from looking like the prototype, but that's fine.

For our Student example, let's first create a generic Student object that can serve as a prototype.

var studentPrototype = {
   name: 'Generic Name',
   courses: [],
   addCourse: function(course) { courses.push(course); } 
};

Now, in order to create objects that have this object as a prototype, you need to set the prototype field of a constructor function. When you create an object using the constructor, the constructor will set the prototype of the object to whatever its prototype field is set to. It can be a bit confusing. Setting the prototype field of a function does not change the prototype of that Function object. In general, JavaScript does not provide a variable where you can set or get the prototype of an object. You have to do it all indirectly by using these constructor functions.

var studentPrototype = {
   name: 'Generic Name',
   courses: [],
   addCourse: function(course) { courses.push(course); } 
};
function Student() {
}
Student.prototype = studentPrototype;

Now, when you create Student objects using the constructor, you will get objects that share a lot of fields.

var joe = new Student();
var ann = new Student();
var sue = new Student();

As you set the names of the Student objects, the prototype remains the same, but the name property of the individual Student objects will be set. This name property in the individual objects essentially "overrides" the name property of the prototype.

joe.name = 'Joe';
sue.name = 'Sue';

You can also set the name inside the constructor function, which will give the same result:

var studentPrototype = {
   name: 'Generic Name',
   courses: [],
   addCourse: function(course) { courses.push(course); } 
};
function Student(student_name) {
   this.name = student_name;
}
Student.prototype = studentPrototype;

var joe = new Student('Joe');
var sue = new Student('Sue');

Unfortunately, a problem happens though when you start dealing with courses.

joe.addCourse('math');
alert(sue.courses);

Somehow, Sue ends up enrolled in the math course, even though the course was only added to Joe. It seems that when modifying the courses property, the property of the prototype gets modified and not of the Joe object. Since all the Student objects share the same courses property of the prototype, it looks like Sue is taking math.

The problem is that the courses property of Joe is never written to. When addCourse is called, the method reads the courses property and gets an array. The "math" course is then added to this array. The array is modified, but the courses property is never written to, so Joe ends up modifying the prototype's array of courses instead of creating its own copy that isn't shared. To get around this problem, we should create a new array of courses for each Student, and assign it to the courses property in the Student constructor function.

Constructors Summary

When you want to create many objects with the same structure, you should use constructors and prototypes. You should take all the properties of these objects and divide them up into

• properties that are constant and that can be shared between different instances of an object (i.e. methods)
• properties that are unique to each object and that can be different in each object (i.e. data fields and pretty much everything that isn't a method)

Constant properties should be put into the prototype of the objects while the other properties should be set in the constructor function.

So suppose we want to be able to make multiple Student objects:

student = { 
   name: 'Joe', 
   courses: [],
   addCourse: function(course) { courses.push(course); } 
};

The method addCourse is the same between all Student objects, so it should appear in the prototype. The other properties will be set in the constructor.

var studentPrototype = {
   addCourse: function(course) { courses.push(course); } 
};
function Student(student_name) {
   this.name = student_name;
   this.courses = [];
}
Student.prototype = studentPrototype;

var joe = new Student('Joe');

Inheritance

Inheritance in JavaScript is less useful than in class-based object-oriented languages. JavaScript has a dynamic type system, so inheritance is not used to indicate which objects share the same interfaces. Inheritance is only used in JavaScript for code reuse. If you have many different objects that all have the same interface (e.g. in a graphics system, you might have objects for different shapes like lines and circles, and these shapes all understand a draw command), these objects do NOT need to inherit from the same base object unless these objects share code for implementing these interfaces.

The easiest way to think about inheritance hierarchies in JavaScript is to ignore it and to simply focus on the concept of prototypes.

Suppose we have a program that makes use of Student objects, which have the fields name and courses in addition to a method called addCoruse, as in the previous section:

function Student(student_name) {
   this.name = student_name;
   this.courses = [];
}
Student.prototype.addCourse = function(course) {
   courses.push(course);
};

Some of the students are special because take their courses via the Internet. For these students, we not only need to know their name and the courses they are taking, but also their e-mail information so that lectures and homework can be e-mailed to them. We'll use an InternetStudent object to represent these types of students.

function makeInternetStudent(student_name, student_mail) {
   return {
      name: student_name,
      courses: [],
      addCourse: function(course) { courses.push(course); },
      email: student_email,
      sendEmail: function(subject, body) { ... }
   };
}

To make a constructor for an InternetStudent, we need a prototype that serves as a good initial template for what an InternetStudent object looks like. Since an InternetStudent shares most of the properties of a Student object, we can use a Student as the prototype.

function InternetStudent() {
}
InternetStudent.prototype = new Student('GenericName');

There are two new properties in an InternetStudent that aren't in a Student: an emailfield that varies from student to student and a constant sendEmail method. The field should go in the constructor function while the method should be added to the prototype.

function InternetStudent(student_name, student_email) {
   this.name = student_name;
   this.email = student_email;
}
InternetStudent.prototype = new Student('GenericName');
InternetStudent.prototype.sendEmail = function(subject, body) { ... };

As in the section on constructors, you have to be careful when dealing with prototypes that you don't accidentally share data structures between different objects. In the above example, the courses array is shared between all InternetStudent objects because they all use the version in the prototype even though each InternetStudent should get their own separate array.

If you recall, the prototype contains all the properties of an object that shouldn't change between different objects while the constructor function initializes the properties that do change from object to object. The constructor function for Student objects creates new name and courses properties for each Student object. We can use that function to create new versions of these properties in the InternetStudent through constructor chaining:

function InternetStudent(student_name, student_email) {
   // Chain the constructor
   Student.call(this, student_name);

   // Initialize the fields that are unique to InternetStudent objects
   this.email = student_email;
}
InternetStudent.prototype = new Student('GenericName');
InternetStudent.prototype.sendEmail = function(subject, body) { ... };

var john = new InternetStudent('John', 'john@example.com');

And we're done.

Inheritance Summary

Inheritance is used for code reuse in JavaScript. In JavaScript inheritance, instead of using a plain Object as a prototype in a constructor, you create some other type of object to use as a prototype base instead.

As always with prototypes, you have to be careful not to accidentally share data structures in your objects. This is especially important when inheriting from something other than a plain Object because you may not know all of the internal data structures of the object you are inheriting from. If you are careful to initialize all non-constant data fields in your constructor functions, you can use constructor chaining to properly initialize these inherited internal data structures.

JavaScript Constructors Were a Mistake and Should Be Removed

For a long time now, I've been uncomfortable with JavaScript's syntax for constructors, but I could never quite figure out what was wrong with them. They always seemed sort of cumbersome and rigid. In fact, for most of my code, I created my objects almost exclusively using the object literal syntax instead of using constructors. The object literal syntax for creating objects simply seems so natural and spontaneous in comparison to using constructors.

JavaScript constructors simply feel like a weird hack. They're normal functions except you call them with new. In fact, all functions have extra fields for tracking prototypes that are only used when you use functions as a constructor. It also seems incongruent that JavaScript objects are not class-based and can be dynamically changed at any time, yet you're expected to put all your object construction code in one place in a single function. I would personally avoid using JavaScript constructors in all situations, but you can only make use of inheritance and reuse if you use constructors.

But constructors just end up feeling even more cumbersome once you start using them for inheritance. Theoretically, the inheritance model of JavaScript is very simple. Every object has a prototype object. When you use a property, JavaScript first looks if the property exists in the current object, if it doesn't, JavaScript then looks to see if the property exists in the chain of prototype objects. But when you actually go about trying to use inheritance in JavaScript, everything suddenly becomes really complicated. Every time I want to use inheritance, I always end up having to search on the Internet for tutorials about how to do it because it simply never sticks in my mind. There's something with the way constructors and inheritance are implemented in JavaScript that somehow makes the simple concept of prototype inheritance completely confusing to me. If you search for "JavaScript inheritance," you end up with all sorts of weird frameworks for abstracting away the inheritance process. It's actually somewhat hard to find good documentation on how to do inheritance (actually, the Mozilla docs that I linked to are very confusing as well because their description of constructor chaining is hard to grasp). I think that part of the problem is that the using constructors to create objects simply doesn't fit well with the prototype model of objects. If I'm creating an abstract base object that other things will inherit from, why do I need to create a constructor for allowing anybody to create multiple instances of that object, then use that constructor to make a single instance, and then inherit from that one instance? It just seems weird that if I want a single Employee base object that other objects will inherit from, I need to create an Employee constructor object, create the Employee, and then use this instance as a prototype in other constructor functions.

After many years of having these JavaScript issues gnaw at me, I've recently started to realize that my unease with constructors and inheritance wasn't a problem with me but a problem with JavaScript. Constructors are simply a mistake in the language and should be removed. It is, of course, impractical to literally remove constructors from the JavaScript language, but they should be deprecated, and all documentation should cease to mention them in reference to objects. JavaScript constructors attempt to impose a class-based object model onto JavaScript, but JavaScript is prototype-based, so it simply doesn't work. Because JavaScript is somewhat inspired by Java, there was an attempt to bring in some Java's object syntax into the language, but Java's constructors simply don't work in JavaScript. And I know that people really want class-based inheritance in JavaScript as evidenced by the fact that people keep trying to add class-based inheritance into JavaScript, but class-based inheritance doesn't exist in JavaScript now, so there's no point in trying to fit a square peg in a round hole. Fortunately, ECMAScript 5 has a new Object.create method that offers a reasonable alternative syntax for creating objects. This method can also be retrofitted into older versions of JavaScript as well (albeit with a performance penalty).

When using Object.create() to create objects, the code for creating an inheritance hierarchy then ends up closely matching the inheritance hierarchy itself:

Employee = {
      department : '',
      giveBonus : function(bonus) {...},
      handleVacation : function() {...},
   }

WageEmployee = Object.create(Employee, {
      wagePerHour : 10 
   });

SalaryEmployee = Object.create(Employee, {
      salaryPerYear : 50000 
   });

When you need to create multiple instances of the same type of object, you can still create a function to do that, instead of an explicit constructor.

function createSalariedEmployee(name, salary) {
   var emp = Object.create(SalaryEmployee);
   emp.name = name;
   emp.salaryPerYear = salary;
   return emp;
}

Sometimes you need to do constructor chaining in order to handle state that cannot be safely be stored in a prototype. For these situations, I would suggest having an initialization method in each object that can be chained (similar to Smalltalk conventions).

Employee = {
   __init__ : function(name) { this.name = name; },
   department : '',
   giveBonus : function(bonus) {...},
   handleVacation : function() {...},
}

WageEmployee = Object.create(Employee, {
      __init__ : function(name, wage) {
         Employee.__init__.call(this, name);
         this.wagePerHour = wage;
      } 
   });

var newEmployee = Object.create(WageEmployee);
newEmployee.__init__('John', 10);

I think this approach for creating objects is less confusing than using constructors. It's definitely a lot cleaner for singleton objects and for abstract objects. It may not be that great for flat hierarchies, where programmers want to create many instances of the same object, but it's not a big loss there either.

Scaling Up the Transitway

I was recently late for a train and had to rush across Ottawa from the west-end to the train station.Unfortunately, what is normally a quick dash across downtown on the Transitway turned into a grueling crawl. Most of the pain is entirely self-inflicted though. The Transitway buses ran on dedicated bus lanes through downtown, so the buses didn't have to weave through waves of cars. No, the problem was that there were just too many buses. The Transitway is used above its capacity, so during rush hour, the Transitway becomes a long line of bumper to bumper buses. The Transitway in downtown is just a single lane, so there's no passing of other buses, and every bus needs to stop at the bus stops, and then stop at the traffic lights, so you have to wait ages for every bus in front of yours to move forward a bit, load and unload passengers, wait at the light, and move on. If there are five buses in front of yours, you have to wait in turn for each bus to stop, board passengers, and then move on. It's brutal.

Given these capacity problems, it's clear to me that the current model for how to run buses along the Transitway through downtown just isn't very efficient any more. Ideally, more bus lanes would be provided downtown, but that isn't going to happen. The LRT through downtown will solve the capacity problems, but it'll be many years before that gets built, if ever. Until then, it would be nice if we could find some way to scale up the capacity of the Transitway a bit so that it can be used more efficiently.

I think it's time to remove the express buses from the Transitway in downtown. I know that one of the main advantages of a Bus Rapid Transit system like the Transitway is that people can take one bus from downtown and have it zip along a transit corridor, leave the corridor, and then deliver people directly to their houses. Transit users don't have to transfer, and they can time their arrivals at bus stops so that they don't have to wait around much. Unfortunately, insufficient capacity on the Transitway through downtown makes this model extremely inefficient. Traveling through downtown takes much too long, and all the traffic makes the arrival times of buses unpredictable. Previously, I've complained that Larry O'Brien's plan for having an underground downtown train line to be silly because it eliminates the advantage of express buses (i.e. no transfers) and makes it impossible for transit users to cross the city efficiently. But I'm now thinking that he might have been on to something. The capacity problems in downtown are so bad that the amount of time needed to get through downtown is beginning to outweigh the advantages of being able to take a single bus home from downtown. Having 20 different express buses all lined up with each one having to stop to let a few people on board, delaying all the buses behind it, just doesn't work. Instead, there should be single bus crossing downtown that moves people to a bus station/terminal where people can then transfer to their express buses. If there's only a single cross-downtown bus available, it would be more efficient because bus users would all simply board onto the first bus that arrives, and they'll fill the bus to capacity. There'll be no need to have a long line of somewhat full express buses inching across downtown. These cross-downtown buses could then deposit passengers off at large bus stations with bus loops where there's space for buses to stop and wait for large numbers of people to board buses. Hurdman and Bayview probably make the most sense as these bus transfer points. This proposal is similar to the initial phase of the current LRT plan in that there'll be a high capacity transit system just for downtown which focuses only on moving people to transfer points outside of downtown where people can transfer to buses for the rest of their journeys home.

It might also be possible to improve the efficiency of the downtown portions of the Transitway by having some sort of preboarding system. Other BRT systems do this, where they treat their bus systems like a subway. People have to pay before boarding a bus, and go through a turnstile into a loading/unloading zone. Then, when the bus comes, people can just jam themselves into the bus from whatever door is available since everyone in the loading/unloading zone has already paid. As a result, the loading and unloading of buses can be done faster.

HTML5 Audio is Still Too Immature to Use in Games

I made a little HTML game a year and a half ago that made some basic use of HTML5 audio, and it worked well enough, but it was very finicky, but I could see HTML5 audio eventually being useful once it matured.

Recently, I reprogrammed an old XNA game I wrote into HTML5 (I never want to go near XNA coding or the XNA community ever again), and I was hoping to program a much more extensive audio engine for the game. Unfortunately, I found HTML5 audio support to be just as finicky as before. Apparently the iPhone/iPad can't play more than one audio stream at once, meaning you can't play music and sound effects at the same time, so it's not possible to make HTML5 games that work well on the iPhone and iPad (basically, all of Apple's talk about HTML5 being superior to Flash on the iPhone and iPad was just propaganda and not reality). Firefox doesn't play short audio files, so the bips, clicks, and other sounds for button presses won't play. Chrome (and possibly Safari too) will not let you play an audio file more than once unless you serve the file from certain types of web servers. The audio in Chrome just sort of dies out after a while anyway, so you don't get any sound after a while. The Internet Explorer 9 Release Candidate seems to only support mp3 files for audio, and using mp3 files in games requires the payment of a licensing fee of $2500 to the mp3 licensing guys. So basically, it's not possible to build a very basic, reliable sound engine for HTML5 games right now.

This struck me as strange though because there are plenty of HTML5 demos and games that have extensive sound support. How can they pull off reliable sound while I can't?

They cheat, of course. All of these games make use of one of these common JavaScript sound libraries like SoundManager2. The dirty little secret is that these libraries will always use Flash for their sound unless Flash support isn't available. Flash is able to offer reliable, solid sound support across many platforms, so developers are able to build solid sound engines for their HTML5 games on top of it. If you try using pure HTML5 audio, things just fall apart.

Perhaps by this time next year, it will be possible to build a pure HTML5 game with good sound and graphics. I haven't used Firefox 4 yet, but I have high hopes for it. Until then, I think Flash is still the only viable platform for online games.

GWT Isn't a Good Environment for HTML5 Games

Last year, I made a small game in XNA. No one played it, so I've started porting it to be a web HTML5 game. Since the game was originally written in C#, I decided that the easiest way to webify it would be to rewrite the code in Java and then use GWT to translate the code into JavaScript. GWT is a set of tools from Google that let you write web code in statically typed Java. It then translates this code into cross-browser JavaScript for you.

After quickly discarding the GWT UI framework, I found GWT experience to be much smoother and much nicer than I had originally expected. Unfortunately, I've found that the current incarnation of GWT (GWT 2) doesn't work well for HTML5 games. The problem is that in development mode, GWT doesn't actually translate any of your code into JavaScript. It runs all of your code as regular Java, and then uses an intermediary layer to transfer manipulations of JavaScript objects or the DOM to a browser where the manipulation is done and the result transferred back to the Java world. Initially, I thought this wasn't a big deal because it only causes problems if you make an outrageous number of DOM API calls or decide to store a lot of things in JavaScript objects for some reason. Unfortunately, I found I was doing this alot in my HTML5 game. I was drawing lots of things to the HTML5 canvas, which requires lots of API calls. I was also using JSON for my save game data, which means you have to store a lot of data in the form of JavaScript objects.

As a result, my game code ran really sluggishly when run in development mode. This was especially true of Chrome whose sandbox design means that the Chrome GWT development plugin is particularly slow in transferring data between the browser and Java code. Doing my development with Firefox made things bearable, but I still found that I was optimizing things incorrectly. Things that seemed to be slow when running in development mode (e.g. the JSON game saving code appeared so slow that it would timeout the browser) were actually instantaneous when the code was properly compiled down to JavaScript. The overhead of interfacing Java code with a brower's JavaScript engine simply distorts performance information so much that it's hard for a developer to get a good feel for how a game behaves.

I understand why GWT is designed in this way. Most browsers don't expose JavaScript debugger APIs that would let a tool like GWT map lines and variables in JavaScript code to the original Java code that a programmer has written. Fortunately, browsers like Firefox are becoming mature enough platforms to have such APIs, so I'm hopeful that in the future, someone might reprogram GWT to actually translate Java code into JavaScript when in development mode and still let you properly debug it.

In the meantime, I'm going to finish coding up my game in GWT, and then go back to pure JavaScript games. I find the complete freeform, unstructured nature of JavaScript to be unproductive, but I'm wondering whether the static typing of Java is the best way to solve the problem. When I used to code in Smalltalk, everything was also dynamically typed, but it was a fairly productive environment to code in. Smalltalk organizes your code in a very structured way though, so it was easy to navigate the code and find things in it. Currently, the style of JavaScript code that I write is too freeform that even Eclipse with JDST can't analyze it too well and can only provide me simple ways to browse it. Perhaps I'll try writing my code in a more structured style to see if a proper code editor can extract useful structure from it, thereby allowing me to navigate and code JavaScript code more productively.

Rhino JavaScript security

My programming website programmingbasics.org contains a Java applet with a code interpreter for running user code. Users will not only run their own code, but possibly code from other people as well, meaning that they might be exposed to malicious code. The user is kept safe though because the code interpreter runs as part of an applet, meaning everything runs within the Java security sandbox.

For many years, I've been planning on making a standalone-version of my applet that can be easily downloaded and run as an application, but I've been concerned about security issues. I want user's to be able to run random code that they've found on the Internet without having to worry about the code infecting their systems with something. Without Java's applet security sandbox, my application would have to create its own sandbox. I always assumed that with Java's multiple layers of security, that I would be able to cobble something together. In the end, due to a convoluted API design, it seems that Java's security system is much less flexible than I had originally thought, meaning it's not really possible to do something like lower your own security permissions or to chroot yourself. I think the actual security mechanism in the VM could support this, but the APIs that Java exposes don't let you access such functionality.

The main security issue that I'm trying to protect against is that I want to let users run potentially malicious code in the interpreter. This interpreter has to call into my own code to access certain features. I'm too lazy to properly secure all of my own code, so I want to sandbox the interpreter code from my own code so that potentially malicious code can't muck around with the public fields of my objects and play with my inner classes to trick my code into doing something unsafe. So basically, I need a mechanism that allows me to take part of my own code, declare that I don't trust myself, and lower my permissions for that portion of code.

Based on what I can understand from the security documentation I've read, there are two primary mechanisms that Java uses to secure itself. The first is a namespace mechanism where different threads can be given access to only certain classes (or different versions of classes). This initially sounded like a great way of separating out my code from the interpreter code. My code would simply not be visible to the interpreter code, meaning that I wouldn't have to bother securing my own code. I would only have to create a hardened API for interfacing the interpreter with my own code. The second mechanism is a permissions mechanism where every class has an associated set of permissions. Whenever a potentially dangerous operation is being performed, the permission framework will go through the stack, find the class/code on the stack with the lowest set of permissions, and only allow the operation to proceed if the permissions are sufficiently high to allow it. So for my interpreter thread, as long as I could create a class with no permissions and then slip this class at the base of the interpreter thread's stack frame, then the interpreter wouldn't be able to do malicious things.

So with these two mechanisms, I could use permissions to prevent the interpreter from doing anything bad and use namespaces to prevent the interpreter from tricking my own code into doing bad things. Unfortunately, although this sounds theoretically great, I couldn't quite make the Java APIs do this for me. It seems like the API was mainly designed so that the Java VM and library could secure itself in applets. If programmers want to use the same mechanisms to secure their own code, you have to jump through a lot of hoops. The main problem seems to be that the Java VM loads the application's code with the system class loader. This means that the application code is basically considered to be as trusted and as secure as Java library code. You can't easily create a new thread with a new namespace with fewer classes and where existing classes are relabeled with lower permissions. It's probably possible to do some crazy classloader voodoo where my code is packaged in a separate jar and the interpreter is in its own jar and then a special bootstrap jar will piece together the other jars in some sort of secure way, but it's messy, hard to debug, and hard to distribute all these jars to end-users (I think this is how Java application servers do their security though).

If I spent enough time thinking about class loaders, I might be able to figure out a way to solve it, but I was able to put together a solution that presumably has similar security but doesn't require so much mental gymnastics. The interpreter I use for programmingbasics.org is the Mozilla Rhino JavaScript engine. The interpreter has a ClassShutter which restricts which Java classes that user scripts can have access to. Assuming that the Rhino interpreter is properly secured, then setting the ClassShutter to prevent access to any Java classes should prevent user code from accessing my own insecure code except through well-defined and secured APIs. This should provide equivalent security to namespaces. I still made use of the Java permissions security mechanism, but that only required me to find a way to use class loaders to load a single class with reduced security. Basically, I created a class that implemented a proxy for java.lang.Runnable and compiled it by hand. I renamed the resulting .class file to a .bin so that the system class loader wouldn't prevent my class loader from seeing the file. I then created a classloader that would intercept attempts to create that class and create a version from the .bin file instead with lower permissions. In order to make sure you use the version of the class loaded by the custom class loader (the one with reduced permissions) and not the system class loader (the one with full permissions), you have to carefully use reflection to get the class loader to load its version though. When creating the interpreter thread, I start the thread off by running this class, thereby inserting these lower permissions at the base of the interpreter's stack frame.

Getting the Rehearsal Timings for Multiple Slides in PowerPoint

When practicing a presentation, you can have PowerPoint record how much time each slide takes using rehearsal mode. Although PowerPoint shows the time for each slide in the slide sorter and in the transition information, I couldn't figure out how to get the total time for multiple slides. This is useful when you want to find out how long different sections of the presentation are so that you know if you are spending too long on certain parts. In the end, I just wrote up a quick PowerPoint macro to do it (just select some slides in the slide sorter and then run the macro to tell you the total time needed for the selected slides):

Sub TotalSlideTiming()
  Dim pres As Presentation
  Set pres = ActivePresentation

  Dim slides As SlideRange
  Set slides = ActiveWindow.Selection.SlideRange
  TotalTime = 0
  For Each s In slides
      TotalTime = TotalTime + s.SlideShowTransition.AdvanceTime
  Next s

  minutes = TotalTime \ 60
  seconds = TotalTime Mod 60

  msg = Str(minutes) + "m " + Str(seconds) + "s"

  MsgBox msg

End Sub

Public Transit in Ottawa in the Age of Cars

This blog is supposed to be mainly about coding, but for engineering-types, the efficient movement of people around a city is always an interesting puzzle, so though this blog post is off-topic, I don't think it's uninteresting (note: I'm not a transit expert; I'm just a transit fan who likes shouting out like a blowhard).

Well, anyway, now that there's a new(ish) mayor of Ottawa, there's been a lot of newspaper articles about whether the old mayor's light rail (LRT) plans should be continued or scrapped. Personally, I always thought that the old mayor was pretty dumb (or at least naive) regarding transit. It takes decades to put together transit plans and get contracts signed, so for the old mayor to cancel the original light rail contracts when he got elected was stupid. The plans may not have been perfect, but it was better than nothing, and by canceling the contracts, the mayor left the city with nothing for at least another decade (the electric light rail line proposed by the old plan sure would have been useful when gas prices went through the roof!). I always assumed that the new light rail plans proposed by the old mayor would be impractical, and everything I heard about it seemed to confirm that. But with all the talk in the newspapers, I finally took a glance at Ottawa's 2008 transportation master plan, and I can now definitively say that it's a bad plan. It's a boondoggle that will cost a fortune but not actually improve public transit at all. It was obviously designed by a car driver who took a look at some other cities, became impressed with the shiny trains and subways, and decided that Ottawa should get them too, without any thought about money, efficiency, or political realities.

The reality is that this is the age of the car. In the age of the car, trains only make sense in certain limited situations. It does not make sense to copy the transit systems of Europe because those cities were built before the age of the car. It does not make sense to copy the transit system of large North American cities because those cities are larger than Ottawa, and those cities evolved before the age of the car. Ottawa grew big during the age of the car, and it built a transit system appropriate for the age of the car with its Bus Rapid Transit (BRT) Transitway. As a result, Ottawa is now a leader in designing transit systems for the age of the car, and Ottawa can't really look to other cities for patterns to copy because most other comparable cities to Ottawa are behind it, not ahead of it. Ottawa must innovate in order to come up with appropriate solutions to its transit problems.

Cities that developed during the age of the car are notable because people live all throughout the city, and they might work all throughout the city. It's the urban sprawl model of urban development. It is true that cities in the age of the car still have a downtown core where a large minority of the population work, but it's definitely not New York where masses of people commute from the suburbs into downtown. In the age of the car, people on the east side will work in an industrial park on the west side, people in downtown will work at a shop in the south, or people in the south-end will work in the south-west. To be useful, public transit shouldn't take everyone to a central hub or to simply move people between two points--it has to be able to take a person from anywhere and move them to anywhere in a reasonable amount of time. The hub and spoke model doesn't work in the age of the car, public transit needs to provide a network or lattice that can move people from anywhere to anywhere. Buses are the most appropriate transit option in the age of the car because they can easily go anywhere in the city, and they can use dedicated busways to go long distances quite quickly. LRT is an obvious choice if you already have a bunch of unused rail lines sitting around (Ottawa dug up its rail lines a long time ago) or if you have a lot of extra money that you can splurge on indulgent infrastructure (Canada hasn't had extra money for decades). If those conditions don't hold, then you have to be a lot more strategic in when you build LRTs.

So although I love trains, you can't let the romanticism of trains influence your decisions. In reality, trains are expensive. In modern medium-sized cities, it almost always makes more sense to use buses for public transit than trains. As far as I can tell, these are the factors that must be considered in evaluating new transit projects:

1. Do the proposed lines go anywhere interesting? In particular, they should go among high density residential, commercial, and industrial districts containing people who are too poor to own cars. Some rail advocates argue that a train station magically makes a place an interesting destination. I think this is false. In the age of the car, a train station can add to the attractiveness of an area, but you can't build something from nothing. If a real estate developer has a choice between building a condominium tower in a place with good amenities and car access (which is good for the 70% of a city's population who are car drivers) or building a condominium tower in a place with nothing except for a train station (which is only good for the 30% of the population who are either prefer a lifestyle where they are within walking distance to amenities or who are too poor to own a car let alone a condo), I think they'll skip over the train station. They may build a slightly taller apartment building in a place if there's a train station there though. It's also important that transit lines go through as many interesting places as possible due to the network effect. A line going from point A to B can carry people from A to B or from B to A. A line going from A to B to C can carry people from A to B or C; or from B to A or C; or from C to a or B (that's six combinations vs. two). A line going between more locations allow for a lot more possible journey combinations, making the line a lot more useful.
2. How long is the waiting time? I think the rule of thumb is that transit riders feel that waiting for transit feels twice as long as it actually takes. So if you have to wait 10 minutes for a bus, then need to waiting another 5 minutes for a bus transfer, you'll feel like you wasted 30 minutes of your life even though you spent only 15 minutes waiting. As a result, a good transit line should minimize transfers and have vehicles that come often.
3. Capacity: a line should have enough capacity to handle the expected ridership. Trains can potentially carry more people than buses, and they can board passengers more efficiently than buses. Ottawa does have a capacity problem in the downtown area in that the roads cannot handle the number of buses that pass through the area.
4. Cost of construction: The cheaper the better. Also, exotic technology should be avoided at all costs. When you build any piece of infrastructure, you end up having to rebuild it every few decades as part of the maintenance. If you use standardized technology, you benefit from lower costs due to mass production since everyone else in the world is using the same technology. If you use exotic stuff, you have to pay elevated prices to rebuild the same custom, exotic stuff every few decades.
5. Cost of operation: the most successful transit lines are the ones that make money (in reality, I don't think any transit line in world supports themselves without subsidies or financial wizardry--though they probably pay for themselves indirectly by improving the efficiency of the economy and reducing the need to build highways). Electric trains have a lower operating costs than buses because they require fewer drivers and can hold more people. There's a bit of a trade-off needed to get this lower operating cost for a train though--you save money by running fewer trains than buses, but that means that people have to wait around longer for trains than for buses. It's not clear to me how mostly empty trains or diesel trains compare to buses in terms of costs. Again, exotic technology like hybrid buses, diesel-electric trains, etc. often end up costing more money in the long run.
6. Speed: I think the speed hierarchy is bus/streetcar, bus/tram with dedicated lanes, bus/lrt with dedicated lanes and traffic priority, busway/dedicated rail line, bus/lrt with grade separation (i.e. tunnel, trench, or elevated line), automated underground trains. As far as I can tell, trains do not go any faster than buses. The main determining factors in the speed of transit are whether a line is separated from car traffic and how many stops there are on a line.
7. Risk minimization through diversification: things go wrong, so it's useful to have a backup plan. With trains, people are always throwing themselves onto the line or whatnot, and that leads to the whole line being backed up. Buses are often useful in that you can reroute them around traffic incidents. With multiple possible routes serving an area, a transit system can more easily withstand problems such as accidents, long construction projects, blackouts, demonstrations, etc.
8. Every phase of the project must provide an incremental benefit: The reality of big infrastructure projects is that they often get canceled due to lack of money or a change of politicians. Although politicians can make 10-20 year plans, the plan usually only survives for 3-5 years. If that first phase provides significant benefits, then if you're lucky, the other phases might get funded. So each phase must be nicely self-contained and provide a benefit in and of itself.

So given these criteria, this is why I think the 2008 transit master plan for Ottawa is a waste of money:

1. Do the proposed lines go anywhere interesting? No. The proposed LRT will follow the existing Transitway line, so it won't provide access to anywhere new.
2. How long is the waiting time? Wait times will be longer, especially during its construction. Anyone crossing the city will need to make two additional transfers.
3. Capacity: the LRT should solve the capacity problems on the downtown portion of the Transitway.
4. Cost of construction: Any sort of grade separation like a tunnel will cost a fortune
5. Cost of operation: I imagine the number of passengers will be high enough that the cost of operation will be lower than running buses along the Transitway.
6. Speed: As far as I can tell, there's no reason to believe that LRTs will be faster than buses along the Transitway. Any speed-ups will be solely due to the tunnel through downtown. This tunnel will probably save about 5-10 minutes per trip that goes through downtown.
7. Risk minimization through diversification: the LRT means Ottawa is actually increasing its risks of unusual disruptions. With buses, you can reroute buses around problems. Although a tunnel will mean fewer disruptions due to traffic, the use of trains means that every time someone throws themselves onto the tracks (I imagine it'll happen once every month or two), the whole system will grind to a halt.
8. Every phase of the project must provide an incremental benefit: This is the big weakness of the plan. The proposed new LRT system only works if the whole thing gets built. If you only build the first phase, you actually end up with a worse system than you started out with. Let's say you build the LRT tunnel and then you run out of money. You've then spent a billion dollars building a train that doesn't go anywhere. Basically, you'll end up with a train that crosses downtown. Ottawa is not Toronto. There isn't enough density in downtown Ottawa to support a train that only goes from one of the downtown to the other. For people in the suburbs, you have to catch a bus for one part of your journey anyway, so it simply makes sense to stay on the bus and ride all the way to or across downtown. The only way to get them to ride the train would be to force them--bus journeys would purposely have to halt at the edge of downtown and everyone would be forced to transfer to a train. People going from the west end to the east end would have to make two transfers if not more. It's just a disaster. The LRT only works if it's long enough to stretch across the city, but I seriously doubt the funding will last that long.

So in my opinion, the proposed LRT plan involves spending two billion dollars to build a train that doesn't go anywhere new but simply cuts travel times by 5-10 minutes. Of course, if a problem develops in the plan and it isn't completed, Ottawa will instead end up with a train that increases everyone's travel times by 5-10 minutes due to increased transfers. This plan just seems like a huge risk and a huge cost with only a small possible benefit. If the risks or the costs were small, then it might be worthwhile. If the possible benefits were huge, it would also be worth it. But this plan has too many negatives. The old mayor used to claim that making transit faster would get more people to use it. This is one of those delusions by car drivers that they would switch to using transit if it could be made faster than driving. This is, of course, totally ridiculous. It's pretty much impossible to make transit faster than driving, and most people still wouldn't switch.

Of course, I have to admit that solving this transit problem is tricky. The most pragmatic plans aren't necessarily the ones that are politically feasible. I also don't have the numbers about costs and ridership, so I can't really make well-informed proposals. But in the interests of being constructive, I'll throw out some completely uninformed suggestions.

The primary transit problem that needs to be addressed by Ottawa is that the city has reached the capacity for buses in downtown. Any transit plan needs to address this problem. It would be nice if a proposed transit plan also provides other benefits, but the current system will run fine for another decade or so as long as the downtown problem is resolved. Although everyone wants to get rid of the Transitway through downtown, this is simply not an option in the next few decades. BRT is the fundamental backbone of the Ottawa transit system. If you mess with it, you might break the entire system, and that's too risky. So all planning decisions must start with the assumption that the Transitway will continue to go through downtown for the foreseeable future. Starting from that assumption quickly narrows down the number of feasible plans for solving the downtown capacity problem:

1. A grade separated busway through downtown (it doesn't have to be a tunnel--a trench or elevated line might be cheaper and less risky) should probably be enough to solve the capacity problems because you can have really long bus platforms without having to be limited by the size of city blocks and traffic lights. Travel times through downtown would also probably decrease by 5-10 minutes. This plan would be expensive though and not very glamorous, so I'm not sure that it's politically feasible to go this route.
2. A supplemental bus transit line through downtown to pull traffic off of the Transitway. Expanding the downtown portion of the Transitway into a four-lane bus highway would probably work but would never get political support. Having a second bus rapid transit line would probably also work (it would be something like buses that eventually go north or south will run along Laurier while east-west buses will continue to use Albert and Slater), but I don't think it would work politically either.
3. Any supplemental downtown transit line would have to be light rail to be politically viable. One advantage of LRT is that it's easier to drum up support for them. Car drivers would rise up in arms if you converted part of a busy road into dedicated bus lanes. But if you convert part of a busy road into a dedicated LRT, people will often grudgingly agree (though they'll mutter about Toronto streetcars the whole time). A surface light rail line would probably be sufficient because it's cheaper and the LRT only needs to serve enough capacity to bring down the Transitway bus traffic to reasonable levels. Unfortunately, a short LRT will hardly have any traffic at all--though riders might save 3-5 minutes by taking the LRT through downtown instead of riding the bus, they'll lose all that time by needing to transfer to a bus later for the rest of their journey. You need to have a long LRT to have any hope of getting reasonable ridership. There's a problem with placement of the line though. Running an LRT along the Transitway probably makes the most sense, but is probably politically infeasible because Ottawa was originally going to do this back in 2006 but it was canceled out by the old mayor. It would look bad to simply revive the old plan. One possibility is to run a LRT along Carling and then through south downtown or centretown, and then somehow possibly down Montreal road. This LRT configuration would serve underserved neighbourhoods that are good candidates for densification, which will help drum up political support for the plan. It'll be comparatively cheap as a surface rail line. It would hopefully pull traffic from the Transitway though I admit that there's no guarantee about that. It also provides a nice diversity of transportation options for people in downtown. It wouldn't be very fast though.
4. Some percentage of the traffic on the Transitway through downtown is caused by people traveling through downtown but not actually stopping there. It might be possible to pull some of the traffic off of the Transitway by developing the O-train into a proper diesel commuter train. The O-train can be extended both south past the greenbelt and north into Hull (not that anyone expects much ridership to/from Gatineau with only a single station, but until there's an actual train station on the other side of the river, no one in Gatineau is going to make appropriate transit plans that incorporate that possibility. Plus, responsibility for the O-Train can then be dumped on the NCC and outsourced). There's a bit of a risk that a commuter train will lead to more urban sprawl, making transit problems worse, but these sorts of risks are impossible to predict. It might also be worthwhile to build an experimental commuter train line that runs from Orleans, to the Via train station, to Billings Bridge, and then up to Bayview. I'm not sure if the O-train line has the capacity and signaling to handle the traffic though.
5. It might be possible to gamble that the future development of the city will lead to a change in traffic patterns as jobs and housing start distributing themselves more evenly around the city instead of having the jobs mostly be in downtown and housing mostly be in the suburbs. In that case, it makes sense to ignore the problem in downtown and focus on making sure that there is a sufficient lattice of BRT lines crisscrossing the city to allow for the efficient movement of people from anywhere in the city to anywhere. If that is the case, it might make sense to create a Transitway ring around the city (possibly two--one inside the Greenbelt and one outside).

MVC is not Elegant, It's the Only Thing that Works

I was doing some Swing programming over the summer. Although I've long been familiar with MVC concepts and although I've been doing Swing programming almost since Swing first came out, it was only this summer when I *really* started understanding MVC.

In the past, I always understood MVC in terms of "elegance." Designing UI frameworks using MVC concepts supposedly resulted in a more elegant design. One could easily change the look of a component and reuse behaviours in different widgets. Separation of presentation from data and control logic led to a cleaner design where orthogonal issues would be stored in different places in the code instead of all grouped together.

In fact, this is all wrong. People don't use MVC because it is elegant. People use MVC because for certain user interfaces, MVC is the only design that works. As such, you don't have much choice. If you have a UI design that allows for two views on the same piece of data, you need MVC (for example, if you have two word processing windows open on the same document--so when you type things in one window, these changes should be reflected in the other window as well). Once you need to support this situation in a UI, then MVC just naturally falls out.

• If you have two windows for editing the same data, you need code to let the user edit data: that's the controller.
• You need to store the data in one spot (not separately in each window) or else it will get out of sync in the two windows: there's your data model
• Finally, whenever the data changes, it needs to update both windows to reflect the changes: that's the view

Once you want to support two views of the same piece of data, the reasoning behind MVC becomes obvious. MVC is not elegant. In fact, for simple UIs that only need to support a single view on a piece of data, MVC is unnecessarily complicated. MVC exists because it is the only design that works for complicated UIs. They really should state this outright in documentation instead of rambling on about this elegance nonsense.

Double-Click Detection in IE and Other Browsers

Several months ago, I wrote some code for cross-browser support for double-click detection. It was sort of tricky to put together, so I should I have posted it, but I forgot. But here it is:

function hookIEDblClickToClickCatcher(object, handler)
{
   var isDown = false;
   var isMismatchedUp = false;
   object.onmousedown = function() { isDown = true; isMismatchedUp = false; };
   object.onmouseup = function() { if (isDown) isDown = false; else isMismatchedUp = true; };
   object.ondblclick = function() { if (isMismatchedUp) { handler.call(this); isMismatchedUp = false; } };
   object = null;
}

The general idea of this code is this. You might add an onclick handler to some HTML element in JavaScript. But then you notice that, in IE, if people click an object repeatedly (like in a game), every 2nd click counts as a double-click and is ignored. So you want to register a double-click handler and have that also trigger a click event.

The problem is that this results in too many clicks for non-IE browsers. Other browsers trigger both a click event and a double-click event on the second click of a double-click, so in total your click handler ends up triggering three times. So what you want is a way to trigger a click handler on a dblclick for IE only (but you don't want IE specific code in case IE changes its behavior in the future).

Fortunately, IE has a distinctive sequence of mouse down and mouse up events that lets you detect an IE double-click vs. the double-click of other browsers (there is no mouse-down event before the double-click event).

Data URI Test

In games, I want to use data URLs for images, but IE only supported this type of URL starting with IE8. Here is some code for testing for URI support. You supply a callback function, and it will be given a true or false value depending on whether data URIs are supported or not (the data URI used is a 1x1 transparent GIF--I couldn't really find anything smaller).

function testDataURLSupport(callbackfn)
{
  var img = new Image();
  img.onload = function() { callbackfn(true); callbackfn = null; };
  img.onerror = function() { callbackfn(false); callbackfn = null; };
  img.onabort = function() { callbackfn(false); callbackfn = null; };
  img.src = 'data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACH5BAEAAAAALAAAAAABAAEAAAICRAEAOw==';
}

Scrolling Games in JavaScript

So I'd previously tried to program a game in JavaScript with a scrolling background, and repeatedly encountered performance problems. In the background of the game was about 100 images, positioned absolutely, that had to scroll as the player moved. These images were part of a larger map involving thousands of image tiles, so not all of the images could be created in advance--images that were not visible had to be removed and new images had to be created as for map tiles coming into view.

All the benchmark information available at the time talked a lot about how innerHTML to create new objects was much faster than manipulating the DOM by hand in JavaScript. This makes sense. JavaScript is slow, but in most browsers, DOM objects are separated from JavaScript by heavy COM or XPCOM abstraction layers, so if you can minimize the number of DOM calls you make, that should make your JavaScript faster. Based on this reasoning, I initially wrote my scrolling code by erasing all my objects and creating replacements with a single innerHTML call. Unfortunately, this was really slow (too slow for most games), but I was too busy to work out a better approach.

I recently found some time to take a second look at this, and I found that the performance issues were more comlex than that. In fact, there is an overhead for manipulating the DOM, but it's actually not too bad. Creating (and to a lesser extent deleting) DOM objects involves a much larger overhead. Also strange is that IE8 is much slower than IE6 for a lot of this DOM manipulation (probably because it's properly synchronized etc.).

So the correct way to create a scrolling background is not to restrict oneself to a single DOM call. Instead, to scroll a bunch of images, it's fastest to go through each image and move each one by an appropriate amount (by using divElement.style.left = '?px'). It results in hundreds of DOM calls, but it's much faster than creating new images. I was thinking of creating some sort of complicated DOM hierarchy, so that I could move multiple images with a single DOM call, but that wasn't necessary--moving each image individually was sufficiently fast. Of course, you need to create new images and remove old ones as new areas come into view or move out of view, but the performance saved by creating fewer new HTML elements counteracts the cost of the extra DOM calls.

So some quicky benchmarks reveal that when 100 moves of around 25 tiles, 128x128 in size, in 5 pixel increments take this amount of time (in milliseconds) :

IE8 with innerHTML complete refresh of all objects	14563
Chrome with innerHTML complete refresh of all objects	5843
FF3.5 with innerHTML complete refresh of all objects	10918
IE8 with simple move elements around	1919
Chrome with simple move elements around	605
FF3.5 with simple move elements around	1691
IE8 with simple move elements and reusing old elements	1641

This means that it's probably possible to do simple games in IE8, so there's no immediate need to switch to using canvas and restricting oneself to non-IE browsers. I'm hoping that developers won't program their HTML5 games using only the canvas element because I think more traditional methods are sufficiently fast and more compatible. In fact, if I do move to use HTML5 features, I'm vaguely thinking of going with SVG, but I'll have to see how the performance evolves.

Miscellaneous Java Swing stuff

I was doing some Java Swing coding over the summer, and I found that there were a few issues that took a lot of time to figure out due to insufficient documentation, so I thought I would dicuss the solutions that I eventually found here. (Note: I started writing this post in July, but I only finished writing this post at the end of October)

One thing that has bugged me about clipboard operations is how to efficiently support an Edit menu in the menu bar with cut/copy/paste menu items. If a user selects cut, how is the UI supposed to know where to cut from? Do you need to write some sort of crazy handler that tracks which UI widget last had input focus, and then if that widget supports cut operations, perform the cut there? In fact, Swing has classes to do this. If you only support cut&paste operations in text widgets, then there's a TextAction class you can use. I think if you want to support more than text widgets, you might be able to use TransferHandler.getCutAction()---though I haven't investigated this second option too deeply, but I think it automatically performs a cut operation on the last widget that supports clipboard operations through a TransferHandler interface.

Another thing that bugged me with Swing is that in the Windows Look and Feel, the JTextArea defaults to using a fixed size font. This is a little bizarre because the AWT TextArea doesn't use a fixed size font, and the JTextArea using the default look and feel doesn't use a fixed size font. I would normally just set the font of a JTextArea to something else, but I couldn't find sufficient information in Swing about how to do this properly. In order to change the font, you need to specify a font size, but what size is appropriate? You can't use a "reasonable" value like 12pt, because the user might have configured their OS to use extra large fonts. Operating systems usually provide an area where you can look up information about which default font should be used in user interfaces, but it seemed like Swing didn't provide access to such information. In the end, the best compromise I could find was to grab the font used in JTextField widgets and apply them to the JTextArea. Presumably, Swing will configure JTextField widgets to use an appropriate font based on a user's settings, so applying this information to a JTextArea will give you a reasonable default. It's not a great solution, but it will have to do until this bizarre JTextArea problem is fixed (it's been there for many, many Java versions though, so I doubt it will be fixed any time soon) or until Java comes with a default look & feel that isn't so confusing and disorienting (even I have problems using the file dialogs in the default metal l&f).

Another thing that I had a hard time finding in the Java documentation is how newlines/linebreaks are handled in a JTextArea. Do they use the platform defaults? If you save the contents of a JTextArea to a file, do you have to manually convert between CR, CR/LF, and LF in order to get things in a neutral format? This is all nicely documented, but it is stored in an unusual spot.

Finally, the last Swing issue that took me a long time to figure out was how to support a JTextArea that you can resize horizontally, but which will grow vertically as you type into it. So for the purposes of word-wrapping, it behaves like it has a fixed width, but you should still be able to change that width by resizing the window. A normal understanding of the Java UI layout model suggests that this isn't possible. The preferredSize()/size()/minimumSize()/maximumSize() model can't handle things that sometimes have a fixed width but expand downwards, but sometimes lets you change the width, resulting in a different height for the widget. In fact, if you code up a JTextArea with no scroll bars but with a layout manager that can control the width of the widget, it works fine. Apparently, Java has various hacks for supporting this sort of setup, so it just works.

Upgrading from Windows Vista to Windows 7

I recently did an upgrade from Windows Vista to Windows 7, and I encountered a few difficulties with the install process, which I documented here.

Windows Mail is Missing

In Windows 7, they removed Windows Mail. Although Windows 7 can still run the Windows Mail program, the upgrade process will uninstall Windows Mail, which is somewhat annoying (I'm not sure where the Windows dev team started having the great idea of uninstalling functionality that was working fine before the upgrade, but I think the new Windows team has some weird priorities that previous Windows teams didn't seem to have).

During the upgrade process, Windows 7 will tell you that it will keep your old Windows Mail settings around, and it will be easy to install Windows Live Mail Desktop later. This is untrue. Windows Live Mail Desktop will automatically import your old Windows Mail settings only if it detects that you have Windows Mail. Of course, Windows 7 uninstalls Windows Mail, so Windows Live Mail Desktop will not automatically import your old settings. So if you use Windows Mail in Vista, you should install Windows Live Mail Desktop FIRST, have it pick up all your old settings, and then upgrade to Windows 7 SECOND.

If you didn't do this, then you have to manually re-enter your account settings, then import your old mail from C:\Users\[userid]\AppData\Local\Microsoft\Windows Mail, and then go into contacts to import your old contact list from Windows Contacts.

East Asian Handwriting Recognition

The whole reason I upgraded to Windows 7 was because the Chinese Handwriting Recognition was a little flaky. It didn't integrate properly with Internet Explorer and Google (it kept losing focus and changing its language), and it was hard to resize the input panel, etc (it, oddly, seemed to work fine in Firefox though). I was hoping that they finally fixed this problem in Windows 7. And they did. They removed East-Asian Handwriting Recognition support from Windows 7. Instead, they want me to shell out an extra $150 for Ultimate in order to get access to this feature, which they removed during my upgrade to Windows 7. To the product manager who earned a nice bonus for thinking of this way to increase Microsoft's revenue: "Thanks a lot, asshole." I remember a time when Microsoft was mean and dangerous, but at least they would try to do right for their customers. Nowadays, their main areas of innovation seem to be finding fiendish ways to increase revenue.

Fortunately, Windows 7 still includes limited East Asian handwriting recognition in the IMEPad (to be removed in Windows 8, no doubt). And it seems to work more reliably than in Windows XP or Windows Vista. The instructions for enabling the Chinese handwriting recognition in IMEPad are the same as for Vista.

No Going Back

I was so annoyed with losing all this functionality during the upgrade that I was going to revert my upgrade back to Windows Vista. Windows has a long history of allowing you to undo even really invasive Windows upgrades (e.g. you can uninstall Windows XP and revert back to Windows 95 after such an upgrade). But, apparently, they stopped providing this functionality ever since Sinofsky took over the Windows Vista team (it might also be related to Windows Activation). So I'm stuck with it. I'm starting to think this will be the last Windows upgrade that I will ever do though, so I'm not too annoyed.

PowerPoint 2007 VBA Macro for Expanding Custom Animation into Multiple Slides (for Export to .PDF)

When I make presentation slides, I like using a lot of diagrams to explain algorithms, and often I use animations to show the different processing stages of these algorithms. In the past, I would just make a different slide for each stage in an animation sequence, but this gets tedious when I have to make lots of edits to a slide (I then have to go back and change all the slides in the animation sequence). So I started using the custom animation feature of PowerPoint, but when PowerPoint exports a presentation or prints notes, it sticks all of the animation elements on a single slide, so it's not possible to follow the animations in an exported presentation. This is especially important when exporting to PDF so that I can put my presentation online or so that I can have a backup copy of the presentation around in case there are portability problems with PowerPoint.

There were a couple of scripts online for doing this (here and here), but I wanted to write my own because one of them came with an installer, which I don't like, and the other one seemed too limited. Figuring out how to write my script ended up being more difficult than I expected though. I've programmed a few things in Visual Basic for Applications (VBA) before--the standard way to write macros for Office--but I vaguely remembered that when designing Office 2007, Microsoft said that it would be phasing out VBA in subsequent versions in preference for Visual Studio .Net. In fact, the record VBA macro feature (a common technique people use to program initial macros) wasn't even included in PowerPoint 2007. Programming things in .Net is a bit of overkill when you just want to write a little macro that's easy to distribute, so that wasn't feasible either. I thought about writing a little VBScript or JavaScript/JScript script that would do what I wanted, but then I found out that Microsoft was deprecating the whole ActiveScripting framework as well. Since the new Office file format OOXML is supposedly XML, I thought about just reading in and modifying the files directly, but after playing with the files a bit, I found that OOXML is very much an XML dump of the legacy Office file formats. There are all sorts of crazy cross-links between the different sub-files inside an OOXML zip file that it's impossible to read and modify a small part of the file without breaking it. In order to modify it properly, you really need to read and parse the whole thing into an intermediate form, modify it there, and then write a new file from scratch, but this is clearly too much work for a little script. I briefly considered making my presentation in OpenOffice instead, and I actually would have if the OpenOffice people had bothered to add in a couple of extra features into their application instead of simply making a brain-dead clone of Office (e.g. like being able to animate the color changes of individual words of text instead of being restricted to paragraphs only), but I was beginning to like the automatic text sizing and animation number indicators of PowerPoint 2007.

After much digging around though, I found out that Microsoft had changed their mind and decided not to deprecate VBA after all. Starting with Office 14 / Office 2010, Microsoft has renewed their commitment to maintaining VBA. So I wrote a little VBA script to split up an animation into multiple slides. I believe my script handles all entrance and exit animations, but I haven't really tested this. It makes use of Office 2007's new API for exposing the different sub-parts of an animation, which should allow a script to handle new animations in a more uniform way. Unfortunately, this new API is still somewhat broken, so it needs various error-handling code to handle anomalies like SetEffect objects without any properties etc.

To use the script, go into PowerPoint 2007, go to View...Macros, create a new macro called "ExpandAnimations", replace the macro code with the code below, and then run it.

Private AnimVisibilityTag As String


Sub ExpandAnimations()
AnimVisibilityTag = "AnimationExpandVisibility"

Dim pres As Presentation
Dim Slidenum As Integer

Set pres = ActivePresentation
Slidenum = 1
Do While Slidenum <= pres.Slides.Count
Dim s As Slide
Dim animationCount As Integer
Set s = pres.Slides.Item(Slidenum)

If s.TimeLine.MainSequence.Count > 0 Then
    Set s = pres.Slides.Item(Slidenum)
    PrepareSlideForAnimationExpansion s
    animationCount = expandAnimationsForSlide(pres, s)
Else
    animationCount = 1
End If
Slidenum = Slidenum + animationCount
Loop
End Sub

Private Sub PrepareSlideForAnimationExpansion(s As Slide)
' Set visibility tags on all shapes
For Each oShape In s.Shapes
oShape.Tags.Add AnimVisibilityTag, "true"
Next oShape

' Find initial visibility of each shape
For animIdx = s.TimeLine.MainSequence.Count To 1 Step -1
Dim seq As Effect
Set seq = s.TimeLine.MainSequence.Item(animIdx)
On Error GoTo UnknownEffect
For behaviourIdx = seq.Behaviors.Count To 1 Step -1
    Dim behavior As AnimationBehavior
    Set behavior = seq.Behaviors.Item(behaviourIdx)
    If behavior.Type = msoAnimTypeSet Then
        If behavior.SetEffect.Property = msoAnimVisibility Then
            If behavior.SetEffect.To <> 0 Then
                seq.Shape.Tags.Delete AnimVisibilityTag
                seq.Shape.Tags.Add AnimVisibilityTag, "false"
            Else
                seq.Shape.Tags.Delete AnimVisibilityTag
                seq.Shape.Tags.Add AnimVisibilityTag, "true"
            End If
        End If
    End If
Next behaviourIdx
NextSequence:
On Error GoTo 0
Next animIdx
Exit Sub

UnknownEffect:
MsgBox ("Encountered an error while calculating object visibility: " + Err.Description)
Resume NextSequence
End Sub


Private Function expandAnimationsForSlide(pres As Presentation, s As Slide) As Integer
Dim numSlides As Integer
numSlides = 1

' Play the animation back to determine visibility
Do While True
' Stop when animation is over or we hit a click trigger
If s.TimeLine.MainSequence.Count <= 0 Then Exit Do
Dim fx As Effect
Set fx = s.TimeLine.MainSequence.Item(1)
If fx.Timing.TriggerType = msoAnimTriggerOnPageClick Then Exit Do

' Play the animation
PlayAnimationEffect fx
fx.Delete
Loop

' Make a copy of the slide and recurse
If s.TimeLine.MainSequence.Count > 0 Then
s.TimeLine.MainSequence.Item(1).Timing.TriggerType = msoAnimTriggerWithPrevious
Dim nextSlide As Slide
Set nextSlide = s.Duplicate.Item(1)
numSlides = 1 + expandAnimationsForSlide(pres, nextSlide)
End If

' Apply visibility
rescan = True
While rescan
rescan = False
For n = 1 To s.Shapes.Count
    If s.Shapes.Item(n).Tags.Item(AnimVisibilityTag) = "false" Then
        s.Shapes.Item(n).Delete
        rescan = True
        Exit For
    End If
Next n
Wend

' Clear all tags
For Each oShape In s.Shapes
oShape.Tags.Delete AnimVisibilityTag
Next oShape

' Remove animation (since they've been expanded now)
While s.TimeLine.MainSequence.Count > 0
s.TimeLine.MainSequence.Item(1).Delete
Wend

expandAnimationsForSlide = numSlides
End Function


Private Sub assignColor(ByRef varColor As ColorFormat, valueColor As ColorFormat)
If valueColor.Type = msoColorTypeScheme Then
varColor.SchemeColor = valueColor.SchemeColor
Else
varColor.RGB = valueColor.RGB
End If
End Sub


Private Sub PlayAnimationEffect(fx As Effect)
On Error GoTo UnknownEffect
For n = 1 To fx.Behaviors.Count
Dim behavior As AnimationBehavior
Set behavior = fx.Behaviors.Item(n)
Select Case behavior.Type
    Case msoAnimTypeSet
        ' Appear or disappear
        If behavior.SetEffect.Property = msoAnimVisibility Then
            If behavior.SetEffect.To <> 0 Then
                fx.Shape.Tags.Delete AnimVisibilityTag
                fx.Shape.Tags.Add AnimVisibilityTag, "true"
            Else
                fx.Shape.Tags.Delete AnimVisibilityTag
                fx.Shape.Tags.Add AnimVisibilityTag, "false"
            End If
        Else
            ' Log the problem
        End If
    Case msoAnimTypeColor
        ' Change color
        If fx.Shape.HasTextFrame Then
            Dim range As TextRange
            Set range = fx.Shape.TextFrame.TextRange
            assignColor range.Paragraphs(fx.Paragraph).Font.Color, behavior.ColorEffect.To
        End If


    Case Else
        ' Log the problem
End Select
Next n
Exit Sub
UnknownEffect:
MsgBox ("Encountered an error expanding animations: " + Err.Description)
Exit Sub
End Sub

Transportation Simulation Games

When SimCity 4 was released, I was very disappointed by the broken transportation model, the assumptions built into underlying economic model that resulted in all cities looking like California, and the weird game design that assumed I was more interested in building stories about Sims than about building stories about the city itself. Since then, I became interested in figuring out how the simulations in these games work, but I always got hung up on a small mathematical detail. I finally figured out the problem a couple of weeks ago. Some simple grade 11 math is all you need, but I just couldn't see it until now.

The most intuitive scale to model these simulations at is at the level of individual people. So for each "person" in the city, you code up a model for the person's preferences and behaviour, and you then "run" this model and record what happens. So if a person wants to drive along a road from one building to another, you then increment the traffic on that road segment to account for the person's car. If you simulate enough people, you can figure out the traffic along each street, resulting in a simulation for the entire city.

The problem is that the city is constantly changing and the people being simulated will change their behaviours, so you want to have the simulation running constantly to take these changes into account. This makes the simulation complicated. If your simulator decides that a person will take an alternate route to get to a destination, the simulator needs to reduce the traffic along the old route of the person (since the person no longer drives on those roads) and increase the traffic along the new route. Keeping track of the routes of all these people is complicated, memory-intensive, and slow. If you don't remove the person's traffic from the old route though, then the traffic along the old route will keep on increasing (since there's no way for the traffic to go down to reflect the fact that fewer people are using it).

One solution is to divide your simulation into rounds. In each round, you simulate the actions of all the people in the city once, record the result, and update the UI with these results. Then you start a new round by discarding all the results (i.e. set the traffic of all roads to zero) and running a complete cycle of the simulation again. This approach isn't satisfactory because one cycle of the simulator might take several minutes to complete. So if you change something in the city, it might take several minutes to see the effect of these changes in the simulator because the UI won't be updated until the next simulation cycle.

We want to constantly update the traffic values, but this results in traffic growing without bounds. Resetting the traffic to zero is not practical because we want to be able to display the simulation values as they are updated. What we need is some way to "decay" the traffic along road segments over time. As a result, the traffic along each road segment will constantly decrease, but as you simulate the actions of different people, the traffic along each road segment will increase again. For this to work though, the speed of the decay must be balanced out the speed at which you add new traffic, so that the simulation converges to reflect the correct traffic along a certain road. But I could never figure out the math for this problem. If traffic decays too quickly, then the traffic will be close to zero in most places, but will spike up randomly in places where the new routes of people are being simulated. If traffic decays too slowly, then the total traffic along each road will increase without bound.

Simulating transportation always results in new traffic being accumulated in an additive fashion. i.e. As you simulate the route of one person, the traffic along the route will be incremented by a constant to reflect the traffic of this one person. But the decay must be in the form of a rate. The traffic along a route cannot be decreased by a constant all the time, but by a percentage of its existing traffic (because heavily trafficked routes should have their traffic decreased by a larger amount than lightly-trafficked routes--otherwise the traffic on light routes will fall to zero while the traffic on the heavier routes will increase without bound). Previously, I tried to think of things as being like a physics simulator where the simulator would try to balance things out so that the amount of traffic added by the simulator will be counter-balanced by removing an equivalent amount of traffic due to decay or something like that, but this isn't quite the right thing to do.

In fact, the solution is the geometric series. For example, assume that you don't change your city at all, so that the simulation should converge to a steady-state. So if you simulate all the people in the city, the same amount of traffic will be added will be added to a particular road segment (say, a). If you decay the traffic on any particular road segment by a rate r (let's assume you apply the decay once every time you do a complete simulation cycle of all the people in the city), then over time, this results in a geometric series. Geometric series will converge to a/(1-r). This is exactly what we need! We don't have to fiddle with balancing the rate of new traffic with old traffic or whatever--the geometric series shows that the simulation will converge to nice stable values. And we can then scale a and r to get the convergence rate and overall stability that we want. It all becomes nicely straight-forward.