Re: [glob2-devel] testing a gradient for explorers

[Kai Antweiler]

>> The pathfinding to those areas can be skimpy.
>> And in those areas more expensive.
>> If we use your algorithm on each area we wouldn't have to copy and
>> reevaluate the whole map for each explorer.
>
> Unfortunately, I think to get good explorer behavior it is necessary
> to propagate the penalties added for all of the other explorers.
> I'd be delighted to be proven wrong ...

But when you enforce the penalties not always but only in the
squares and only for the explorers that are assigned to it
you could get a behaviour that is not too bad.

To general suggestions:

1. Don't focus to much on doing something good.  Sometimes it's more
   important that things just get done.
2. And most people try to optimize a procedure so that the worst case
   behaviour get's better.  Which is good in most cases.  But sometimes
   it's better to focus on a good average behaviour.
  (That's why I proposed different personalities for explorers.
   They would get the same information, but act differently.   )
   Also sometimes it's wise to partition a problem into several cases.

   Here we can use different algorithms for the start of a game
   (an explorer assigned to an suboptimal square could be disastrous),
   the uncovering phase and the rest of the game.


> I'm unlikely to have time to do any C++ programming, but I am happy to
> help with designing algorithms.

Sounds good.  I designed an gradient updating algorithm last year, but
haven't had time to implement it.  Unfortunately its design is scattered
over different mails (not in the mailing list).  Also the idea evolved
while thinking about a different problem.

At first we wanted to reduce the recomputation of resource gradients
for different teams.  They have to be different because they have
individual forbidden areas.
Then it got more and more complex and totally unrelated to the original
problem.
Now it should recompute an individual gradient like wheat gradient
of team 1, from its prior gradient and a list of environment changes.
(Globs right now are not part of the environment and have no influence
 on the computation.  And that is good because glob positions change
 frequently even compared to the resources.)
Putting in a new source is easy.  Putting in a new obstacle is the
hard part.  I solved this by making the adjacent fields new sources
that start with lower gradient values than normal sources.  And by
designing a repair algorithm algorithm that checks, if there is an
adjacent field that could be a source for the current one.  If not
the gradient value becomes 1 (0 = forbidden) an the adjacent fields
are will be repaired.  Of course you can only repair a field, when
the gradient algorithm has propagated down to the value of it.
So the algorithm needs a sorted input list of sources.
A vanishing source (like wheat that has been harvested) is much like
a new obstacle, and an vanishing obstacle much like a new source.
That is not totally correct, the init has to be done different, but
in principle it is.
There were a lot a details that I left out, but I hope the idea
became clear.


>> Perl is ugly.  I'll look at it in summer.
>
> You don't need to look at it.  Just run it (be sure to use my latest
> version) and say your opinion on the behavior you see.

I'm the wrong person, because I play way to little glob2 to compare
this to our behaviour.  But I ran your first program yesterday and
think that it works.
Better ask Leo about it, he also might help with the gradient.
But I think right now he is very busy with testing and fixing bugs.


> This could be interesting for globules in general.  It would be nice
> if the globules with different personalities had slightly different
> appearances, so that the users would understand what was happening and
> could enjoy it properly.

For workers and warriors it is more difficult, because they face
obstacles and must rely on the gradient.  Explorers are easier to
pathfind.

Maybe I shouldn't think about pathfinding explorers but about
searching the map for something with the help of explorers.
That would be more like your approach.

-- 
Kai Antweiler