Wednesday, 15 October 2008

Something resembling an Octree

There is an interesting thread on 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.


1 comment:

  1. Using octrees for that is a great idea. I've been thinking off on and on how to implement something like that, and have been thinking about doing something using GIS based tools, but I think I like your approach better. I will be interested to see how your experiments turn out.