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

[Kai Antweiler]

> i see a problem in pathfinding that i don't see any solution to within
> the capabilities of gradient maps. if a glob wants to put corn into
> some swarm it runs to the closest corn and then to the swarm rather
> than to the corn that minimizes the way start-corn-swarm.
> Who has a conceptual approach to this problem? I'll keep thinking it
> over and ll let u know if i have a good idea on it.

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.


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.


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.


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.


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


> P.S.: Little Example:
> Even wors when the [G]lob has to do the job many times and does it bad
> again and again like in this situation:
> [C]orn, [H]ospital, [I]nn
>
> C
> C
> CHHG
> CHH
> CII
> CII
> Cx
> C
>
> G runs around H again and again rather than sitting at x and handing
> in the C.

I guess here you are looking at two different inns.
The upper right inn and the lower left - is that correct?
This is a different problem than that of finding a good route.

The problem seems to be: which building should be allowed to claim the
worker.  So when the buildings have to decide which of it gets it, you
can take the building-resource-distance into account - and increase
the weight this value gets by the amount of resource of this kind the
building needs.
(Only if the workpower is low)

-- 
Kai Antweiler