Xác định bài toán và phạm vi của BFS
Giả sử robot di chuyển giữa các ô kề nhau trong mê cung dạng lưới. Mỗi ô được xác định bằng cặp tọa độ (hàng, cột); robot có một ô xuất phát S và cần đến ô đích G. Nếu mọi lần chuyển sang ô kề đều có cùng chi phí, thuật toán tìm kiếm theo chiều rộng BFS sẽ tìm được đường đi có ít bước chuyển ô nhất.
Trước khi lập trình, hãy thống nhất robot được đi theo những hướng nào. Ví dụ, với bốn hướng lên, xuống, trái, phải, robot không được đi chéo qua góc tường. Đường có ít bước chuyển ô nhất chưa chắc là đường ít lần rẽ nhất hoặc mất ít thời gian nhất.
Biểu diễn bản đồ mê cung
Lưu mê cung thành một ma trận: ô trống có thể đi qua, ô tường không thể đi qua, cùng tọa độ của S và G. Chẳng hạn, ba hàng của một bản đồ bốn cột là «S . # .», «# . # .», «. . . G», trong đó «.» là ô trống và «#» là tường.
Hãy kiểm tra rằng mỗi hàng có cùng số cột, S và G nằm trong phạm vi bản đồ, và trạng thái của từng ô được ghi đúng. Với bản đồ chưa được quan sát đầy đủ, nên đánh dấu riêng các ô chưa biết thay vì mặc nhiên coi chúng là đường trống.
Duyệt mê cung bằng hàng đợi BFS
Tạo một hàng đợi, một tập ô đã thăm và một bảng lưu ô liền trước. Đưa S vào hàng đợi và đánh dấu S đã thăm ngay lúc đó. Sau đó, lặp lại: lấy ô ở đầu hàng đợi; nếu đó là G thì dừng. Nếu không, xét lần lượt các ô kề theo bốn hướng.
Với mỗi ô kề, chỉ xử lý nếu ô đó nằm trong bản đồ, có thể đi qua và chưa được thăm. Đánh dấu ô kề đã thăm ngay khi đưa vào hàng đợi, ghi ô hiện tại là ô liền trước của nó, rồi thêm ô kề vào cuối hàng đợi. Việc đánh dấu lúc thêm vào hàng đợi giúp tránh đưa cùng một ô vào nhiều lần.
Nếu hàng đợi rỗng mà chưa gặp G, không có đường từ S đến G trên bản đồ đang xét. Nếu S trùng G, đường đi chỉ gồm ô xuất phát và robot không cần chuyển ô.
Truy vết để lấy đường đi
Khi tìm thấy G, đi ngược qua bảng ô liền trước: bắt đầu từ G, lần lượt lấy ô liền trước cho đến S, rồi đảo ngược danh sách. Kết quả là chuỗi ô robot cần đi qua theo thứ tự từ S đến G.
Với bản đồ ví dụ, một đường đi là (0,0) → (0,1) → (1,1) → (2,1) → (2,2) → (2,3). Đường này gồm năm lần chuyển ô. Nếu có nhiều đường ngắn nhất, thứ tự xét các hướng kề có thể quyết định BFS trả về đường nào.
Chuyển đường đi thành lệnh điều khiển robot
Đường đi gồm tọa độ chưa phải là lệnh cho động cơ. Hãy lưu thêm hướng robot đang quay mặt. Với mỗi cặp ô liên tiếp, xác định hướng cần đi, cho robot xoay đến hướng đó nếu cần, rồi ra lệnh tiến một ô.
Chỉ cập nhật tọa độ hiện tại sau khi robot xác nhận đã hoàn thành bước di chuyển bằng cơ chế đo hoặc cảm biến phù hợp. Nếu phát hiện vật cản tại ô dự định đi tới, hãy dừng trước vật cản, cập nhật bản đồ và chạy lại BFS từ vị trí hiện tại. Không nên tiếp tục thực hiện các lệnh còn lại của đường cũ khi bản đồ đã thay đổi.
Kiểm tra chương trình và nhận biết giới hạn
Trước khi nối với robot, hãy thử chương trình trên các bản đồ nhỏ: có đường đi, không có đường đi, S nằm cạnh G và S trùng G. Với mỗi kết quả, kiểm tra rằng hai ô liên tiếp luôn kề nhau, không ô nào là tường, và đường bắt đầu ở S, kết thúc ở G.
BFS phù hợp khi các ô có thể đi qua đã được xác định và mỗi bước chuyển ô được tính như nhau. Nếu mê cung còn nhiều ô chưa biết, robot cần một cách khám phá và cập nhật bản đồ; BFS trên phần bản đồ đã biết không thể tự bảo đảm tìm được lối thoát. Nếu muốn tối ưu thời gian, năng lượng hoặc số lần rẽ, cần mô hình hóa các chi phí đó và chọn cách tìm đường phù hợp.
