[glob2-devel] Map.h, map.cpp and gradients

[Andrew Sayers]

Some of the code in glob2 could do with some spring-cleaning.  Having
spent long enough saying that to myself now, I've started a complete
rewrite of Map.h and Map.cpp (and disturbing nearby files in the
process).

Where would be the best place for me to put my code for people to look
at?  What are the chances you'd actually accept such a significant
change?  Although I've changed the API a great deal, I've tried to keep
the actual behaviour of the algorithms the same as much as I can.  There
will doubtless be some user-visible changes, but they should be minor.
One small user-visible change I'd like to put in is for squares that are
three parts water and one part sand to be considered as water squares.
Another is to allow units to walk over buildings that haven't even
started being built yet (so you can't block your opponents' globs in
with walls).  Does anyone have a problem with those ideas?

However, one thing that I would like to change significantly is the
gradient system.  It's a big change, so I could do with some feedback on
whether the ideas I'm suggesting would work (and whether they'd be
accepted, obviously :).  Since I'm not sure I completely understand
gradients (and since most other people probably don't either), here's my
understanding of the theory:

__Gradients__

Imagine a glob2 map as being filled with hills and valleys, with (say)
forests at the top of each hill, tapering down gradually into valleys at
the points most distant from a wood.  The hillside descends around
obstacles rather than over them,  so workers can find their way to a
wood even when the path is quite complex simply by following the
gradient up the hillside they happen to be standing on.

As well as gradients for each type of resource, glob2 uses guard area
gradients, forbidden gradients*, and building gradients.  Every square
on the board has several gradients for each team, and every building
has a grid of gradients for itself.  The elevation of a single square is
represented by a number from 0 to 255.

I like to think of gradients as being separated into four
broad categories:

* Troughs - these are squares globs avoid at all costs - occupied spaces
  and water (for non-swimming globs).  I haven't checked, but I assume
  that the reason free globs wander about is that they are trying
  to get away from the trough created by their own presence.
  Troughs have an elevation of 0.
* Valleys - these are areas that globs don't try to avoid, but don't
  particularly like to be in.  Valleys can be quite large, and a glob
  stuck in the middle of a valley won't be able to find his way out.
  Valleys have an elevation of 1.
* Hilltops - these are the points globs try to reach.  Hilltops have an
  elevation of 255.
* Hillsides - these represent the approach to a hilltop.  Squares on a
  hillside have an elevation fro 2 to 254, depending on the distance to
  the nearest hilltop.  The elevation is equal to 255 minus the distance
  to the nearest hilltop.

The code also seems to treat squares with an elevation of 2 in some sort
of special way, but I think this might just be an implementation detail.

Gradients are implemented by first setting every square as either a
trough, valley, or hilltop; then elevations are propagated around the
map, with each square repeatedly taking the greatest out of its current
value and the values of the surrounding squares minus 1.



Gradients strike me as an excellent way of finding your way around the
world, but there are some implementation details I'd like to work on:

Two extensions I'd like to put into the system are darkness gradients
(so your explorers can search out areas they haven't seen for a while),
and danger gradients (so your warriors can attack nearby targets).

Two fundamental changes I'd like to make are the way gradients are
updated (which seems quite inefficient to me), and the idea of "compound
gradients", which are a function of several actual gradients.

__ Darkness gradients __

Explorers tend to wander around at random (or hover around the edge of
an exploration flag), workers at the start of a game pace back and forth
rather than exploring their surroundings.  A way to solve this problem
would be to have a gradient leading globs to unexplored parts of the
map.

In other words, unseen parts of the map are hilltops, and there are no
troughs.  It is tempting to make areas in active vision into troughs,
but that would just make huge troughs around areas that globs are in,
which they couldn't find their way out of.

This simple "discovery gradient" would only encourage explorers to
explore new terrain, not to check back across old terrain.  There are
three major problems to overcome in making an algorithm to re-explore
old terrain:

* How to avoid frequently-seen areas from becoming one huge valley.
* How to make areas that take more than a few seconds to get dark
  without creating huge plateaus 
* How to avoid explorers following each other in a long line, without
  making it impossible to cross frequently-trodden paths.

I think a solution that would avoid these problems is:

* At the start of the game, unseen areas are set to hilltops, areas
  containing globs are set to troughs, areas in active vision are set to
  valleys, and values are propagated.
* When an explorer enters a square, it sets the elevation of that square
  to 0, when a worker or warrior enters a square, it sets the elevation
  to 1 (unless the elevation was already 0).
* When an explorer is adjacent to a square with an elevation of 1, and
  there are no positive gradients in any other adjacent squares (i.e.
  the trail has probably been broken by a passing worker or warrior),
  the explorer will enter that square and carry on in the same direction
  until it reaches a square with a non-1 elevation.
* Every 64th tick, the elevation of each square is increased by one, and
  the values propagated.

This isn't a conceptually neat solution, but in practice, I would expect
frequently used areas generally have low elevations, and unused areas to
increase until they go dark after about 10 minutes.

__ Danger gradients __

Globulation currently uses a very simple way of looking for enemies,
which means that warriors won't attack nearby buildings unless lead to
them by the nose, and workers will merrily collect wheat while being hit
by a tower.  A better system would use a (slightly altered) gradient
system:

* Towers have a danger elevation equal to their attack distance, plus 3
* Workers and other buildings have a danger elevation of 3
* Warriors have a danger elevation of 8

Warriors will then climb danger gradients (or wander around danger
valleys when there's no danger to be had), while workers will follow
gradients *down*, avoiding danger, and ignoring gradients less than 4.
This should give behaviour similar to the way things work at the minute.
Following negative gradients are an addition that would be best
implemented with...

__ Compound gradients __

These strike me as quite a natural and simple addition to the gradient
system.  For example, workers currently follow resource gradients,
unless doing so would move them down a forbidden gradient.  It would be
easier for them to calculate one "compound gradient" based on several
other gradients, and follow that.

Warriors could follow a compound gradient of:
        forbidden_gradient*256*256 +
        danger_gradient*256 +
        guard_gradient

Workers looking for resources could follow a compound gradient of:
        forbidden_gradient*256*256 +
        (253-danger_gradient)*256 +
        resource_gradient

And so on.

__ Gradient updating __

At the moment, the entire field of a gradient is updated regularly -
every few ticks or whenever a glob uses it, depending on the resource
type.  This strikes me as both inefficient and incorrect.  The current
system means that globs "just magically know" (as the play guide
originally put it) where everything is in the world, and that a lot of
time is wasted updating gradients that haven't changed.

It strikes me as a better solution that when a space enters a team's
active vision, or is changed while in active vision, that space should
be recalculated.

When an elevation is recalculated, it is first reset from being a
hilltop, hillside, valley or trough into being a hilltop a valley or a
trough.  The next step depends on what it was before and what it turned
into:

* If it remained the same, nothing happens
* If it turned into a hilltop, gradients are propagated to nearby
  squares.
* If it turned from a hillside into a valley or trough, it is reset back
  to its old elevation.
* If it turned from a hilltop into a valley or a trough, neighbouring
  squares with an elevation of 254 need to be rechecked:
  * if they are not adjacent to a square with a higher elevation, all
    its adjacent squares need to be rechecked
    * and so on recursively.
  * the square is then reset based on the elevation of the surrounding
    squares
  Finally, the original hilltop-come-valley is reset based on the
  elevation of surrounding squares.

For extra marks, we could even use darkness gradients to stop propagating
when we get far enough away from squares that have been frequently used.

Obviously, this algorithm would get a bit more complex when used with
danger gradients, but it should still be fairly easy.

__ Epilogue __

Wow, it's not often I spend long enough writing an e-mail that I need to
put an epilogue in it!  Anyway, these are my ideas for how to change the
behaviour of Map.cpp to make for a better game.  Please tell me whether
you like the ideas, whether the maths of it adds up, and how to make it
available for inspection and eventual inclusion in the main tree.

        - Andrew

* Occupied spaces and water spaces (for non-swimming globs) are counted
  as forbidden, as well as normal forbidden areas.