glob2-devel
[Top][All Lists]

## Re: [glob2-devel] Pheramonal-Directional Algorithm

 From: Andrii Zvorygin Subject: Re: [glob2-devel] Pheramonal-Directional Algorithm Date: Tue, 8 Nov 2005 23:14:50 -0500

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