Working with a large array

This is a discussion on Working with a large array within the C++ Programming forums, part of the General Programming Boards category; Im writing a new terrain engine, My old one used an array like this CTerData position[10000][10000]; Apart from the fact ...

  1. #1
    Registered User
    Join Date
    Aug 2001
    Posts
    411

    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.

  2. #2
    Registered User
    Join Date
    Nov 2001
    Posts
    1,348
    What kind of data are stored in it? Consider storing an array of objects inside of an array. The same design could work with a linked list, which will make it easier to delete items. In general use an STL container if you want to store data of undetermined size.

    Kuphryn

  3. #3
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    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;
    }
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  4. #4
    Code Monkey Davros's Avatar
    Join Date
    Jun 2002
    Posts
    812
    I agree with Magos.

    Declaring arrays as CTerData position[10000][10000]; will place them on the stack, which is limited. Running out of stack memory will result in Stack Overflow Errors.

  5. #5
    Registered User
    Join Date
    Aug 2001
    Posts
    411
    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.

  6. #6
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    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.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  7. #7
    Registered User
    Join Date
    Aug 2001
    Posts
    411
    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.

  8. #8
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,703
    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.
    Code:
    #include <cmath>
    #include <complex>
    bool flip(bool value)
    {
           return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) * std::complex<float>(std::atan(1.0)*(1 << (value + 2)))
        ).real() < 0;
    }

  9. #9
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  10. #10
    Registered User
    Join Date
    Aug 2001
    Posts
    411
    That would work, but its not what im after. In most modern games terrain is one of the most memory hogging things.

  11. #11
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,703
    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
    Code:
    #include <cmath>
    #include <complex>
    bool flip(bool value)
    {
           return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) * std::complex<float>(std::atan(1.0)*(1 << (value + 2)))
        ).real() < 0;
    }

  12. #12
    Registered User
    Join Date
    Aug 2001
    Posts
    411
    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?

  13. #13
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,499
    > CTerData position[10000][10000];
    Consider this.
    If you're standing in the middle of the terrain, the edge is at least 5000 units away.

    The first thing you need to calculate is at what distance from the current position would an object be rendered as just one pixel. Because beyond this, storing and drawing such distant objects is a waste of time IMO.

    This may reduce the visible terrain to say
    CTerData position[1000][1000];

    As you move around, you need to add data to the terrain in the direction you're moving in, and remove data from the opposite direction. To me, a linked list where you can easily append/remove data to the head/tail of the list seems an ideal data structure.

    Another point - many adjacent positions in the terrain may contain the same data (eg. bit of forest). Some mechanism for efficiently storing area information may be worth considering.

  14. #14
    Registered User
    Join Date
    Aug 2001
    Posts
    411
    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.

  15. #15
    Registered User
    Join Date
    Apr 2002
    Posts
    1,571
    Are you using octrees or binary space partitioning?
    "...the results are undefined, and we all know what "undefined" means: it means it works during development, it works during testing, and it blows up in your most important customers' faces." --Scott Meyers

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. from 2D array to 1D array
    By cfdprogrammer in forum C Programming
    Replies: 17
    Last Post: 03-24-2009, 10:33 AM
  2. how to get and use large size array.
    By lehe in forum C++ Programming
    Replies: 7
    Last Post: 03-13-2009, 09:13 AM
  3. Replies: 9
    Last Post: 11-18-2008, 01:59 AM
  4. Storing large numbers as an array
    By Rush152 in forum C Programming
    Replies: 9
    Last Post: 05-19-2006, 11:51 PM
  5. What's the best way to initialize a large const array?
    By pliang in forum C++ Programming
    Replies: 4
    Last Post: 04-11-2005, 07:56 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21