Python游戏开发，pygame模块，哈密顿环算法实现自动玩贪吃蛇小游戏 Python游戏开发，pygame模块，哈

前言时隔一个月，再带大家尝试借助哈密顿环来自动玩一波贪吃蛇小游戏呗，废话不多说，让我们愉快地开始吧~
开发工具 Python版本：3.6.4
相关模块：
【Python游戏开发，pygame模块，哈密顿环算法实现自动玩贪吃蛇小游戏】pygame模块；
以及一些python自带的模块。
环境搭建安装Python并添加到环境变量，pip安装需要的相关模块即可。
原理简介这里我们主要讲如何设计算法来自动玩贪吃蛇小游戏。先来简单介绍一下哈密顿环的定义(引自维基百科)：

哈密顿图是一个无向图，由哈密顿爵士提出，
由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。
在图论中是指含有哈密顿回路的图，
闭合的哈密顿路径称作哈密顿回路（Hamiltonian cycle），
含有图中所有顶点的路径称作哈密顿路径
（英语：Hamiltonian path，或Traceable path）。
哈密尔顿图的定义：G=(V,E)是一个图，
若G中一条通路通过且仅通过每一个顶点一次，
称这条通路为哈密尔顿通路。
若G中一个圈通过且仅通过每一个顶点一次，称这个圈为哈密尔顿圈。
若一个图存在哈密尔顿圈，就称为哈密尔顿图。

举个例子，有一个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 = https://www.it610.com/article/(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)

That's all，完全源代码详见个人主页简介获取相关文件。