This article is part of the Diggin Project.
preface
After a month, we will try to play a wave of snake games with the help of Hamilton ring. Let’s start happily
The development tools
**Python version: **3.6.4
Related modules:
Pygame module;
And some modules that come with Python.
Environment set up
Install Python and add it to the environment variables. PIP installs the required related modules.
Introduction of the principle
Here we mainly talk about how to design algorithms to play snake games automatically. Here’s a quick definition of a Hamiltonian ring (from Wikipedia) :
- The Hamiltonian diagram is an undirected graph, developed by Sir William Hamilton,
- From a specified starting point to a specified end point, passing all other nodes on the way only once.
- In graph theory, a graph that contains a Hamiltonian loop,
- The closed Hamiltonian path is called the Hamiltonian cycle.
- A path that contains all the vertices in the graph is called a Hamiltonian path
- (Hamiltonian path, Traceable path)
- Hamilton graph definition: G=(V,E) is a graph,
- If a path in G passes through each vertex only once,
- We call this pathway the Hamilton pathway.
- If a circle in G passes through each vertex only once, the circle is called a Hamiltonian circle.
- If a graph has a Hamilton circle, it is called a Hamilton graph.
For example, there is a 4 by 4 map:
Then the Hamiltonian ring can be (not unique) :
By constructing a Hamiltonian ring, we can easily ensure that snakes don’t bump into themselves and die in the process. For example, if grid 0, 1, and 2 are our gluttonous snakes, where 2 is the head, 0 is the tail, and the rest are the body, we can construct Hamiltonian rings by using the following algorithm (Figure source reference [1]) :
Note that this algorithm is not a general algorithm for finding Hamiltonian rings, so there are some cases where Hamiltonian rings cannot be found (in order to improve the probability of finding Hamiltonian rings, we changed the original game map from 4025 squares to 2020 squares).
Specifically, the code implementation of the algorithm is as follows:
'''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
ifnode ! = 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
whilenode ! = 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
whilenode ! = 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
Copy the codeFind the shortest path from the snake’s head to its tail, and then build the desired Hamiltonian loop by expanding the path. (We’re playing snake here. The goal is to eat the food on the map, not to follow our own tail.)
Because it’s tedious and time-consuming to follow a fixed loop all the time, it might seem silly, for example, if the algorithm was designed above, the snake would behave like this:
To solve this problem, we can use the following rules to make the snake take some shortcuts (figure source reference [1]) :
Create an empty matrix as big as the game grid:
world = [[0 for i in range(self.num_cols)] for j in range(self.num_rows)]
Copy the codeThe empty matrix is then filled sequentially with ordered numbers according to the previously calculated Hamiltonian rings:
num = 1
node = snake.coords[-1]
world[node[1]][node[0]] = num
node = self.path[node]
whilenode ! = snake.coords[-1]:
num += 1
world[node[1]][node[0]] = num
node = self.path[node]
Copy the codeUsing these ordered numbers, we can easily find the snake’s shortcut (i.e. get as close to the randomly generated food on the map as possible without bumping into ourselves) :
# 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
ifnode ! = food:return {}
return self.reverse(path, snake.coords[0], food)
Copy the codeThat’s all, full source code see personal profile for relevant files.