Older blog entries for joolean (starting at number 84)

I've been working on game-related stuff, time permitting. I'm at a point where I can roughly synchronize the movement of a little naked guy walking around a green field (thanks, Liberated Pixel Cup!) between the server and connected clients, and I wanted to add some spatial occlusion to the mix: Areas of the map that both the client and the server understand to be blocked. I knew this wasn't a trivial problem to solve efficiently, so I started doing research on spatial indexing, and found out about...


An R-tree is a container structure for rectangles and associated user data. You search the tree by specifying a target rectangle and a visitor function that gets called for every rectangle in the tree that overlaps your target. Like all tree-based structure, the advantage you get when searching an R-tree derives from the use of branches to hierarchically partition the search space. R-trees use intermediate, covering rectangles to recursively group clusters of spatially-related rectangles. If your target rectangle overlaps a given covering rectangle, it may also overlap one of its covered leaf rectangles; if it doesn't overlap that rectangle, you can safely prune that branch from the search. The secret sauce of a particular R-tree implementation is in the rebalancing algorithm, which generates these covering nodes. A common approach seems to be to iteratively generate some number of covering rectangles that partition their underlying set of constituent rectangles as evenly as possible while minimizing the overlap of the covering set.

I whipped up a couple of implementations -- one in C with GLib dependencies, one in Scheme in terms of gzochi managed records -- based on my reading of the source code by Melinda Green, available here.


My own usage of this library uncovered another embarrassing issue: Deserializing a message with an embedded message field in r6rs-protobuf 0.6 doesn't work reliably, on account of the way the Protocol Buffers wire protocol directs the deserializer to handle what it perceives as unknown fields (throw 'em away). The solution is that you have to tell a delegate message deserializer exactly how much of a stream it's allowed to read, either explicitly (by passing the delimited length) or by preemptively consuming those bytes and wrapping an in-memory port around them -- which is what I did, to get a patch out as quickly as possible. Find version 0.7 here, if you need it.

14 Jan 2014 (updated 25 Jan 2014 at 13:18 UTC) »

Happy new year, everyone. I've just released gzochi version 0.5. Get it here!

As part of the fixes that went into this version, I made several adjustments to the error-handling behavior of the data storage layer, mostly to enable better communication about the result of a query to the database and the ensuing changes in transaction state. Prior to this, I'd taken the approach that any "failure" in data access -- such as a transaction deadlock -- could be indicated by the return value of the data access function, in part to smooth out differences in API between the various storage engines that gzochi supports. This had the fairly obvious disadvantage that it was impossible to tell the difference between a lookup for a non-existent key and an error (well, I figured, application code just shouldn't be doing that), and also that there was no way at all to indicate an error for functions that return void; and so after tracking down and fixing enough hard-to-fix bugs, I decided to fix the behavior of this API. In C, your options for returning multiple bits of information to a caller or distinguishing between, say, an "empty" response and an error are limited. You can make the type of data you return more complex by wrapping it inside of a data structure that also includes metadata about the invocation; or you can pass pointers to "outvalues" as arguments to your function, and have the callee modify them to indicate errors or other out-of-band responses. I like this latter approach because it allows you to preserve for the most part the intended interface between the function and its caller. You can, after all, allow people to pass NULL for those outvalues if they don't care about anything besides the return value. It does require, however, that your function reliably handle the intricacies of checking whether the outvalues are non-NULL and possibly allocating storage for them. GLib's GError type and its associated helper functions and macros are very convenient here. Pass a GError ** to your function and use g_set_error to set it conditionally.

The problem I was trying to solve with the foolishness above still exists, though: gzochi still supports several different storage engines (or, at least, it will -- support for GDBM was removed in this release; future versions will support HamsterDB) and each supported database has its own set of error codes and ways of returning them. So I created a kind of error code independence layer to convert implementation-specific values to values that are part of that layer. For example, in BerkeleyDB:


Back to the release: There's also a new "managed" data structure that employs the principles behind Project Darkstar's ScalableList and provides SRFI-44 collection semantics (one of the more contentious SRFI discussions I've read); and enhancements to the web monitoring console. Like I said, go get it!

Further adventures in game development: I've been working with Clutter to create a primitive client-side game engine to integrate with gzochi. Clutter's a 2-D scene graph library for writing OpenGL applications in C. It's the canvas library behind Mutter and, from what I can tell, a bunch of next-level GTK+ stuff. The documentation says it's for building "visually rich graphical user interfaces," but I don't see why you couldn't also use it to, say, manage the layout of a game screen, which is what I'm trying to use it for: There are a lot of things I don't miss from my brief career as a professional Flash developer, but computing dirty rectagles and figuring out the draw order for actors in a scene isn't something I was looking forward to writing myself. Finding Clutter felt serendipitous.

One thing Clutter doesn't come with, though, is a component that can render frame-based animations, which I'm modeling as sets of raster images that get painted on the stage in sequence at a specified rate. I've built some components that can load image atlases from disk or over the web and carve them up into frames in memory, and I've been trying to get Clutter to turn those frames into a flipbook. It took a lot of meditating over the documentation and some coaching from Clutter developers on IRC for me to get that doing animations this way wasn't going to be a misuse of the library -- but it would be something I'd have to write myself.

Clutter does ship with some data structures you can use for displaying images, so that's what I tried first. There are two: ClutterTexture, which is a GObject subtype of ClutterActor; and ClutterImage, which implements the ClutterContent interface and can thus be used to render ClutterActors that don't know how to render themselves. I saw some indication online that ClutterTexture was probably on its way out, so the first technique I used to implement my animation system was to have a handler for the "new-frame" signal on an animation-specific ClutterTimeline update the internal state of the animated actor's ClutterImage content with the pixel data for a new frame (via clutter_image_set_data). To my surprise, it actually worked (go Clutter!) but it also drove the CPU utilization on my netbook up to about 60%. Here's why: Since Clutter gets its drawing done via OpenGL (actually via Cogl, a GL/GLES compatibility layer), before you can display an image to the framebuffer, Clutter wants to get a handle to a CoglTexture, a block of allocated (and filled-out) GPU texture memory. Pushing textures to the GPU is expensive, so doing it every frame is pretty much a non-starter.

The next thing I tried was maintaining a roster of ClutterImage objects, each with static, pre-uploaded data for a single frame of animation, and updating the content of my sprite actor with the requisite image (via clutter_actor_set_content) on every new frame. This was an improvement, but only got me down to about 40% utilization. I think the problem with this approach might have been that updating the content at the actor level triggers an invalidation that forces some unnecessary invalidations of the scene graph that are expensive to recalculate, but I didn't investigate deeply.

At the suggestion of someone on IRC, the next thing I tried was creating my own implementation of the ClutterContent interface such that the paint_content function would use a pre-uploaded Cogl texture to paint each required frame. The paint_content function has the prototype:

void (*) (ClutterContent *, ClutterActor *, ClutterPaintNode *);

...where ClutterPaintNode argument is a local root of the render graph that corresponds to the actor to which the content is attached (content can be shared across multiple actors). To get your content painted, you need to attach a child paint node to that root. The ClutterPaintNode interface doesn't expose any primitive drawing callbacks, so I don't think they want you to write your own, but there's a provided implementation (ClutterTexturePaintNode) that paints the contents of the texture you give it. I built my ClutterContent implementation around this paint node type -- and it worked, but I was still at around 30% CPU. When I profiled my application, I found that the invalidation signal was being fired much more frequently than the new-frame signal, and the default mechanism for handling invalidation -- which I wasn't sure I wanted to override -- queues a paint operation.

I was feeling a bit down in the mouth about the prospects of animating my sprite at 20% CPU or less. I started Googling various combinations of "clutter" and "animation," and somehow arrived at the Gitorious page for Rob Staudinger's clutter-sprite project, which promises obliquely to provide "A sprite actor for clutter." It didn't look like much, but I started rifling the source files to see if I could learn something. Sure enough, I found that Rob cleverly overrides ClutterActor's paint function and uses cogl_rectangle to paint the frame of animation directly from an image stored as a CoglMaterial, skirting the Clutter render tree entirely. Using a variation on his technique, I was able to get my utilization down to about 25%, which seems like it might be as low as I'm going to get with my netbook's GPU and this version of Clutter.

Having at least temporarily put that security fuss to bed, I decided to implement a few of the remaining missing features of the gzochi server container; specifically, periodic task rescheduling and some light application metrics reporting. The result is a fresh release, 0.4. It's been sync'd to Savannah's trusty network of mirrors by now -- so go get it! Software's never, you know, done, but I think with this release the framework might be feature-complete, at least in terms of its v1 functionality. (A "distributed mode" might be in the works for v2, if I ever get around to reading how RedDwarf Server went about that.) So what's left to work on? Bugs, for sure. In particular, there are several worrisome memory leaks. Unit test coverage. Performance, because there's no reason the container shouldn't really scream, especially with recent GNU Guile builds.

But wow: the rare joy of getting to be a user.

Like a lot of programmers, I think, I developed a mode of thinking about and designing a software system as a set of mostly independent components, each with a limited, discrete function, working in concert to produce a complex epiphenomenal behavior. Until relatively recently, though, I didn't think of these systems as potentially spanning multiple processes or machines. It may seem like a trivial observation, but I've come to find it useful to think of complex systems as appliances that use some set of computing hardware to host one or more processes whose combined behavior forms the behavior of the whole system. The benefit of this kind of thinking is that you no longer need to figure out a reasonable way to wedge a web server into, say, your spreadsheet application process code. Instead, you've got your web server, and you've got your spreadsheet. The difficulty is that you may need to launch and coordinate several processes -- or machines -- to get the complete appliance into the right state, such that its different parts are relaying data back and forth and responding to requests properly.


...Which brings me to my plodding, ongoing experiments in writing an online game. I'd invested quite a bit of time attempting to model the concept of downloadable assets of different types from within my gzochi application code before ultimately deciding that the game server had no business manipulating asset data. That kind of thing, I figure, is the rightful purview of some kind of independent asset management system that's aware of user authorization but not necessarily game state. So I set about figuring out how to manage authorization across processes, and, naturally, Kerberos came to mind. Everything you read about Kerberos steers you in the direction of using it via GSS, the Generic Security Services API. A lot of what you read about GSS suggests that perhaps you ought to consider using SASL, the Simple Authentication & Security Layer. So I did. On first glance, SASL looked like a bad fit -- your SASL-ized applications get to enter into negotiations over which of a set of mutually-supported authentication mechanisms will be used to initiate a session. I guess the idea is that you want secure authentication and you don't care how it happens. But I did care how it happened. So I dropped down to GSS, and found that at first it sort of made sense: Everything is a principal and has credentials, and two principals can create a security context with each other through which they can securely exchange information. But the GSS API designers seemed desperate to avoid explicit representation of anything that might remotely suggest that it's a wrapper around any particular security implementation, much less Kerberos -- no ticket-granting tickets, no service tickets, no distinction between user and service principals. I spent weeks trying to figure out how to model the authentication and authorization flow I had in mind: A client application would obtain a TGT for user with a password, and then use it to obtain tickets to authenticate with the asset server and game server.

When, out of frustration, I dug into the verboten krb5 API, I found it easy to understand -- in the course of trying to get GSS to work I'd figured out the details of key tables and credential caches -- and had something approximating my desired architecture working in an evening. And it's, like, ten lines of code. So I'm kind of on board with what Simon Josefsson says in the appendix of the GNU GSS manual:

...GSS may not be the simplest solution available to solve actual problems, since otherwise more projects would have chosen to take advantage of the work that went into GSS instead of using another framework (or designing their own solution).
I'm with him right up until he says the only circumstance under which you should use GSS is when you're sure you want a Kerberos 5 implementation. Bzzzht!

gzochi 0.3 is out -- go get it! The big news in this release is that there's much more scalable and robust support for transaction execution: transactions can time out, get rolled back, and then get retried automatically. This was the functionality that I was most eager / most scared to add to the server, and the fact that it's there and works predictably and quickly is a major confidence boost. The only thing that's missing at this point from, say, a minimum viable product point of view is support for preiodic task scheduling. And I'll be working on that shortly.

Another thing that I think is really significant in this release (even though it's not much code) is the addition of the GLib-compatible reference client, which is something I've wanted to add since starting work on the first gzochi example game. Being able to hook callbacks into a select loop (or something similar) is just so much neater, more predictable, and easier to debug than launching a new independent thread to govern, say, your communication with a server, and having to worry about its interactions with other threads in your application. Weirdly enough, I think this is something that I started to appreciate more fully after writing (and re-writing) multi-step client-server interactions in JavaScript.

As I mentioned in an earlier post, I have indeed begun to start building some actual personal projects on top of gzochi. I don't have anything to show for it yet, except that I've been exposed to a fascinating array of problems that belong to the domain of rich client development: Rendering pipelines, dirty rectangles.

I've started working on a project that depends on some of the code generation features of r6rs-protobuf (by way of a build-aux helper script) and I realized it's been handling library generation all wrong, at least for multi-.proto builds. The source of the trouble was my decision to map a Protocol Buffers package directly to an R6RS library. That's a fine choice if you can be sure that you know about all declarations of that package, but in a lot of cases, you don't -- for example, when you're applying the compiler to each .proto file in a list. Each file might re-declare that package for its own set of definitions, and since R6RS libraries are effectively immutable -- unlike Java packages or C++ namespaces -- you'll wind up generating a bunch of mutually conflicting libraries that share the same name.

So I've made a new release that changes that behavior. Going forward, the library generator will create a library per top-level definition in each package and name that library accordingly. There'll be a lot more libraries generated, but they'll actually be usable. Get it here.

I've just released a new version of gzochi, my online game development framework. You should go get it! This release features resolves the most disruptive bugs from the first release and adds a bunch of cool new things like an interactive remote debugger, support for Berkeley DB, and new concurrent vector and hash table implementations. I think this is the point at which I'm going to start more actively dog-fooding with it, especially given that the Liberated Pixel Cup and the OpenGameArt folks have done such a great job of eliciting content from talented pixel artists.

One thing I'd known but hadn't really internalized: Example code takes forever to write. I added a new example game in gzochi 0.2, a scaled-down, Scheme-based port of the original AberMUD with an Ncurses client in C, and it took me weeks and weeks to get the structure of the code into a comprehensible, reasonably factored state and write all the code comments. Obviousy, there's tremendous benefit in having clear, well-annotated example code -- it's often the first thing people look at when they download your project -- so I think it's probably okay that it took me so long. But considering how quickly I did the rest of the work for the release, I think this might be the last example I add for a while.

A few notes on some older projects:


In the course of writing the lexer and the corresponding tests for r6rs-thrift I realized that r6rs-protobuf just flat out didn't support "//"-style comments. That's embarrassing -- not least of all because it made the library more or less unusable for real work, and thus nobody must have been using it successfully. But I've fixed that and assembled a new release. Get it here.


Antono Vasiljev correctly pointed out that the API method scss:scss->css in SCSS doesn't seem to work with the same arguments as the function in the same name in Chicken's version of SCSS (which I only just found out about). In fact, it didn't work at all, following a redesign of SCSS's stylesheet data structure several versions and years ago. I've brought it up to date -- made it almost robust -- and after I make a few more fixes I'll put together a release of SCSS as well.


I've just thrown together a release of a little project I started during this year's LibrePlanet conference, an implementation of the Apache Thrift framework in R6RS Scheme: r6rs-thrift. I thought it would be a fun, quick hack -- my assumption was that I could lift a lot of the type system and code generation stuff from r6rs-protobuf, my Scheme Protocol Buffers implementation from last year -- but it turned out that Thrift's a bit more complicated. Which is not to say that it wasn't fun to work on. But Thrift includes pluggable wire protocols, parameterized types, and some interesting variations on Protocol Buffers' vanilla structs (unions and exceptions). And there's not a whole lot (read: any) documentation, so I had to pretty much reverse engineer the serialization and codegen semantics by picking through the thriftc source code.

One interesting thing that came out Thrift's type system is that because you can effectively declare a type at the same time you're declaring a field of that type -- via, say, a container type as a field in a struct -- I had to add a layer of indirection to the type resolution system such that a descriptor for a user-defined type is declared (and registered) once and then used via an explicit "type reference" record everywhere else. Type references themselves can be parameterized to support Thrift's "generic" containers. I was initially worried about introducing that construct, but it ended up being reasonably discrete and quite powerful. I'm considering porting it back to r6rs-protobuf, just for, you know, funsies.

I was able to port the builder pattern that Protocol Buffers uses over to this implementation, which I thought was a neat little coup. Thrift is, you know, fine, but the mutability of the data types generated by the official compiler has always irked me, in part because it means there's no validation applied until you're about to marshal something over the wire. I suppose you could mount a philosophical defense to the effect that you don't really need an object to be well-formed until that point, but that presumes an awful lot about how you're planning to use your generated data structures.

At any rate: I made it; go get it.

75 older entries...

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!