|
Author Topic:   data structures
kaber0111
Member
posted January 16, 2000 07:33 PM            
well i am rewriting my engine and was wondering, do you have any tips or poiners you could tell us when writing our data structures and our functions.
I mean should we use pointers to structures, arrays of structures,etc.
thanks
akbar A.

IP:

Bryan T
Member
posted January 17, 2000 10:52 AM            
I can tell you how my code is arranged, and how I'd modify it if I did it again..

I have two classes, the Landscape Class, and the Patch Class.

Landscape is just a means to hold a large square block of the Height Map (from 512->2048 units square have been tested). It keeps a two dimentional array of Patch objects, a pointer to a dynamicly allocated Height Map array and some other junk.

It is not built for infinite tiling like the Tread Marks engine, so if you want this feature, a dynamically allocated Patch array would be more useful here.

For that, you'd allocate patches which are offset from the camera eye to cover everything the player might see that frame. In the case of Tread Marks, I believe this is a 16x16 grid of patches for 1000m visibility.

The Patch class keeps two TriTreeNode structs. These are not dynamically allocated to the patch but rather owned by the object itself. Each Patch object also keeps two variance trees in the form of an array (see a previous post by Seumas about Implicit Binary Trees and how to use them).

The TriTreeNode struct is a basic C structure with five pointers. The Landscape class keeps a static pool of these structures (lots, like 20,000+ of them) as well as a static allocator function for them. This way a Patch can ask the Landscape class to give it a new TriTreeNode off the pool instead of having the system dynamically allocate it (which can fragment memory).

If I were to rewrite this part, I would introduce a BinTriTree class to encapsulate the TriTreeNode stuff and move it out of the Patch class. This would eliminate a useless 'current tree' variable that my code needs to keep track of which tree it's in.

Hope that helped it's early for a Monday... Feel free to ask if you would like more info. My code will be released within a month and is well documented.

--Bryan

IP:

Effin Goose
Member
posted January 17, 2000 10:24 PM            
G'day,

Bryan, I havent done a lot of memory management programming and i was wonering if you could elaborate on the static pool concept. Is this just a big pool of memory like a big array? Would this mean that you would have to handle fragmentation yourself, and if so howsit done?

Anyhow, thanks for your time

Ryan

IP:

Cthulhu
Member
posted January 18, 2000 12:00 PM            
My pool(s) are just arrays of structures and I believe so are everyone else's. I think that actually removes the memory fragmentation problem when you don't constantly allocate and free memory but use a static pool.

IP:

Effin Goose
Member
posted January 18, 2000 07:20 PM            
Gotcha, but how do you handle the problem of where your next allocation comes from, do you just use a linked list of available spaces in the pool or something like that?

IP:

Cthulhu
Member
posted January 19, 2000 03:25 AM            
There are many solutions. I only keep count of number of allocated nodes and allocate the next one. Or you could have a function that seeks for a free place in pool.

Note that if you choose the last one, DO NOT ALWAYS START SEARCH FROM THE BEGINNING OF THE POOL! I did and when I changed that, fps increased 300% or something.

IP:

Bryan T
Member
posted January 19, 2000 10:51 AM            
Effin,

Yes, the pool is just an array of structs:

static TriTreeNode tri_pool[25000];
static int nextFreeNode;

I initialize 'nextFreeNode' to be zero when resetting for the next frame. Then I call a function which essentially does this:

return &(tri_pool[nextFreeNode++]);

It's a bit more complex because I reset a few pointers in the struct, and I make sure nextFreeNode < 25000, but that's the basics.

You'll never have to search for a free pointer since the whole pool is 'freed' for the next frame. If you are working on a frame-coherent version, I suggest adding a 'next' pointer and keeping two lists (one for freed structs and one for allocated structs).

--Bryan

IP:

Effin Goose
Member
posted January 20, 2000 06:36 PM            
Thanks guys for helping clear that up..

Ryan

IP: