每次更新网格中每个单元格的值需要太多时间。（蚂蚁，Hallengeaic网站)

Question

我偶然发现aichallenge.org网站上周，我认为这个“蚂蚁”游戏是学习Python和学习编写AI代码的好方法。在

游戏是一个（x，y）网格，最多可以包含一只蚂蚁。瓦片可以表示为陆地或水，这是不可通行的。在

我的人工智能做得很好，通过广度优先搜索算法发送蚂蚁收集食物，并使用*寻路攻击敌人的山丘。在

但是，我正在尝试实现的探索算法花费了太多的时间，大约700毫秒。我的人工智能每回合只允许500毫秒，这意味着它是不合格的。在

要执行探索，我想为每个平铺指定一个“ExploreValue”。这个值在游戏开始时从0开始，每转一圈增加1，在战争的迷雾中隐藏瓷砖。当互动程序可见时，我希望explore值重置为0。每只蚂蚁的视野半径为10平方。在

首先，我从每只蚂蚁中运行一个广度优先搜索，将分片标记为“可见”。每只蚂蚁大约需要10毫秒 之后，我迭代地图上的每一个图块以更新它们的“ExploreValue”。如果它们被标记为可见，则该值将重置为0，否则将增加1。在

在大约为100x100的地图上，这需要半秒钟以上的时间。在

这是代码，你觉得我能做些什么来让它运行得更快？ 我已经把我的列表转换成集合，因为它们应该更快。在

def do\u设置在游戏开始时运行一次，def do\u turn在游戏中的每个回合运行。在

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

Answer 1

除了提到的普通python here，还有一些更快的替代方法，比如Cython和{a3}。在

我个人用来挑战我的部分代码。你不必改变太多，它会给你戏剧性的速度提升。有一个很好的介绍Cython here。在

更新：

如果您无法找到哪些图块可见，我建议您查看this starter pack。它有一个2d numpy数组来显示可见的分片。在