Re: [glob2-devel] a->b->c (pathfinding with zwischenstop)

[Kai Antweiler]

> Thanx for taking your time to think it over but i guess there are some
> misunderstandings.
>
>> 1. The first thing that comes into my mind is:
>> when deciding in which direction to go, try a field that reduces the
>> distance to the nearest resources and if possible the distance to the
>> building that controls the worker too (or at least doesn't increase
>> it).  Maybe consider a small disk instead of just the next field.
>> For a start this should weaken the problem in some cases.
>
> The now used algorithm (gradient/wavefront) does not allow this approach.
> ...
> Now corn is found by walking down the corn-landscape to level 0 and then the
> inn12 is found by walking down the inn12 landscape. if you mix 2 landscapes
> you get local minima where the glob is closest to both corn and inn12 but
> doesn't find neither the one nore the other.

> Bad idea, i think :( 
> Walk down the Inn12+corn gradient to a local minimum(/saddle point) and then
> procede with the normal algo. unfortunately this local min needn't be a
> global min. also the combined gradient might be const on wide areas. :( also
> the direct path to the shortest path between inn and corn would be an
> improvement it is far from beeing optimal.


Here you got me wrong.  The idea was to calculate each gradient the
usual way.  After that when it comes to determining which field a
glob should go next look at the resource gradient values of each
its neighbouring fields.  Take the ones with lowest gradient-value and
use the building gradient on theme to determine which field of these
is closest to the building.
If we take a static map for example then each turn the distance
glob-resource is reduced by one and the distance to the building
isn't increased unnecessarily - if possible even reduced.

(btw: In my opinion globs need not to behave optimal.
 If they do exactly what I want - that would be perfect.
 If they behave not silly - that should be fine enough.)

Since calculation of the gradient isn't touched at all, i expected
this to be easy to implement compared to totally new pathfinding
algorithm.


>> 2. When a worker gets a job for a new building-resource,
>> you could use the gradients to determine the resource the worker
>> is heading to. (Well this works not in constant time, but it is fast
>> since you know each step.  Combine this with 1. to get a promising
>> resource.)
>> Then you can compare the distances:
>> worker-this_resource-building
>> with
>> worker-building-nearest_resource-building
>> and dicide if resource or building should be the target.
>
> ?? if i got you right, you take the resource that's closest to the building
> in consideration. that resource doesn't need to be reachable by the glob at
> all.

I haven't thought about that.  But you could determine a path from
worker to the building as well and use the last field's gradients.


>> 3. If the worker hands over its first delivery to the building, it could
>> be let to the part of the building that is nearest to a needed
>> resource - only if that is not to far off and a considerable improvement.
>> (For example using a small gradient initiated from that field)
>> I think the actual improvement would be small, but the globs might
>> look smarter this way.
>
> again: if the spot is reachable, this could help.

Instead of starting a small gradient from that field, we could
start one from the field the worker is on and determine a field that
has minimum resource+building gradient and then make that one a target
by again a small gradient.  Then only reachable fields would be considered.
And if this field gets cut of from the worker we could calculate a new
one or use normal behaviour.


>> 4. Globs could go to the building before they start out for the resource.
>> Ok, this is ugly, but fast to calculate and never worse then 2 times
>> the optimal route.
>
> no way! that's the worst of all possibilities as a remote suply-inn would
> never get a single corn.

No, I distinguish between pathfinding and determining which building
gets the worker assigned.  I think it is done that way right now.


>> 5. Make globulish behaviour part of race customization and let
>> the user worry about it ;-)
>
> ??

This was meant to be funny.  One of the things that is on the list of
what should be implemented into glob2 in the far future is race
customization.  Part of that could be put on user level
(and why not include variables that influence pathfinding).

But that was not meant to be serious.
Never the less the general idea:
Take a bug and sell it as feature could lead to a solution.
Instead of thinking how to solve this pathfinding problem,
we could from time to time think about what advantage the
present implementation has and try to improve it.

Globs that travel long ways increase the observation
area.  Since we have special units for that, this isn't
going to win something.  But continuing the thought we
could implement level 3 warriors to get camouflage suits
and become invisible by observers.
Or give a special fruit the property of causing
this invisibilty for a time when eaten.

Or a total different idea which will eventual turn out to
become the killer feature that glob2 will be loved for in
the whole world ...


>> I guess here you are looking at two different inns.
>> The upper right inn and the lower left - is that correct?
>
> no. inns are 2x2. so it is just one inn.

Oh! I see.
Then this is belongs to case 3.

-- 
Kai Antweiler