🚀 go-pugleaf

>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? 

I've seen this question more than once, so here's my 3 cents...

I have faced this same problem many times (in game writing as well as "real"
work).  Early on, I always tried to implement large maps as arrays (as you
seem to want to do), but no matter how clever I was (I tried compression,
clever hacks, and even wrote my own virtual memory manager) it never worked
the way I wanted it to.

Years ago I finally found what I think is a good way to do it.  Instead of
envisioning the world as a grid with objects scattered around on it - usually
in such a way that 99+% of the grid has nothing on it, give the objects
themselves position.  Let's say I have a 4x4 map (it's easier to use a tiny
map for this example), and on the map I have two rocks (or spaceships, or
dragons, or whatever).

     1   2   3   4
   +---+---+---+---+
 1 |   | X |   |   |
   +---+---+---+---+
 2 |   |   |   |   |
   +---+---+---+---+
 3 |   |   |   | X |
   +---+---+---+---+
 4 |   |   |   |   |
   +---+---+---+---+

The classic way to represent this would be to have a 4x4 array, with
elements (2,1) and (4,3) set to "ROCK".  This takes up a fixed amount of RAM
(4x4x<element size>, or 16 bytes if each element is 1 byte).  In pseudocode
this would look like...

.
ROCK=1
WATER=2
FROG=3
.
byte array map(4,4)
.
map(2,1)=ROCK
map(4,3)=ROCK
.

Instead, try it this way.  Create a data structure for each object that has
fields for position (x and y) and object type.  In pseudocode this would
look like...

.
ROCK = 1
WATER = 2
FROG = 3
.
structure mapobject:
  byte objtype
  int16 x,y	; Using 16 bit integers, you can describe a map up to
		; 65536x65536.
.
mapobject array obj(2)
.
using obj(1) {objtype = ROCK; x = 2; y = 1}
using obj(2) {objtype = ROCK; x = 4; y = 3}
.

This example is painfully simplistic, but I'm sure you get the idea.

I discovered this before the days of so-called "Object Oriented Programming",
but that's obviously what it is.  This approach takes orders of magnitude less
RAM, but requires much more work by the designer to make sure that the program
can find any object it needs to in a reasonable amount of time.  If there are
only a few objects, this is trivial, but if there are lots of them you have to
be clever about it.

You also mentioned that you need to represent "elevation".  I have successfully
done this using "regions".  I describe a "region" to be a series of points that
describes a space on the "map" - in my case a "region" can be convex or concave,
and even have holes in it.  Each region is assigned an elevation.  It is
generally desirable that no regions overlap.  To find the elevation of a map
coordinate, I traverse the list of regions until I find one (using simple
geometry) that contains the map coordinate I'm interested in.  This technique
is also useful for describing buildings, rivers, or anything else that occupies
more than one map coordinate.

I hope this helps, and good luck.

-Bill
--
--------------------------------------------------------------------------------
William P. Bame                    | sneakernet: William P. Bame
internet: bill@bill.ab.umd.edu     |             M.I.E.M.S.S.
          bbame@achi1.ab.umd.edu   |             22 South Greene Street
AT&T    : [Work] (410) 328-3062    |             Baltimore, MD 21201
CIS     : 71620,425                |             Room: T1R55
--------------------------------------------------------------------------------

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