[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/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 - A BFS Tutorial in two images

It is currently Thu Dec 14, 2017 1:18 pm Advanced search

A BFS Tutorial in two images

Share and discuss ideas for your entries here.

A BFS Tutorial in two images

Postby BenJackson » Wed Nov 30, 2011 1:33 am

Lots of people are asking about how to pathfind and how BFS works in the ant grid. I figured the best way to help people was to make an animation that gives you a sense of how it works.

The grid below represents your map. Blacker squares are closer to the start. The row at the bottom is the queue you use within the BFS. Initially a start node is added and marked as distance "0". Immediately a marker (shown in yellow) is added to the queue which we will trip across after expanding all distance=0 nodes. Then the first entry in the queue (red squares) is popped off and "expanded". We examine its neighbors and mark them as being +1 from where we are. The expansion nodes are shown in blue, and any that have not yet been visited fly down into the queue for later work. When the yellow marker comes up we know we've finished all the nodes at a given distance and so we increment the distance and put the marker back at the end. When we find the marker and nothing else we are done.

One example is a totally open map. The other has obstacles in purple to show what happens when you run the BFS near water.

Image

Image
BenJackson
Colonel
 
Posts: 94
Joined: Sat Oct 29, 2011 4:16 am

Re: A BFS Tutorial in two images

Postby BenJackson » Wed Nov 30, 2011 1:43 am

On IRC antimatroid suggested a multi-source illustration. Here there are just two "start" nodes which become distance 0:

Image
BenJackson
Colonel
 
Posts: 94
Joined: Sat Oct 29, 2011 4:16 am

Re: A BFS Tutorial in two images

Postby pguillory » Wed Nov 30, 2011 4:05 am

Man that looks fantastic.
pguillory
Lieutenant
 
Posts: 10
Joined: Thu Nov 17, 2011 7:39 pm

Re: A BFS Tutorial in two images

Postby codetiger » Wed Nov 30, 2011 5:28 am

Simply the best way I can explain someone about diffusion maps.

I wish, you posted this few week earlier. I had to reinvent the wheel myself and it took 1 week to optimize but looks exactly the same as you have posted. Anyway, I would appreciate the time you've put in making this animations.

codetiger
Lieutenant-Colonel
 
Posts: 47
Joined: Sun Aug 21, 2011 4:47 am

Re: A BFS Tutorial in two images

Postby deccan » Wed Nov 30, 2011 8:02 am

Maybe there's something really obvious that I'm missing here, or maybe it's a secret that no one should share prior to the end of the contest, but what is the advantage of doing a BFS from multiple sources at the same time, as opposed to doing one serially from one source at a time as required?
deccan
Lieutenant
 
Posts: 18
Joined: Tue Nov 30, 2010 1:30 am

Re: A BFS Tutorial in two images

Postby bluegaspode » Wed Nov 30, 2011 8:42 am

If you want to find shortest path to food tiles you don't want to do that 100x for 100 food tiles (because you won't have enough time for it). So by doing ONE BFS from all food tiles at the same time, you can have ALL ants aim for the nearest food tile.

Obviously it's not optimal to have all ants actually run for the same food tile, so as an optimization one could remove all foodtiles that have an ant assigned from the first run, and do the BFS a second time to assign all left food tiles.

One can do it also vice versa, i.e. search from all ants at the same time. Then when you reach a food tile you will know the ant with the shortest path.
bluegaspode
Colonel
 
Posts: 51
Joined: Mon Nov 07, 2011 8:38 am

Re: A BFS Tutorial in two images

Postby antimatroid » Wed Nov 30, 2011 10:52 am

Using multiple sources is so you can find a minimum path from any of your sources to a target location, otherwise you either need to suboptimally pick a source to move before path finding or run the search for each source to find out which has a shortest path to a target.

If you want to move all sources to their closest target location I have found the best thing to do is a bfs with all of your target locations starting as sources then moving any ant you find into the square you found it from (or into its own square if the square you're moving it into already contains an ant or food).

If however you want to iteratively collect targets (so you don't send two ants towards the same target) then things become a little more complicated. For collecting food I iteratively collect uncollected food items using a new multi source and multi target A* search from moveable ant locations to uncollected food.

I'm still not entirely sure what the best way to iteratively collect targets is when your target set is larger, as my heuristic function for multi target A* doesn't really work very well then.
antimatroid
Brigadier-General
 
Posts: 126
Joined: Tue Feb 16, 2010 7:41 am

Re: A BFS Tutorial in two images

Postby deccan » Wed Nov 30, 2011 1:24 pm

deccan
Lieutenant
 
Posts: 18
Joined: Tue Nov 30, 2010 1:30 am

Re: A BFS Tutorial in two images

Postby antimatroid » Wed Nov 30, 2011 1:39 pm

If you're searching from food to ants I still don't see why you wouldn't just add all uncollected food to the search queue and search until you find an ant to move towards a food item, in this case you're still using multiple targets just that they're food locations.
antimatroid
Brigadier-General
 
Posts: 126
Joined: Tue Feb 16, 2010 7:41 am

Re: A BFS Tutorial in two images

Postby bluegaspode » Wed Nov 30, 2011 2:07 pm

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

Next

Return to Strategy

Who is online

Users browsing this forum: No registered users and 1 guest

cron