The way I've implemented it, the diffusion of scent equals a weighted shortest path to the target in question, plain linear in other words. The smell of food disappears when it is eaten but as soon as that food spot is no longer in visual range it starts giving off a (weaker) scent.
The advantage to this for me over repeated breadth first searches originating from the ants can be summarized most simply: the hills and food tiles don't move! The shortest paths need updating as the explored space grows; I keep track of the edge of explored space and have also made provisions for pruning paths x steps out from certain objects (particularly food) which saves time since otherwise updates of shortest paths for all the foods takes quite some time on large maps with 150+ "spotted" food piles to check on.
I've got some crowding issues around the home hill on some maps; part of it is desirable (makes me harder to kill), but some of it is excessive, plus I haven't implemented collision handling yet, so if one of my assignments fails it ends up killing a few ants--it's very rare in the early game, attesting to the reasonably optimal assignment of tasks, but more common in the crowd around the home.
My next thing to try is to adapt my "gradient descent" to allow for avoiding enemy ants other than around the home hill, by allowing them to exude a "repellent" rather than attracting scent... we'll see how this works out...
As others have pointed out, much of this (all of it?) is not right or wrong, but different design choices and trade-offs that invite experimentation, iteration and hopefully discussion. Also, implementing these principles can be done with more or less elegance--personally, the idea of a simple rule set for the ants leading to emergent complex behavior is more appealing right now than tactical search trees for optimal tactical problems...
Also, we all come into this with different goals and motivations; I've read the contest rules to encourage this sort of discussion, as long as we don't share code amongst ourselves...
athkalia wrote:Can you help me a bit with this diffusion, I have a couple of questions:
a)diffusion of any target (e.g. food or hill) takes place in one turn on the whole map ?
b)when a food is eaten the scent of it disappears from the whole map instantly as well?
c)I am wondering how diffusion can help inside a maze. If the "solution" exit is visible then the scent will reach the ant. But if it isn't then what ? In general diffusion is only calculated on the visible tiles right ? (apart from exploration diffusion i guess)
d)Can you tell me how diffusion would work out on this simple scenario where on the very first turn the bot sees 2 foods
. . . F . . .
. . . . W. .
. . FW. . .
. . . . . . .
where F is food and W is water. I don't understand where I would start from for calculating diffusion values on a tile with a single calculation. Don't I have to visit every tile as many times as the food places are ? (Because each food affects the scent of each tile on the map but we can only calculate it when the tiles right next to it get their scent calculated)