Thuật toán giải mê cung: Từ DFS/BFS cổ điển đến demo trực tiếp trong trình duyệt

Bài viết này sẽ:

• Mô hình hóa mê cung thành grid (lưới ô).
• Giải mê cung bằng DFS và BFS.
• Có demo chạy trực tiếp: random mê cung, chọn thuật toán, chỉnh tốc độ, step/pause.

1. Bản chất bài toán “giải mê cung” là gì?

Ta có:

• Một bản đồ dạng lưới (grid).
• Mỗi ô là:
  • Tường (wall): không đi qua được
  • Đường (empty): đi được
  • Start: điểm xuất phát
  • Goal: điểm đích

Nếu nhìn dưới góc độ thuật toán:

• Mỗi ô “đi được” là một node.
• Hai node nối với nhau nếu kề nhau theo 4 hướng (trên/dưới/trái/phải).
• “Giải mê cung” = tìm một đường đi từ Start đến Goal.

2. DFS và BFS khác nhau thế nào?

• DFS (Depth-First Search): đi sâu một nhánh đến cùng rồi mới quay lại. Thường cho cảm giác “liều”, dễ vòng vèo, nhưng code gọn và nhanh để demo.
• BFS (Breadth-First Search): loang ra từng lớp như nước. Nếu mọi bước đi có chi phí như nhau, BFS đảm bảo tìm được đường đi ngắn nhất.

Điểm hay nhất: hai thằng này “cãi nhau” bằng hình ảnh rất rõ, chạy demo là thấy ngay.

3. Demo: Maze Solver (DFS/BFS)

4. Kết luận

DFS và BFS đều giải được mê cung, nhưng:

• DFS thường tìm được đường “điên” (nhanh tìm ra một đường, không chắc ngắn).
• BFS loang theo lớp và đảm bảo đường đi ngắn nhất khi mọi bước có chi phí như nhau.

Bài tiếp theo chúng ta sẽ nâng cấp lên A* (A-star): vẫn là “tìm đường”, nhưng biết dùng heuristic để đi thông minh hơn rất nhiều.