[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/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 Fri Jan 19, 2018 7:30 pm 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 erdman » Thu Nov 03, 2011 7:08 pm

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?
erdman
Major
 
Posts: 34
Joined: Thu Oct 27, 2011 12:52 am

Re: Ignoring path finding and using collaborative diffusion

Postby Narsis » Thu Nov 03, 2011 7:16 pm

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

Re: Ignoring path finding and using collaborative diffusion

Postby RyokuHasu » Fri Nov 04, 2011 10:01 am

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.
RyokuHasu
Captain
 
Posts: 25
Joined: Wed Nov 02, 2011 2:24 pm

Re: Ignoring path finding and using collaborative diffusion

Postby mac » Fri Nov 04, 2011 12:19 pm

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

Re: Ignoring path finding and using collaborative diffusion

Postby Parasprites » Fri Nov 04, 2011 1:12 pm

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.
Parasprites
Major-General
 
Posts: 224
Joined: Mon Oct 24, 2011 3:08 pm

Re: Ignoring path finding and using collaborative diffusion

Postby mac » Fri Nov 04, 2011 1:34 pm

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

Re: Ignoring path finding and using collaborative diffusion

Postby DrClaes » Fri Nov 04, 2011 1:42 pm

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.
DrClaes
Lieutenant-Colonel
 
Posts: 49
Joined: Sat Oct 29, 2011 6:27 am

Re: Ignoring path finding and using collaborative diffusion

Postby RyokuHasu » Fri Nov 04, 2011 3:23 pm

RyokuHasu
Captain
 
Posts: 25
Joined: Wed Nov 02, 2011 2:24 pm

Re: Ignoring path finding and using collaborative diffusion

Postby icefox » Fri Nov 04, 2011 4:01 pm

icefox
Cadet
 
Posts: 9
Joined: Wed Oct 26, 2011 6:08 pm

Re: Ignoring path finding and using collaborative diffusion

Postby mac » Sat Nov 05, 2011 2:34 am

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

PreviousNext

Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest