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...
R-trees
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.
r6rs-protobuf
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.
void (*) (ClutterContent *, ClutterActor *, ClutterPaintNode *);
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.
krb5
...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!
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.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.A few notes on some older projects:
r6rs-protobuf
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.
SCSS
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.
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!