My wife and I enjoy playing games together, specifically games that involve solving puzzles. We particularly enjoyed Safecracker for the Wii, a good example of the genre niche that we like: a “pass the controller” interface that allows us to sit together while we play, and puzzles with some mathematical meat to them, with solutions that involve at least some ingenuity and not just tedious systematic brute force search. Plot and atmosphere don’t hurt, but if you have played Safecracker, then you know neither are necessarily high on our list of priorities.
We brought home a game this evening to try out called Mystery Legends: Sleepy Hollow. It has also been fun, but of a different and unexpected sort. The game is, I think, really for kids, and is essentially an “I Spy”-type “find the hidden objects in the scene” game. There are a few puzzles sprinkled throughout, but these are also not really challenging. In summary, it wasn’t what we were looking for, but it’s a fun way to spend time together anyway.
So where am I going with this? Well, as we played the game, I noticed that when we saw an object in the scene, and clicked the mouse on the object to identify it, we had to click directly on the object… but we could click on any part of the object, no matter how oddly shaped it might be. In fact, whenever you click on an object, the game briefly highlights its irregular outline, suggesting the very specific “interior” set of pixels that comprise the object.
How does this work? That is, when the software detects a mouse click at a particular location on the screen, how does it determine whether the click is on an object, and if so, on which object? I encountered exactly this problem not long ago, while implementing my computer version of the board game Carcassonne. However, I suspect that the solution in that case was different than the approach used in Sleepy Hollow.
In Carcassonne, the window displays a 3D perspective view of the tiles and “meeples” on the board. When clicking (or even passively moving) the mouse in the window, it is necessary to transform the mouse position from 2D window pixel coordinates to the 3D coordinates of the corresponding location on the virtual tabletop on which the tiles make up the board. This is a pretty standard technique, effectively “ray tracing” from the mouse position in the window viewport back “into” the 3D virtual world coordinate frame. It is so standard, in fact, that there is a function in the OpenGL API, gluUnProject, that does most of the math for us.
There is at least a little still to think about, though; in particular, a location in window coordinates maps to an entire line in world coordinates, so we have to determine where along that line the user “meant” to point. In this case, it’s simple: we only care about things on the tabletop, and the tabletop lies in the plane z=0. So we need only find the intersection of the ray from the window with the plane of the tabletop, and we have our desired position on the board where the user meant to click.
In Sleepy Hollow, the scenes and the shapes of the objects within them are much more complicated. In this case, there is another technique which is easier to implement– and thus I would imagine is being implemented– using what is called a stencil buffer. When drawing a 3D image, there are generally several 2D arrays in video memory that accumulate information about the image being drawn. The obvious one is the color buffer, which contains the red/green/blue color values of the corresponding pixels in the image. The stencil buffer is less frequently used, but is handy here. The idea is to draw each of the objects in the scene in turn; before drawing an object, assign it a unique numeric identifier, and when drawing the object “render” that numeric value to the corresponding locations in the stencil buffer.
The result is sort of a “paint by numbers” view of the scene, where the background is made up of zero values (or whatever), and the interior of each object is made up of values corresponding to that object’s identifier. With this “stencil” in hand, whenever the user clicks the mouse on the scene, we simply look up the corresponding value in the stencil buffer to see what, if any, object was selected.
(A side note: I doubt that the scenes in the game are really 3D. By that I mean that the objects in the scenes, and the “camera” location from which they are viewed, are all fixed. You can’t “walk around” and look at the scenes from different angles. The scenes may have been rendered from individual 3D object models during development, but I would guess that in the final version of the software the scenes are simply “stills,” bitmaps of the entire pre-rendered scene, as opposed to pushing all of the individual objects through a rendering pipeline. And so the resulting stencil buffers are probably also pre-computed.)