上周我偶然发现了 aichallenge.org，我认为这个“ Ant ”游戏是学习 Python 和学习人工智能编码的好方法。
游戏是一个 (x,y) 网格，最多可以包含一只 Ant 。方 block 可以表示土地或水，这是无法通行的。
我的人工智能做得很好，通过广度优先搜索算法发送 Ant 收集食物，并使用 A* 寻路攻击敌人的山丘。
但是，我尝试实现的探索算法花费了太多时间，大约 700 毫秒。我的AI每回合只允许500毫秒，这意味着它被取消资格。
为了执行探索，我想为每个图 block 分配一个“ExploreValue”。该值在游戏开始时从 0 开始，并且每回合瓷砖隐藏在 war 迷雾下都会增加 1。当图 block 可见时，我希望将探索值重置为 0。每只 Ant 的视线半径为 10 个方 block 。
首先，我对每只 Ant 进行广度优先搜索，将图 block 标记为“可见”。每只 Ant 大约需要 10 毫秒 之后，我迭代 map 上的每个图 block 以更新它们的“ExploreValue”。如果它们被标记为可见，则该值将重置为 0，否则会增加 1。
在尺寸必须约为 100x100 的 map 上，这需要半秒以上的时间。
这是代码，你认为我可以做些什么来让它运行得更快？ 我已经将列表转换为集合，因为它们应该更快。
def do_setup 在游戏开始时运行一次，def do_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
最佳答案
有一些比提到的普通 python 更快的替代方案 here ，如Cython和pypy .
我个人在 AI 挑战赛中使用 Cython 来加速我的部分代码。您无需进行太多更改，它就能显着提高速度。 Cython 有一个很好的介绍 here .
更新:
如果您无法找到可见的图 block ，我建议您查看 this starter pack 。它有一个显示可见图 block 的 2d numpy 数组。
关于python - 每回合更新网格中每个单元格的值需要花费太多时间。 ( Ant ，AIChallenge.org)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10003659/