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

[Kai Antweiler]

>> Obviously, explorers should follow a gradient based on exploring
>> unknown and/or not-recently-seen locations.

Not that obvious.  There are no obstacles for explorers so pathfinding
is generally much easier than for workers.  But if we want to improve
the quality of exploration we can think about that.

>>  The main difficulty with
>> this is how to prevent all the explorers from going to the same
>> destination.  I suggest the following idea.  Calculate some reasonable
>> gradient for which locations would be good to explore.  (I will
>> suggest one below.)  Then, for each explorer, make a copy of this
>> gradient.

That copying might be to slow.  This alone is linear in time to the
mapsize for each explorer.


>>  Flip the copy (i.e., consider 0 to be high and 255 (or
>> whatever the highest possible value is) to be low).  Raise the
>> location of each _other_ currently-exploring (i.e., not seeking
>> food/healing or assigned to a exploration flag) explorer by some
>> amount (e.g., 10).  (It is important that we don't do this for the
>> explorer the gradient is for, because that would be likely to destroy
>> the information about the unexplored thing that the explorer is
>> currently "seeking".  The way I propose to do it will lower peaks that
>> are in some sense "assigned" to _other_ explorers.)  Apply the
>> gradient algorithm to make the gradient valid again.

I have to check this.  This might often take a very long time as well.


>> Then flip the resulting gradient (undoing the first flip).
>> (Flipping doesn't have to modify the numbers for each location; you
>> just switch which direction you consider up or down.)  I think this
>> should do a good job of getting distinct explorers to explore
>> distinct parts of the world.  Comments?  Is my idea any good or
>> does it suck?

Yes should work.  But a lot more expensive.
It might be worth to think about partitioning a map in n square areas,
calculatate the average unknowness for each part and assign the areas
to explorers, based on a score of unknowness and distance to the
explorer.
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.


>>  (In the information recorded about what is not
>> recently seen, do we know how long it has been since the location has
>> been seen?)

I doubt it, but this shouldn't be a problem.  One 32bit layer of the map
and each time we see a field, it will get a time stamp.
If 32bit isn't enough for a game we can choose circular time for the stamp:
current game time % 2^32


> I did not get any feedback on this, so I still don't know what people
> think of this idea.

When you write about gradient the other devs probably expect me to
read it.  And in ignore it in such busy times.
And I won't have as much time to care about glob2 as I had last month.
I try to focus my glob2 attention on organizational issues right now.

But since this seems to be important for you I thought I should study
it.

Well here is my the opinion:
Nice idea.  But probably it is not fast enough, for many explorers.
Maybe we can someday adopt it.  
If you are willing to implement it someday and I have time, I would like
to help you.  Are you familiar with C++?


>  I wrote a quick test program in Perl to try this idea out.

Perl is ugly.  I'll look at it in summer.


ps:
There is some idea that got while reading this mail, to extent the
current explorer pathfinding.
We could give different explorers different personalities.
Some that like to work in a breadth first search way,
some that are more into going for far journeys.
Intermediates of this or zick-zack-explorers.
Explorer that love to be near enemies.
Hydrophobic explorers.

-- 
Kai Antweiler