Re: [glob2-devel] Pheramonal-Directional Algorithm

[Leo Wandersleb]

Hi

I'd say you have many good ideas of how things should work. pathfinding, as
was mentioned, is already bound to the buildings withe the used wavefront
algo. your proposal probably would save memory but at the cost of a more
complicated structure.
the ideas about automatically assigning workers to buildings and auto-repair
are really something to be solved to further minimize micromanagement.
perhaps that could envolve some strategy to make globs first gather the
needed amount of resources timed to arrive at the say inn when the last glob
leaves it. then the downtime of the inn could be minimized. this strategy
should definitively be implemented for automatic repair-processes as you
know repairing can potetially take very long.

:( still no inet at home and inet-cafe closes now. cu guys. sorry for beeing
so quiet and unproductive.

Giszmo

> --- Ursprüngliche Nachricht ---
> Von: Andrii Zvorygin <address@hidden>
> An: Globulation2 development mailing list <address@hidden>
> Betreff: Re: [glob2-devel] Pheramonal-Directional Algorithm
> Datum: Tue, 8 Nov 2005 23:35:05 -0500
> 
> oh right, i forgot to mention why the recent kills and average glob time
> to
> get back.
> if it knows recent kills then it could perhaps either request and send
> warriors along a particular path, or if the numebr is too high it will
> make
> a new path that will go around the danger zones.
> 
> if the buildings are what decide where it is that the globs should go then
> information such as average round time and path length would be very good.
> for instance if the average time is getting very high but the path short,
> then the building can assume that maybe there isn't much resource left,
> then
> say knowing the level of the globs that come to it, it can send the slow
> ones along the low resource route and the fast ones on the longer route
> but
> that might yield more fruit. (though I guess if you go that far it might
> be
> easier simply to check how much resource is available in an area). then if
> say there are no routes for non-swimmers then it simply wont hire those
> globs.
> 
> if we use the above then i guess the buildings would calculate say the
> three
> closest routes and if all three are swimming then the fourth over land
> (assuming that's possible)
> 
> building paths of course will end say three or four squares before they
> actually reach the resource to allow the globs to move freely to get at
> the
> resource, and once they get it they go on the path that will take them
> back.
> to resource and to path back using A*, so in order to have that we also
> have
> to have the building store the start point of the path back (globs should
> also be able to signal to the building if they can't find any resource
> (though the building can run checks every few seconds or so.
> 
> 
> 
> On 11/8/05, Andrii Zvorygin <address@hidden> wrote:
> >
> > Well if the type has the water/no water set then there isn't much of a
> > problem. As any glob if it does not find valid path will make it's own.
> So
> > if it is a glob that can't swim it will check and see if there is any
> > available wheat source say on the island. If not it can search for a
> > swimming pool.
> >
> > 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.
> >
> > 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.
> >
> > 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.
> >
> > 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
> 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.
> >
> >
> > anyways but most of these ideas will consume more RAM then we are
> > currently consuming, (though i'm not sure how much more) in any case i
> think
> > storing data in buildings will drastically decrease a lot of the
> problems to
> > do with paths (for instance how does a glob know which path to follow?)
> >
> > oh and btw, say if they also stored recent deaths and things like that.
> we
> > might be able to reduce the amount of cpu it takes for units to figure
> out
> > paths by simply having the buildings set the roads, and the globs will
> > follow them. then we can actually get rid of a lot of the RAM load
> created
> > by pheramones as we will only have to store one direction at a time.
> >
> > if a path is changed under a glob it will use A* to find it's way back
> to
> > it, (i'm thinking of making it a two step process, first it checks all
> > squares in a cricle going outwards around it for if it can find the path
> or
> > building, when and if it does it will use A* to get to it, if it doesn't
> > find the path or building then it will wait around until it is called
> upon
> > for another job for it to do.)
> >
> > paths will still be structured in the same way (middle path being with
> > strongest pheramone and on the side it has lower pheramones) same
> evasion
> > maneuvers will be used to get around objects etc. If a glob finds a
> problem
> > with the path, for instance it can't get through anywhere within the 7
> > square path, or if someone is for instance attacked on the path, it can
> send
> > message to building, and the building will reconstruct the path, I guess
> at
> > this point the glob can either find it's own way to the resource, or
> find
> > the path or building as was explained above, though i guess if it
> scanned
> > for resource along with path and building it would be a pretty easy
> decision
> > to make.
> >
> > though now that i think about it, maybe Dijkstra's algorithm will be
> > better then what I came up with in terms of scanning. And it wouldn' t
> be
> > too resource burdening as it will be rather rarely done.
> >
> > On 11/8/05, Andrew Sayers <address@hidden> wrote:
> > >
> > > On Tue, Nov 08, 2005 at 03:42:58PM -0500, Andrii Zvorygin wrote:
> > > > what i was thinking was that when the first glob using A* finds the
> > > > resources (as the trails will be from a certain inn say to the wheat
> > > > resource) we can along side the type destination borrow a bit to
> show
> > > if
> > > > any water squares are crossed in the proccess (this should be pretty
> > > > simple to implement, simply when it has found the optimal path it
> runs
> > > the
> > > > squares through to check if any are water squares, if yes then we
> set
> > > the
> > > > swim bit, if not then we don't)
> > > >
> > > > btw i forgot to mention, the type will point to 2 bytes that could
> > > store
> > > > the end location and swim bit, it wont store the locations to a
> > > precise
> > > > point, it can say divide the grid by 4, so instead of 512x512 it
> will
> > > be
> > > > 128x128, and not only will it take up less room. also if a glob gets
> > > lost
> > > > it will check the entire square for say wheat instead of just the
> > > original
> > > > wheat source.
> > >
> > > If the path crosses water, what then? Surely you need a different path
> > > for the globs that can't swim?
> > >
> > > - Andrew
> > >
> > >
> > > _______________________________________________
> > > glob2-devel mailing list
> > > address@hidden
> > > http://lists.nongnu.org /mailman/listinfo/glob2-devel
> > >
> >
> >
>