Thread: Working with a large array

Im writing a new terrain engine, My old one used an array like this

CTerData position[10000][10000];

Apart from the fact that I dont like useing an array of this size, I want to make it so I can vary the size of the grid, adding to any direction.

Now I considerd a linked list, but it wouldnt work for me. So my question is, How would you mannage the data in this situation?

The seperate data items need to be ordered in some logical fashion so I can do culling and sorts.

Use dynamic allocation?

Code:

CTerData* DataPointer;
int Width=1000;
int Height=1000;

Datapointer = new CTerData[Width * Height];
if(DataPointer)
{

   //Do whatever you want

   delete[] DataPointer;
}

That was a bad example, I do declare dynamically.

The thing is, im not happy with an array, accessing large ones like that slows speed, and size cant be altered at runtime easily.

Now ive been thinking about it, each array element describes a point on the terrain. Now to optimize the draw code each poly must be sorted into a list so that texture changes are minimized.

If I made the elements describe polys and not points, then I could just store them in linked lists to begin with.



The way it would work is I would chop the terrain into sectors, say 50 x 50. One list would be used to store the data for the sectors (that data would just describe the points for the terrain).

Then there would be another list of lists of lists (is that even possable), each node in the main list would point to a different list for each sector sector, each node of those lists would point to a list for each type of texture used in the sector, and each node of that list would point to an object for each poly to be drawn, and that object would just point to the raw data contained in the other list.

Now a system like that would allow me to add new sectors at runtime, and sort the polys only once, and morph the terrain data easily, and not have to worry about updating touching sector edges.

The only downfall I see is sorting what sectors to draw at a time I would have to run the list of all the sectors and check each. My current system works with single polys and not sectors, but if I didnt do the sectors thing I would have to run through every single poly to see which ones needed to be drawn.

Maybe if I made the sectors smaller, say 10 x 10, then I could cut down the off screen polys, this might also be more desirable, as the resources required for drawing terrain would be constant. If fluctuates alot when drawing per poly.

I pretty much answered my own question.

Wouldn't a linked list be slower than an array? To reach a certain element, you'd have to traverse the list, which is slower than direct accessing an array.
Perhaps I don't understand your thoughts... Try it out and see if it's better.

for each sector that is active everything in the list will be used, so i would run the entire main list, and each sector that needed to be drawn would be used, and the other sectors would just be touched.

You honestly want to create a 100MB-400MB+ terrain? That's absurd! Use a fractal or any other suitable terrain-generating equation. Create a 200X200 max grid and place your perspective in the middle. As you move in some direction, apply the fractal translationally. Objects shoud be stored in their own grid, and use an algorithm to constantly scan the grids to check whether an object is within "sight", and apply it right there.

heres some info

That would work, but its not what im after. In most modern games terrain is one of the most memory hogging things.

Just how fast do you think you can iterate through such a data structure? By my estimates, 2-10 seconds just once (perhaps 1 second on a 1+Ghz processor)! That is not very efficient. Most games these days use fractals since they are so powerful and render beautiful, lifelike landscapes. How long to code 100 million elevations into this array by hand?? A couple of months at best! And to download the game on a modem connection? More than a day on mine! Bad idea

thats a joke right, code terrain elevations by hand? dose "level editor" or "terrain editor" ring a bell.

For example my old method runs through about 5-6 thousand polygons and sorts them all into an array of linked lists, then each list is run one after the other to draw the polygons. On a 550 Mhz Athlon with 128 Megs of ram I used to run over 200 fps, that means it was doing all that over 200 times a second, not to mention all the other stuff that was going on and I believe the bottleneck on that speed was the drawing and not the processing of the arrays and lists.


But since you didnt like my idea, why dont you suggust a better one? If I used fractals would I be able to morph the terrain at runtime - its required for my application?

So your saying to have like an "active terrain pool", where only the data to be drawn is loaded.

Thats cool, but do you think reading terrain data from the HD is practical in a realtime app? My use will mainly be overhead, so optimizing for visable distance, etc isnt my concern.

Are you using octrees or binary space partitioning?