I stumbled on aichallenge.org last week and I thought this "Ants" game was a good way to both learn Python and learn to code AI.

The game is a (x,y) grid which can contain up to one ant. Tiles can be denoted as land or water, which is impassable.

My AI is doing a good job, sending ants to collect food through a breadth-first search algorithm and attacking enemy hills using A* pathfinding.

However, the algorithm I am trying to implement for exploration is taking way too much time, about 700 ms. My AI is only allowed 500 ms per turn, which means it is disqualified.

To perform exploration, I want to assign an "ExploreValue" to each tiles. This value starts at 0 at the start of the game and increases by 1 every turn the tile is hidden under the fog of war. When a tile is visible, I want the explore value to be reset to 0. Each ants has a sight radius of 10 squares.

First, I run a breadth-first search from each ant to tag tiles as "visible". This takes about 10 ms per ant After that, I iterate through every tile on the map to update their "ExploreValue". If they are tagged as visible then the value is reset to 0, else it is increased by one.

This takes more than half a second on maps that must be about 100x100.

Here is the code, what do you think I could do to make this run faster? I already converted my lists to sets since they are supposed to be faster.

def do_setup is run once at the start of the game, def do_turn is run every turn in the game.

def do_setup(self, ants):
  self.tile_visible = set() 

  self.explorevalue = {}  
  for row in range(ants.rows):
     for col in range(ants.cols):
        self.explorevalue[(row, col)]=0


def do_turn(self, ants):
    self.tile_visible = [] # empty visible list

#Define visible tiles set:
    ants_tiles_scan_distance=10

    for ant in ants.my_ants(): #start bfs of length ants_tiles_can_distance
        tiles_dist = {} #dict visited tiles
        tiles_from = {} #dict previous tiles
        from_nodes=[]
        from_nodes.append(ant)
        to_nodes=[]
        close_friends_count[ant]=0

        steps=1
        while (steps<=ants_tiles_scan_distance and len(from_nodes)>=1):
            for from_node in from_nodes:
                for new_loc in ants.tiles_voisins[(from_node)]:

                    if (new_loc not in tiles_dist):
                        tiles_dist[new_loc]=steps
                        to_nodes.append(new_loc)

                        if new_loc not in self.tile_visible:
                            self.tile_visible.append(new_loc)

            from_nodes=to_nodes
            to_nodes=[]
            steps=steps+1


#Update ExploreValues : 
    for tile in self.explorevalue.keys() :
        if (tile in self.tile_visible):
            self.explorevalue[tile]=0
        else:
            self.explorevalue[tile]=self.explorevalue[tile]+1

• python
• breadth-first-search

There's a few faster alternatives to normal python mentioned here, such as Cython and pypy.

I personally used Cython for the AI Challenge to speed up parts of my code. You don't have to change much and it gives you dramatic speed boosts. There's a good intro to Cython here.

Update:

If you're having trouble finding which tiles are visible, I'd suggest looking into this starter pack. It has a 2d numpy array that shows the visible tiles.