[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4586: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4588: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4589: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4590: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
AI Challenge Forums • View topic - Ignoring path finding and using collaborative diffusion

It is currently Tue Dec 11, 2018 5:45 am Advanced search

Ignoring path finding and using collaborative diffusion

Share and discuss ideas for your entries here.

Re: Ignoring path finding and using collaborative diffusion

Postby mrflippy » Sat Nov 05, 2011 6:13 pm

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

Re: Ignoring path finding and using collaborative diffusion

Postby athkalia » Sun Nov 06, 2011 1:18 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)
athkalia
Cadet
 
Posts: 8
Joined: Thu Sep 30, 2010 12:25 am

Re: Ignoring path finding and using collaborative diffusion

Postby mac » Sun Nov 06, 2011 2:01 pm

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

Re: Ignoring path finding and using collaborative diffusion

Postby Parasprites » Sun Nov 06, 2011 2:15 pm

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

Re: Ignoring path finding and using collaborative diffusion

Postby DrClaes » Sun Nov 06, 2011 3:21 pm

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

Re: Ignoring path finding and using collaborative diffusion

Postby bluegaspode » Mon Nov 07, 2011 8:55 am

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

Re: Ignoring path finding and using collaborative diffusion

Postby IWriteCode » Mon Nov 07, 2011 9:13 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

Re: Ignoring path finding and using collaborative diffusion

Postby infernalmachine » Mon Nov 07, 2011 11:05 am

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.)
infernalmachine
Lieutenant-Colonel
 
Posts: 48
Joined: Fri Oct 21, 2011 2:25 pm
Location: Toronto, Canada

Re: Ignoring path finding and using collaborative diffusion

Postby Narsis » Mon Nov 07, 2011 6:51 pm

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.
Narsis
Cadet
 
Posts: 3
Joined: Thu Nov 03, 2011 4:34 am

Re: Ignoring path finding and using collaborative diffusion

Postby bluegaspode » Mon Nov 07, 2011 9:25 pm

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.
bluegaspode
Colonel
 
Posts: 51
Joined: Mon Nov 07, 2011 8:38 am

PreviousNext

Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron