Here’s the second part of the story behind Lakbayan. You should also read the first part or the launch blog entry if you haven’t done so.

Warning! the following content is quite geeky and technical. I’ve tried to describe things in layman’s terms as much as possible, but some reader knowledge about the Web is assumed. Read at your own risk!

Generating the map

Generating the “footprint” Philippine map is the most technically-sophisticated part of the whole Lakbayan application. If you’re familiar or have had experience building web applications, the technical workings of the other parts of Lakbayan should be quite easy to figure out. For the record, Lakbayan is completely written using the common Perl-CGI architecture.

Anyway, the important things I considered when planning how to construct the map-generating program are listed below (although I wasn’t consciously aware about all of these things when I implemented Lakbayan).

• disk space

• CPU usage

• bandwidth

• aesthetics

• flexibility / upgradability

• ease of use / virality

Regarding disk space, of course I don’t want to use up my web hosting account’s disk space. For CPU usage, I didn’t want to generate my map using a computationally-intensive algorithm since my website’s on a shared server so the map-generation should be simple and efficient. Like disk space, I also don’t want to use up my account’s limited bandwidth.

In terms of aesthetics, I was turned off by the generated maps of the Visited Countries website, so I resolved to produce maps that look good. For flexibility and upgradability, it should be easy to modify the map-generating program to add new territories, for example. As for ease-of-use, displaying the map on one’s website or blog should be as painless as possible.

In Lakbayan, there are two possible ways to let the users show their maps on their websites and blogs. First is to force them to save their maps and upload them to their own accounts. Second is to just give them an HTML code which displays the map straight from my website.

The first solution is excellent in terms of disk space (no generated maps are stored on my website, of course), CPU usage and bandwidth (the cost is only once per user). The problem is that it sucks on ease-of-use big time. I’m willing to bet that Lakbayan wouldn’t go as viral as it did if I forced users to save and upload their maps themselves. So I had to go with the second solution in order to maximize the virality of Lakbayan.

The challenge now is to make sure that I minimize disk space, CPU usage, and bandwidth while maintaining good looks and flexibility.

In my original idea, I focused on aesthetics more and so I planned to generate the map by manipulating a base Scalable Vector Graphic (SVG) image. Since SVG images just contain text (XML) that describes the elements of the image, it would be an easy task to modify the image elements that comprise each Philippine location by just changing their color information. Then the SVG must be converted to a PNG or GIF image since the most web browsers (i.e., IE) couldn’t display SVG images. The converted maps are to be anti-aliased so they look good.

Unfortunately, generating maps this way is too CPU-intensive (converting SVG to GIF or PNG is relatively inefficient). This means that I should cache each generated map to minimize CPU usage. Of course, this takes up disk space so I planned to use caching with expiration mechanisms to minimize both disk space and CPU usage. Tweaking the SVG-conversion parameters will take care of the balance between aesthetics and bandwidth (the more pretty the map, the bigger the file size, which eats up bandwidth).

Well, I wasn’t able to find a nice SVG-to-PNG converter (like the one used in Wikipedia) that I can try in my web hosting account and so I went with my back-up plan of manipulating the color palette of a GIF image. This is the technique used by the Visited Countries website to generate their maps.

How does this work? Well, GIF images are 8-bit images. This means that every pixel in the image points to one of 256 predefined colors in the GIF’s color palette. So if you manipulate, say, color #16 in the palette, you change the color of every pixel that points to color #16. So my blank map actually contains 160 different colors for each territory plus several others (for the sea and the labels). And the territory colors are all initially set to white before being modified into various shades of blue. (This technique also puts a limit on the number of territories that I can have on the map.)

Because modifying the GIF’s palette is so much simpler than converting from SVG to PNG and thus won’t consume much CPU resources, I can afford to generate each map on demand. I don’t have to cache the maps anymore thus saving myself a lot of disk space.

If you’ll notice the URL for the map image, there’s a really long alphanumeric code. This is actually an encoded version of the visited places that is already rearranged into the palette order of the base GIF image. With just a few processing steps, I am able to extract the bits and bytes comprising the palette data and simply insert it into the base GIF image. This is a vast improvement over the method used by the Visited Countries website where the URL pointing to the map is not an ordered version of the visited countries and thus will take a few more steps before the palette data is computed. With my coded version the problem of CPU usage is drastically improved.

One problem with this GIF image trick is that the map is bound to be ugly because it’s pixellated and is not smoothed nor anti-aliased. I minimized this “ugly” effect by using subtle and cool colors leading me to settle on the current gray and blue color scheme. The map produced by the Visited Countries website is, on the other hand, really quite ugly because the red is too bright and the blue is too saturated. They should’ve chosen more neutral colors so that the red and the blue don’t clash as much. So, aesthetics for Lakbayan, ok!

Since we’ve nicked the ease-of-use problem earlier, the only problem I have now is bandwidth. Unfortunately, I underestimated the bandwidth I might use and so I overshot the bandwidth limit of my web hosting account. It’s a good thing that when I informed my web hosting provider about the impending bandwidth doom, they gave me a free temporary bandwidth boost! (Thanks Dreamcode Web Hosting!) I also mitigated the problem by offloading some of the load to my other web hosting accounts. I haven’t tried using the caching features of the web protocol (HTTP) so that’s a new avenue for improving the bandwidth problem.

The Visited Code

The visited code is that long string of small letters that you may have noticed in the URL pointing to the map image. As I mentioned in the previous section, this is an encoded version of the places you have visited arranged in the GIF palette order. This code also provided a handy tool for me to implement a “save” feature.

If you have read the Lakbayan results page, you should be able to notice that there’s a link to let you update your Lakbayan map. And not surprisingly, the same code used to call the map is the same code that let’s you update it. Neat, no?

This is the reason why I can’t currently grant Jazzy’s request in the comments to minimize the code to be pasted, the “map ID,” which is just the visited code, in particular. The Lakbayan application is completely stateless with respect to its visitors—all the information is stored in the URLs.

In the future, it’s possible that I can add user accounts so that the visited code can be stored on-site and only a little HTML needs to be pasted in one’s blog. This also makes it possible to “widgetize” Lakbayan.