[Adonthell-devel] New map structure in the making

[Kai Sterker]

After more researching and many sketches on paper I've finally  
started coding what will eventually resemble a dynamic octree for  
storing our game world.

There isn't a lot to see yet. Basically, I just have a method for  
inserting objects, which runs in parallel to the current map  
generation. I then dump the resulting tree in a format that can be  
parsed by dot, and out comes:

The numbers mean:
* the number of map objects in a node
* the bounding box of the node specified by two points in R3
* the split planes dividing a node into smaller nodes ([0 0 0] means  
there's no split yet)

The general idea is that map objects need to fit completely into a  
node (that's why objects are present in non-leave nodes). That  
appears to be a necessity, as it would be hard to split our objects  
in half and not ideal to store objects in more than one node.


The next steps would be to decrease the object count in each node and  
get the tree more balanced. Then I could finish the map view  
implementation (which mostly lacks determining the objects actually  
in view).

In the long run, it might be worth checking if this data structure  
can be used efficiently by the collision detection code. In which  
case we should go ahead and replace the world grid (and grid based  
coordinates) and only keep the tree structure (and pixel coordinates).


One thing worth noting is that the tree is currently constructed  
without knowledge of the final world size (I guess that's the  
scenario in the map editor). Once the world size is known (like once  
the map has been saved), it should be more balanced from the start.

Kai

P.S: if anybody has objections or better ideas, please let me know  
soon! Wouldn't want to write a lot of code only to throw it away  
afterwards :-).