Storing vs. computing

[Crirus]

I have ~200 players on a server...
They share the same 512x512 tiles map...
Each player have an explored area and a visible area... visible area is
given by players's current units and buildings...

Now, I'm facing with the problem of how to store does areas...

One way is to keep a explored(512,512) array of booleans... each
explored(i,j)=True mean player explored the tile on (i.j)... the same for
visible...
Each time a unit/building change it's visibility by
moving/creating/destroying etc I have to recompute the whole visible and
explored arrays
I think is quite memory costly to store in array of 512 form.... any other
ideeas to shrink this memory usage?

On the other side, the computing of all does arrays can be time
consumming... how do you guys, think I should implement that?

All this true values on my arrays should be converted on GraphicsPaths on
client size map to reflect the map visiblity


Crirus

 

[solex]

Crirus,

Have you looked at the FlyWeight design pattern. It sounds like your
application my benefit from having many light weight objects pointing to a
single concrete object that represents the tiles. Here is a link to the
design pattern:

http://www.dofactory.com/Patterns/PatternFlyweight.aspx

Dan

 

[Crirus]

I know about that type of pattern, actually I use such things more or less
But I cant see the link to my problems here

 

[Crirus]

How many memory need a BitArray of (512*512) elements?

 

[Jay B. Harlow [MVP - Outlook]]

Crirus,
I would consider a "sparse array".

Define a class that looks like an array, however it is implemented in terms
of a HashTable. As elements are set I add a key pair as the key to the
HashTable, on get if the key pair is not in the hash table I would return
the "default". Of course as the "sparse array" reaches a certain point, the
overhead of the HashTable will become greater then an array itself. Which is
where you could either revert to using an actual array or "flip" the
"default" (from being found to not found for example) & rebuild the
HashTable. I'm would considering incorporating a Flyweight into this design
(for the 'default' & individual values for example).

Here is a quick example of a key pair class:

Public NotInheritable Class KeyPair

Private ReadOnly m_key1, m_key2 As Integer

Public Sub New(ByVal key1 As Integer, ByVal key2 As Integer)
m_key1 = key1
m_key2 = key2
End Sub

Public Overrides Function GetHashCode() As Integer
Return m_key1.GetHashCode() Xor m_key2.GetHashCode()
End Function

Public Overloads Function Equals(ByVal other As KeyPair) As Boolean
Return m_key1 = other.m_key1 AndAlso m_key2 = other.m_key2
End Function

Public Overloads Overrides Function Equals(ByVal obj As Object) As
Boolean
If TypeOf obj Is KeyPair Then
Return Me.Equals(DirectCast(obj, KeyPair))
Else
Return False
End If
End Function

End Class

You need to override GetHashCode & Equals to ensure the class works
correctly in a HashTable.

Hope this helps
Jay

 

[solex]

Cirirus,

Is your problem that you have an array of with 512x512 bits = 252,144 bits.
You need to store/calculate the "True" values for each player 252,144 x 200
= 52,428,800 bits. So you would like to reduce this potential memory
requirement?

Have you considered a linked list, do you need this array in memory for the
entire session, how about persisting what the user does not need. Perhaps
more info on the game play might help...

Dan

 

[Crirus]

Sorry for this delayed answer as the Xmas camed along...

I'm not sure I understand what do you mean ...
You say to design that KeyPairs class and add to a hashtable new instance of
that class for each tile in my map that is set to true?

Why not to use Point class?

 

[Crirus]

Do you think that is a better way than using a BitArray? Seems that BitArray
use a byte to store 8 coordinates of my map... I was thinking on alocating a
512*512 BitArray that use 32 bytes.. am I right?

How much space your class added to a hashtable will need?

 

[Jay B. Harlow [MVP - Outlook]]

Crirus,
It depends on how full the array is. As with the array you are always
allocating all of the storage. With a sparse array you are only allocating
what is used, of course a sparse array has some overhead associated with it.
There will be a point when the overhead of the sparse array will exceed the
storage used by the entire array, hence my suggestion of making it
"adaptive"...

Hope this helps
Jay

 

[Jay B. Harlow [MVP - Outlook]]

Crirus,

Why not to use Point class?

From a technical point of view, I believe Point is usable as it overrides
Object.GetHashCode & Object.Equals so it should be usable as a key to
HashTable. (Good keys for HashTables need to override both methods).

However from a concept point of view is an "address" on your map a
YourProject.Coordinate or a System.Drawing.Point?

Yes Point & Coordinate share most if not all the same attributes &
behaviors. However a Coordinate may not necessarily be a Point, or a Point
necessarily a Coordinate. I was using "keypair" to refer to the "Coordinate"
class is used as an "address" on your map.

Consider a Person's Age. If I were creating a Person class I could easily
make the Age property an Integer. However this suggests that a Person's Age
can be negative as Integers can be negative, it suggests that you can make a
person younger as you can subtract values from Integers. It would be more
specific to make the Person's Age property a "Duration" object that
represents an absolute value that can only be added to. The "Duration" class
could then encapsulate all the logic that is unique to "Duration" type
values such as Age. (Of course I may make Birthday the actual attribute,
then Age could be calculated from Birthday!) ;-)

A Point can be negative, can you have negative map addresses?

One of the "pitfalls" of OOP, do we be specific and create a class for what
we mean, or do we just grab a class from the framework that "seems" to work.
Which is where Refactoring http://www.refactoring.com is handy, as it allows
you to use a framework class, then replace it with a more appropriate class
later.

Another consideration the KeyPair class is an implementation detail of the
SparseArray, rather then requiring a reference to the System.Drawing
assembly, the KeyPair class might be private to the SparseArray class or the
assembly where SparseArray is defined.

Hope this helps
Jay