Ignoring path finding and using collaborative diffusion

[heartcore1970]

Very informative thread!
This challenge is so much more a learning experience (steep curve!) for me, as it is a challenge. Thus far I have been challenging primarily myself.

I have just implemented collaborative diffusion using your blog post and the related PDF article. Took me more than an hour but low and behold: my ants are getting food all over the map!

Amazing how much fun this is!
Thanks

[athkalia]

thnx for all the advice.. I managed to do it after like a week of programming lol!

[zanirzrold]

Anyone who is doing this figured out how to do mazes using collaborative diffusion? On random walks I have beautiful flock-like behavior, but on mazes I get entirely stuck because my explore diffusion gets broken. Do I need to also introduce pathfinding/lampposts to get out of here?

[mac]

Do I need to also introduce pathfinding/lampposts to get out of here?

Absolutely not, you don't unless you wish to.

However you are not the first to say in this thread your ants get stuck with CD, but frankly it's hard for me to even understand how this is possible [I did three different iteration of my diffusion algorithm and in none of them this was an issue].

Could you articulate a bit more what the problem is and why it happens?

[zanirzrold]

Do I need to also introduce pathfinding/lampposts to get out of here?

Absolutely not, you don't unless you wish to.

However you are not the first to say in this thread your ants get stuck with CD, but frankly it's hard for me to even understand how this is possible [I did three different iteration of my diffusion algorithm and in none of them this was an issue].

Could you articulate a bit more what the problem is and why it happens?

I think the biggest problem is that things diffuse into the water

so if you have

___ WWWWWW
(Ant) _________ (FOOD)
___WWWWWW

That Ant will go for food that is twice as far as to the west. And its even worse in a situation like

W(FOOD)
WWWWWWW
W(Ant)

Because the ant will never want to run around and get that food (it will eventually become something like 1000 -> 300 -> 100 -> 30 -> 10 -> 3 V 1 V .3 <- .01 <- .003 <- .0001, whereas something that has land on four sides that is the same manhatten distance away will be 25x as strong. I see one thing happening a lot on my maps is
_____WWWWWWW
(Ant)__(Food)___W
____WW_______W
________________

and the ant will wiggle up and down and will only be cut free when another ant comes from the bottom and gets the food.

The most obvious solution would be to give each neighbor extra weight per water neighbor a la
switch(num neighbors that are water):
case 1:
gridvalue += .33gridavlue

etc, but I'm using python (technically, numpy) and doing this will slow things way down, although if its the only way I might have to do it anyways.

[bluegaspode]

you should not diffuse into water.
the diffusion formula should only take those neighbors into consideration, that have a diffusion value (which water has not)

then you get a proper diffusion 'floating around' the water

[infernalmachine]

I've had the same problem with the water squares. After reading your post I went and changed my code (thanks!) so that water is not relevant. There's 2 ways to do this that I can think of, neither of which should be all that expensive in comp. time.

1. Count the neighbors who aren't water, and divide by this number instead of 4 -- note here you can still add the 0 value for water to the sum -- it just won't count for anything -- or you can skip the addition of 0. This way is probably simplest if you are using a diffusion coefficient (D) of 0.25 (ie just averaging the neighbors).

2. In my case, I was using a different D, and had split the diffusion formula into parts so I could pre-calculate half of it. So changing the divisor would mess up my earlier calculations. What I did instead was to set the value of a water square to the same as the central square in the diffusion process (but still set it to 0 on the map).

So when looking at the 4 neighbors, if a neighbor square is water, add central square's value to neighbor total instead of 0, and then still divide by 4 to calculate new central square value. This cancels out the water square's contribution, but leaves non-water squares contributing 1/4 as before.

It definitely made an improvement to the wiggling ant problem.

The only concern is that now the diffusion map keeps getting hotter and hotter (because the water squares are no longer functioning as a sink), and at some point that means that information is lost, because the number of steps between high and low gets smaller over time. But I suppose I could just divide all values on map by 2 every so many turns if it becomes a problem.

[mac]

I think the biggest problem is that things diffuse into the water

Ouch. As others have pointed out, that's not how diffusion should work. Water is not permeable, so it has to stop the scent.

I see one thing happening a lot on my maps is
_____WWWWWWW
(Ant)__(Food)___W
____WW_______W
________________

and the ant will wiggle up and down and will only be cut free when another ant comes from the bottom and gets the food.

Diffusion requires a good deal of tweaking to its parameters to work. My ants too tends to go around obstacles rather then getting themselves in one tile wide passages... but they don't wiggle up-down... I suppose in your case is still the water problem. I'm confident I will eventually fix my bot too to get himself through the passage!

but I'm using python (technically, numpy) and doing this will slow things way down, although if its the only way I might have to do it anyways.

NumPy here too. My bot still doesn't implement attack analysis, however I'm using a fraction of the turn time and I still managed to rank ~250... rest assured: you definitively can fix your diffusion algorithm without timing out!

[stupidquestions]

This is a pretty basic question, but: How do you guys solve ant collision problems?

[mac]

This is a pretty basic question, but: How do you guys solve ant collision problems?

my friend "stupdianswers" suggested: "by avoiding each other!"

Seriously: you should specify what you want to know or even better: what your problem is and what you have tried so far to solve it...