Trong bài hướng dẫn trước, trituenhantao.io đã hướng dẫn các bạn lập trình game rắn với pygame. Lần này, ta hãy cùng nhau tạo ra một AI đơn giản với trò chơi này. Trước khi đọc tiếp bài này, xin lưu ý đây là bài viết tương đối nâng cao dành cho các bạn đã có nền tảng lập trình và cấu trúc dữ liệu và giải thuật. Ngoài ra, bạn nên dành thời gian hoàn thành bài Hướng dẫn lập trình game Rắn với thư viện pygame trước khi đọc tiếp. Nó bao gồm những hướng dẫn về cách cấu hình, cài đặt môi trường cũng như những giải thích cơ bản để chúng ta có thể lập trình game rắn với python.
Chiến lược chung
BFS là thuật toán tìm kiếm theo chiều rộng nổi tiếng trong lý thuyết đồ thị. Thuật toán này sẽ duyệt từ nút gốc và loang dần đến các nút có độ sâu tăng dần. Nó là một thuật toán đơn giản giúp chúng ta tìm được đường đi ngắn nhất giữa hai ô trong ma trận. AI của chúng ta sẽ được xây dựng dựa trên thuật toán này.
Với BFS, ta có thể dễ dàng tìm được đường đi ngắn nhất giữa đầu con rắn và thức ăn. Khi mới bắt đầu trò chơi, đó là tất cả những gì ta cần, nhưng khi con rắn ngày một dài ra, nó cần phải có năng lực điều khiển thân của mình để tránh trường hợp “cái thân làm tội cái đầu”. Chúng ta có thể trang bị năng lực này cho con rắn thông qua một nhận xét quan trọng: Miễn là tồn tại đường đi từ đầu rắn đến đuôi rắn, về cơ bản con rắn có thể đi tiếp.
Khởi tạo các mảng lưu trạng thái
Đầu tiên, chúng ta viết hàm khởi tạo các mảng phục vụ cho việc duyệt BFS và tìm đường đi phù hợp cho con rắn. Trong chương trình này, chúng ta sử dụng hai tập hợp mảng đại diện cho đường đi thực sự của rắn và đường đi thử nghiệm của nó.
HEIGHT = 10 # Chiều cao cửa sổ
WIDTH = 15 # Chiều rộng cửa sổ
FIELD_SIZE = HEIGHT * WIDTH # Kích thước ma trận trò chơi
HEAD = 0 # Chỉ số đầu rắn
SNAKE_BLOCK = 20 # Kích thước thân rắn
SNAKE_SPEED = 200 # Tốc độ
ERR = -2333 # Hằng số đại diện cho lỗi
FONT_STYLE = pygame.font.SysFont("bahnschrift", 12)
SCORE_FONT = pygame.font.SysFont("comicsansms", 20)
def initial_game():
global board, snake, snake_size, tmpboard, tmpsnake, tmpsnake_size, food,best_move
board = [0] * FIELD_SIZE #[0,0,0,……]
snake = [0] * (FIELD_SIZE+1)
snake[HEAD] = 1*WIDTH+1
snake_size = 1
tmpboard = [0] * FIELD_SIZE
tmpsnake = [0] * (FIELD_SIZE+1)
tmpsnake[HEAD] = 1*WIDTH+1
tmpsnake_size = 1
food = 4 * WIDTH + 7
best_move = ERRSau khi khai báo các mảng lưu giá trị, chúng ta cần thiết lập giá trị ban đầu cho chúng. Thức ăn sẽ được gán giá trị nhỏ nhất (0), các ô chưa được duyệt sẽ được gán trạng thái lớn hơn tổng số ô tồn tại trong ma trận (UNDEFINED), và các ô thuộc thân rắn sẽ nhận gia trị bằng 2 lần các ô chưa được duyệt (2*UNDEFINED). Điều này sẽ giúp cho chương trình phân biệt được đâu là ô chứa đường đi (các ô có trạng thái nhỏ hơn UNDEFINED)
FOOD = 0 # Trạng thái của thức ăn
UNDEFINED = (HEIGHT + 1) * (WIDTH + 1) # Trạng thái của các ô chưa được duyệt
SNAKE = 2 * UNDEFINED # Trạng thái của các ô thuộc thân rắn
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] = SNAKECài đặt BFS
Ta viết hàm board_BFS để triển khai thuật toán BFS trên ma trận trò chơi và lưu lại trạng thái duyệt của từng ô. Đây là thông tin quan trọng để con rắn có thể chọn được đường đi phù hợp. Ô chứa thức ăn sẽ là nút gốc, trong trường hợp tồn tại đường đi từ nút gốc đến ô ứng với đầu rắn, mỗi ô được gán giá trị là khoảng cách ngắn nhất tới nút gốc.
LEFT = -1 # Trái
RIGHT = 1 # Phải
UP = -WIDTH # Trên
DOWN = WIDTH # Dưới
MOV = [LEFT, RIGHT, UP, DOWN] # Các hướng di chuyển của rắn
def board_BFS(pfood, psnake, pboard):
queue = []
queue.append(pfood)
inqueue = [0] * FIELD_SIZE
found = False
while len(queue)!=0:
idx = int(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 foundDuyệt đường đi thử nghiệm và kiểm tra đuôi
Ta viết hàm virtual_shortest_move để đưa con rắn tới vị trí thức ăn mà BFS tìm ra. Tại vị trí đó, ta kiểm tra xem có tồn tại đường đi từ đầu con rắn tới đuôi của nó hay không. Đây là hàm quan trọng để thực hiện nhận xét mà ta có được ở đầu bài viết.
def virtual_shortest_move():
global snake, board, snake_size, tmpsnake, tmpboard, tmpsnake_size, food
tmpsnake_size = snake_size
tmpsnake = snake[:]
tmpboard = board[:]
board_reset(tmpsnake, tmpsnake_size, tmpboard)
food_eated = False
while not food_eated:
board_BFS(food, tmpsnake, tmpboard)
move = choose_shortest_safe_move(tmpsnake, tmpboard)
shift_array(tmpsnake, tmpsnake_size)
tmpsnake[HEAD] += move
if tmpsnake[HEAD] == food:
tmpsnake_size += 1
board_reset(tmpsnake, tmpsnake_size, tmpboard)
tmpboard[food] = SNAKE
food_eated = True
else:
tmpboard[tmpsnake[HEAD]] = SNAKE
tmpboard[tmpsnake[tmpsnake_size]] = UNDEFINEDVà hàm để kiểm tra đuôi:
def is_tail_reachable():
global tmpboard, tmpsnake, food, tmpsnake_size
tmpboard[tmpsnake[tmpsnake_size-1]] = FOOD
tmpboard[food] = SNAKE
result = board_BFS(tmpsnake[tmpsnake_size-1], tmpsnake, tmpboard)
for i in range(4):
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Để con rắn có thể đuổi theo đuôi của nó, ta sử dụng thủ thuật hoàn đổi trạng thái của ô chứa thức ăn với trạng thái của ô chứa đuôi rắn và duyệt BFS. Sau khi hoán đổi, BFS sẽ tìm đường đi ngắn nhất đến vị trí của đuôi mà không duyệt qua ô chứa thức ăn.
def follow_tail():
global tmpboard, tmpsnake, food, tmpsnake_size
tmpsnake_size = snake_size
tmpsnake = snake[:]
board_reset(tmpsnake, tmpsnake_size, tmpboard)
tmpboard[tmpsnake[tmpsnake_size-1]] = FOOD
tmpboard[food] = SNAKE
board_BFS(tmpsnake[tmpsnake_size-1], tmpsnake, tmpboard)
tmpboard[tmpsnake[tmpsnake_size-1]] = SNAKE
return choose_longest_safe_move(tmpsnake, tmpboard) Các hàm tìm đường đi ngắn nhất và dài nhất
Dựa trên kết quả của BFS, ta có thể tìm được đường đi ngắn nhất và dài nhất. Khi con rắn đuổi theo thức ăn, nó cần đường đi ngắn nhất, khi nó đuổi theo cái đuôi của chính nó, nó nên chọn đường đi dài nhất (trong số các đường đi ngắn nhất) để có thêm không gian để có thể ở lại game lâu hơn.
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
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_moveHoàn thiện code
Bước tiếp theo, chúng ta cần hoàn thiện các hàm hiển thị và hỗ trợ để chương trình có thể hoạt động được. Với phiên bản trong bài hướng dẫn trước, ở mỗi vòng lặp của gameLoop chúng ta cho con rắn tiến theo hướng hiện tại và đổi hướng mỗi khi phím được ấn. Trong phiên bản này, tại mỗi vòng lặp, chương trình phải tự tìm ra ô tối ưu để đi tiếp. Ý tưởng chính như sau:
if board_BFS(food, snake, board): # nếu tồn tại đường đi
best_move = find_safe_way() # tìm đường đi an toàn tốt nhất
else:
best_move = follow_tail() # nếu không, thử đuổi theo đuôi
if best_move == ERR: # nếu không thể đuổi theo đuôi
best_move = any_possible_move() # đi ngẫu nhiên một ô hợp lệ
if best_move != ERR:
make_move(best_move)
else:
game_close = TrueDựa trên những ý tưởng của bài hướng dẫn này, bạn có thể tự hoàn thiện code game của chính mình. Ngoài ra bạn có thể tải file hoàn chỉnh snake_bfs.py để đối chiếu và so sánh. Để trang bị thêm kiến thức, chúng tôi xin gợi ý bạn đăng ký nhận tài liệu python miễn phí tại đây.
Nếu bạn thấy bài viết hữu ích, hãy chia sẻ cho mọi người. Chúc các bạn thành công!