Very large data structure needed. Looking for ideas

Question

I have been chewing on this for a while and I thought I would open a question up and try to get some ideas about it. Maybe something will spark a light bulb.

I need to build a hex grid and that hex grid will be a minimum 10 x 10 and a maximum 500x500 - and possibly bigger. This is obviously a massive grid at the top end and will naturally have to be broken down.

Here is the bulk of the problem.

• 500x500 grid of hexagons. approx.
• They do not change very often, but they can change.
• Breaking it down into 50x50 or 100x100 sections is very doable however it is possible that someone could run from one end of the map to the other so I need to be able to deal with the whole thing at some point, even if it is in sections.
• This will obviously create a big memory drain.

I can store the data (shared vars) as simple byteArray or even in plainText. The information per hex is very simple, it's just how many there are. I don't "have" to save the data. (would be a feature)

The basic structure per hexagon is:

• hex color (with outline obviously) (or a bitmap picture) blitting anyone!
• TextField with a number in it. (max 2 digits)

That is pretty much all the info that is needed.

If there wasn't the possibility of the hex changing at all this would be fairly trivial.

So I am curious if anyone has any ideas on this. (any absolute truths wouldn't be bad ;)

Edit: Oh the information on the hexes comes over a tcp stream. This isn't an issue, like I said the data is simplistic per hex and my parser is lightning fast so it isn't an issue.

Update: The possibility of having to create and maintain 250,000 objects (hexes) is what has me mostly asking this question. This is why I am looking for ideas. (250k objects in flash is well laf)

Answer 1

The basic structure per hexagon is:

* hex color (with outline obviously) (or a bitmap picture) blitting anyone!
* TextField with a number in it. (max 2 digits)

I suppose you don't need to store all 250K TextFields and bitmaps, since they're need to exist only on screen. Pack this data into small number of bytes - max 2 digits is 7 bits, add color id's from your palette (or 24 bits if you need truecolor) and bitmap id's. If you make structures of same size, you can write them into ByteArray. This will let you get rid of 250K object references and prevents possible memory fragmentation.
Then you only need to create pack/unpack functions for those bytes into some usable objects (don't forget object pools) and do the arythmetics to get them from ByteArray right. As others noted, 250K cells aren't much if you pack cell data into pair of int's.

Answer 2

Maybe you could approach this as an exercise in data deduplication? For instance, there are no more than 100 distinct text values that can be associated with your hexes. Assuming you only really use a small number of different hex colors (like, say, less than 20), then a relatively small set of hex instances can represent every possible hex configuration. So you could have a utility function like (not valid ActionScript syntax, sorry):

Hex getHex(int color, String label)

...which checks to see if a hex already exists with the given configuration, and only creates a new Hex instance if one doesn't already exist.

So you still have 250,000 references in your array (or whatever structure you use to keep track of your hexes), but only a much smaller number of actual object instances. Seems like that should be manageable, even in Flash.

You would, of course, have to be very careful if your hexes are mutable after being created.