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

[Stephane Magnenat]

Hi everyone,

I finally got some time to read the ml.

Please note that Nuage just moved to India. No news yet, so let's home he is 
fine ! Nuage, when you connect back to the net, please consider reading this 
mail, you are the gradient master ! :-)

> 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).

Nice (the cleaning, not the disturbing)

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

That's ok for me. I nevertheless strongly suggest you put your changes in a 
branch as long as they are "unstable". That's the way I've done all major 
libgag changes during the last 5 years, and it works fine.

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

There might be much easier ways to improve explorer's behaviours. Nuage loved 
the idea of having "randomy and not so efficient explorers". The gradient 
could do it, but perhaps some spiral-like behaviors could do it too.

I've no problem for the gradient if it works fine and doesn't consume too much 
CPU.

> __ 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...

Nice idea, perhaps some idea/code from local gradient could be used. 
Nevertheless, I can see a problem of blocking here if warriors go to one 
direction and worker and damaged warriors in another.

> __ 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.

The idea is nice, I like it, but I'm not sure it works all the time. For 
instance, a forbidden gradient is forbiden. That doesn't only mean you have 
to get out, that's also mean you are not allowed to go in, under *any 
circumstances*.

> __ 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.

The gradient is *not* recomputed all the time. The array system, used by 
gradient update algorith, is not our first trial in efficient gradient update 
(we had two other systems before). It is quite efficient by stopping new 
computation when no new swaure has to be updated. Nuage designed it, so I 
would prefer to let him give his opinion, as I may be wrong about the 
internals of gradient system.

> __ 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.

Thanks for your interest. I hope Nuage will be able to answer you also. 
Creating a branch looks like the best solution to me. It allows you to play 
without any trouble, while still allowing other people to compile your 
version or the HEAD version. Eventually, if we want to merge, that's quite 
easy.

Steph

-- 
http://nct.ysagoon.com