Saving tree's
Author
Hello!
Does anyone here know how to save a binary tree to disk, so that the tree can be re-created from disk??
Any references/code/ideas would be appreciated!!
Paul
NOTE that i am trying to save an octree to disk!! not working so far :\
Go through your tree and assign each node in your tree an integer. Now go through and replace each pointer to a node with the relevant integer, based upon the node it is pointing to. You do a similar thing with your geometry(I don''t know your exact representation so can''t help you there). Then you need to write out in chunks: your geometry, your tree nodes. This will produce a structure very similar to that used by iD software for their BSP trees. Have a look at the Quake BSP file format for an example.
Check out http://www.gametutorials.com/Tutorials/OpenGL/Quake3Format.htm for a simple look at the Quake3 file format.
James
Check out http://www.gametutorials.com/Tutorials/OpenGL/Quake3Format.htm for a simple look at the Quake3 file format.
James
I don''t see how you could possibly want an easier method than that. You need to store the pointers in a memory independant way, so you are simply converting the pointers to "virtual pointers." I suppose you could make the pointers be relative to the file... but that presents problems of its own. My advice, just go with jamessharpes'' method.
quote:Original post by Muncher
ta m8! is there a simpler way of doing it?
I don''t think you can get any simpler than this. As dmounty says you need some way to represent the pointers in the file, and assigning ID''s to each node is the only way you can really do it, and still have the ability to easily change the file without having to modify data throughout the file to reset offsets into the file. It is quite a common method if you look at different file formats to have a directory either at the beginning or end of the file which tells you where the different sections are and their length. The data then tends to use indexes into other chunks of data to allow for dynamic sizes and pointers.
Note: your octree leafs may have an arbitary number of objects. To store these, first write the number of objects as a long/short(depending on the max in a single leaf) and then write out the object indices in an appropriate way.
James
no matter what method you use, there is one thing that is constant, at LOAD time, there must be some entity that contains a directory of node indexes to actual loaded node pointers ...
at SAVE time, you can just output the actual pointer value to the file - using the already unique pointer for the index, but at LOAD time, you MUST convert the old (invalid) pointer address or index into the new address (created when you called "new" while loading each node).
However, I would reinterate that converting the pointer values to logical numbers during the save is not hard (the simplest method is to output the "node count" as the node''s index), and is often worth it to make the file more human readable, as well as to prevent hackers from gaining additional insight into your running game mechanics (by seeing the distrobution of pointer addresses) ...
at SAVE time, you can just output the actual pointer value to the file - using the already unique pointer for the index, but at LOAD time, you MUST convert the old (invalid) pointer address or index into the new address (created when you called "new" while loading each node).
However, I would reinterate that converting the pointer values to logical numbers during the save is not hard (the simplest method is to output the "node count" as the node''s index), and is often worth it to make the file more human readable, as well as to prevent hackers from gaining additional insight into your running game mechanics (by seeing the distrobution of pointer addresses) ...
Author
Thanks for al your help!!!
In case anyone is wondering, i found a pretty easy way of saving a tree structure and loading it.
I just recurse through the tree and save each node to disk, as well as the level the node is, ie/ level 0 is the root, a level 1 node is a child of the root, level 2 is child of a level 1 node and so on.... Then when loading i can tell where a node is supposed to be!
Paul
In case anyone is wondering, i found a pretty easy way of saving a tree structure and loading it.
I just recurse through the tree and save each node to disk, as well as the level the node is, ie/ level 0 is the root, a level 1 node is a child of the root, level 2 is child of a level 1 node and so on.... Then when loading i can tell where a node is supposed to be!
Paul
in case you wanted it, you can also use a seriealization method, where you traverse the tree writing the size of each node, and the data there, or zero for a null. When you hit a null, it goes down the other child nodes path. It works pretty well for simpler trees.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
