Skip to content

Instantly share code, notes, and snippets.

@mdecourse

mdecourse/brython_snake.py

Last active December 1, 2021 02:28
Show Gist options
  • Save mdecourse/d55158478f4f8fcbfedd455f8be8c7b6 to your computer and use it in GitHub Desktop.
Save mdecourse/d55158478f4f8fcbfedd455f8be8c7b6 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
brython_snake.py
# 從 browser 導入 document 並設為 doc
from browser import document as doc
# 使用者可以透過 window 當作介面使用其他 Javascript 功能
from browser import html, window
# 用於定時執行特定函式
import browser.timer
# 導入數學模組
import math
# 導入亂數模組
from random import random, randint
def update_score2(new_score):
global high_score
score_doc.innerHTML = "Score: " + str(new_score)
if new_score > high_score:
high_score_doc.innerHTML = "High Score: " + str(new_score)
high_score = new_score
def eat(px, py, ax, ay):
global xv, yv, pre_pause, paused
# (px, py) go to (ax, ay) through incremented xv, yv
if ax != px or ay != py:
if ax > px and not paused:
xv = 1
yv = 0
if ax < px and not paused:
xv = -1
yv = 0
if ay > py and not paused:
xv = 0
yv = 1
if ay < py and not paused:
xv = 0
yv = -1
def game2():
global px, py, tc, gs, ax, ay, trail, tail, score
# px 為 snake 第一個點的 x 座標, 增量值為 xv
px += xv
py += yv
# 允許穿越四面牆, 以 tc 表示牆面座標極限
# 若 px 為負值則設定為 tc -1, 表示 tc 為 x 方向 limit
# x 座標方向的穿牆設定
if px < 0:
px = tc-1
if px > tc-1:
px = 0
# y 座標方向的穿牆設定
if py < 0:
py = tc-1
if py > tc-1:
py = 0
ctx.fillStyle = "black"
# 畫布填入黑色
ctx.fillRect(0, 0, canvas.width, canvas.height)
# snake 為 lime 色
ctx.fillStyle = "lime"
# trail 為數列, 代表 snake 各節 [x,y] 座標
# trail = [[x0,y0], [x1, y1], [x2, y2]...]
# gs 為方塊邊長 pixel 數
for i in range(len(trail)):
# https://developer.mozilla.org/zh-TW/docs/Web/API/Canvas_API/Tutorial/Drawing_shapes
# fillRect(x, y, width, height)
ctx.fillRect(trail[i][0]*gs, trail[i][1]*gs, gs-2, gs-2)
# 若 snake 第一節座標 (px, py) 穿過身體任一節, 則 score 歸零
if trail[i][0] == px and trail[i][1] == py:
score = score if paused else 0
# snake reset 為五節
tail = 5
# trail 數列以碰到的 [px, py] 座標數列插入作為第一節
trail.insert(0, [px, py])
while len(trail) > tail:
# pop() 內建移除數列最後一個 element
trail.pop()
# ax, ay 為紅點座標
# 當 snake 第一節座標[px, py] 與紅色食物座標 [ax, ay] 重合
# 則 tail 增量, 即多一節且得分加 1, 然後食物座標 [ax, ay] 重新以亂數定位
if ax == px and ay == py:
tail += 1
ax = math.floor(random()*tc)
ay = math.floor(random()*tc)
score += 1
# [ax, ay] is known here
# [px, py] is where the head of the snake
# xv needed to be incremented from px to ax first
# and yv needed to be incremented from py to ay
eat(px, py, ax, ay)
# 更新計分顯示
update_score2(score)
ctx.fillStyle = "red"
ctx.fillRect(ax*gs, ay*gs, gs-2, gs-2)
def key_push2(evt):
global xv, yv, pre_pause, paused
key = evt.keyCode
# 37 is left arrow key
# 74 is j key
if key == 74 and not paused:
xv = -1
yv = 0
# 38 is up arrow key
# 73 is i key
elif key == 73 and not paused:
xv = 0
yv = -1
# 39 is right arrow key
# 76 is l key
elif key == 76 and not paused:
xv = 1
yv = 0
# 40 is down arrow key
# 77 is m key
elif key == 77 and not paused:
xv = 0
yv = 1
# 32 is pause key
# 80 is p key
elif key == 80:
temp = [xv, yv]
xv = pre_pause[0]
yv = pre_pause[1]
pre_pause = [*temp]
paused = not paused
def show_instructions2(evt):
window.alert("keys to control: i=up, m=down, j=left, l=right, p=pause")
# 利用 html 建立 canvas 超文件物件
canvas = html.CANVAS(width = 600, height = 600)
canvas.id = "game-board2"
brython_div = doc["brython_div2"]
brython_div <= canvas
score_doc = html.DIV("score2")
score_doc.id = "score2"
brython_div <= score_doc
high_score_doc = html.DIV("high-score2")
high_score_doc.id = "high-score2"
brython_div <= high_score_doc
button = html.BUTTON("Keys to control")
button.id = "instructions-btn2"
brython_div <= button
score = 0
high_score = 0
px = py = 10
# gs*tc = canvas width and height
gs = 20
tc = 30
ax = ay = 15
xv = yv = 0
trail = []
tail = 5
pre_pause = [0,0]
paused = False
ctx = canvas.getContext("2d")
doc.addEventListener("keydown", key_push2)
instructions_btn = doc["instructions-btn2"]
instructions_btn.addEventListener("click", show_instructions2)
browser.timer.set_interval(game2, 1000/15)
Raw
snake_brython_div.py
# 從 browser 導入 document 並設為 doc
from browser import document as doc
# 使用者可以透過 window 當作介面使用其他 Javascript 功能
from browser import html, window
# 用於定時執行特定函式
import browser.timer
# 導入數學模組
import math
# 導入亂數模組
from random import random, randint
def update_score2(new_score):
global high_score
score_doc.innerHTML = "Score: " + str(new_score)
if new_score > high_score:
high_score_doc.innerHTML = "High Score: " + str(new_score)
high_score = new_score
def eat(px, py, ax, ay):
global xv, yv, pre_pause, paused
# (px, py) go to (ax, ay) through incremented xv, yv
if ax != px or ay != py:
if ax > px and not paused:
xv = 1
yv = 0
if ax < px and not paused:
xv = -1
yv = 0
if ay > py and not paused:
xv = 0
yv = 1
if ay < py and not paused:
xv = 0
yv = -1
def game2():
global px, py, tc, gs, ax, ay, trail, tail, score
# px 為 snake 第一個點的 x 座標, 增量值為 xv
px += xv
py += yv
# 允許穿越四面牆, 以 tc 表示牆面座標極限
# 若 px 為負值則設定為 tc -1, 表示 tc 為 x 方向 limit
# x 座標方向的穿牆設定
if px < 0:
px = tc-1
if px > tc-1:
px = 0
# y 座標方向的穿牆設定
if py < 0:
py = tc-1
if py > tc-1:
py = 0
ctx.fillStyle = "black"
# 畫布填入黑色
ctx.fillRect(0, 0, canvas.width, canvas.height)
# snake 為 lime 色
ctx.fillStyle = "lime"
# trail 為數列, 代表 snake 各節 [x,y] 座標
# trail = [[x0,y0], [x1, y1], [x2, y2]...]
# gs 為方塊邊長 pixel 數
for i in range(len(trail)):
# https://developer.mozilla.org/zh-TW/docs/Web/API/Canvas_API/Tutorial/Drawing_shapes
# fillRect(x, y, width, height)
ctx.fillRect(trail[i][0]*gs, trail[i][1]*gs, gs-2, gs-2)
# 若 snake 第一節座標 (px, py) 穿過身體任一節, 則 score 歸零
if trail[i][0] == px and trail[i][1] == py:
score = score if paused else 0
# snake reset 為五節
tail = 5
# trail 數列以碰到的 [px, py] 座標數列插入作為第一節
trail.insert(0, [px, py])
while len(trail) > tail:
# pop() 內建移除數列最後一個 element
trail.pop()
# ax, ay 為紅點座標
# 當 snake 第一節座標[px, py] 與紅色食物座標 [ax, ay] 重合
# 則 tail 增量, 即多一節且得分加 1, 然後食物座標 [ax, ay] 重新以亂數定位
if ax == px and ay == py:
tail += 1
ax = math.floor(random()*tc)
ay = math.floor(random()*tc)
score += 1
# [ax, ay] is known here
# [px, py] is where the head of the snake
# xv needed to be incremented from px to ax first
# and yv needed to be incremented from py to ay
eat(px, py, ax, ay)
# 更新計分顯示
update_score2(score)
ctx.fillStyle = "red"
ctx.fillRect(ax*gs, ay*gs, gs-2, gs-2)
def key_push2(evt):
global xv, yv, pre_pause, paused
key = evt.keyCode
# 37 is left arrow key
# 74 is j key
if key == 74 and not paused:
xv = -1
yv = 0
# 38 is up arrow key
# 73 is i key
elif key == 73 and not paused:
xv = 0
yv = -1
# 39 is right arrow key
# 76 is l key
elif key == 76 and not paused:
xv = 1
yv = 0
# 40 is down arrow key
# 77 is m key
elif key == 77 and not paused:
xv = 0
yv = 1
# 32 is pause key
# 80 is p key
elif key == 80:
temp = [xv, yv]
xv = pre_pause[0]
yv = pre_pause[1]
pre_pause = [*temp]
paused = not paused
def show_instructions2(evt):
window.alert("keys to control: i=up, m=down, j=left, l=right, p=pause")
# 利用 html 建立 canvas 超文件物件
canvas = html.CANVAS(width = 600, height = 600)
canvas.id = "game-board2"
brython_div = doc["brython_div"]
brython_div <= canvas
score_doc = html.DIV("score2")
score_doc.id = "score2"
brython_div <= score_doc
high_score_doc = html.DIV("high-score2")
high_score_doc.id = "high-score2"
brython_div <= high_score_doc
button = html.BUTTON("Keys to control")
button.id = "instructions-btn2"
brython_div <= button
score = 0
high_score = 0
px = py = 10
# gs*tc = canvas width and height
gs = 20
tc = 30
ax = ay = 15
xv = yv = 0
trail = []
tail = 5
pre_pause = [0,0]
paused = False
ctx = canvas.getContext("2d")
doc.addEventListener("keydown", key_push2)
instructions_btn = doc["instructions-btn2"]
instructions_btn.addEventListener("click", show_instructions2)
browser.timer.set_interval(game2, 1000/15)
Raw
snake_pathfinding_ai_curses.py
# coding: utf-8
# source: https://hawstein.com/2013/04/15/snake-ai/
'''
https://blog.csdn.net/fox64194167/article/details/19965069
http://www.waitingfy.com/archives/846
https://github.com/mdecourse/snake-4
'''
import curses
from curses import KEY_RIGHT, KEY_LEFT, KEY_UP, KEY_DOWN
from random import randint
# 貪食蛇運動的場地長寬
HEIGHT = 10
WIDTH = 20
# FIELD_SIZE 為場地長乘以寬表示格子 (CELL) 總數
FIELD_SIZE = HEIGHT * WIDTH
# 貪食蛇頭總是位於snake數列的第一個元素
HEAD = 0
# 用來代表不同意義的數字，由於矩陣上每個格子會處理成到達食物的路徑長度，
# 因此這三個變數間需要有足夠大的間隔(>HEIGHT*WIDTH)
# 以整數 0 代表 FOOD, 意即若 board 數列中某一元素
# 將隨機取得座標後將該數列索引值設為 0 就表示該格子為 FOOD
# UNDEFINED 值之所以必須大於 HEIGHT*WIDTH, 因為該值將在 BFS 後
# 表示蛇頭距離 FOOD 的路徑步數, 而最大距離步數將會是 HEIGHT*WIDTH
# SNAKE 以整數代表, 由於必須有別於 UNDEFINED 與 FOOD 的值, 因此選擇
# 以 2 * UNDEFINED 這個數字代表該格子被 snake 身體佔住
FOOD = 0
UNDEFINED = (HEIGHT + 1) * (WIDTH + 1)
SNAKE = 2 * UNDEFINED
# 由於 snake 是一維數列，所以對應元素直接加上以下數值就表示向四個方向移動
# 應該是說, 原本該以二維座標表示 board 中各格子的座標, 但在此選擇以一維
# 數列的資料結構來代表二維座標, (1, 1) 可表示為 1*WIDTH+1,
# (x, y) 則表示為 x*WIDTH+y
# 因此往上或往下的移動, 就一維數列值而言, 必須減或加上 WIDTH
LEFT = -1
RIGHT = 1
UP = -WIDTH
DOWN = WIDTH
# 錯誤碼
ERR = -1111
# 用一維數列來表示二維的座標, 使用此資料結構的原因是:
# 貪食蛇每行進一步, 只需要配合蛇頭移動位置新增一個方格座標,
# 且更改蛇尾對應值 (即從原先的蛇身因行進移動一步而變更設定)
# 且讓 snake[HEAD] = x*WIDTH+y, 假設蛇長 snake_size=n
# 則蛇尾 snake[HEAD+n-1] 假設位於 xn*WIDTH+yn
# board[x*WIDTH+y]=SNAKE=2 * UNDEFINED
# board[xn*WIDTH+yn] 表示為蛇尾, 蛇頭走一步後, 蛇尾從 2 * UNDEFINED
# 轉為空白可在搜尋流程中加上距離食物的總步數
# board 表示蛇運動的矩形場地
# 初始化蛇頭在(1,1)的地方，第0行，HEIGHT行，第0列，WIDTH列為圍牆，不可用
# 初始蛇長度為1
# board 與 snake 均為總元素為格點數大小的一維數列
board = [0] * FIELD_SIZE
#snake = [0] * (FIELD_SIZE+1)
# 原程式加 1
snake = [0] * (FIELD_SIZE)
# 座標 (1, 1) 在一維數列中, 表示為 1*WIDTH+1
snake[HEAD] = 1*WIDTH+1
snake_size = 1
# 與上面變量對應的臨時變量，蛇試探性地移動時使用
tmpboard = [0] * FIELD_SIZE
#tmpsnake = [0] * (FIELD_SIZE+1)
# 原程式加 1
tmpsnake = [0] * (FIELD_SIZE)
tmpsnake[HEAD] = 1*WIDTH+1
tmpsnake_size = 1
# food:食物位置(0~FIELD_SIZE-1),初始在(3, 3)
# best_move: 運動方向
food = 3 * WIDTH + 3
best_move = ERR
# 運動方向數組
mov = [LEFT, RIGHT, UP, DOWN]
# 接收到的鍵和分數
key = KEY_RIGHT
# 初始蛇為一節
score = 1 #分數也表示蛇長
# 檢查一個 cell 有沒有被蛇身覆蓋，沒有覆蓋則為 free，返回 true
def is_cell_free(idx, psize, psnake):
return not (idx in psnake[:psize])
# 檢查某個位置idx是否可向move方向運動
def is_move_possible(idx, move):
flag = False
if move == LEFT:
flag = True if idx%WIDTH > 1 else False
elif move == RIGHT:
flag = True if idx%WIDTH < (WIDTH-2) else False
elif move == UP:
flag = True if idx > (2*WIDTH-1) else False # 即idx/WIDTH > 1
elif move == DOWN:
flag = True if idx < (FIELD_SIZE-2*WIDTH) else False # 即idx//WIDTH < HEIGHT-2
return flag
# 重置 board
# board_refresh 後，UNDEFINED 值都變為了到達食物的路徑長度
# 如需要還原，則要重置它
def board_reset(psnake, psize, pboard):
# 查驗所有格點內容
for i in range(FIELD_SIZE):
if i == food:
pboard[i] = FOOD
elif is_cell_free(i, psize, psnake): # 該位置為空
pboard[i] = UNDEFINED
else: # 該位置為蛇身
pboard[i] = SNAKE
# 廣度優先搜索遍歷整個 board，
# 計算出 board 中每個非 SNAKE 元素到達食物的路徑長度
def board_refresh(pfood, psnake, pboard):
queue = []
queue.append(pfood)
inqueue = [0] * FIELD_SIZE
found = False
# while 循環結束後，除了蛇的身體，
# 其它每個方格中的數字代碼從它到食物的路徑長度
while len(queue)!=0:
idx = queue.pop(0)
if inqueue[idx] == 1: continue
inqueue[idx] = 1
for i in range(4):
if is_move_possible(idx, mov[i]):
if idx + mov[i] == psnake[HEAD]:
found = True
if pboard[idx+mov[i]] < SNAKE: # 如果該點不是蛇的身體
if pboard[idx+mov[i]] > pboard[idx]+1:
pboard[idx+mov[i]] = pboard[idx] + 1
if inqueue[idx+mov[i]] == 0:
queue.append(idx+mov[i])
return found
# 從蛇頭開始，根據 board 中元素值，
# 從蛇頭周圍 4 個領域點中選擇最短路徑
def choose_shortest_safe_move(psnake, pboard):
best_move = ERR
min = SNAKE
for i in range(4):
if is_move_possible(psnake[HEAD], mov[i]) and pboard[psnake[HEAD]+mov[i]]<min:
min = pboard[psnake[HEAD]+mov[i]]
best_move = mov[i]
return best_move
# 從蛇頭開始，根據board中元素值，
# 從蛇頭周圍 4 個領域點中選擇最遠路徑
def choose_longest_safe_move(psnake, pboard):
best_move = ERR
max = -1
for i in range(4):
if is_move_possible(psnake[HEAD], mov[i]) and pboard[psnake[HEAD]+mov[i]]<UNDEFINED and pboard[psnake[HEAD]+mov[i]]>max:
max = pboard[psnake[HEAD]+mov[i]]
best_move = mov[i]
return best_move
# 檢查是否可以追著蛇尾運動, 即蛇頭和蛇尾間是有路徑的
# 為的是避免蛇頭陷入死路
# 虛擬操作, 在 tmpboard,tmpsnake 中進行
def is_tail_inside():
global tmpboard, tmpsnake, food, tmpsnake_size
tmpboard[tmpsnake[tmpsnake_size-1]] = 0 # 虛擬地將蛇尾變為食物(因為是虛擬的，所以在tmpsnake,tmpboard中進行)
tmpboard[food] = SNAKE # 放置食物的地方，看成蛇身
result = board_refresh(tmpsnake[tmpsnake_size-1], tmpsnake, tmpboard) # 求得每個位置到蛇尾的路徑長度
for i in range(4): # 如果蛇頭和蛇尾緊挨著，則返回 False。即不能 follow_tail，追著蛇尾運動了
if is_move_possible(tmpsnake[HEAD], mov[i]) and tmpsnake[HEAD]+mov[i]==tmpsnake[tmpsnake_size-1] and tmpsnake_size>3:
result = False
return result
# 讓蛇頭朝著蛇尾運行一步
# 不管蛇身阻擋，朝蛇尾方向運行
def follow_tail():
global tmpboard, tmpsnake, food, tmpsnake_size
tmpsnake_size = snake_size
tmpsnake = snake[:]
board_reset(tmpsnake, tmpsnake_size, tmpboard) # 重置虛擬board
tmpboard[tmpsnake[tmpsnake_size-1]] = FOOD # 讓蛇尾成為食物
tmpboard[food] = SNAKE # 讓食物的地方變成蛇身
board_refresh(tmpsnake[tmpsnake_size-1], tmpsnake, tmpboard) # 求得各個位置到達蛇尾的路徑長度
tmpboard[tmpsnake[tmpsnake_size-1]] = SNAKE # 還原蛇尾
return choose_longest_safe_move(tmpsnake, tmpboard) # 返回運行方向(讓蛇頭運動 1 步)
# 在各種方案都不行時，隨便找一個可行的方向來走(1 步),
def any_possible_move():
global food , snake, snake_size, board
best_move = ERR
board_reset(snake, snake_size, board)
board_refresh(food, snake, board)
min = SNAKE
for i in range(4):
if is_move_possible(snake[HEAD], mov[i]) and board[snake[HEAD]+mov[i]]<min:
min = board[snake[HEAD]+mov[i]]
best_move = mov[i]
return best_move
def shift_array(arr, size):
for i in range(size, 0, -1):
arr[i] = arr[i-1]
def new_food():
global food, snake_size
cell_free = False
while not cell_free:
w = randint(1, WIDTH-2)
h = randint(1, HEIGHT-2)
# food coordinate
food = h * WIDTH + w
cell_free = is_cell_free(food, snake_size, snake)
win.addch(food//WIDTH, food%WIDTH, '@')
# 真正的蛇在這個函數中, 朝 pbest_move 走 1 步
def make_move(pbest_move):
global key, snake, board, snake_size, score
shift_array(snake, snake_size)
snake[HEAD] += pbest_move
# 按 esc 退出，getch 同時保證繪圖的流暢性, 沒有它只會看到最終結果
win.timeout(10)
event = win.getch()
key = key if event == -1 else event
if key == 27: return
p = snake[HEAD]
win.addch(p//WIDTH, p%WIDTH, '*')
# 如果新加入的蛇頭就是食物的位置
# 蛇長加 1，產生新的食物，重置 board (因為原來那些路徑長度已經用不上了)
# snake[HEAD] is the coordinate of the snake head
# food is the coordinate of the food
if snake[HEAD] == food:
# mark on the board where the snake head is
board[snake[HEAD]] = SNAKE # 新的蛇頭
snake_size += 1
score += 1
if snake_size < FIELD_SIZE: new_food()
else: # 如果新加入的蛇頭不是食物的位置
board[snake[HEAD]] = SNAKE # 新的蛇頭
board[snake[snake_size]] = UNDEFINED # 蛇尾變為空格
win.addch(snake[snake_size]//WIDTH, snake[snake_size]%WIDTH, ' ')
# 虛擬地運行一次，然後在調用處檢查這次運行可否可行
# 可行才真實運行。
# 虛擬運行吃到食物後，得到虛擬下蛇在 board 的位置
def virtual_shortest_move():
global snake, board, snake_size, tmpsnake, tmpboard, tmpsnake_size, food
tmpsnake_size = snake_size
tmpsnake = snake[:] # 如果直接tmpsnake=snake，則兩者指向同一處內存
tmpboard = board[:] # board中已經是各位置到達食物的路徑長度了，不用再計算
board_reset(tmpsnake, tmpsnake_size, tmpboard)
food_eated = False
while not food_eated:
board_refresh(food, tmpsnake, tmpboard)
move = choose_shortest_safe_move(tmpsnake, tmpboard)
shift_array(tmpsnake, tmpsnake_size)
tmpsnake[HEAD] += move # 在蛇頭前加入一個新的位置
# 如果新加入的蛇頭的位置正好是食物的位置
# 則長度加1，重置board，食物那個位置變為蛇的一部分(SNAKE)
if tmpsnake[HEAD] == food:
tmpsnake_size += 1
board_reset(tmpsnake, tmpsnake_size, tmpboard) # 虛擬運行後，蛇在board的位置(label101010)
tmpboard[food] = SNAKE
food_eated = True
else: # 如果蛇頭不是食物的位置，則新加入的位置為蛇頭，最後一個變為空格
tmpboard[tmpsnake[HEAD]] = SNAKE
tmpboard[tmpsnake[tmpsnake_size]] = UNDEFINED
# 如果蛇與食物間有路徑，則調用本函數
def find_safe_way():
global snake, board
safe_move = ERR
# 虛擬地運行一次, 因為已經確保蛇與食物間有路徑，所以執行有效
# 運行後得到虛擬下蛇在board中的位置, 即 tmpboard，見 label101010
virtual_shortest_move() # 該函數唯一調用處
if is_tail_inside(): # 如果虛擬運行後，蛇頭蛇尾間有通路，則選最短路運行(1步)
return choose_shortest_safe_move(snake, board)
safe_move = follow_tail() # 否則虛擬地follow_tail 1步，如果可以做到，返回 true
return safe_move
curses.initscr()
win = curses.newwin(HEIGHT, WIDTH, 0, 0)
win.keypad(1)
curses.noecho()
curses.curs_set(0)
win.border(0)
win.nodelay(1)
win.addch(food//WIDTH, food%WIDTH, '@')
while key != 27:
win.border(0)
win.addstr(0, 2, 'S:' + str(score) + ' ')
win.timeout(10)
# 接收鍵盤輸入，同時也使顯示流暢
event = win.getch()
key = key if event == -1 else event
# 重置矩陣
board_reset(snake, snake_size, board)
# 如果蛇可以吃到食物，board_refresh返回true
# 並且board中除了蛇身(=SNAKE)，其它的元素值表示從該點運動到食物的最短路徑長
if board_refresh(food, snake, board):
best_move = find_safe_way() # find_safe_way 的唯一調用處
else:
best_move = follow_tail()
if best_move == ERR:
best_move = any_possible_move()
# 上面一次思考，只得出一個方向，運行一步
if best_move != ERR: make_move(best_move)
else: break
curses.endwin()
print("\nScore - " + str(score))
Raw
snakey.py
# 先將無法在 Brython 環境中執行的程式碼轉為 comment
#import curses
#from curses import KEY_RIGHT, KEY_LEFT, KEY_UP, KEY_DOWN
from random import randint
# 貪食蛇運動的場地長寬
HEIGHT = 10
WIDTH = 20
# FIELD_SIZE 為場地長乘以寬表示格子 (CELL) 總數
FIELD_SIZE = HEIGHT * WIDTH
# 貪食蛇頭總是位於snake數列的第一個元素
HEAD = 0
# 用來代表不同意義的數字，由於矩陣上每個格子會處理成到達食物的路徑長度，
# 因此這三個變數間需要有足夠大的間隔(>HEIGHT*WIDTH)
# 以整數 0 代表 FOOD, 意即若 board 數列中某一元素
# 將隨機取得座標後將該數列索引值設為 0 就表示該格子為 FOOD
# UNDEFINED 值之所以必須大於 HEIGHT*WIDTH, 因為該值將在 BFS 後
# 表示蛇頭距離 FOOD 的路徑步數, 而最大距離步數將會是 HEIGHT*WIDTH
# SNAKE 以整數代表, 由於必須有別於 UNDEFINED 與 FOOD 的值, 因此選擇
# 以 2 * UNDEFINED 這個數字代表該格子被 snake 身體佔住
FOOD = 0
UNDEFINED = (HEIGHT + 1) * (WIDTH + 1)
SNAKE = 2 * UNDEFINED
# 由於 snake 是一維數列，所以對應元素直接加上以下數值就表示向四個方向移動
# 應該是說, 原本該以二維座標表示 board 中各格子的座標, 但在此選擇以一維
# 數列的資料結構來代表二維座標, (1, 1) 可表示為 1*WIDTH+1,
# (x, y) 則表示為 x*WIDTH+y
# 因此往上或往下的移動, 就一維數列值而言, 必須減或加上 WIDTH
LEFT = -1
RIGHT = 1
UP = -WIDTH
DOWN = WIDTH
# 錯誤碼
ERR = -1111
# 用一維數列來表示二維的座標, 使用此資料結構的原因是:
# 貪食蛇每行進一步, 只需要配合蛇頭移動位置新增一個方格座標,
# 且更改蛇尾對應值 (即從原先的蛇身因行進移動一步而變更設定)
# 且讓 snake[HEAD] = x*WIDTH+y, 假設蛇長 snake_size=n
# 則蛇尾 snake[HEAD+n-1] 假設位於 xn*WIDTH+yn
# board[x*WIDTH+y]=SNAKE=2 * UNDEFINED
# board[xn*WIDTH+yn] 表示為蛇尾, 蛇頭走一步後, 蛇尾從 2 * UNDEFINED
# 轉為空白可在搜尋流程中加上距離食物的總步數
# board 表示蛇運動的矩形場地
# 初始化蛇頭在(1,1)的地方，第0行，HEIGHT行，第0列，WIDTH列為圍牆，不可用
# 初始蛇長度為1
# board 與 snake 均為總元素為格點數大小的一維數列
board = [0] * FIELD_SIZE
#snake = [0] * (FIELD_SIZE+1)
# 原程式加 1
snake = [0] * (FIELD_SIZE)
# 座標 (1, 1) 在一維數列中, 表示為 1*WIDTH+1
snake[HEAD] = 1*WIDTH+1
snake_size = 1
# 與上面變量對應的臨時變量，蛇試探性地移動時使用
tmpboard = [0] * FIELD_SIZE
#tmpsnake = [0] * (FIELD_SIZE+1)
# 原程式加 1
tmpsnake = [0] * (FIELD_SIZE)
tmpsnake[HEAD] = 1*WIDTH+1
tmpsnake_size = 1
# food:食物位置(0~FIELD_SIZE-1),初始在(3, 3)
# best_move: 運動方向
food = 3 * WIDTH + 3
best_move = ERR
# 運動方向數組
mov = [LEFT, RIGHT, UP, DOWN]
# 接收到的鍵和分數
#key = KEY_RIGHT
# 初始蛇為一節
score = 1 #分數也表示蛇長
# 檢查一個 cell 有沒有被蛇身覆蓋，沒有覆蓋則為 free，返回 true
def is_cell_free(idx, psize, psnake):
return not (idx in psnake[:psize])
# 檢查某個位置idx是否可向move方向運動
def is_move_possible(idx, move):
flag = False
if move == LEFT:
flag = True if idx%WIDTH > 1 else False
elif move == RIGHT:
flag = True if idx%WIDTH < (WIDTH-2) else False
elif move == UP:
flag = True if idx > (2*WIDTH-1) else False # 即idx/WIDTH > 1
elif move == DOWN:
flag = True if idx < (FIELD_SIZE-2*WIDTH) else False # 即idx//WIDTH < HEIGHT-2
return flag
# 重置 board
# board_refresh 後，UNDEFINED 值都變為了到達食物的路徑長度
# 如需要還原，則要重置它
def board_reset(psnake, psize, pboard):
# 查驗所有格點內容
for i in range(FIELD_SIZE):
if i == food:
pboard[i] = FOOD
elif is_cell_free(i, psize, psnake): # 該位置為空
pboard[i] = UNDEFINED
else: # 該位置為蛇身
pboard[i] = SNAKE
# 廣度優先搜索遍歷整個 board，
# 計算出 board 中每個非 SNAKE 元素到達食物的路徑長度
def board_refresh(pfood, psnake, pboard):
queue = []
queue.append(pfood)
inqueue = [0] * FIELD_SIZE
found = False
# while 循環結束後，除了蛇的身體，
# 其它每個方格中的數字代碼從它到食物的路徑長度
while len(queue)!=0:
idx = queue.pop(0)
if inqueue[idx] == 1: continue
inqueue[idx] = 1
for i in range(4):
if is_move_possible(idx, mov[i]):
if idx + mov[i] == psnake[HEAD]:
found = True
if pboard[idx+mov[i]] < SNAKE: # 如果該點不是蛇的身體
if pboard[idx+mov[i]] > pboard[idx]+1:
pboard[idx+mov[i]] = pboard[idx] + 1
if inqueue[idx+mov[i]] == 0:
queue.append(idx+mov[i])
return found
# 從蛇頭開始，根據 board 中元素值，
# 從蛇頭周圍 4 個領域點中選擇最短路徑
def choose_shortest_safe_move(psnake, pboard):
best_move = ERR
min = SNAKE
for i in range(4):
if is_move_possible(psnake[HEAD], mov[i]) and pboard[psnake[HEAD]+mov[i]]<min:
min = pboard[psnake[HEAD]+mov[i]]
best_move = mov[i]
return best_move
# 從蛇頭開始，根據board中元素值，
# 從蛇頭周圍 4 個領域點中選擇最遠路徑
def choose_longest_safe_move(psnake, pboard):
best_move = ERR
max = -1
for i in range(4):
if is_move_possible(psnake[HEAD], mov[i]) and pboard[psnake[HEAD]+mov[i]]<UNDEFINED and pboard[psnake[HEAD]+mov[i]]>max:
max = pboard[psnake[HEAD]+mov[i]]
best_move = mov[i]
return best_move
# 檢查是否可以追著蛇尾運動, 即蛇頭和蛇尾間是有路徑的
# 為的是避免蛇頭陷入死路
# 虛擬操作, 在 tmpboard,tmpsnake 中進行
def is_tail_inside():
global tmpboard, tmpsnake, food, tmpsnake_size
tmpboard[tmpsnake[tmpsnake_size-1]] = 0 # 虛擬地將蛇尾變為食物(因為是虛擬的，所以在tmpsnake,tmpboard中進行)
tmpboard[food] = SNAKE # 放置食物的地方，看成蛇身
result = board_refresh(tmpsnake[tmpsnake_size-1], tmpsnake, tmpboard) # 求得每個位置到蛇尾的路徑長度
for i in range(4): # 如果蛇頭和蛇尾緊挨著，則返回 False。即不能 follow_tail，追著蛇尾運動了
if is_move_possible(tmpsnake[HEAD], mov[i]) and tmpsnake[HEAD]+mov[i]==tmpsnake[tmpsnake_size-1] and tmpsnake_size>3:
result = False
return result
# 讓蛇頭朝著蛇尾運行一步
# 不管蛇身阻擋，朝蛇尾方向運行
def follow_tail():
global tmpboard, tmpsnake, food, tmpsnake_size
tmpsnake_size = snake_size
tmpsnake = snake[:]
board_reset(tmpsnake, tmpsnake_size, tmpboard) # 重置虛擬board
tmpboard[tmpsnake[tmpsnake_size-1]] = FOOD # 讓蛇尾成為食物
tmpboard[food] = SNAKE # 讓食物的地方變成蛇身
board_refresh(tmpsnake[tmpsnake_size-1], tmpsnake, tmpboard) # 求得各個位置到達蛇尾的路徑長度
tmpboard[tmpsnake[tmpsnake_size-1]] = SNAKE # 還原蛇尾
return choose_longest_safe_move(tmpsnake, tmpboard) # 返回運行方向(讓蛇頭運動 1 步)
# 在各種方案都不行時，隨便找一個可行的方向來走(1 步),
def any_possible_move():
global food , snake, snake_size, board
best_move = ERR
board_reset(snake, snake_size, board)
board_refresh(food, snake, board)
min = SNAKE
for i in range(4):
if is_move_possible(snake[HEAD], mov[i]) and board[snake[HEAD]+mov[i]]<min:
min = board[snake[HEAD]+mov[i]]
best_move = mov[i]
return best_move
def shift_array(arr, size):
for i in range(size, 0, -1):
arr[i] = arr[i-1]
def new_food():
global food, snake_size
cell_free = False
while not cell_free:
w = randint(1, WIDTH-2)
h = randint(1, HEIGHT-2)
# food coordinate
food = h * WIDTH + w
cell_free = is_cell_free(food, snake_size, snake)
win.addch(food//WIDTH, food%WIDTH, '@')
# 真正的蛇在這個函數中, 朝 pbest_move 走 1 步
def make_move(pbest_move):
global key, snake, board, snake_size, score
shift_array(snake, snake_size)
snake[HEAD] += pbest_move
# 按 esc 退出，getch 同時保證繪圖的流暢性, 沒有它只會看到最終結果
#win.timeout(10)
#event = win.getch()
#key = key if event == -1 else event
#if key == 27: return
p = snake[HEAD]
#win.addch(p//WIDTH, p%WIDTH, '*')
# 如果新加入的蛇頭就是食物的位置
# 蛇長加 1，產生新的食物，重置 board (因為原來那些路徑長度已經用不上了)
# snake[HEAD] is the coordinate of the snake head
# food is the coordinate of the food
if snake[HEAD] == food:
# mark on the board where the snake head is
board[snake[HEAD]] = SNAKE # 新的蛇頭
snake_size += 1
score += 1
if snake_size < FIELD_SIZE: new_food()
else: # 如果新加入的蛇頭不是食物的位置
board[snake[HEAD]] = SNAKE # 新的蛇頭
board[snake[snake_size]] = UNDEFINED # 蛇尾變為空格
#win.addch(snake[snake_size]//WIDTH, snake[snake_size]%WIDTH, ' ')
# 虛擬地運行一次，然後在調用處檢查這次運行可否可行
# 可行才真實運行。
# 虛擬運行吃到食物後，得到虛擬下蛇在 board 的位置
def virtual_shortest_move():
global snake, board, snake_size, tmpsnake, tmpboard, tmpsnake_size, food
tmpsnake_size = snake_size
tmpsnake = snake[:] # 如果直接tmpsnake=snake，則兩者指向同一處內存
tmpboard = board[:] # board中已經是各位置到達食物的路徑長度了，不用再計算
board_reset(tmpsnake, tmpsnake_size, tmpboard)
food_eated = False
while not food_eated:
board_refresh(food, tmpsnake, tmpboard)
move = choose_shortest_safe_move(tmpsnake, tmpboard)
shift_array(tmpsnake, tmpsnake_size)
tmpsnake[HEAD] += move # 在蛇頭前加入一個新的位置
# 如果新加入的蛇頭的位置正好是食物的位置
# 則長度加1，重置board，食物那個位置變為蛇的一部分(SNAKE)
if tmpsnake[HEAD] == food:
tmpsnake_size += 1
board_reset(tmpsnake, tmpsnake_size, tmpboard) # 虛擬運行後，蛇在board的位置(label101010)
tmpboard[food] = SNAKE
food_eated = True
else: # 如果蛇頭不是食物的位置，則新加入的位置為蛇頭，最後一個變為空格
tmpboard[tmpsnake[HEAD]] = SNAKE
tmpboard[tmpsnake[tmpsnake_size]] = UNDEFINED
# 如果蛇與食物間有路徑，則調用本函數
def find_safe_way():
global snake, board
safe_move = ERR
# 虛擬地運行一次, 因為已經確保蛇與食物間有路徑，所以執行有效
# 運行後得到虛擬下蛇在board中的位置, 即 tmpboard，見 label101010
virtual_shortest_move() # 該函數唯一調用處
if is_tail_inside(): # 如果虛擬運行後，蛇頭蛇尾間有通路，則選最短路運行(1步)
return choose_shortest_safe_move(snake, board)
safe_move = follow_tail() # 否則虛擬地follow_tail 1步，如果可以做到，返回 true
return safe_move
#curses.initscr()
#win = curses.newwin(HEIGHT, WIDTH, 0, 0)
#win.keypad(1)
#curses.noecho()
#curses.curs_set(0)
#win.border(0)
#win.nodelay(1)
#win.addch(food//WIDTH, food%WIDTH, '@')
'''
while key != 27:
win.border(0)
win.addstr(0, 2, 'S:' + str(score) + ' ')
win.timeout(10)
# 接收鍵盤輸入，同時也使顯示流暢
event = win.getch()
key = key if event == -1 else event
# 重置矩陣
board_reset(snake, snake_size, board)
# 如果蛇可以吃到食物，board_refresh返回true
# 並且board中除了蛇身(=SNAKE)，其它的元素值表示從該點運動到食物的最短路徑長
if board_refresh(food, snake, board):
best_move = find_safe_way() # find_safe_way 的唯一調用處
else:
best_move = follow_tail()
if best_move == ERR:
best_move = any_possible_move()
# 上面一次思考，只得出一個方向，運行一步
if best_move != ERR: make_move(best_move)
else: break
curses.endwin()
print("\nScore - " + str(score))
'''
print("Start coding!")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment