🚀 go-pugleaf

     -=> Thorsten Schiller spoke of "Large "map" management" <=-
    To All at 08-07-92  01:24
 TS> Greetings.

 TS> I'm thinking of writing a strategy game which should implement a
 TS> rather large map (ie. preferably an arbitrary size in the excess of
 TS> 10,000 x 10,000 squares). 
 TS> Can someone suggest an algorithm (or a source even) to efficiently
 TS> manage such a beast? 

 TS> The matter is complicated by the fact that elevation, etc will be
 TS> taken into account so I need to be able to perform line-of-sight
 TS> calculations and the like.

this really shouldn't complicate things.  My suggestion is too
use a SPARSE matrix.  Basically it's a linked list.  However by
adding hashing you can boost speed considerable.  If the
information varies between data points this scheme is really the
best.

 TS> I have considered (and basically discarded) a number of internal
 TS> compression schemes but discared them for various reasons ranging from
 TS> performance to insufficient compression ratios. (actually, a basic
 TS> runlength compression scheme seemed kinda promising, but having to
 TS> decompress various chunks of data for line-of-sight calculations, etc
 TS> seems to get quite expensive  alarmingly quickly)

Well not really.  Using the above combined with compression of
selected data and adding a bit of VM buffering this should only
slow things down a little bit.  Depending on the type and how
much of course.

 TS> So, is there a good, solid approach to managing this much data (I'd
 TS> really prefer to avoid disk swaps if at all possible) at once?
 TS> (personally, I have 5 megs of RAM to play with but would much prefer it
 TS> ran in significantly less that this)

 By having a large indexed swap file this shouldn't be a problem.

 TS> Like they say... 90% of a good program is picking the right algorithm
 TS> :) 
 TS> Thanks in advance for any help.

Well in this case the word is ALGORITHMS.  You will be applying
Virtual memory techniques, data structure techniques, and
compression techniques.  Good luck.  I'm using something similar
to make my newest 3d maze generator.  Right now I'm just making
it so that it will generate a random maze :)

Then I can add rooms and stuff [like an entrance].

The maximum size will be 128 x 128 x 128 or 2million cells :)
nothing like a 2meg game file!  hehehe
of course TESTS will be a paltry 5 x 5 x 5.

        Stephen Cyberman@Toz.Buffalo.NY.US
        Scripted at Sat  08-08-1992  14:22:57

... Life should come with a Quick Reference Guide.
--- Blue Wave/QWK v2.10