Archive for July, 2009

ScummVM month



“Indiana Jones and the Fate of Atlantis” on Android

I installed the ScummVM (Wikipedia) on my Android phone and put a couple of games on it: they work great. For people not familiar with the ScummVM, it’s a virtual machine created by Ron Gilbert at Lucas Arts to factor out some of the tedium associated to the creation of adventure games in a library. Of course, the concept of virtual machines was not new even back then (around 1987) but the idea of creating such a machine for adventure games was quite innovative at the time and the VM was used in the following years to create about twenty different games.



ScummVM on Android

The ScummVM was ported on a dizzying array of platforms and operating systems, including Android recently, by Angus Lees. Once I had the machine running on my phone, I couldn’t resist installing it on my laptop as well. The good thing about the VM is that it doesn’t matter which platform the game runs on: you can just copy the data files to your computer, point your native ScummVM to it and you’re in business.

I have a lot of fantastic memories associated with the ScummVM, back when the days when adventure games were popular, and in particular, Indiana Jones and the Fate of Atlantis, shown above on my Android phone.

My second favorite game, and one of the most difficult adventure games I have ever played is “Zak Mc Kracken and the Alien Mindbenders”. This game is hard and some of the puzzles are downright in the “Are you kidding me?” category. This was an early ScummVM game and the interface didn’t really help either (for example, there was no support for hovering, you had to click on an object to find out if it was active) but it has an epic feel in the various continents and puzzles it submits you to, and of course, the ever present humor that is a staple of most Lucas Arts ScummVM games.



“Zak McKracken and the Alien Mindbenders” on Mac

And of course, my number 1 favorite ScummVM game of all times is… The Secret of Monkey Island, which is coincidentally making the video game news in two areas: Lucas Arts just released a “remastered” edition and also a new series based on it is beginning.

The remastered version is a complete rewrite of the original game. This new version is native, not a ScummVM game, and interestingly, it lets you switch between the old and the new version on the fly by pressing on F10, so you can see for yourself how the new game compares to the original one:



“The Secret of Monkey Island” (original version)



“The Secret of Monkey Island” (new edition)

If you have never played any of the Monkey Island games, I strongly recommend spending $10 and downloading this new edition on Steam (Windows only, unfortunately).

And for people who still enjoy the quirky humor and the overall relaxing and piratey impression that permeates the entire series, Lucas Arts is releasing a brand new Monkey Island game in the form of five short stories. The first episode is available today on Steam under the name “The Launch of the Screaming Narwhal”:



“The Launch of the Screaming Narwhal” on Windows

I just started playing it but I have a feeling that the puzzles have taken a Myst-like tone that is going to be challenging but probably exhilarating to solve.

Happy ScummVM month!

Splitting the atom is hard, splitting strings is even harder

I always seem to underestimate how much readers of this blog enjoy a good coding challenge. A few days ago, one of my coworkers was tripped by a line of code and I thought I’d share his confusion with people following me on Twitter, which turned out to be a fitting medium for this micro challenge:

Pop quiz: "abc.def".split(".").length should return...?

I really didn’t think much of it but I got much more responses than I anticipated. A lot of them were incorrect (hey, if I throw a challenge, there has to be a trick), but I still want to congratulate everyone for playing the game and answering without testing the code first. That’s the spirit!

A few people saw the trap, and interestingly, they pointed out that I must have made a mistake in the question instead of just giving the correct answer (“You must have meant split(“\\.”)”).

As hinted above, the trick here is that the parameter to java.lang.String#split is a regular expression, not a string. Since the dot matches all the characters in the given string and that this method cannot return any character that matches the separator, it returns an empty string array, so the answer is “0″.

This didn’t stop a few people from insisting that the answer is “2″, which made me realize that the code snippet above happens to be valid Ruby code, a pretty unlikely coincidence. So to all of you who answered 2 because you thought this was Ruby, you were right. To the others, you are still wrong, sorry :-)

The bottom line is that this method is terribly designed. First of all, the string confusion is pretty common (I’ve been tricked by it more than a few times myself). A much better design would be to have two overloaded methods, one that takes a String (a real one) and one that takes a regular expression (a class that, unfortunately, doesn’t exist in Java, so what you really want is a java.util.regex.Pattern).

API clarity is not the only benefit of this approach, there is also the performance aspect.

With the current signature, each call to split() causes the regular expression to be recompiled, as the source sadly confirms:

public String[] split(String regex, int limit) {
return Pattern.compile(regex).split(this, limit);
}

Since it’s not uncommon to have such parsing code in a loop, this can become a significant performance bottleneck. On the other hand, if we had an overloaded version of split() that accepts a Pattern, it would be possible to precompile this pattern outside the loop.

Interestingly, that’s how Ruby implements split():

If pattern is a String, then its contents are used as the delimiter when
splitting str. If pattern is a single space, str is split on whitespace, with
leading whitespace and runs of contiguous whitespace characters ignored.

If pattern is a Regexp, str is divided where the pattern matches. Whenever
the pattern matches a zero-length string, str is split into individual
characters.

But there is a catch: since Ruby is dynamically typed (which means it doesn’t support overloading either), the determination of the class of the parameter has to be done at runtime, and even though this particular method is implemented in C, there is still an unavoidable performance toll to be paid, which is unfortunate for such a core method.

The conclusion of this little drill is that if you are going to split strings repeatedly, you are better off compiling the regular expression yourself and use Pattern#split instead of String#split.