Re: [glob2-devel] Pheramonal-Directional Algorithm

[Andrii Zvorygin]

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