Sign in to follow this  
CIJolly

How to cut down memory usage of huge array

Recommended Posts

I am about to start developing a quick prototype for a Liquid Wars style game. I just wanted to check that I wasn't dooming myself to failure. It seems like it will be pretty memory and processor intensive if a take a naive approach. This game will take place on an enourmous grid. One screen, 1024 * 768. Every pixel on the grid will be designated land, sea, or wall (so it's just a grid of integers). On top of that will be a 1024 * 768 grid to represent the combatants, each will be one pixel in size. A fighter's class will have much more in it than a piece of terrain. Integers to represent type, commanding player, health, destination, etc. My first question is: How would I figure out how much memory usage a large array of a custom class would take up? To cut down on the amount of memory used, I figured I could make the fighter array an array of pointers, and store the fighters themselves in a linked list. That way I only use as much memory as I have fighters (instead of having to reserve memory for an entire grids worth of them), plus the memory taken up by the pointer grid, but still get to retain the benefits of the grid (quickly being able to see what fighters are surrounded the fighter of interest by looking at what fighter, if any, is pointed at by the adjoining tiles). Would this work? Or would I be better off just initialising the whole thing as a ClassFighter[1024][768] array? How would I go about finding how much processing time it would take to loop through up to 786432 combatants? Lastly, I was going to have another screen sized grid of class ClassOrder to give orders to the fighters. Orders will be painted on the terrain. Any fighter stepping onto a tile with an order painted on it will obey that order (eg, by changing to a suicide bomber/bridge builder/healer type, or by setting a new waypoint as it's destination). Each player would need their own grid to paint orders onto. Would this be pushing the memory limits of most computers?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by CIJolly
Or would I be better off just initialising the whole thing as a ClassFighter[1024][768] array?

How would I go about finding how much processing time it would take to loop through up to 786432 combatants?


1) no, you'll probably want to use the STL, i.e. a std::vector for something like this

2) normally, you would simply do a benchmark


however, overall you may want to rethink some of your design desicions-as some of the things you are considering right are not necessarily as flexible as you may envision them

Share this post


Link to post
Share on other sites
Quote:
Original post by CIJolly
This game will take place on an enourmous grid. One screen, 1024 * 768. Every pixel on the grid will be designated land, sea, or wall (so it's just a grid of integers).


Or indeed, you could use char or byte (depending on what language you're using) which is usually the smallest thing you can easily use.

That would take 1024*768 bytes (Hint: About 768k)

Quote:

On top of that will be a 1024 * 768 grid to represent the combatants, each will be one pixel in size.
A fighter's class will have much more in it than a piece of terrain. Integers to represent type, commanding player, health, destination, etc. My first question is: How would I figure out how much memory usage a large array of a custom class would take up?


If you wanted to store an array of the objects, then it would be 1024 * 768 * the size of your object.

Quote:

To cut down on the amount of memory used, I figured I could make the fighter array an array of pointers, and store the fighters themselves in a linked list.


Yes, you could do that. That would take the size of a pointer * 1024 *768.

Quote:

Would this work? Or would I be better off just initialising the whole thing as a ClassFighter[1024][768] array?


It depends entirely how much stuff is in ClassFighter, if you can minimise the amount of data members in this struct, it might be more efficient to use instances.

OF course if you use instances you'll need to do some copying every time one moves to another tile.

Quote:

How would I go about finding how much processing time it would take to loop through up to 786432 combatants?


Well that depends on a great deal of factors. The only way is by trying it - see what sort of performance you can get. Looping through them isn't going to take long - but the logic might.

Presumably not every tile on the map will contain a combatant (in fact most won't), so this will speed things up a bit.

Doing a lot of stuff with this much data can blow your caches out quite effectively so you may find that it doesn't scale up linearly even though you think it's O(n)

Quote:

Lastly, I was going to have another screen sized grid of class ClassOrder to give orders to the fighters. Orders will be painted on the terrain. Any fighter stepping onto a tile with an order painted on it will obey that order (eg, by changing to a suicide bomber/bridge builder/healer type, or by setting a new waypoint as it's destination). Each player would need their own grid to paint orders onto. Would this be pushing the memory limits of most computers?


Seeing as these aren't going to be more than 768k each, not really. Presumably you'll have less than 256 types of order?

Mark

Share this post


Link to post
Share on other sites
Consider tracking the fighters the other way around, instead: That is, set up an associative container which maps Positions to Fighters, instead of trying to map a Fighter (or not) to every possible Position.

This looks like, for example:


class Fighter {
// stuff
};

struct Position {
int x, y;
bool operator<(const Position& other) const {
if x < other.x return true;
if x == other.x && y < other.y return true;
return false;
}
Position(int x, int y) : x(x), y(y) {}
};

std::map<Position, Fighter> fighterMap;
fighterMap fighters;

// Move the Fighter, if any, at (x, y), by (dx, dy) amount.
// You might prefer to put "new location calculation" logic into the Fighter class.
void moveFighter(int x, int y, int dx, int dy) {
fighterMap::iterator it = fighters.find(Position(x, y));
if (it != fighters.end()) {
Fighter f(it->second);
fighters.erase(it);
fighters(Position(x + dx, y + dy)) = f;
}
}

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this