用python移动食物避免蛇游戏中的死角

Question

我正在尝试做一个贪吃蛇游戏，其中两条蛇相互竞争。一条蛇只是跟随食物，避开障碍物，另一条蛇是我正在编写代码的一条蛇，并且应该找到获取食物的最佳方式。食物的位置，地图上的每一点和另一条蛇的位置都是已知的，食物的位置随着蛇的每一次移动而变化。

如果地图允许，如果没有障碍物，蛇可以穿过墙壁，走到地图的另一边，就像地图是一个甜甜圈一样。蛇不对角移动，只能垂直和水平移动，不能向后移动。

我正在使用跳点搜索来找到食物的路径，它工作得很好，尽管有时游戏速度会减慢一些。我面临的主要问题是找到一种方法来避免死胡同。如果食物进入死胡同，我想等待它离开死胡同。但发生的是，我的蛇走到那里，然后死亡。因为我不是在避免死胡同，当我的蛇变得足够大时，有时它会撞在自己的身体里。

这是我蛇的代理人的代码。

class AgentStudent(Snake, SearchDomain):
def __init__(self, body=[(0, 0)], direction=(1, 0), name="punkJD"):
    super().__init__(body, direction, name=name)
    self.count = 0;

#given the current state, and the next state, it returns a direction ( (1,0), (-1,0), (0,1), (0,-1) )
def dir(self, state, n_state):
    if state[0] == 0 and n_state[0] == (self.mapsize[0] - 1):
        return left
    elif state[0] == (self.mapsize[0] - 1) and n_state[0] == 0:
        return right
    elif state[1] == 0 and n_state[1] == (self.mapsize[1] - 1):
        return up
    elif state[1] == (self.mapsize[1] - 1) and n_state == 0:
        return down
    return n_state[0] - state[0], n_state[1] - state[1]

#doesn't matter for the question
def update(self, points=None, mapsize=None, count=None, agent_time=None):
    self.mapsize = mapsize
    return None

#given current position and food position, it will create a class that will do the search. Seach code bellow
def search_food(self, pos, foodpos):
    prob = SearchProblem(self, pos, foodpos, self.olddir)
    my_tree = SearchTree(prob, self.mapsize, self.maze)
    #doesn't matter, before i was using A*, but then i changed my whole search class
    my_tree.strategy = 'A*'
    return my_tree.search()

#given the current position and the direction the snake is faced it returns a list of all the possible directions the snake can take. If the current direction is still possible it will be put first in the list to be the first to be considered
def actions(self, pos, dir):
    dirTemp = dir
    invaliddir = [x for (x, y) in self.complement if y == dir]
    validdir = [dir for dir in directions if not (dir in invaliddir)]
    validdir = [dir for dir in validdir if
                not (self.result(pos, dir) in self.maze.obstacles or self.result(pos, dir) in self.maze.playerpos)]
    dirList = [dirTemp] if dirTemp in validdir else []
    if dirList != []:
        for a in range(len(validdir)):
            if validdir[a] != dirTemp:
                dirList.append(validdir[a])
        return dirList
    return validdir

#given the current position and the current direction, it returns the new position
def result(self, a, b):
    n_pos = a[0] + b[0], a[1] + b[1]
    if n_pos[0] == -1:
        n_pos = (self.mapsize[0] - 1), a[1] + b[1]
    if n_pos[1] == -1:
        n_pos = a[0] + b[0], (self.mapsize[1] - 1)
    if n_pos[0] == (self.mapsize[0]):
        n_pos = 0, a[1] + b[1]
    if n_pos[1] == (self.mapsize[1]):
        n_pos = a[0] + b[0], 0
    return n_pos

#given the current position and food position it returns the manhattan distance heuristic
def heuristic(self, position, foodpos):
    distancex = min(abs(position[0] - foodpos[0]), self.mapsize[0] - abs(position[0] - foodpos[0]))
    distancey = min(abs(position[1] - foodpos[1]), self.mapsize[1] - abs(position[1] - foodpos[1]))
    return distancex + distancey

#this function is called by the main module of the game, to update the position of the snake
def updateDirection(self, maze):
    # this is the brain of the snake player
    self.olddir = self.direction
    position = self.body[0]
    self.maze = maze
    # new direction can't be up if current direction is down...and so on
    self.complement = [(up, down), (down, up), (right, left), (left, right)]


    self.direction = self.search_food(position, self.maze.foodpos)

Bellow是执行搜索的代码。我重用了我拥有的文件和一些类来进行树搜索，并将其更改为使用跳点搜索。对于我找到的每个跳点，我都会扩展树中的一个节点。

class SearchDomain:

def __init__(self):
    abstract

def actions(self, state):
    abstract

def result(self, state, action):
    abstract

def cost(self, state, action):
    abstract

def heuristic(self, state, goal_state):
    abstract

class SearchProblem:
def __init__(self, domain, initial, goal,dir):
    self.domain = domain
    self.initial = initial
    self.goal = goal
    self.dir = dir
def goal_test(self, state):
    return state == self.goal

# class that defines the nodes in the tree. It has some attributes that are not used due to my old aproach.
class SearchNode:
def __init__(self,state,parent,heuristic,dir,cost=0,depth=0):
    self.state = state
    self.parent = parent
    self.heuristic = heuristic
    self.depth = depth
    self.dir = dir
    self.cost = cost
    if parent!=None:
        self.cost = cost + parent.cost
def __str__(self):
    return "no(" + str(self.state) + "," + str(self.parent) + "," + str(self.heuristic) + ")"
def __repr__(self):
    return str(self)

class SearchTree:


def __init__(self,problem, mapsize, maze, strategy='breadth'): 
    #attributes used to represent the map in a matrix
    #represents obstacle
    self.OBS = -1
    #represents all the positions occupied by both snakes
    self.PPOS = -2
    #represents food position
    self.FOODPOS = -3
    #represents not explored
    self.UNIN = -4
    self.problem = problem
    h = self.problem.domain.heuristic(self.problem.initial,self.problem.goal)
    self.root = SearchNode(problem.initial, None,h,self.problem.dir)
    self.open_nodes = [self.root]
    self.strategy = strategy
    self.blacklist = []
    self.pqueue = FastPriorityQueue()
    self.mapa = maze
    #here i initialize the matrix to represent the map
    self.field = []
    for a in range(mapsize[0]):
        self.field.append([])
        for b in range(mapsize[1]):
            self.field[a].append(self.UNIN)
    for a,b in maze.obstacles:
        self.field[a][b] = self.OBS
    for a,b in maze.playerpos:
        self.field[a][b] = self.PPOS
    self.field[maze.foodpos[0]][maze.foodpos[1]] = self.FOODPOS
    self.field[self.root.state[0]][self.root.state[1]] = self.UNIN


#function to add a jump point to the priority queue
def queue_jumppoint(self,node):
    if node is not None:
        self.pqueue.add_task(node, self.problem.domain.heuristic(node.state,self.problem.goal)+node.cost)

# given a node it returns the path until the root of the tree
def get_path(self,node):
    if node.parent == None:
        return [node]
    path = self.get_path(node.parent)
    path += [node]
    return(path)

#Not used in this approach
def remove(self,node):
    if node.parent != None:
        a = self.problem.domain.actions(node.parent.state, node.dir)
        self.blacklist+=node.state
        if a == []:
            self.remove(node.parent)
    node = None



#Function that searches for the food
def search(self):
    tempNode = self.root
    self.queue_jumppoint(self.root)
    count = 0
    while not self.pqueue.empty():
        node = self.pqueue.pop_task()
        actions = self.problem.domain.actions(node.state,node.dir)
        if count == 1:
            tempNode = node
        count+=1

        #for every possible direction i call the explore function that finds a jump point in a given direction
        for a in range(len(actions)):
            print (a)
            print (actions[a])
            jumpPoint = self.explore(node,actions[a])
            if jumpPoint != None:
                newnode = SearchNode((jumpPoint[0],jumpPoint[1]),node,self.problem.domain.heuristic(node.state,self.problem.goal),actions[a],jumpPoint[2])
                if newnode.state == self.problem.goal:
                    return self.get_path(newnode)[1].dir
                self.queue_jumppoint(newnode)

    dirTemp = tempNode.dir
    return dirTemp

#Explores the given direction, starting in the position of the given node, to find a jump point
def explore(self,node,dir):
    pos = node.state

    cost = 0

    while (self.problem.domain.result(node.state,dir)) != node.state:

        pos = self.problem.domain.result(pos, dir)
        cost += 1

        #Marking a position as explored
        if self.field[pos[0]][pos[1]] == self.UNIN or self.field[pos[0]][pos[1]] == self.PPOS:
            self.field[pos[0]][pos[1]] = 20
        elif pos[0] == self.problem.goal[0] and pos[1] == self.problem.goal[1]:  # destination found
            return pos[0],pos[1],cost
        else:
            return None

        #if the snake is going up or down
        if dir[0] == 0: 

            #if there is no obstacle/(or body of any snake) at the right but in the previous position there was, then this is a jump point
            if (self.field [self.problem.domain.result(pos,(1,0))[0]] [pos[1]] != self.OBS and self.field [self.problem.domain.result(pos,(1,0))[0]] [self.problem.domain.result(pos,(1,-dir[1]))[1]] == self.OBS) or \
            (self.field [self.problem.domain.result(pos,(1,0))[0]] [pos[1]] != self.PPOS and self.field [self.problem.domain.result(pos,(1,0))[0]] [self.problem.domain.result(pos,(1,-dir[1]))[1]] == self.PPOS):
                return pos[0], pos[1],cost

            #if there is no obstacle/(or body of any snake) at the left but in the previous position there was, then this is a jump point
            if (self.field [self.problem.domain.result(pos,(-1,0))[0]] [pos[1]] != self.OBS and self.field [self.problem.domain.result(pos,(-1,0))[0]] [self.problem.domain.result(pos,(1,-dir[1]))[1]] == self.OBS) or \
            (self.field [self.problem.domain.result(pos,(-1,0))[0]] [pos[1]] != self.PPOS and self.field [self.problem.domain.result(pos,(-1,0))[0]] [self.problem.domain.result(pos,(1,-dir[1]))[1]] == self.PPOS):
                return pos[0], pos[1],cost

        #if the snake is going right or left
        elif dir[1] == 0:

            #if there is no obstacle/(or body of any snake) at the upper part but in the previous position there was, then this is a jump point
            if (self.field [pos[0]][self.problem.domain.result(pos,(1,1))[1]] != self.OBS and self.field [self.problem.domain.result(pos,(-dir[0],dir[1]))[0]] [self.problem.domain.result(pos,(1,1))[1]] == self.OBS) or \
            (self.field [pos[0]][self.problem.domain.result(pos,(1,1))[1]] != self.PPOS and self.field [self.problem.domain.result(pos,(-dir[0],dir[1]))[0]] [self.problem.domain.result(pos,(1,1))[1]] == self.PPOS):
                return pos[0], pos[1],cost

            #if there is no obstacle/(or body of any snake) at the down part but in the previous position there was, then this is a jump point
            if (self.field [pos[0]] [self.problem.domain.result(pos,(-1,-1))[1]] != self.OBS and self.field [self.problem.domain.result(pos,(-dir[0],dir[1]))[0]] [self.problem.domain.result(pos,(-1,-1))[1]] == self.OBS) or \
            (self.field [pos[0]] [self.problem.domain.result(pos,(-1,-1))[1]] != self.PPOS and self.field [self.problem.domain.result(pos,(-dir[0],dir[1]))[0]] [self.problem.domain.result(pos,(-1,-1))[1]] == self.PPOS):
                return pos[0], pos[1],cost

        #if the food is aligned in some way with the snake head, then this is a jump point
        if (pos[0] == self.mapa.foodpos[0] and node.state[0] != self.mapa.foodpos[0]) or \
        (pos[1] == self.mapa.foodpos[1] and node.state[1] != self.mapa.foodpos[1]):
            return pos[0], pos[1],cost

        #if the food is in front of the head of the snake, right next to it, then this is a jump point
        if self.field[self.problem.domain.result(pos,(dir[0],dir[1]))[0]][self.problem.domain.result(pos,(1,dir[1]))[1]] == self.FOODPOS:
            return pos[0], pos[1],cost

        ##if an obstacle is in front of the head of the snake, right next to it, then this is a jump point
        if self.field[self.problem.domain.result(pos,(dir[0],dir[1]))[0]][ self.problem.domain.result(pos,(1,dir[1]))[1]] == self.OBS:
            return pos[0], pos[1],cost



    return None


class FastPriorityQueue:

def __init__(self):
    self.pq = []                         # list of entries arranged in a heap
    self.counter = 0                     # unique sequence count

def add_task(self, task, priority=0):
    self.counter+=1
    entry = [priority, self.counter, task]
    heapq.heappush(self.pq, entry)

def pop_task(self):

    while self.pq:

        priority, count, task = heapq.heappop(self.pq)
        return task
    raise KeyError('pop from an empty priority queue')

def empty(self):

    return len(self.pq) == 0

这是我的密码。我非常感谢任何帮助，以避免死路一条。我搜索了类似的问题，但找不到任何对我有帮助的问题。

Answer 1

StackOverflow不是一个编码服务，所以我不会为您编写代码，但我可以非常明确地告诉您需要采取哪些步骤来解决您的问题。

在你的评论中，你说如果你能在游戏开始前检查死胡同，那就太好了。死胡同可以归类为具有三个或更多正交相邻壁的任何点。我假设你希望每一点都通向不可避免的死胡同。以下是您将如何检查：

1. 检查每个点从一个角开始并移动到另一个点，无论是行还是列，都没关系。到达具有三个或更多正交相邻壁的点后，将该点标记为死胡同，然后转到 2。
2. 找到此点旁边的空白区域的方向（如果有），并检查该方向的每个点。对于这些点中的每一个：如果它有两个或更多相邻的墙，则将其标记为死胡同。如果它只有一堵墙，请转到 3。如果它没有墙壁，请停止向这个方向检查并继续数字 1。
3. 在每个没有墙的方向上，重复数字 2。

按照以下步骤操作，直到步骤 1 检查了网格上的每个磁贴。

如果您需要编程示例，只需在评论中询问一个。我没有时间做一个，但如果需要，我可以稍后做一个。另外，如果您需要额外的说明，请询问！