Избегание тупиков в игре змеи с движущейся пищей в питоне

Question

Я пытаюсь сделать змеиную игру, где 2 змеи соревнуются между собой. Одна змея просто следует за едой и избегает препятствий, другая - та, для которой я пишу код, и должен найти лучший способ добраться до еды. Пищевая позиция, каждый бит карты и положение другой змеи известны, а положение пищи меняется с каждым движением змей.

Если карта позволяет, если нет препятствий, змея может пройти через стены, чтобы перейти на другую сторону карты, например, карта - это пончик. Змея не перемещается по диагонали, только вертикально и горизонтально, и она не может двигаться назад.

Я использую поиск точки прыжка, чтобы найти способ питания, и он отлично работает, хотя при скорости 50 кадров в секунду игра немного замедляется. Основная проблема, с которой я сталкиваюсь, - найти способ избежать тупиков. Если еда заходит в тупик, я хочу подождать, когда она покинет тупик, но происходит то, что моя змея, идет туда, а затем умирает. Потому что я не избегаю тупиков, когда моя змея становится достаточно большой, иногда она падает в своем теле.

Это код агента моей змеи.

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 не будет проверена каждая плитка на сетке.

Если вам нужен пример программирования, просто спросите его в комментариях. У меня не было времени сделать это, но я могу сделать его позже, если потребуется. Кроме того, если вам нужно дополнительное разъяснение, просто спросите!