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

[Andrew Sayers]

(This is in response to everyone's questions, really)

<gradients generally>

simon schuler said:
> Hmm, strange description, I think it's just a normal floodfill
> algorithm.

Sorry, my computational theory is a bit weak on this one, and googling
for "floodfill" just gives me a lot of talk about graphics packages
(which I now realise, yes, is the same algorithm).  Do you have a good
URL handy that explains the theory so I can stick a comment in the code?

Actually, if you're good with standard algorithms, would you mind having
a look at makeRandomMap()? (it's the last-but-one function in my new
Map.cpp).  The comments in the original code strongly suggest it's a
standard algorithm copied from somewhere, but I don't know what the
algorithm is.  I've tried to explain the function as best I can, but it
would be really handy to have a name for it.

<Shadow gradients>

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

Yes and no - zeroing out paths as you go along them will make that
harder, and I've thought about creating "dents" in the landscape around
your globs.  Nuage's idea of going in random directions could work too -
I'd like to see how things go in practice before thinking out a cleverer
solution.

<Compound gradients>

First, to answer Simon's general argument: the resources would be
calculated exactly as they are now, the only difference is that the
globs would calculate their own personal gradient based on more than one
actual gradient.  So for example, you can prefer to avoid danger to such
a degree that you will only follow a resource gradient if there's no
danger gradient in view.

Stephane Magnenat said:
> 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*.

Since the maximum possible elevation is 255, and the forbidden elevation
is multiplied by 256*256, a forbidden gradient trumps any other gradient
in that calculation.  However...

> >Workers looking for resources could follow a compound gradient of:
> >     forbidden_gradient*256*256 +
> >     (253-danger_gradient)*256 +
> >     resource_gradient
> Makes a great deal of sense. Problem is, if the closest resources are, 
> for example, right next to an enemy tower, then won't the glob hover at 
> the edge of the tower's range? Or am I not understanding something 
> here?

And...

> >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.
> 
> Thing is, without the 'Magical Knowledge', how do you build your first 
> inn? You can't order your workers to explore, your Explorers might not 
> look in the right direction, and the wood isn't always that close...

Hmm, sort of.  Thinking about it, buildings should all have a danger
gradient equal to their firing range (or 0 if they can't fire) plus 3.
Also, workers should use the following compound gradient:

        forbidden_gradient*256*256*256 +
        (danger_gradient<4?0:(255-danger_gradient)*256*256) +
        resource_gradient*256 +
        shadow_gradient

Here's an example that will try to deal with everyone's objections at once:

Say you have a worker that is trying to gather wheat.  The only patch of
wheat in the map is two squares to its right.  Four squares to the right
of that is a level 1 tower (so the wheat is the most distant square
within its range).

To his left is a water square (and he can't swim).  The elevations for
that are:
        forbidden: 0
        danger: 0
        resource: 0
        shadow: 0

To his right is a non-forbidden patch of grass.  Two squares to the
right of that is a non-forbidden piece of wheat, and five squares to the
right of that is a level 1 tower (so the wheat is the most distant
square within its range):
        forbidden: 255
        danger: 1
        resource: 253
        shadow: 0

Above him is a forbidden patch of grass, and immediately below that is a
piece of wheat:
        forbidden: 254
        danger: 0
        resource: 254
        shadow: 0

Below him is a spot he's never seen before:
        forbidden: 255
        danger: 0
        resource: 0
        shadow: 255

The worker is standing on a forbidden patch of sand:
        forbidden: 254
        danger: 0
        resource: 253
        shadow_gradient: 0

The other directions are blocked off by various obstacles.

So, for the square to the left:
          0*256*256*256 + (255-0)*256*256 +   0*256 +   0 == 16711680
For the square to the right:
        255*256*256*256 + (255-0)*256*256 + 253*256 +   0 == 4294966528
For the square to the top:
        254*256*256*256 + (255-0)*256*256 + 254*256 +   0 == 4278189568
For the square to the bottom:
        255*256*256*256 + (255-0)*256*256 +   0*256 + 255 == 4294902015
And for the square it's standing on,
        254*256*256*256 + (255-0)*256*256 + 253*256 +   0 == 4278189312

So it follows the highest gradient, to the right.

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

Fair enough, I'll leave this for another day - clearly I need a better
understanding of the system and more input :)

> >* Occupied spaces and water spaces (for non-swimming globs) are counted
> >  as forbidden, as well as normal forbidden areas.
> That is odd. I often have globs stray into my forbidden areas (and 
> leave immediately), but I have never seen a glob stray into water or a 
> building. What's the difference there?

Forbidden areas are valleys, occupied spaces etc. are troughs.

Finally, thanks to nct giving me CVS access, here is the code as it
looks tonight:

http://savannah.nongnu.org/cgi-bin/viewcvs/glob2/glob2/src/Map.h?rev=1.137.2.1&only_with_tag=experimental&content-type=text/vnd.viewcvs-markup
http://savannah.nongnu.org/cgi-bin/viewcvs/glob2/glob2/src/Map.cpp?rev=1.197.2.1&only_with_tag=experimental&content-type=text/vnd.viewcvs-markup

It's not even close to compiling, but it shows the general direction I'd
like to be going in.

        - Andrew