A BFS Tutorial in two images

[BenJackson]

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.

[BenJackson]

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

[pguillory]

Man that looks fantastic.

[codetiger]

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.

[deccan]

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?

[bluegaspode]

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.

[antimatroid]

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.

[deccan]

[antimatroid]

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.

[bluegaspode]