It is currently Thu Jun 21, 2018 10:46 am Advanced search

- mrflippy
- Lieutenant
**Posts:**11**Joined:**Fri Oct 15, 2010 3:55 pm

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)

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)

- athkalia
- Cadet
**Posts:**8**Joined:**Thu Sep 30, 2010 12:25 am

- mac
- Brigadier-General
**Posts:**151**Joined:**Mon Oct 31, 2011 6:39 am

Not really. The hard part is in choosing the parameters and equations, not the actual implementation.

- Parasprites
- Major-General
**Posts:**224**Joined:**Mon Oct 24, 2011 3:08 pm

- DrClaes
- Lieutenant-Colonel
**Posts:**49**Joined:**Sat Oct 29, 2011 6:27 am

- bluegaspode
- Colonel
**Posts:**51**Joined:**Mon Nov 07, 2011 8:38 am

Moving is nog a problem, the scent will move as well... (and only 1 space at a time...)

- IWriteCode
- Cadet
**Posts:**2**Joined:**Tue Nov 01, 2011 7:19 pm

That disappearing middle square thing is characteristic of using 0.25 as the diffusion coefficient, because it turns the equation into a cellular automata. Obviously clamping helps, but it's still a little "blocky". If you try the 1d version, you notice that you get a lot of "shelves" towards the outside where 2 squares in a row are equal. Also, it appears that in one time step, only half of the cells actually change value, and then in the next one, the other half do while the first don't -- obviously you can use that to get 2-for-1 steps if it holds true for the 2d variety: like updating the black squares then the white ones on a chess board).

I think that the videos you link to may be using a lower value than 0.25 for the diffusion constant. In that case, the diffusion happens more slowly, but the process has more "history" to it. That or they're using 0.25 for the computational speed-up and then putting the old and new square values into a history function like g(t) = f(t)* alpha + (1 - alpha)* f(t-1), where f(x) is the diffusion formula and alpha obeys 0<= alpha <= 1, and is chosen for its "niceness" in terms of balancing the speed of propagation versus avoiding the flickering effect of the CA and the loss of a meaningful gradient. Obviously, the lower alpha is, the more historical and smooth it becomes but it will diffuse much more slowly.

Or you could just run the diffusion a few turns per turn, which would allow it to settle down a little in the centre. (I mean, there's no reason other than computational expense to be equating the time-step for diffusion with the time it takes an ant to move one square -- they're entirely independent processes.)

I think that the videos you link to may be using a lower value than 0.25 for the diffusion constant. In that case, the diffusion happens more slowly, but the process has more "history" to it. That or they're using 0.25 for the computational speed-up and then putting the old and new square values into a history function like g(t) = f(t)* alpha + (1 - alpha)* f(t-1), where f(x) is the diffusion formula and alpha obeys 0<= alpha <= 1, and is chosen for its "niceness" in terms of balancing the speed of propagation versus avoiding the flickering effect of the CA and the loss of a meaningful gradient. Obviously, the lower alpha is, the more historical and smooth it becomes but it will diffuse much more slowly.

Or you could just run the diffusion a few turns per turn, which would allow it to settle down a little in the centre. (I mean, there's no reason other than computational expense to be equating the time-step for diffusion with the time it takes an ant to move one square -- they're entirely independent processes.)

- infernalmachine
- Lieutenant-Colonel
**Posts:**48**Joined:**Fri Oct 21, 2011 2:25 pm**Location:**Toronto, Canada

clamping sources and then doing multiple diffusions per turn is the best way to solve that problem imo.

as for moving targets: one of the nice (and at times frustating) parts of diffusion is that it uses data from the previous turn(s). so although your target may move 1 square, the area in general will still be high. and if you repeat the diffusion process several times then it will settle down anyway.

as for moving targets: one of the nice (and at times frustating) parts of diffusion is that it uses data from the previous turn(s). so although your target may move 1 square, the area in general will still be high. and if you repeat the diffusion process several times then it will settle down anyway.

- Narsis
- Cadet
**Posts:**3**Joined:**Thu Nov 03, 2011 4:34 am

ok, using a coefficient like 0.2 or 0.1 works much much better than 0.25

Now I need to tackle the problem that (because my ants have a diffusion value of 0 to be used as 'goal obfuscation') around the hill no diffusion is left, for new ants to start exploring.

Now I need to tackle the problem that (because my ants have a diffusion value of 0 to be used as 'goal obfuscation') around the hill no diffusion is left, for new ants to start exploring.

- bluegaspode
- Colonel
**Posts:**51**Joined:**Mon Nov 07, 2011 8:38 am

Users browsing this forum: No registered users and 1 guest