Re: [glob2-devel] Pheramonal-Directional Algorithm

[Andrew Sayers]

On Tue, Nov 08, 2005 at 11:14:50PM -0500, Andrii Zvorygin wrote:
(snip - water vs. no water)
>    and actually I was doing some reading and our globs can find the closest
>    resource using Dijkstra's Algorithm which is just like A* but non
>    directional.

Dijkstra's algorithm works very much like the wavefront algorithm, only
you have to recalculate it each time, for each glob.

Actually, to back up Stephane's point, a useful property of the
wavefront system is that, although it takes a lot of memory and
processor time, the amount it takes is not proportional to the number of
globs using the system.  A map with 10 globs will run as quickly or
slowly as a map with 10,000.

>    In the process of all this I was thinking that perhaps all paths for the
>    bulding should be "registered" with the building. That way for instance if
>    there is no wheat on the island, the globs will not have to search for it
>    more then once as they will see on the registration board a type path
>    which will basically be a null, as in no route to resource, say we give
>    them the first 3 digits, as in no wheat, no wood, no stone.  but then we
>    would need to make queries to the actual buildings, though in real life
>    that is how it would happen. if we aren't sure we ask for directions.

This would also have the useful property that globs look for the
resource closest to the building, not the one closest to themselves.
The following situation is quite common and quite frustrating:

R   G BBB
      BBB
      BBB R
"R" is a resource, "G" is a glob, "B" is a building

At present, the glob will repeatedly walk over to the resource nearest
to itself and back, rather than walking round to the other resource,
which it could harvest far more efficiently.

>    in fact we can go really crazy with it and have statistics for every path
>    at the originating building (though i'm not sure it would be very ram
>    efficient) and it could hold such statistics as approximate length of
>    path, number of recents deaths on the path(to determine it's safety), and
>    average time it takes for a glob to return with resource.

These ideas are interesting, but you should probably leave them to one
side until you've got a basic implementation done.  You can always come
back and work on the things that need work later on.

>    Though i'm not sure if our globs have Id's(maybe we can identify them
>    based on their instance number, or two bytes for their Id? :S) so I dono

Easy - you can store pointers to the globs rather than ID numbers.  Then
you can easily access all the information about each glob.

>    how feasible average time would be (though it would be great as it would
>    fix the inn bug, as a building could set how many workers it requires to
>    keep everything in stock
>    though i think with that we could change how it is that buildings select
>    workers as we could then have it as a priority, for instance lower
>    prioritied buildings will take less workers then they need to keep their
>    supply relatively in stock, as calculated by the average) then it would
>    decrease micromanagment as we would no longer have to worry about how many
>    workers work where. There can be safe guards made to keep the population
>    from dieing off, say if starvation goes over 30% then inns could be
>    prioritized along with new inns. and if there is a shortage of labour then
>    base swarm labour would increase along with construction of new swarms.

Again, this is a promising idea, but you need to get the groundwork done
first.  Also, we can't really discuss the unit system in any great depth
until it's been properly documented, so this is a debate for another
time.

        - Andrew