10 Apr 2014 joolean   » (Journeyer)

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.

Latest blog entries     Older blog 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!