On the fuel tree

As I sat down to write some my prototypes, I immediately ran into a problem, which was that I hadn't yet figured out a way for fuel types to be dynamic. There's really no way I could hard code each type as a separate class and have it derive from a parent type at compile-time. I needed to have a hierarchical tree of fuel types, but I needed one that could be expanded as needed at run time. The easiest way of doing this is just to have a base Fuel class which holds a list or a set of Fuels (ie, a list of objects of its same type) representing its children, and a parent Fuel.

This works just fine, but I was concerned it wouldn't be very flexible or efficient (not to mention not very elegant or pretty), so I wrote an algorithm which traverses an existing fuel tree and assigns a value to each node which encodes information about that node's parent and children, all the way to the root node of the tree. I'm sure this has been done a thousand times, but a quick googling didn't turn up anything obvious, so I just did it.

This would be a really fast way of checking the tree for parents and children--it's basically just a simple index. Rather than hike the tree up or down each time you want to check if a given fuel is the parent or child of another fuel, you just do a (constant time) comparison of each fuel's indexed value and you have your answer.

Of course, the main drawback is that each time you add anything to the tree, the entire thing must be re-indexed. Another drawback is that the amount of bits needed to index the tree is n/2, where n is the number of nodes. This is because any node with children doesn't need any extra bits above what its children need (ie if a node has four children, then all five nodes--parent and four children--can be represented by four bits), but any node without children requires an entire bit for itself. Since we could reasonably expect half of all nodes to not have children (since you can only ever add a leaf or a parent), we'd have to be careful about managing our data types to make sure we didn't run out of room to store our index total.

So the process would be first building a tree using some syntactic notation like the one in the previous post, and from there maintaining a big tree of our fuels and re-indexing it each time a new fuel is added (or removed), the advantage being only the index would be used for the frequent fuel-type checks. I wouldn't anticipate new fuels being added (and forcing a re-index) nearly often enough to compare to the cost of hiking the tree for each check.

Then again, the tree will probably remain small. Under a thousand items for the forseeable future. Hiking through a tree of that size, even a thousand times a second, is easy-mode for modern processors, especially since we'd expect most queries against the tree from a given node to be made relatively close to the target node. I'll have to decide if it's worth implementing once I see what kind of performance problems I have from all the other systems running at the same time.