Strategy Guide

This page is intended to give you a few ideas for climbing the ranks in the leaderboard. In order to minimize the size of examples, it is assumed that the edges are not wrapped for any of the examples.

Pathfinding

A frequent problem in Ants is going to be finding the shortest path from one your ants to potential objective squares. For example, you might have the following situation and want to find the food square that can be reached fastest:

.......
.*..a%*
.......

The easiest way to do this is with a breadth-first search from the ants location, noting the distance to a square as you mark it as visited. The above example would result in the following information:

5432123
6321a%4
5432123

Comparing the two food locations, we see that the left food square can be reached in 3 moves while the right food square can be reached in 4 moves, despite the fact that the distance to the right food square is shorter.

Taking any objective square, you can then use the numbers to trace back a shortest path from the ants starting location.

If you know your objective square for an ant before you start searching, you will find that A* search works quite well.

You can use a breadth-first search for many other things as well, such as simultaneously searching from all ant locations to partition the map into which squares each bot can reach first and finding what squares are visible to a bot.

Collecting Food / Growing Your Army

A naive way of collecting food would be to perform a breadth-first search from each food square to find its closest ant and moving that ant towards it.

If you wanted to move ants towards the closest food square first, you could iteratively perform these breadth-first searches from all non-covered food squares simultaneously using the one queue, moving an ant towards the appropriate food square as you find one.

Below are some example cases you might want to consider where the above two methods would not work optimally:

b...*..a.*

...bb...
........
........
**..a.*.