Monday, December 03, 2007

Tiles Don't Generalize

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

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

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

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




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



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

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

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

Friday, September 14, 2007

Resolution Independence in Vista

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

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

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

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

Saturday, February 17, 2007

Serializing Signals without Atomic Compare and Swap

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

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

Here's the pseudocode for the event wrapper function:


globals root, queue
if root == null
root := true
execute own handler
root := null
while !queue.empty()
root := true
queue.dispatch()
root := null
else
queue.add(self)
And here's the pseudocode for the queue methods:


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

queue.empty()
globals isClaimed[], start
return isClaimed[start]==null

queue.dispatch()
globals isClaimed[], handlers[], start, end, queueLength
if isClaimed[start] != null
myend := end
if myend == start
myend++
if myend >= queueLength
myend := 0
end := myend
execute handlers[start]
handlers[start] := null
isClaimed[start] := null
start ++
if start >= queueLength
start := 0
And here's how you could code it up in JavaScript. Basically, I define a handler function. You can then use the handler function to wrap your own event handlers before setting them to listen for events:


<script>
// Initialization script that creates the "handler" function for wrapping
// handlers
(function () {
var SIZE = 100; // max number of simultaneous events
var root = false; // boolean, indicating whether
// event handler is the first one in a
// chain or not
var queue = new Array(SIZE); // Event handlers to be executed later
var thisQueue = new Array(SIZE); // Corresponding this objects
var isClaimed = new Array(SIZE); // reserves a spot in queue
var start = 0; // position in queue circular buffer
var end = 0;

// Define the global handler wrapper function
handler = function(eventHandler)
{
return function() {
if (root == false) {
root = true;
eventHandler.call(this);
root = false;
while (isClaimed[start] != null)
{
root = true;
if (isClaimed[start] != null) {
var myend = end;
if (myend == start) {
myend++;
if (myend >= SIZE) myend = 0;
end = myend;
}
queue[start].call(thisQueue[start]);
queue[start] = null;
thisQueue[start] = null;
isClaimed[start] = null;
start++;
if (start >= SIZE) start = 0;
}
root = false;
}
} else {
var myend = end;
while (true) {
if (isClaimed[myend] != null) {
myend++;
if (myend >= SIZE) myend = 0;
continue;
}
isClaimed[myend] = true;
if (queue[myend] != null) continue;
queue[myend] = eventHandler;
thisQueue[myend] = this;
break;
}
end = myend;
}
};
}
})(); // Execute the initialization code

function loaded()
{
alert('loaded ' + this.src);
}

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

Asynchronous Callbacks in IE6 JavaScript

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

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

<script>
function loaded()
{
alert('loaded ' + this.src);
}

var img1 = new Image();
var img2 = new Image();
img1.onload = loaded;
img2.onload = loaded;
img1.src = "test1.png";
img2.src = "test2.png";
alert('done')
</script>
I believe this problem was corrected in Internet Explorer 7 because if you run the same code in IE7, you only get one dialog box showing up at a time.

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