🚀 go-pugleaf

In article <BsLAKE.E7v@undergrad.math.waterloo.edu>, tschille@undergrad.math.waterloo.edu (Thorsten Schiller) writes:
|> Greetings.
|> 
|> I'm thinking of writing a strategy game which should implement a rather large
|> map (ie. preferably an arbitrary size in the excess of 10,000 x 10,000 squares).
|> 
|> Can someone suggest an algorithm (or a source even) to efficiently manage
|> such a beast? 
|> 
|> The matter is complicated by the fact that elevation, etc will be taken into
|> account so I need to be able to perform line-of-sight calculations and the
|> like.  
|> 
|> I have considered (and basically discarded) a number of internal compression
|> schemes but discared them for various reasons ranging from performance to
|> insufficient compression ratios. (actually, a basic runlength compression
|> scheme seemed kinda promising, but having to decompress various chunks of
|> data for line-of-sight calculations, etc seems to get quite expensive 
|> alarmingly quickly)
|> 
|> I've also looked at the quadrant method, but found that unless my map turns
|> out to be fairly homogenous I can't be certaint that I'll be able to load a
|> significant chunk of it.
|> 
|> So, is there a good, solid approach to managing this much data (I'd really
|> prefer to avoid disk swaps if at all possible) at once? (personally, I have
|> 5 megs of RAM to play with but would much prefer it ran in significantly
|> less that this)
|> 
|> Like they say... 90% of a good program is picking the right algorithm :)
|> 
|> Thanks in advance for any help.
|> 
|> Thorsten Schiller
|> tschiller@cayley.uwaterloo.ca

You want to represent 100.000.000 squares that are so different that they cant
be put in a quadrant tree into a datastructure that will avoid swapping
to disk, withing 5Mb of RAM?

Sounds like a tough task...  :-)

You mentioned the quadrant method, and find it useless, as it requires the map
to be fairly homogenous as you say. That is true, but how do you defined
homogenues? What I'm getting at is that if you are describing a rocky landscape,
the _height_ of a square might not be a good measure for homogenity as it
will vary wildly. Why not look at _elevation_ instead? This way, all squares
in an otherwise uniform hillside need not be split further.

When looking up a particular point, you will have to calculate that points
height from information stored in the quadrant struct.

Just an idea...

Good luck !

-- 
Roar Foshaug                                      (roarf@stud.cs.uit.no)
Department of Computer Science
University of Tromsoe                             'oe' is '\o{}' in Tex
N-9000 TROMSOE, NORWAY                            'OE' is '\O{}' in Tex