Friday 17 October 2008

Something resembling an Octree: 2

My expanding octree implementation is now cleaned up and checked into a random SVN repository.

I thought I might as well flesh it out and get it to a polished state, as there are a few of my projects for which that hasn't been done. My Gmail backup script is one that badly needs a GUI added to it, for instance.

It has always been a mystery to me that people actually used the Gmail backup script, as it just dumps backed-up emails as pickles. As such, anyone who uses it either doesn't care that they don't know how the emails are stored, or they are willing to do the extra work required to work with the dumped files.

Wednesday 15 October 2008

Something resembling an Octree

There is an interesting thread on LPMuds.net about working around the limitations of the MudOS dictionary type (in LPC a dictionary is called a mapping). The problem is that a mapping can only have 64000 entries. The proposed solution is to make an MD5 hash of the string representation of a 3D position, break it up into substrings and index each substring as a mapping entry under the preceding one.

Unfortunately, this lead to me implementing something resembling an Octree in Python, aimed at limiting the number of entries it puts in any given dictionary to 64000 at most.

All of the octree implementations I have seen in the past have to have a predetermined maximum size, within which objects are placed, subdividing the current quadrant into child quadrants as needed.

My implementation takes a different approach and starts with a predetermined minimum size, expanding as the need to place objects outside of the current quadrant arises. It is not fully complete, and needs a little extra work to get it into a usable state. But the guts of it are there.

I'm not really sure what to think of this code. Then again, it's past my bed time.

Link: http://pastebin.com/f19686a59