DFS Snake求解算法（NoneTypeobject没有len）
DFS Snake solving algorithm (NoneType object has no len)
我正在网格上使用 DFS（Depth-first 搜索）制作蛇求解算法。蛇大部分时间都在工作，但我一直收到此错误。
我朋友也发了一个关于BFS的类似问题（breadth-first搜索）我们是同组的，同样的错误
这是完整 运行 游戏的一些输出，直到出现此 NoneType 错误。起始位置表示蛇头所在的位置。 food position表示你要寻路的食物所在的位置，food position后面的数组是到当前食物的路径，后面的元组是它沿着路径前进应该转向的方向。每当蛇吃食物时，食物位置就会随机化并输出到控制台，标题为 NEW FOOD。我相信我知道代码崩溃的原因，但我不知道如何修复它。该算法试图在蛇在食物上时找到一条具有旧食物位置的路径，这会生成一条空路径，因为蛇的路径长度为 0。即使已经生成了新的食物位置。此代码大部分时间都与路径一起工作，但一定是某处的特殊情况导致了此问题。
一直向下滚动到主要方法
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()
答案很简单：
Node.get_neigbors 中的第 204 行您添加了一个条件来检查 children（邻居）是否在网格上：
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 无法找到通往食物的路径，并且 returns 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
注意：
如果蛇无法找到路径，因为路径被蛇 body 挡住了，则会引发相同的错误。 （您可以通过添加“等待行为”来解决此问题，例如为此在第 224 行）
我正在网格上使用 DFS（Depth-first 搜索）制作蛇求解算法。蛇大部分时间都在工作，但我一直收到此错误。
我朋友也发了一个关于BFS的类似问题（breadth-first搜索）我们是同组的，同样的错误
这是完整 运行 游戏的一些输出，直到出现此 NoneType 错误。起始位置表示蛇头所在的位置。 food position表示你要寻路的食物所在的位置，food position后面的数组是到当前食物的路径，后面的元组是它沿着路径前进应该转向的方向。每当蛇吃食物时，食物位置就会随机化并输出到控制台，标题为 NEW FOOD。我相信我知道代码崩溃的原因，但我不知道如何修复它。该算法试图在蛇在食物上时找到一条具有旧食物位置的路径，这会生成一条空路径，因为蛇的路径长度为 0。即使已经生成了新的食物位置。此代码大部分时间都与路径一起工作，但一定是某处的特殊情况导致了此问题。
一直向下滚动到主要方法
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()
答案很简单：
Node.get_neigbors 中的第 204 行您添加了一个条件来检查 children（邻居）是否在网格上：
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 无法找到通往食物的路径，并且 returns 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
注意：
如果蛇无法找到路径，因为路径被蛇 body 挡住了，则会引发相同的错误。 （您可以通过添加“等待行为”来解决此问题，例如为此在第 224 行）