Python自动贪吃蛇遇到自我锁死的算法问题

Question

我在制作一个Python自动的贪吃蛇程序，由于我不会BFS或者DFS，所以就基于曼哈顿距离制作了一个，但是我发现我的蛇有时候会绕成一个圈把自己锁在里面，请问有什么思路可以解决这个问题的

from random import randrange
from turtle import *

from freegames import square, vector

food = vector(0, 0)
snake = [vector(10, 0)]
aim = vector(0, -10)
aim_list = []


def change():
    global aim
    global head
    head = snake[-1].copy()
    food_x = food.x
    food_y = food.y
    head_x = head.x
    head_y = head.y

    directions = [vector(0, 10), vector(0, -10), vector(10, 0), vector(-10, 0)]  # 上，下，右，左
    valid_directions = []

    for bodys in snake:
        if bodys == head:
            if len(snake) > 4 and head in snake[:-1]:
                # 蛇围成一个圈
                # 让蛇沿着自身的身体移动一段距离
                for i in range(1, 5):
                    next_head = head.copy()
                    next_head.move(aim)
                    if next_head not in snake:
                        head = next_head
                        break
                    aim.rotate(90)
        else:
            pass

    for direction in directions:
        next_head = head.copy()
        next_head.move(direction)
        if inside(next_head) and next_head not in snake:
            valid_directions.append(direction)
    if valid_directions:
        aim = min(valid_directions, key=lambda direction: abs(food_x - (head_x + direction.x)) + abs(food_y - (head_y + direction.y)))
   
        
def inside(head):
    return -200 < head.x < 190 and -200 < head.y < 190


def move():
    global head
    global aim
    change()
    head = snake[-1].copy()
    head.move(aim)
    food_x = food.x
    food_y = food.y
    head_x = head.x
    head_y = head.y


    if not inside(head) or head in snake:
        square(head.x, head.y, 9, 'red')
        update()
        return

    
    snake.append(head)

    if head == food:
        print('Snake:', len(snake))
        food.x = randrange(-15, 15) * 10
        food.y = randrange(-15, 15) * 10
    else:
        snake.pop(0)

    clear()

    for body in snake:
        square(body.x, body.y, 9, 'black')

    square(food.x, food.y, 9, 'green')
    update()
    ontimer(move, 5)

setup(420, 420, 370, 0)
hideturtle()
tracer(False)
move()

done()

Answer 1

【以下回答由 GPT 生成】

问题标题: Python自动贪吃蛇遇到自我锁死的算法问题

问题内容: 我正在用Python制作一个自动贪吃蛇程序。由于我不了解BFS或DFS算法，所以采用了基于曼哈顿距离的方法。但是我发现我的蛇有时候会绕成一个圈把自己锁在里面。请问有什么方法可以解决这个问题吗?

from random import randrange
from turtle import *
from freegames import square, vector

food = vector(0, 0)
snake = [vector(10, 0)]
aim = vector(0, -10)
aim_list = []

def change():
    """
    在每次移动之前检查蛇头和食物的位置，然后更新移动方向。
    """
    global aim
    global head
    head = snake[-1].copy()
    food_x = food.x
    food_y = food.y
    head_x = head.x
    head_y = head.y

    directions = [vector(0, 10), vector(0, -10), vector(10, 0), vector(-10, 0)]  # 上、下、右、左
    valid_directions = []

    for bodys in snake:
        if bodys == head:
            if len(snake) > 4 and head in snake[:-1]:
                # 蛇围成一个圈
                # 让蛇沿着自身的身体移动一段距离
                for i in range(1, 5):
                    next_head = head.copy()
                    next_head.move(aim)
                    if next_head not in snake:
                        head = next_head
                        break
                    aim.rotate(90)
        else:
            pass

    for direction in directions:
        next_head = head.copy()
        next_head.move(direction)
        if inside(next_head) and next_head not in snake:
            valid_directions.append(direction)

    if valid_directions:
        aim = min(valid_directions, key=lambda direction: abs(food_x - (head_x + direction.x)) + abs(food_y - (head_y + direction.y)))

def inside(head):
    """
    判断蛇头是否在游戏边界内。
    """
    return -200 < head.x < 190 and -200 < head.y < 190

def move():
    """
    移动蛇的位置并更新蛇的身体。
    """
    global head
    # 实现移动的过程

请问有什么方法可以解决这个问题吗？

回答： 目前的实现方式中没有对蛇头和蛇身体接触时的等待时间进行限制，因此导致蛇会在蛇身体内部转圈子。为了解决这个问题，可以在蛇头碰到蛇身体时，增加一个等待时间，让蛇能继续朝其他方向前进。

以下是解决方案的修改部分代码：

from random import randrange
from turtle import *
from freegames import square, vector
import time

...

def change():
    """
    在每次移动之前检查蛇头和食物的位置，然后更新移动方向。
    """
    global aim
    global head
    head = snake[-1].copy()
    food_x = food.x
    food_y = food.y
    head_x = head.x
    head_y = head.y

    directions = [vector(0, 10), vector(0, -10), vector(10, 0), vector(-10, 0)]  # 上、下、右、左
    valid_directions = []

    for bodys in snake:
        if bodys == head:
            if len(snake) > 4 and head in snake[:-1]:
                # 蛇围成一个圈
                # 让蛇沿着自身的身体移动一段距离
                for i in range(1, 5):
                    next_head = head.copy()
                    next_head.move(aim)
                    if next_head not in snake:
                        head = next_head
                        break
                    aim.rotate(90)
                    time.sleep(0.2)  # 增加等待时间
        else:
            pass

    ...

def move():
    """
    移动蛇的位置并更新蛇的身体。
    """
    global head
    # 实现移动的过程

    time.sleep(0.1)  # 增加等待时间

    ...

...

这样，当蛇头碰到蛇身体时，会有一个等待时间，让蛇头有足够的时间继续朝其他方向前进，从而避免了蛇在蛇身体内部转圈子的问题。

【相关推荐】

• 这篇博客: Python实现用BFS、DFS和A*算法解决8数码问题中的 代码： 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^