Ignoring path finding and using collaborative diffusion

[erdman]

Suppose you have an ant 10 steps from a newly spawned food. If scents are diffused one step per turn, it will take 10 turns for the ant to even be aware of the presence of the food, plus another 10 steps for the ant to move to it. This seems suboptimal, especially if an opponent ant is 11-19 steps away and uses a more direct pathing algo. Further, after the food is consumed, there will be lingering scent that is diffused for some unknown length of time that could cause ants to chase a goal that no longer exists.

Is there an algorithm to fully diffuse a given map at each turn in an efficient manner?

[Narsis]

Suppose you have an ant 10 steps from a newly spawned food. If scents are diffused one step per turn, it will take 10 turns for the ant to even be aware of the presence of the food, plus another 10 steps for the ant to move to it. This seems suboptimal, especially if an opponent ant is 11-19 steps away and uses a more direct pathing algo. Further, after the food is consumed, there will be lingering scent that is diffused for some unknown length of time that could cause ants to chase a goal that no longer exists.

Is there an algorithm to fully diffuse a given map at each turn in an efficient manner?

what i've done is simply take a breadth-first approach. so every square gets updated every turn, but it starts updating from around goals first.

[RyokuHasu]

something that might be good to look into would be a hybrid of path finding and diffusion.

Think about it, use minimal path finding to avoid getting stuck and to navigate mazes, and use diffusion to push the general direction of the paths.

[mac]

something that might be good to look into would be a hybrid of path finding and diffusion.

Not sure I am following. A hybrid of the two would mean to compute both, with an obvious performance hit... or am I missing something?

Think about it, use minimal path finding to avoid getting stuck and to navigate mazes

Collaborative diffusion already achieve this.

and use diffusion to push the general direction of the paths.

Again... maybe I am failing to understand what you mean, but having bots following a "general direction" would probably mean to include an extra layer of computation: diffusion doesn't give you a "general" direction. It gives you a direct path to the most attractive goal (relative to your position).

Care to clarify?

[Parasprites]

I still don't see how diffusion is as awesome as claimed. You still have to do multiple diffusion steps per turn, so it's nearly equivalent to BFS.


In fact, in the case where there's only one goal, this is identical to BFS.

[mac]

I still don't see how diffusion is as awesome as claimed.

Diffusion strong points:
- scales much better(the number of pursuing agents is almost irrelevant and so it is the one of goals)
- virtuous behaviours emerge autonomously

[DrClaes]

I'm going down something similar to the diffusion road with my bot, and so far I'm liking how the ants distribute in the early part of the game, both in mazes and open maps. I think there's some good ideas in the paper linked to by the original poster, especially in reconceptualizing the game so the map is where most of the calculations are done as opposed to in the individual ants who have a much easier job.

Right now I've got gradients (computed breadth first and updated as the explored area of the map grows) running from food as it's discovered, from enemy hills, and from the edge of explored space. Each ant ends up with a list of "options" each turn, for example "4 moves to Food A, 10 moves to Food B, 15 moves to closest edge". Tentatively I've set up a greedy algorithm of sorts that sorts each ant's option list, then sorts the ants in order of shortest option, and starts assigning ant paths. I only assign one ant each to food (visible) and previously spotted food currently out of range.
Things I want to try out right now include:

Weighting the distances to prioritize some things more than others, for example prioritize the enemy hill when it's 4 times further away than the closest food. I've laid some foundations for doing this on a per-ant basis, which would allow for ant classes (soldier, worker et cetera).

Optimizing my choices of data structures and algorithms for the updating of the bfs data as the map grows.

Maybe only compute paths out to some given length (30? 50?) from food sources, since it's unlikely that it's worthwhile to go further for food, and this could save a lot of time on larger maps and eliminate the tedium of recalculating a lot of path lengths when the explored space wraps around.

Adding some tactics for when other ants are encountered.

What I've found so far is that the computation time grows linearly both with number of ants and number of found food tiles, ie probably O(n^2). Still, my problems from earlier attempts at, for example, moving away from the home hill, with ants piling up in corners and cul-de-sacs seem gone, and I think with a little tweaking of the weights for different goals I will have a nice way of distributing my ants over a variety of maps.

[RyokuHasu]

something that might be good to look into would be a hybrid of path finding and diffusion.

Not sure I am following. A hybrid of the two would mean to compute both, with an obvious performance hit... or am I missing something?

by itself diffusion is a lot easier to calc and a lot faster. but if you add a MILD path finding to go with it then you can avoid trapping yourself in dead ends as much.

[icefox]

Suppose you have an ant 10 steps from a newly spawned food. If scents are diffused one step per turn, it will take 10 turns for the ant to even be aware of the presence of the food, plus another 10 steps for the ant to move to it. This seems suboptimal, especially if an opponent ant is 11-19 steps away and uses a more direct pathing algo. Further, after the food is consumed, there will be lingering scent that is diffused for some unknown length of time that could cause ants to chase a goal that no longer exists.

Is there an algorithm to fully diffuse a given map at each turn in an efficient manner?

Lets say I have a 1d "world" and X means food and the numbers are the current food scent.

00X000

A simple example would be if i diffuse from 0 to n in the array. My world would look like the following at each step:

00X000
00X000
00X600
00X630
00X631

With a single pass through this world front to back everything to the right of the food will get a diffused food scent. After this diffusion any ant to the right would be able to find the food. On every turn I could reset the food diffused values back to 0 so only brand new food would be discovered by the ants. But for other things like enemy ants or areas to explore you might not want to reset it back to 0.

[mac]

if you add a MILD path finding to go with it then you can avoid trapping yourself in dead ends as much.

My bot is still not ready and I have tested it only on a single map [so it might simply be that I still have to bump into that problem], but so far I never got stack in a dead end (and I can't imagine how that could happen with my implementation). How do you get stuck ants with diffusion?