Space, the next frontier:  Regions
Mon, 15 Nov 1993, Ernest N. Prabhakar
[Comments by Dustin Laurence, "D>"]

When last we left our intrepid theoreticians, they had succeeded in
parametrizing space in terms of three floating-point numbers [no great
feat, that].  More usefully, they had described a metric (semi-metric,
to be precise) that would allow hex maps to be specified naturally by
two integers, as a special case of the above.

Having defined points, we will go on to define sets - i.e.,
collections of points.  Closed sets, to be precise, in that they
contain their limit points (or edges, if you prefer).  Our general
sets are three dimensional extents, but we will think of them in
2-D terms, since that is what they usually are in practice.

In additions to points and sets, there is a third geometrical
construct we will eventually need to deal with: the curve.  Or, if you
prefer, you can think of the 1-D line in addition to the 0-D point and
the 2-D plane.  Regardless, it is the actual path (WarPath?) a piece traverses
across various regions.  But that is a later essay.  Right now we will
only consider the static placement of items in space.  While we
acknowledge that things will move around, we shall not consider how
that motion is accomplished.

Really, what we are trying to do here is describe all the functions of
that wonderful creation, the game board.  Oddly enough, though, we
will not deal with its most obvious function, presenting a visual
display to the player.  That will be saved for our discussion on
interface.  Rather, we are trying to determine what all information it
keeps track off, and how best to organize it for the sake of the
computer.

			      BREAKDOWN

On one hand, you could consider the world as a single object.  On the
other hand, you could think of it as a mesh of interlocking individual
hexes.  I believe the optimal size (for a variety of reasons) is
somewhere in between, at about the scale of a typical geographical
feature.  However, the paradigm I propose could cover both of those
extremes as well.

The basic unit of space, then is what I will call a region.  The
largest region I call the "KnownWorld" (a term we use in high energy
physics a lot).  All other regions are contained in the KnownWorld,
however many levels deep you like.

There are several different properties regions have:
	A. Spatial: its location, size, and extent
	B. Topological: who are its subregions and its superregion?
	C. Geographical: what kind of terrain does it have?


A. SPACE:  The WarSpace protocol

Corresponding to the 0-D Location is our 2-D (well, 3-D, but almost
always of zero height) WarSpace.  There are three boolean queries and
two information methods it has to respond to:
				   
	-(float) contains:Location;
	-(float) overlaps:<WarSpace>;
	-(float) surrounds:<WarSpace>;

0 means false, non-zero is true.  This can convey other,
implementation-dependent information, like distance inside, extent of
overlap, or whatever, but that is not required.

	-(Location) center;
	-(float) maxRadius;

The 'center' and 'maxRadius' provide a sort of 'bounding sphere'
(circle) to aid in establishing a relationship between spaces for the
latter two queries.  All points contained within maxRadius of center.
Of course, specific instances of spaces (square/parallelograms, hexes,
etc.) might have more efficient means of doing so, but this is a good
start.

I will almost certainly require spaces to be simply connected (no
donuts, no distinct patches).  I might want to require that regions be
"relatively convex."  That is, if I draw a straight line between the
centroids of two regions, either:
	a) the regions intersect along that line
	b) they do not intersect at all
This would simplify writing an 'overlaps' routine.  However, I have
absolutely no idea whether this is a meaningful constraint, or how
stringent it is.  Anybody got any ideas?  It's not important, so I can
throw it away, but I'm very curious as whether it is any good. 

D> I don't have a good feeling for what constraints it puts on us, but
D> I suspect that a constraint at least as strong will be necessary in
D> order to make things workable.

The internal data structure can be anything: a list of points, a
mathematical function.  In fact, the only time it matters what the
actual shape of the region is (apart from how it satisfies the
queries) is when drawing a picture for the player (via some sort of
drawSelf method, which we aren't discussing yet:).  Everything else
can be handled by (possibly tedious) calls to one of the query
methods.

Note that there may need to be additional methods for WarPaths, but I
do not yet know what they should be.

B. TOPOLOGY:  The Topology class and protocol

Topologically speaking, there are three things we might want to know
about a region:
	a) what region is it contained by
	b) what regions does it contain
	c) what regions is it adjacent to
which I call parent, child, and peer relationships.  
[Parent, peer, and progeny is more symmetric, but I'm sure I'd get
stoned for using the word progeny in publicly readalbe source code...]

D> Question about topology: are peers strictly a question of ajacency, or
D> can they be something different?  I ask because often two regions will
D> be ajacent for one piece, but not for another, if by ajacent you mean
D> that a piece is elgible to more to that region (this was implied by the
D> risk example).  Probably better to stick to strict geometric ajacency,
D> and let the pieces query the regions to see whether it can actually
D> move.

E> Well, I guess peers are 'possibilities' to move (which may include
E> more than geographical adjacency), but of course addition behavior
E> and restrictions on 'actual' moving are possible.

These are sufficiently general it may be sufficient to define a class
as well as a protocol.  The methods are simply returning a parent
object or lists of peers and children.  There should probably be
'addPeer' or 'addChild' methods as well, though, for additional
book-keeping (like setting the parent of the child and reflexively
setting peers).  Actually, I suppose peers and children are "sets",
not lists, as items should only appear once.

One of the main reason for having regions is to divide up the world in
a nice object-oriented way.  As we'll see later, pieces and terrain
features are associated with regions, rather than in some huge master
table.  The only tricky part is figuring out how to associate regions.

I am still a bit unsure whether there should be both parent and
peer relationship, or they should be lumped together as "outside."
Let me tell you how I expect regions to be used, and you can tell me
what makes sense to you.

At the top-level, we have the KnownWorld region.  Nothing exists which is
not inside this region.  Thus there is no parent.  Strictly speaking,
there are no peers, but if you had periodic boundary conditions it
might be convenient to be your own peer.

Now, consider a simple game with a featureless playing surface.  We have a
single region, with no relationships.  Now consider a game like Ogre,
which adds cratering.  Each crater can be modeled a single child
region.  For a game like risk, the children might be continents, which
would have various countries as their own children.

Since pieces tend to move between countries, it would make sense for
them to know their adjacent peers, rather than having to go all the
way up the topology hierarchy and back down.  Especially for peers on different
continents, like going from North America to Asia via Alaska.

At this point, parents would only be interesting as a special kind of
peer.  However, they might still be interesting for other things, like
inheriting characteristics, or even boundaries.  Of course, some games
- like MUDs - a primarily peer-connections, although each level might
be considered a parent.

Using appropriate delegates, lists, and palettes, one could imagine
setting up these relationships via Interface Builder, getting the
basic topology of the map.  From there, it is a straightforward (if
potentially tedious) process to assign locations and areas to the
different regions, to get an aesthetically (and militarily)
interesting world.

C. GEOGRAPHY: The Terrain protocl

The other interesting point about regions is that each would have at
most one Terrain associated with it (if it had none, it would inherit
the terrain of its parent, which is one good reason to know who your
parent is!).  I've though about Terrains a lot, but I haven't reached
many conclusions.  Part of the reason is that they vary a lot from
game to game, and I'm not yet sure what (if any) the essential
features are.  Another reason is that they affect movement, supply,
sensing, and attack.  Is that one protocol, or four? 

D> I think you've answered your own question--operational definitions are
D> what we want, and the essential features of a terrain object are that
D> it affects movement, supply, sensing, and attack.

I haven't even figured out whether Terrain should know about its
effect on different pieces, or pieces should know about how it is
affected by different Terrains.  Any ideas?

D> I think the latter.  The former potentially requires each terrain
D> object to know a great deal about the rules for all the pieces in the
D> game, while for the latter each pieces knows the rules which apply to
D> it.  Having each piece know its own rules sounds better to me
D> conceptually and practically.  It doesn't make sense (to me) for a
D> forest to know whether a tank can see a foxhole through it, while it
D> would make perfect sense for the tank to know this.  And it sounds like
D> a nasty programming job to teach terrain how all the pieces work, while
D> it seems natural to teach each piece what it can do.  It seems like the
D> natural way to organize the code.  Also, the other way you are liable
D> to end up teaching the rules to both the pieces and the terrain, since
D> presumably it is the pieces which will be querying each other in order
D> to move and attack.

D> I suspect that there is a reason why wargames print information about
D> unit capabilities on the counters but not on the board.  I suggest we
D> do likewise.

D> Anyone else see it differently?

I do feel, however, that Terrains should be separate objects.  And further,
that it be distinct from the topological and spatial properties of
regions.  It need not be unaware of space, though - a Terrain object
Hill could be a smoothly varying Gaussian.  

At times I think that the Terrain protocal should only have a single
method, "heightAt:Location" [apart from things like drawing itself]
and everything else should be handled by pieces switching on
ClassType.  Other times I think it should have an integer (enum?) type
that pieces can key off of, since so many games rely on discrete
terrain types.  In wilder moments, I envision floating point
parameters for:
	- height
	- vegetation
	- hydricity (how watery the land is)
	- urbanization

But mostly I think we're going to have to wait and see how we handle
all the behaviors listed above, and decide whether it is even possible
to generalize them.

D> What about this: the default class returns integers.  This is the
D> simplest case, and thus the one we want to get up and running first,
D> and the most widely used one (at least, it was a while ago.  I don't
D> have a feel for what proportion of games now use semi-continuous maps
D> like SL/ASL (Ernie wanted me to watch my abbreviations; that's Squad
D> Leader/Advanced SL).  We can derive a class for the games which need
D> "height at" information.  People who want to program the very few games
D> which ought to need height/vegetation/hydricity/urbanization info can
D> just derive their own classes, thank you.  Besides, that kind of info
D> is so game specific that we can't do more than just provide an example
D> anyway.

D> Since I don't actually program in ObjC, I hope the intent of the above
D> is clear even if the terminology is odd.

E> I think I would suggest the simplest protocol be "-(int)type;"
E> And that other protocols be in parralel with that, rather than
E> inherit from it.

D. POLITICS: The WarMap protocol

A WarMap object maps pieces onto real estate, always an important
thing to do.  In particular, as discussed earlier, the WarMap actually
"owns" the location of the piece - pieces must message the WarMap to
move themselves.  Note that this is only a protocol.  An actual class
could hold conform to both the WarSpace and WarMap protocols, and be a
single hex which knows which pieces (if any) are on it.

There are several pieces of information a WarMap needs to know.  In
some cases these will be trivial, but in others they will be quite
tricky to synchronize:
	- pieces in the region
	- their locations
	- delegates

I don't know whether one would want a list of piece/location pairs, or
two synchronized lists.  In the latter case, it may then be useful to
refer to a piece by its index in the list, rather than its id.  Of
course, then you have to start worrying about how long that index is
valid...  Fortunately, that's an implementation issue left as an
exercise for the reader. All it has to do is follow the protocol:

	- pieces;
	- locationOf:piece;
	- place: piece at:Location;  [add if not already present]
	- give:piece to:region;	[removes, does not change location]
	- pieceAt:Location; (nil if none)
	- pieceBy:Location; (nearest, nil if none)
	- fill: list for:subregion; (fills all inside)

D> Seeing this written out like this, I feel more comfortable that this
D> WarMap idea is the right way to try to organize the map.

D> Oh, the delegates I like.

E> Thanks.  I would modify the 'fill' method to:
E> 	-fill:<WarMap>map in:<WarSpace>space;
E> (see followup on WarMove)

The reason for the delegates is as follows:  theoretically, every
piece on the board may want to know where every other piece is.
[We'll go into this more when we discuss sensing] They can either
recheck the entire board every time (bad), or maintain a list of
specific regions they are interested (better).

However, this is complicated by the fact some pieces want to know
what others are doing before, while, or immediately after they move.
The mechanism for doing this (which I dare say will be complicated)
we'll discuss in WarPath.  However, the way we handle it is by given
WarMap a set of delegates which (may) respond to the informal WarWatch
protocol:

	@category WarWatch (Object)
	- (float) willMove:piece along:<WarPath>;
	[non-zero can halt movement]
	- didMove:piece to:Location;

Thus, when a piece is moved, all the delegates (and of course the
pieces also in the region) are notified.  So, for that matter, are the
delegates of its parents all the way up the hierarchy [the alternative
would be to have delegate setting/removing propagate all the way
down].  This makes it important to choose a 'natural' breakdown into
regions, to improve efficiency.

The actual methods are:
	- notify:delegate about:<WarSpace>;
	- renotify:delegate about:<WarSpace>n;
	- unnotify:delegate;
The WarMap can add the delegate to itself, or to its children (if they
effectively surround the WarSpace of interest).

As usual, there may need to be additional methods for handling
movement, depending on how WarPath is defined.

		SUMMARY

While I think this covers all the basic information, it just scratches
the surface of a number of difficult issues.  Indeed, we won't really
know whether this is sufficient until we go on to WarPath (pardon the
expression).  Also, so far we have just been tossing "piece" around as
a completely passive pointer; at some point, we will need to interact
with it, and thus define what it does. 

D> It may well end up with encapsulating the rules for a particular piece
D> as a main function.

E> I think you mean 'as its' main function.  Yeah, hopefully the
E> system will be modular enough that:
E> 	a) all generic behavior is in the "piece" base class
E>	b) to add a new piece -only- involves creating a new subclass


And we've already started to worry about sensing and attack...

But, we shall try to maintain order, and take things one step at a
time.  We will probably have to backtrack some, if we run into a dead
end, but that's life.