当前位置：首页 > news >正文

杭州商城型网站建设/今日国内新闻大事

news 2025/7/19 3:18:20

杭州商城型网站建设,今日国内新闻大事,wordpress上传图片http错误,做网站的公司深圳停课不停学|软件学子技术分享(第五期)-基于BFS广度优先搜索算法的智能贪吃蛇3月14日晚九点，软件工程学院团总支学生会科技服务部线上开展的“停课不停学——软件学子技术分享”活动第5期如期举行。直播间的同学们求学信念炙热，热情不减，在线观…

停课不停学|软件学子技术分享

(第五期)-基于BFS广度优先搜索算法的智能贪吃蛇

3月14日晚九点，软件工程学院团总支学生会科技服务部线上开展的“停课不停学——软件学子技术分享”活动第5期如期举行。

直播间的同学们求学信念炙热，热情不减，在线观看直播人数达75人。

(正在直播的何杨)

主讲人介绍：何杨，软件工程学院13001806班，现担任校ACM集训队队长，ACM算法协会副会长，高中时期参加NOIP算法竞赛，大学参加过多项算法竞赛。曾获2019年ACM国际大学生程序设计竞赛亚洲区域赛南昌赛区-银奖、南京赛区-铜奖、西安邀请赛-铜奖，2019年中国大学生程序设计竞赛厦门站-银奖、湖南邀请赛-银奖、秦皇岛站-铜奖、全国总决赛-优秀奖等多项程序算法类奖项。

何杨为同学们带来了不一样的“贪吃蛇”。直播一开始，何杨学长向我们展示了他用python写的贪吃蛇，通过这个小程序向我们介绍了如何用BFS广度优先搜索算法寻找蛇的觅食路线，从起点开始寻找排查，依次找到联通点。(贪吃蛇咬到自己和撞墙都算游戏失败。)

(何杨用画图方式讲解贪吃蛇觅食路径思路)

BFS简介：中文名为宽度(广度)优先搜索，是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。BFS属于一种盲目搜寻法，不考虑结果的可能位置，彻底地收缩整张图，直到找到结果位置。

(有灵魂的直播画面)

(认真学习的锦鲤和小飞)

何杨学长从贪吃蛇的原理到如何寻找路径，自然而然的引出了BFS算法，最后为大家总结了自己编写贪吃蛇的算法思路，让大家感受到在编程中算法的重要性与独特魅力，同时激发了同学们对算法应用学习的兴趣。

在此，为大家温馨附上何杨完善后的智能贪吃蛇代码，供大家课余参考、学习并理解算法的应用：

import pygame
from sys import exit
import random, math

pygame.init()
mapW = 300
mapH = 330
ROW = 11
COL = 10
# 0 * 0 ~ 29 * 19
# pixelSize = mapH / ROW
dirs = [[1,0],[0,1],[0,-1],[-1,0],[0,0]]
dirNow = 1
dirPause = 4
window = pygame.display.set_mode((mapW, mapH))
pygame.display.set_caption('Snack')

snack = [(ROW // 2, COL // 2)]
food = [(ROW - 1, COL - 1)]
colors = [(200, 147, 158), (0, 158, 128)]

def drawRect(pos, color):
    RecX = pos[1] * mapH / ROW
    RecY = pos[0] * mapW / COL
    pygame.draw.rect(window, color, (RecX, RecY, mapH / ROW, mapW / COL))

def ex(pos):
    if(pos[0] < 0 or pos[1] < 0 or pos[0] > ROW - 1 or pos[1] > COL - 1):
        return False
    return True

def gen_food():
    newFood = (random.randint(0, ROW - 1), random.randint(0, COL - 1))
    while(newFood in snack):
        newFood = (random.randint(0, ROW - 1), random.randint(0, COL - 1))
    food.append(newFood)

def bfs(st, ed, block):
    flag = False
    queue = [st]
    pre = [0]
    head = 0
    while(head < len(queue)):
        newNode = queue[head]
        head+=1
        rd = random.randint(0,3)
        for i in range(4):
            i = (i + rd) % 4
            ppos = (newNode[0] + dirs[i][0], newNode[1] + dirs[i][1])
            if not ex(ppos):
                continue
            if ppos == ed:
                queue.append(ppos)
                pre.append(head - 1)
                flag = True
                break
            if ppos in block:
                continue

            if ppos not in queue:
                queue.append(ppos)
                pre.append(head - 1)
        if flag:
            break
    res = []
    last = len(queue) - 1
    if flag :
        while last != pre[last]:
            res.append(queue[last])
            last = pre[last]
    return res[::-1]

def get_dir(pos1, pos2):
    for i in range(4):
        if((pos1[0] + dirs[i][0], pos1[1] + dirs[i][1]) == pos2):
            return i
    return 4

quitFlag = True
clock = pygame.time.Clock()
road = []
def finddir(snack):
    res = []
    for i in range(4):
        Node = (snack[0][0] + dirs[i][0], snack[0][1] + dirs[i][1])
        if Node in snack:
            continue
        if not ex(Node):
            continue
        if len(bfs(Node, snack[-2], [Node] + snack[:-2])) > 0:
            res.append(Node)
    if(len(res) <= 0):
        debug = 1
        return res
    ret = res[0]

    for i in res:
        if(abs(i[0] - food[0][0]) + abs(i[1] - food[0][1]) > abs(ret[0] - food[0][0]) + abs(ret[1] - food[0][1])):
            ret = i
    return [ret]
while quitFlag:
    clock.tick(60)
    # 获取事件，包括键盘事件和退出事件，也可防止卡死
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            quitFlag = False
        if event.type == pygame.KEYDOWN:
            if event.key == pygame.K_SPACE:
                t = dirPause
                dirPause = t
                dirNow = dirPause

    if len(road) == 0:
        nextPath = bfs(snack[0], food[0], snack)
        findTail = bfs(snack[0], snack[-1], snack)
        if len(nextPath) > 0:
            if(len(nextPath) > len(snack)):
                findTail2 = bfs(nextPath[-1], nextPath[-len(snack) - 1], nextPath[-1:-len(snack) - 2])
            else:
                findTail2 = bfs(nextPath[-1], snack[len(snack) - len(nextPath)], nextPath + snack[0:len(snack) - len(nextPath)])
            if len(findTail2) > 0:
                road = nextPath
            else:
                road = finddir(snack)
        else :
            road = finddir(snack)
        if len(road) == 0:
            road = findTail
    nextRec = road[0]
    road.pop(0)
    if ex(nextRec):
        if(nextRec not in food):
            snack.pop()
        else :
            food.pop()
            gen_food()
        snack.insert(0, nextRec)
    else:
        print("Game over at %d %d"%(nextRec[0],nextRec[1]))
        quitFlag = False

    pygame.draw.rect(window, (245, 135, 155), (0, 0, mapW, mapH))
    for body in snack:
        drawRect(body, colors[0])
    drawRect(snack[0], (255,255,255))
    for body in food:
        drawRect(body, colors[1])
pygame.display.flip()

错过了直播的同学也不要紧，每一期的直播内容都可以在群里进行回放观看哦~
每周六，周日晚上九点，软件工程学院大佬在线技术分享，我们在钉钉群“停课不停学-技术讲堂”与你不见不散！