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

[Andrew Sayers]

Again, replying to everyone at once.

First, sorry about the ambiguous branch name - I didn't realise that the
precedent was one-branch-per-feature, so I'll change it with my next
upload.

Second, the gradient system reminded me of Dijkstra's algorithm, but
that's probably because it's the only shortest path algorithm I know.  I
find the similarity to flood filling is interesting, even if it's not
the exact same thing.  I've made a couple of references to this thread
on the wiki, which I think is good enough documentation for the topic on
its own.

Third, yes - you're all right about danger and I'm wrong :)
Actually, we're sort of tangling up the issues of compound and danger
gradients here, so I'll try and split them up a bit:

__ danger gradients __

In principle, I think that gradients are an appropriate way to determine
how a warrior reaches a target, just as they are appropriate to
determine how a worker reaches a resource.  However, as you've all been
trying to tell me, they are not an appropriate way of getting workers to
avoid danger.  Besides the problems with my implementation, it confuses
gradients (which are a shortest path algorithm) with tower attacks
(which are based on raw distance).  So I need to split this issue in two
again:

_ Warriors _

Danger gradients strike me as a good solution as I described them
originally.  However, since warriors want to attack each other, they
would need to be a hilltop on the danger gradient.  Since they move
about a lot, there could be an issue there with them consuming an awful
lot of processor time.  Also, it might be interesting to look at
modifying danger gradients for different teams:

If player A is allied with B, not happy with C, and trying
to destroy D, his danger gradient for B could be zeroed out, his
gradient with C halved, and his gradient with D left as is.  This way,
he would never attack B, and would prefer attacking D over C.

But that's an issue for the future.  The question for today is: if it
were calculated like a normal gradient, that snakes around forbidden
areas and obstacles, does this sound like a sensible idea?  What if we
played around with elevations so that warriors preferred to attack a
more distant tower rather than a nearby inn?  Would recalculating be too
processor-intensive?

_ Workers _

If we agree that workers shouldn't be walking through fire to get to a
resource, there's two better solutions than working with compound
gradients.  First, if a resource is within firing range of a tower, just
don't make it a hilltop.  Globs will then ignore it for the purposes of
finding resources.  Second, if a glob is killed or critically injured on
its way to a resource, automatically mark that resource as a forbidden
area.

The second solution would be pretty easy to implement - when a glob is
killed/injured, you follow the gradient along to the nearest hilltop,
and mark that square bad.  We might need to do something about marking
squares adjacent to it as forbidden (so that workers actually avoid the
areas), but that strikes me as a minor practical detail that can be
worked out later.

The first solution would presumably be easy, but it reminds me of an
important question - does anybody know what sectors are there for?
It's a part of the code that seems to only be called during display and
when the map gets updated each tick.  The sector map is like the normal
map, but 1/16th the scale (ie. one sector per 16x16 map section).
Sectors contain linked lists of bullets and bullet explosions from
towers in their area.  I'm sure they serve a purpose, but I'd like to
know what that purpose is - and given the low number of bullets there
would be in the air at any given time, whether there's a better
implementation (e.g. a plain 2D linked list).

__ Compound gradients __

In its simplest form, this is just a different way of calculating
gradients.  Rather than, say, examining forbidden gradients first
followed by resource gradients, you examine them both at the same time,
with sufficient weight given to forbidden gradients that they will
always trump resource gradients.  One weakness of the system is that you
can only compare 4 independent gradients at once (given an 8 bit
gradient and 32 bit comparison), but a strength is that it allows you to
express gradients in a more simple and adaptable way (e.g. negative
gradients).

>From the discussion so far, I don't see any problem with this approach.

        - Andrew