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

[simon schuler]

Hi

Quite a long time, since I thought I had enough time for glob2, but i 
think I'll
comment anyway, since I had also thought about some ofthese things and
found some problems.

Andrew Sayers wrote:

> 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).
>  
Very good idea. It can use a lot of cleaning.

> 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.
>  
Hmm, strange description, I think it's just a normal floodfill algorithm.

> 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.
>  
I had also thought about this, and I counted the changes then. most of the
time only between 0 and 10 Fields are changed, but the whole gradient is 
recalculated... It
seems really a waste of time.

> __ 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.
>  
I like the Idea of shadow gradients, but it won't be easy to implement. The
main problem is, when you got more than one explorer, they will most
probably all go to the same place. And if they once have reached the same
place, they will never split up again. So it will be worse than before.

> __ 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...
>  
Workers already follow the ressources gradients, so this will only affect
them if they are unoccupied.

> __ 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.
>  
You mean for example 1 wood gradient for all the players, or am I wrong?

> 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.
>  
If I understand your idea correctly, this will produce invalid paths. (a 
worker
follows the path until he comes to a forbidden area, and then he doesn't
know where to go. (he's not at the hilltop, but there is no way up the 
hill).

> __ 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.
>
>  
Well I don't think the algorithms get too complicated, but the problem 
is, that
you will have to update all the gradients sometimes. Imagine you make a
building which blocks a way. all the gradients of all the players will 
have to be
updated. So you risk using different amounts of time for every turn. (I 
don't
know if this hurts). But the computations it will in general consume 
much less
time than they do now.

Simon