今天给大家演示哈密顿环自动玩贪吃蛇小游戏呀~

开发工具

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_path
wall = 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]] = node
if node != food:
  return {}
return self.reverse(path, snake.coords[0], food)

大功告成，完整源代码详见相关文件呗~