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