開發工具

Python版本：3.6.4

相關模塊：

pygame模塊；

以及一些python自帶的模塊。

關注公眾號：Python學習指南，回復“AI貪吃蛇2”即可獲取相關文件

環境搭建

安裝Python并添加到環境變量，pip安裝需要的相關模塊即可。

原理簡介

這里我們主要講如何設計算法來自動玩貪吃蛇小游戲。先來簡單介紹一下哈密頓環的定義(引自維基百科)：

1. 哈密頓圖是一個無向圖，由哈密頓爵士提出，

2. 由指定的起點前往指定的終點，途中經過所有其他節點且只經過一次。

3. 在圖論中是指含有哈密頓回路的圖，

4. 閉合的哈密頓路徑稱作哈密頓回路（Hamiltonian cycle），

5. 含有圖中所有頂點的路徑稱作哈密頓路徑

6. （英語：Hamiltonian path，或Traceable path）。

7. 哈密爾頓圖的定義：G=(V,E)是一個圖，

8. 若G中一條通路通過且僅通過每一個頂點一次，

9. 稱這條通路為哈密爾頓通路。

10. 若G中一個圈通過且僅通過每一個頂點一次，稱這個圈為哈密爾頓圈。

11. 若一個圖存在哈密爾頓圈，就稱為哈密爾頓圖。

舉個例子，有一個4*4的地圖：

那么哈密頓環就可以是(不唯一)：

通過構造哈密頓環，我們就可以很輕松地保證蛇在運動的過程中不會因為撞到自己而死掉。舉個例子，假設格子0，1，2是我們的貪吃蛇，其中2為蛇頭，0為蛇尾，其余為蛇身，則我們可以通過以下算法來構造哈密頓環(圖源參考文獻[1])：

注意，該算法并不是用來找哈密頓環的通用算法，因此存在找不到哈密頓環的情況(為了提高算法找到哈密頓環的概率，我們把原版游戲地圖里的4025個方格改成了2020個方格)。

具體而言，該算法的代碼實現如下：

'''check boundary'''def checkboundary(self, pos):
  if pos[0] < 0 or pos[1] < 0 or pos[0] >= self.num_cols or pos[1] >= self.num_rows:    return False
  return True'''the shortest'''def shortest(self, wall, head, food):
  wait = OrderedDict()
  node, pre = head, (-1, -1)
  wait[node] = pre
  path = {}  while wait:
    node, pre = wait.popitem(last=False)
    path[node] = pre    if node == food:      break
    if pre in path:
      prepre = path[pre]
      direction = (pre[0]-prepre[0], pre[1]-prepre[1])      if (direction in self.directions) and (direction != self.directions[0]):
        self.directions.remove(direction)
        self.directions.insert(0, direction)    for direction in self.directions:
      to = (node[0] + direction[0], node[1] + direction[1])      if not self.checkboundary(to):        continue
      if to in path or to in wait or to in wall:        continue
      wait[to] = node  if node != food:    return None
  return self.reverse(path, head, food)'''reverse path'''def reverse(self, path, head, food):
  if not path: return path
  path_new = {}
  node = food  while node != head:
    path_new[path[node]] = node
    node = path[node]  return path_new'''the longest'''def longest(self, wall, head, food):
  path = self.shortest(wall, head, food)  if path is None:    return None
  node = head  while node != food:    if self.extendpath(path, node, wall+[food]):
      node = head      continue
    node = path[node]  return path'''extend path'''def extendpath(self, path, node, wall):
  next_ = path[node]
  direction_1 = (next_[0]-node[0], next_[1]-node[1])  if direction_1 in [(0, -1), (0, 1)]:
    directions = [(-1, 0), (1, 0)]  else:
    directions = [(0, -1), (0, 1)]  for d in directions:
    src = (node[0]+d[0], node[1]+d[1])
    to = (next_[0]+d[0], next_[1]+d[1])    if (src == to) or not (self.checkboundary(src) and self.checkboundary(to)):      continue
    if src in path or src in wall or to in path or to in wall:      continue
    direction_2 = (to[0]-src[0], to[1]-src[1])    if direction_1 == direction_2:
      path[node] = src
      path[src] = to
      path[to] = next_      return True
  return False'''build a Hamiltonian cycle'''def buildcircle(self, snake):
  path = self.longest(snake.coords[1: -1], snake.coords[0], snake.coords[-1])  if (not path) or (len(path) - 1 != self.num_rows * self.num_cols - len(snake.coords)):    return None
  for i in range(1, len(snake.coords)):
    path[snake.coords[i]] = snake.coords[i-1]  return path

即先找到蛇頭到蛇尾的最短路徑，然后再通過不斷擴展路徑來構造我們所需要的哈密頓環。(可能有小伙伴會問啦，最短路徑都找到了，干嘛還擴成哈密頓環啊，注意，我們這里是在玩貪吃蛇，目標是吃到地圖上的食物，而不是不停地跟著自己的尾巴運動。)

因為始終遵循固定的環路既繁瑣又費時，看起來十分愚蠢，比如按照上面設計的算法，貪吃蛇會像下圖這個樣子運動：

為了解決這個問題，我們可以通過以下規則來讓蛇走一些捷徑(圖源參考文獻[1])：

翻譯過來就是先新建一個和游戲網格矩陣一樣大的空矩陣：

world = [[0 for i in range(self.num_cols)] for j in range(self.num_rows)]

然后根據之前計算的哈密頓環，利用有序數字來順序地填充這個空矩陣：

num = 1
node = snake.coords[-1]
world[node[1]][node[0]] = num
node = self.path[node]
while node != snake.coords[-1]:
  num += 1
  world[node[1]][node[0]] = num
  node = self.path[node]

利用這些有序數字，我們就可以輕松地尋找貪吃蛇的運動捷徑啦(其實就是在不撞到自己的前提下，盡可能快地接近地圖上隨機生成的食物，即下一步里的網格數字盡可能接近食物所在網格的數字)：

# obtain shortcut_pathwall = snake.coords
food = food.coord
food_number = world[food[1]][food[0]]
node, pre = wall[0], (-1, -1)
wait = OrderedDict()
wait[node] = pre
path = {}
while wait:
  node, pre = wait.popitem(last=False)
  path[node] = pre
  if node == food:    break
  node_number = world[node[1]][node[0]]
  neigh = {}
  for direction in self.directions:    to = (node[0]+direction[0], node[1]+direction[1])    if not self.checkboundary(to):      continue    if to in wait or to in wall or to in path:      continue    to_number = world[to[1]][to[0]]    if to_number > node_number and to_number <= food_number:      neigh[node_number] = to
  neigh = sorted(neigh.items(), key=itemgetter(0), reverse=True)
  for item in neigh:    wait[item[1]] = nodeif node != food:
  return {}
return self.reverse(path, snake.coords[0], food)

大功告成，完整源代碼詳見相關文件唄~