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

[Joe Wells]

Kai Antweiler <address@hidden> writes:

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

Okay, let me explain my reasoning.  Clearly, it is not so obvious, if
I have to explain it.  :-)

A gradient is good for explorers because it simultaneously considers
the entire world of possible places for an explorer to explore.
Generally, until the entire world has been explored, there will be
thousands of possible destinations for an explorer to consider.
(Worlds range in size from 4096 cells for a 64 by 64 map to 262144
cells for a 512 by 512 map.)  Considering each unknown destination
separately is clearly impractical.  A gradient allows considering them
all simultaneously and allows easily combining searching desirability
with distance in making the decision.

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

Agreed.  However, the copying is much cheaper than recomputing the
gradient for each explorer.  :-)

I haven't been able to figure out a good way (and I suspect there
simply is no good way) to use a single gradient for all explorers.

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

The part described above actually seems to run fairly quickly.

In my later message, I discussed adding some additional steps (after
what is described above) which produce much better explorer behavior,
but seem to take more time.

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

The question in my mind is whether some additional thought in doing
the calculations more cleverly could reduce the expense substantially.

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

Or even a quad tree could conceivably be used.  It is not clear how
well this would work.  It would be more complicated.

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

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

Ooh.  Wraparound.  Good point.

(Anyway, I haven't tried yet to add any handling of revisiting
not-recently-seen locations.)

>> 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'm unlikely to have time to do any C++ programming, but I am happy to
help with designing algorithms.

>>  I wrote a quick test program in Perl to try this idea out.
>
> 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.  The program
will show you a sample map (plain ASCII in a terminal window) with
some explorers (letter “E”) exploring it and one step happening every
time you press space.  Just say whether you think that behavior is
good or not.

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

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.

-- 
Joe