Avoiding dead ends in snake game with moving food in python

Question

I'm trying to do a snake game, where 2 snakes compete between each other. One snake simply follows the food, and avoids obstacles, the other, is the one, for which i'm writing the code, and is supposed to find the best way to get to the food. The food position, every bit of the map and the position of the other snake is known, and the position of the food changes, with every movement of the snakes.

If the map allows it, if there is no obstacle, the snake can traverse through the walls, to go to the other side of the map, like the map is a donut. The snake doesn't move diagonally, only vertically and horizontally, and it can't move backwards.

I'm using jump point search to find a way to the food, and it's working fine, although at 50fps some times the game slows down a bit. The major problem i'm having, is finding a way to avoid dead ends. If the food gets in a dead end, i want to wait that it leaves the dead end, but what happens is that my snake, goes there, and then dies. Because i'm not avoiding dead ends, when my snake get's big enough, sometimes it crashes in its own body.

This is the code of the agent of my snake.

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 is the code to do the search. I reused a file i had with some classes to do a tree search, and changed it to use jump point search. And for every jump point i find i expand a node in the tree.

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

This is my code. I would appreciate any help to be able to avoid dead ends. I searched for similar problems but couldn't find any that helped me.

Answer 1

StackOverflow is not a coding service, so I'm not going to write your code for you, but I can most definitely tell you what steps you would need to take to solve your issue.

In your comments, you said it would be nice if you could check for dead ends before the game starts. A dead end can be classified as any point that has three or more orthogonally adjacent walls. I'm assuming you want every point leading up to a dead end that is inescapable. Here is how you would check:

1. Check every point starting from one corner and moving to the other, in either rows or columns, it doesn't matter. Once you reach a point that has three or more orthogonally adjacent walls, mark that point as a dead end, and go to 2.
2. Find the direction of the empty space next to this point (if any), and check every point in that direction. For each of those points: if it has two or more adjacent walls, mark it as a dead end. If it has only one wall, go to 3. If it has no walls, stop checking in this direction and continue with number 1.
3. In every direction that does not have a wall, repeat number 2.

Follow these steps until step 1 has checked every tile on the grid.

If you need a programming example, just ask for one in the comments. I didn't have time to make one, but I can make one later if needed. Also, if you need extra clarification, just ask!