python - DFS Snake 求解算法（NoneType 对象没有 len）

Question

我正在网格上使用 DFS（深度优先搜索）制作蛇求解算法。这条蛇大部分时间都在工作，但我一直收到这个错误。

我的朋友也发布了一个关于 BFS（广度优先搜索）的类似问题，我们在同一个组中并且有相同的错误

这是游戏完整运行的一些输出，直到出现此 NoneType 错误。起始位置表示蛇头的位置。食物位置表示你要寻路的食物在哪里，食物位置后面的数组是当前食物的路径，后面的元组是它应该沿着它的路径前进的方向。每当蛇吃掉食物时，食物的位置就会随机化，并以新食物的标题输出到控制台。我相信我知道为什么代码会崩溃，但我不知道如何修复它。该算法试图在蛇在食物上时找到一条具有旧食物位置的路径，这会生成一个空路径，因为它们的路径长度为 0。即使已经生成了一个新的食物位置。

一直向下滚动到 main 方法

start: 
(9.0, 9.0)
food:
(2.0, 6.0)
[(9, 9), (9, 8), (9, 7), (9, 6), (8, 6), (7, 6), (6, 6), (5, 6), (4, 6), (3, 6), (2, 6)]
(0, -1)
turned
moved
start: 
(9.0, 8.0)
food:
(2.0, 6.0)
[(9, 8), (9, 7), (9, 6), (8, 6), (7, 6), (6, 6), (5, 6), (4, 6), (3, 6), (2, 6)]
(0, -1)
turned
moved
start: 
(9.0, 7.0)
food:
(2.0, 6.0)
[(9, 7), (9, 6), (8, 6), (7, 6), (6, 6), (5, 6), (4, 6), (3, 6), (2, 6)]
(0, -1)
turned
moved
start: 
(9.0, 6.0)
food:
(2.0, 6.0)
[(9, 6), (8, 6), (7, 6), (6, 6), (5, 6), (4, 6), (3, 6), (2, 6)]
(-1, 0)
turned
moved
start: 
(8.0, 6.0)
food:
(2.0, 6.0)
[(8, 6), (7, 6), (6, 6), (5, 6), (4, 6), (3, 6), (2, 6)]
(-1, 0)
turned
moved
start: 
(7.0, 6.0)
food:
(2.0, 6.0)
[(7, 6), (6, 6), (5, 6), (4, 6), (3, 6), (2, 6)]
(-1, 0)
turned
moved
start: 
(6.0, 6.0)
food:
(2.0, 6.0)
[(6, 6), (5, 6), (4, 6), (3, 6), (2, 6)]
(-1, 0)
turned
moved
start: 
(5.0, 6.0)
food:
(2.0, 6.0)
[(5, 6), (4, 6), (3, 6), (2, 6)]
(-1, 0)
turned
moved
start: 
(4.0, 6.0)
food:
(2.0, 6.0)
[(4, 6), (3, 6), (2, 6)]
(-1, 0)
turned
moved
start: 
(3.0, 6.0)
food:
(2.0, 6.0)
[(3, 6), (2, 6)]
(-1, 0)
turned
moved
The score is 1
NEW FOOD: (7.0, 9.0)
start:
(2.0, 6.0)
food:
(7.0, 9.0)
[(2, 6), (3, 6), (4, 6), (5, 6), (6, 6), (7, 6), (7, 7), (7, 8), (7, 9)]
(1, 0)
turned
moved
start: 
(1.0, 6.0)
food:
(7.0, 9.0)
[(1, 6), (1, 7), (2, 7), (3, 7), (4, 7), (5, 7), (6, 7), (7, 7), (7, 8), (7, 9)]
(0, 1)
turned
moved
start: 
(1.0, 7.0)
food:
(7.0, 9.0)
[(1, 7), (2, 7), (3, 7), (4, 7), (5, 7), (6, 7), (7, 7), (7, 8), (7, 9)]
(1, 0)
turned
moved
start: 
(2.0, 7.0)
food:
(7.0, 9.0)
[(2, 7), (3, 7), (4, 7), (5, 7), (6, 7), (7, 7), (7, 8), (7, 9)]
(1, 0)
turned
moved
start: 
(3.0, 7.0)
food:
(7.0, 9.0)
[(3, 7), (4, 7), (5, 7), (6, 7), (7, 7), (7, 8), (7, 9)]
(1, 0)
turned
moved
start: 
(4.0, 7.0)
food:
(7.0, 9.0)
[(4, 7), (5, 7), (6, 7), (7, 7), (7, 8), (7, 9)]
(1, 0)
turned
moved
start: 
(5.0, 7.0)
food:
(7.0, 9.0)
[(5, 7), (6, 7), (7, 7), (7, 8), (7, 9)]
(1, 0)
turned
moved
start: 
(6.0, 7.0)
food:
(7.0, 9.0)
[(6, 7), (7, 7), (7, 8), (7, 9)]
(1, 0)
turned
moved
start: 
(7.0, 7.0)
food:
(7.0, 9.0)
[(7, 7), (7, 8), (7, 9)]
(0, 1)
turned
moved
start: 
(7.0, 8.0)
food:
(7.0, 9.0)
[(7, 8), (7, 9)]
(0, 1)
turned
moved
The score is 2
NEW FOOD: (14.0, 9.0)
start:
(7.0, 9.0)
food:
(14.0, 9.0)
[(7, 9), (8, 9), (9, 9), (10, 9), (11, 9), (12, 9), (13, 9), (14, 9)]
(1, 0)
turned
moved
start: 
(8.0, 9.0)
food:
(14.0, 9.0)
[(8, 9), (9, 9), (10, 9), (11, 9), (12, 9), (13, 9), (14, 9)]
(1, 0)
turned
moved
start: 
(9.0, 9.0)
food:
(14.0, 9.0)
[(9, 9), (10, 9), (11, 9), (12, 9), (13, 9), (14, 9)]
(1, 0)
turned
moved
start: 
(10.0, 9.0)
food:
(14.0, 9.0)
[(10, 9), (11, 9), (12, 9), (13, 9), (14, 9)]
(1, 0)
turned
moved
start: 
(11.0, 9.0)
food:
(14.0, 9.0)
[(11, 9), (12, 9), (13, 9), (14, 9)]
(1, 0)
turned
moved
start: 
(12.0, 9.0)
food:
(14.0, 9.0)
[(12, 9), (13, 9), (14, 9)]
(1, 0)
turned
moved
start: 
(13.0, 9.0)
food:
(14.0, 9.0)
[(13, 9), (14, 9)]
(1, 0)
turned
moved
The score is 3
NEW FOOD: (1.0, 4.0)
start:
(14.0, 9.0)
food:
(1.0, 4.0)
[(14, 9), (14, 8), (14, 7), (14, 6), (14, 5), (14, 4), (13, 4), (12, 4), (11, 4), (10, 4), (9, 4), (8, 4), (7, 4), (6, 4), (5, 4), (4, 4), (3, 4), (2, 4), (1, 
4)]
(0, -1)
turned
moved
start: 
(14.0, 8.0)
food:
(1.0, 4.0)
[(14, 8), (14, 7), (14, 6), (14, 5), (14, 4), (13, 4), (12, 4), (11, 4), (10, 4), (9, 4), (8, 4), (7, 4), (6, 4), (5, 4), (4, 4), (3, 4), (2, 4), (1, 4)]      
(0, -1)
turned
moved
start: 
(14.0, 7.0)
food:
(1.0, 4.0)
[(14, 7), (14, 6), (14, 5), (14, 4), (13, 4), (12, 4), (11, 4), (10, 4), (9, 4), (8, 4), (7, 4), (6, 4), (5, 4), (4, 4), (3, 4), (2, 4), (1, 4)]
(0, -1)
turned
moved
start: 
(14.0, 6.0)
food:
(1.0, 4.0)
[(14, 6), (14, 5), (14, 4), (13, 4), (12, 4), (11, 4), (10, 4), (9, 4), (8, 4), (7, 4), (6, 4), (5, 4), (4, 4), (3, 4), (2, 4), (1, 4)]
(0, -1)
turned
moved
start: 
(14.0, 5.0)
food:
(1.0, 4.0)
[(14, 5), (14, 4), (13, 4), (12, 4), (11, 4), (10, 4), (9, 4), (8, 4), (7, 4), (6, 4), (5, 4), (4, 4), (3, 4), (2, 4), (1, 4)]
(0, -1)
turned
moved
start: 
(14.0, 4.0)
food:
(1.0, 4.0)
[(14, 4), (13, 4), (12, 4), (11, 4), (10, 4), (9, 4), (8, 4), (7, 4), (6, 4), (5, 4), (4, 4), (3, 4), (2, 4), (1, 4)]
(-1, 0)
turned
moved
start: 
(13.0, 4.0)
food:
(1.0, 4.0)
[(13, 4), (12, 4), (11, 4), (10, 4), (9, 4), (8, 4), (7, 4), (6, 4), (5, 4), (4, 4), (3, 4), (2, 4), (1, 4)]
(-1, 0)
turned
moved
start: 
(12.0, 4.0)
food:
(1.0, 4.0)
[(12, 4), (11, 4), (10, 4), (9, 4), (8, 4), (7, 4), (6, 4), (5, 4), (4, 4), (3, 4), (2, 4), (1, 4)]
(-1, 0)
turned
moved
start: 
(11.0, 4.0)
food:
(1.0, 4.0)
[(11, 4), (10, 4), (9, 4), (8, 4), (7, 4), (6, 4), (5, 4), (4, 4), (3, 4), (2, 4), (1, 4)]
(-1, 0)
turned
moved
start: 
(10.0, 4.0)
food:
(1.0, 4.0)
[(10, 4), (9, 4), (8, 4), (7, 4), (6, 4), (5, 4), (4, 4), (3, 4), (2, 4), (1, 4)]
(-1, 0)
turned
moved
start: 
(9.0, 4.0)
food:
(1.0, 4.0)
[(9, 4), (8, 4), (7, 4), (6, 4), (5, 4), (4, 4), (3, 4), (2, 4), (1, 4)]
(-1, 0)
turned
moved
start: 
(8.0, 4.0)
food:
(1.0, 4.0)
[(8, 4), (7, 4), (6, 4), (5, 4), (4, 4), (3, 4), (2, 4), (1, 4)]
(-1, 0)
turned
moved
start: 
(7.0, 4.0)
food:
(1.0, 4.0)
[(7, 4), (6, 4), (5, 4), (4, 4), (3, 4), (2, 4), (1, 4)]
(-1, 0)
turned
moved
start: 
(6.0, 4.0)
food:
(1.0, 4.0)
[(6, 4), (5, 4), (4, 4), (3, 4), (2, 4), (1, 4)]
(-1, 0)
turned
moved
start: 
(5.0, 4.0)
food:
(1.0, 4.0)
[(5, 4), (4, 4), (3, 4), (2, 4), (1, 4)]
(-1, 0)
turned
moved
start: 
(4.0, 4.0)
food:
(1.0, 4.0)
[(4, 4), (3, 4), (2, 4), (1, 4)]
(-1, 0)
turned
moved
start: 
(3.0, 4.0)
food:
(1.0, 4.0)
[(3, 4), (2, 4), (1, 4)]
(-1, 0)
turned
moved
start: 
(2.0, 4.0)
food:
(1.0, 4.0)
[(2, 4), (1, 4)]
(-1, 0)
turned
moved
The score is 4
NEW FOOD: (15.0, 5.0)
start:
(1.0, 4.0)
food:
(15.0, 5.0)
[(1, 4), (1, 5), (2, 5), (3, 5), (4, 5), (5, 5), (6, 5), (7, 5), (8, 5), (9, 5), (10, 5), (11, 5), (12, 5), (13, 5), (14, 5), (15, 5)]
(0, 1)
turned
moved
start: 
(1.0, 5.0)
food:
(15.0, 5.0)
[(1, 5), (2, 5), (3, 5), (4, 5), (5, 5), (6, 5), (7, 5), (8, 5), (9, 5), (10, 5), (11, 5), (12, 5), (13, 5), (14, 5), (15, 5)]
(1, 0)
turned
moved
start: 
(2.0, 5.0)
food:
(15.0, 5.0)
[(2, 5), (3, 5), (4, 5), (5, 5), (6, 5), (7, 5), (8, 5), (9, 5), (10, 5), (11, 5), (12, 5), (13, 5), (14, 5), (15, 5)]
(1, 0)
turned
moved
start: 
(3.0, 5.0)
food:
(15.0, 5.0)
[(3, 5), (4, 5), (5, 5), (6, 5), (7, 5), (8, 5), (9, 5), (10, 5), (11, 5), (12, 5), (13, 5), (14, 5), (15, 5)]
(1, 0)
turned
moved
start: 
(4.0, 5.0)
food:
(15.0, 5.0)
[(4, 5), (5, 5), (6, 5), (7, 5), (8, 5), (9, 5), (10, 5), (11, 5), (12, 5), (13, 5), (14, 5), (15, 5)]
(1, 0)
turned
moved
start: 
(5.0, 5.0)
food:
(15.0, 5.0)
[(5, 5), (6, 5), (7, 5), (8, 5), (9, 5), (10, 5), (11, 5), (12, 5), (13, 5), (14, 5), (15, 5)]
(1, 0)
turned
moved
start: 
(6.0, 5.0)
food:
(15.0, 5.0)
[(6, 5), (7, 5), (8, 5), (9, 5), (10, 5), (11, 5), (12, 5), (13, 5), (14, 5), (15, 5)]
(1, 0)
turned
moved
start: 
(7.0, 5.0)
food:
(15.0, 5.0)
[(7, 5), (8, 5), (9, 5), (10, 5), (11, 5), (12, 5), (13, 5), (14, 5), (15, 5)]
(1, 0)
turned
moved
start: 
(8.0, 5.0)
food:
(15.0, 5.0)
[(8, 5), (9, 5), (10, 5), (11, 5), (12, 5), (13, 5), (14, 5), (15, 5)]
(1, 0)
turned
moved
start: 
(9.0, 5.0)
food:
(15.0, 5.0)
[(9, 5), (10, 5), (11, 5), (12, 5), (13, 5), (14, 5), (15, 5)]
(1, 0)
turned
moved
start: 
(10.0, 5.0)
food:
(15.0, 5.0)
[(10, 5), (11, 5), (12, 5), (13, 5), (14, 5), (15, 5)]
(1, 0)
turned
moved
start: 
(11.0, 5.0)
food:
(15.0, 5.0)
[(11, 5), (12, 5), (13, 5), (14, 5), (15, 5)]
(1, 0)
turned
moved
start: 
(12.0, 5.0)
food:
(15.0, 5.0)
[(12, 5), (13, 5), (14, 5), (15, 5)]
(1, 0)
turned
moved
start: 
(13.0, 5.0)
food:
(15.0, 5.0)
[(13, 5), (14, 5), (15, 5)]
(1, 0)
turned
moved
start: 
(14.0, 5.0)
food:
(15.0, 5.0)
[(14, 5), (15, 5)]
(1, 0)
turned
moved
The score is 5
NEW FOOD: (11.0, 8.0)
start:
(15.0, 5.0)
food:
(11.0, 8.0)
[(15, 5), (15, 6), (15, 7), (15, 8), (14, 8), (13, 8), (12, 8), (11, 8)]
(0, 1)
turned
moved
start: 
(15.0, 6.0)
food:
(11.0, 8.0)
[(15, 6), (15, 7), (15, 8), (14, 8), (13, 8), (12, 8), (11, 8)]
(0, 1)
turned
moved
start: 
(15.0, 7.0)
food:
(11.0, 8.0)
[(15, 7), (15, 8), (14, 8), (13, 8), (12, 8), (11, 8)]
(0, 1)
turned
moved
start: 
(15.0, 8.0)
food:
(11.0, 8.0)
[(15, 8), (14, 8), (13, 8), (12, 8), (11, 8)]
(-1, 0)
turned
moved
start: 
(14.0, 8.0)
food:
(11.0, 8.0)
[(14, 8), (13, 8), (12, 8), (11, 8)]
(-1, 0)
turned
moved
start: 
(13.0, 8.0)
food:
(11.0, 8.0)
[(13, 8), (12, 8), (11, 8)]
(-1, 0)
turned
moved
start: 
(12.0, 8.0)
food:
(11.0, 8.0)
[(12, 8), (11, 8)]
(-1, 0)
turned
moved
The score is 6
NEW FOOD: (17.0, 9.0)
start:
(11.0, 8.0)
food:
(17.0, 9.0)
None
Traceback (most recent call last):
  File "c:\Users\person\Desktop\Snake\dfs.py", line 387, in <module>
    main()
  File "c:\Users\person\Desktop\Snake\dfs.py", line 369, in main
    snake_dir = snake_directions(path).pop()
  File "c:\Users\person\Desktop\Snake\dfs.py", line 295, in snake_directions
    for i in range(len(path) - 1):
TypeError: object of type 'NoneType' has no len()
PS C:\Users\person\Desktop\Snake> 

import pygame
import sys
import random
import numpy as np
import heapq as hq
from pygame.display import update
#import splashscreen

SCREEN_WIDTH = 720
SCREEN_HEIGHT = 720

GRIDSIZE = 40
GRID_WIDTH = int(SCREEN_HEIGHT / GRIDSIZE)
GRID_HEIGHT = int(SCREEN_WIDTH / GRIDSIZE)

UP = (0, -1)
DOWN = (0, 1)
LEFT = (-1, 0)
RIGHT = (1, 0)

times_in = 0

class Snake(object):
    def __init__(self):
        self.length = 1
        self.positions = [((SCREEN_WIDTH / 2), (SCREEN_HEIGHT / 2))]
        self.direction = random.choice([UP, DOWN, LEFT, RIGHT])
        self.color = (240, 240, 240)
        self.tail = (0, 0)

    def get_head_position(self):
        return self.positions[0]

    def turn(self, point):
        if self.length > 1 and (point[0] * -1, point[1] * -1) == self.direction:
            return
        else:
            self.direction = point

    def move(self):
        cur = self.get_head_position()
        x, y = self.direction
        new = (((cur[0] + (x*GRIDSIZE))), (cur[1] + (y*GRIDSIZE)))
        if (len(self.positions) > 2 and new in self.positions[2:-1]) or new[0] == -GRIDSIZE or new[1] == -GRIDSIZE or new[0] == SCREEN_WIDTH or new[1] == SCREEN_HEIGHT:
            self.reset()
            reset_grid()
            food.randomize_position()
        else:
            
            for i in self.positions:
                grid[int(i[1] / GRIDSIZE), int(i[0] / GRIDSIZE)] = 1
            
            grid[int(new[1] / GRIDSIZE), int(new[0] / GRIDSIZE)] = 3
            
            if len(self.positions) + 1 > self.length:
                old = self.positions.pop()
                grid[int(old[1] / GRIDSIZE), int(old[0] / GRIDSIZE)] = 0
            self.positions.insert(0, new)
            grid[int(self.positions[-1][1] / GRIDSIZE), int(self.positions[-1][0] / GRIDSIZE)] = 4
            self.tail = self.positions[-1]

    def reset(self):
        global score
        self.length = 1
        self.positions = [((SCREEN_WIDTH / 2), (SCREEN_HEIGHT / 2))]
        self.direction = random.choice([UP, DOWN, LEFT, RIGHT])
        score = 0
    
    def draw(self, surface):
        for index, p in enumerate(self.positions):
            r = pygame.Rect((p[0], p[1]), (GRIDSIZE, GRIDSIZE))
            if index == 0:
                pygame.draw.rect(surface, (230, 0, 255), r)
                pygame.draw.rect(surface, (93, 216, 228), r, 1)
                continue
            if index == snake.length - 1:
                pygame.draw.rect(surface, (0, 230, 255), r)
                pygame.draw.rect(surface, (93, 216, 228), r, 1)
                continue
            pygame.draw.rect(surface, (abs(240 - 4*index), abs(240 - 4*index), abs(240 - 4*index)), r)
            pygame.draw.rect(surface, (93, 216, 228), r, 1)

    def handle_keys(self):
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                pygame.quit()
                sys.exit()
            elif event.type == pygame.KEYDOWN:
                if event.key == pygame.K_UP:
                    self.turn(UP)
                elif event.key == pygame.K_DOWN:
                    self.turn(DOWN)
                elif event.key == pygame.K_LEFT:
                    self.turn(LEFT)
                elif event.key == pygame.K_RIGHT:
                    self.turn(RIGHT)

class Food(object):
    def __init__(self):
        self.position = (0, 0)
        self.color = (114, 137, 218)
        self.randomize_position()

    def get_position(self):
        return self.position

    def randomize_position(self):
        grid[int(self.position[1]/GRIDSIZE), int(self.position[0]/GRIDSIZE)] = 0
        self.position = (random.randint(0, GRID_WIDTH-1) * GRIDSIZE, random.randint(0, GRID_HEIGHT-1) * GRIDSIZE)
        #if the 
        if self.position in snake.positions:
            self.randomize_position() #recursive call
        grid[int(self.position[1]/GRIDSIZE), int(self.position[0]/GRIDSIZE)] = 2

    def draw(self, surface):
        r = pygame.Rect((self.position[0], self.position[1]), (GRIDSIZE, GRIDSIZE))
        pygame.draw.rect(surface, self.color, r)
        pygame.draw.rect(surface, (93, 216, 228), r, 1)

    def get_position(self):
        return self.position

def drawGrid(surface, myfont):
    for y in range(0, int(GRID_HEIGHT)):
        for x in range(0, int(GRID_WIDTH)):
            if (x + y) % 2 == 0:
                r = pygame.Rect((x*GRIDSIZE, y*GRIDSIZE), (GRIDSIZE, GRIDSIZE))
                pygame.draw.rect(surface, (44, 47, 51), r)
                text = myfont.render(str((x, y)), 1, (0, 0, 0))
                surface.blit(text, ((x*GRIDSIZE, y*GRIDSIZE), (GRIDSIZE, GRIDSIZE)))
            else:
                rr = pygame.Rect((x*GRIDSIZE, y*GRIDSIZE), (GRIDSIZE, GRIDSIZE))
                pygame.draw.rect(surface, (35, 39, 42), rr)
                text = myfont.render(str((x, y)), 1, (0, 0, 0))
                surface.blit(text, ((x*GRIDSIZE, y*GRIDSIZE), (GRIDSIZE, GRIDSIZE)))

class Node():
    def __init__(self, position, parent = None):
        self.position = (int(position[0]), int(position[1]))
        #parent is the parent node
        self.parent = parent
    
    # Compare Nodes
    def __eq__(self, other):
        return self.position == other.position

    # Print Nodes
    def __repr__(self):
        return str(self.position)

    def get_parent(self):
        return self.parent

    def get_neighbors(self):
        #returns neighbors (UP, RIGHT, DOWN, LEFT)
        #THIS DOES NOT MEAN THE NEIGHBORING POSITIONS ARE not obstacles
        parent_pos = self.position
        x = parent_pos[0]
        y = parent_pos[1]

        children = []
        for new_position in [UP, RIGHT, DOWN, LEFT]:

            node_position = (self.position[0] + new_position[0], self.position[1] + new_position[1])

            temp = self
            broken = False
            while temp is not None:
                if (temp.position == node_position):
                    broken = True
                    break
                temp = temp.parent

            if broken:
                continue


            if node_position[0] >= (GRID_HEIGHT - 1) or node_position[0] < 0 or node_position[1] >= (GRID_HEIGHT -1) or node_position[1] < 0:
                continue

            # if grid[node_position[0], node_position[1]] != 0 and grid[node_position[0], node_position[1]] != 2 and grid[node_position[0], node_position[1]] != 4:
            #     continue

            if (grid[node_position[1], node_position[0]] == 1 or grid[node_position[1], node_position[0]] == 3 or (grid[node_position[1], node_position[0]] == 4)):
                continue

            new_node = Node(node_position, self)

            children.append(new_node)
        return children

    def on_grid(self):
        x = self.position[0]
        y = self.position[1]
        return (x >= GRID_WIDTH or x < 0 or y >= GRID_HEIGHT or y < 0)
    
    def is_snake_node(self, snake):
        x = self.position[0]
        y = self.position[1]
        
        for pos in snake.positions:
            if (pos[0] == x and pos[1] == y):
                return True
        return False
    
    def get_position(self):
        return self.position
    
    #this method traces through its parents and adds their positions to a list
    #order would be [1st gen node, 2nd gen node, ..., this node]
    def listify(self):
        list = []
        list.insert(0, self.position)

        node = self.parent
        while node is not None:
            list.insert(0, node.position)
            node = node.parent
        return list

def mult_node_is_obstacle(nodes):
        return_bools = []
        for node in nodes:
            return_bools.append(node.on_grid() and (not node.is_snake_node))
            
        return return_bools

#food = Food()
def dfs(start_pos, goal_pos):
    open_list = []
    closed_list = []

    start_node = Node(start_pos)
    goal_node = Node(goal_pos)

    open_list.append(start_node)

    while (len(open_list) != 0):
        cur_node = open_list.pop(-1)

        closed_list.append(cur_node)
        
        if (cur_node == goal_node):
            path = []
            while cur_node != start_node:
                path.append(cur_node.get_position())
                cur_node = cur_node.get_parent()
            #code before wouldnt insert start node into path so i added it here
            path.append(start_node.get_position())

            return path[::-1]

        cur_x = (start_node.get_position())[0]
        cur_y = (start_node.get_position())[1]
        goal_x = goal_node.get_position()[0]
        goal_y = goal_node.get_position()[1]

        cur_node_neighbors = cur_node.get_neighbors()
        #array to see if neighbors are obstacles
        #Checks to see if there are available nodes

        for child in cur_node_neighbors:
            #if the node isnt an obstacle and it isnt in the closed list then add it to the open list
            #adds child nodes to open list 
            if child in closed_list:
                continue

            if child not in open_list:
                open_list.insert(0, child)
    
    return None
        


            
score = 0
grid = 0
def reset_grid():
    global grid
    grid = np.zeros((GRID_WIDTH, GRID_HEIGHT))
    grid = grid.astype(int)

reset_grid()
# 0 = empty
# 1 = snake piece
# 3 = snake head
# 2 = food
# 4 = end of snake

directions = []

def snake_directions(path):
    directions = []

    for i in range(len(path) - 1):
        direction_vector = (path[i + 1][0] - path[i][0], path[i + 1][1] - path[i][1])
        directions.insert(0,direction_vector)
    return directions

def dead():
    snake.reset()
    reset_grid()
    food.randomize_position()
    while True:
        for event in pygame.event.get():
                print(event)
                if event.type == pygame.QUIT:
                    splashscreen.game_intro()

food = 0
snake = 0
surface = 0
depth = 0
MAX_DEPTH = 0

def main():
    global score, food, snake, surface, simulated
    pygame.init()

    clock = pygame.time.Clock()
    screen = pygame.display.set_mode((SCREEN_WIDTH, SCREEN_HEIGHT), 0, 32)

    myfont = pygame.font.SysFont("monospace", 16)

    surface = pygame.Surface(screen.get_size())
    surface = surface.convert()
    drawGrid(surface, myfont)

    snake = Snake()
    food = Food()

    #print(a_star((0, SCREEN_WIDTH - 20), (SCREEN_HEIGHT - 20, SCREEN_WIDTH - 20), Snake()))
    while (True):
        
        clock.tick(15)
        #snake.handle_keys()
        #drawGrid(surface, myfont)
        #snake.move()
        
        #simulated = False
        #print("test")
        
            
        if snake.get_head_position() == food.get_position():
            snake.length += 1
            score = snake.length - 1
            food.randomize_position()
            print("The score is {}".format(score))
            print("NEW FOOD: (" + str(food.get_position()[0] / GRIDSIZE) + ", " + str(food.get_position()[1] / GRIDSIZE) + ")")

        snake.draw(surface)
        food.draw(surface)
        screen.blit(surface, (0, 0))
        screen.blit(surface, (0, 0))
        text = myfont.render("Score {0}".format(score), 1, (255, 255, 0))
        screen.blit(text, (5, 10))
        
        drawGrid(surface, myfont)
        
        start_pos = (snake.get_head_position()[0]/GRIDSIZE, snake.get_head_position()[1]/GRIDSIZE)
        food_pos = (food.get_position()[0] / GRIDSIZE, food.get_position()[1]/GRIDSIZE)

        print('start: ')
        print(start_pos)
        print('food: ')
        print(food_pos)
        path = dfs(start_pos, food_pos)
        print(path)
        snake_dir = snake_directions(path).pop()
        print(snake_dir)

        snake.turn(snake_dir)
        print("turned")
        snake.move()
        print("moved")

        
         
        pygame.display.update()
        for event in pygame.event.get():
            if event.type==pygame.QUIT:
                pygame.quit()
                print("test")
        #print("test")

if __name__ == "__main__":
    main()

标签： pythonpygamedepth-first-searchpath-finding

Answer 1

答案很简单：

您在第 204 行Node.get_neigbors添加了一个条件来检查孩子（邻居）是否在网格上：

if node_position[0] >= (GRID_HEIGHT - 1) or node_position[0] < 0 \
or node_position[1] >= (GRID_HEIGHT - 1) or node_position[1] < 0:
    continue

您正在检查 x/y 位置是否为>= (GRID_HEIGHT - 1). 所以如果位置等于GRID_HEIGHT - 1，意味着它位于最左边的列/底行，它被 检测到并被>=丢弃。因此，如果食物恰好在这一行或列中产生，dfs则无法找到食物的路径并返回None，然后将其传递给snake_directions，从而引发错误。

使固定：

if node_position[0] >= GRID_WIDTH or node_position[0] < 0 \  # use GRID_WIDTH for the x-axis check
    or node_position[1] >= GRID_HEIGHT or node_position[1] < 0:
    continue

注意：
如果蛇无法找到路径，因为路径被蛇的身体挡住了，同样的错误将会出现。（您可以通过添加“等待行为”来解决此问题，例如在第 224 行中为此）