Một Phương Pháp Tiền Xử Lý Tìm Đường Trên Bản Đồ
Trong bài viết trước, chúng ta đã thảo luận về việc tối ưu hóa thuật toán tìm đường trên máy chủ. Cuối bài có đề cập đến một phương pháp đặc biệt hiệu quả cho nhu cầu cụ thể: đó là tiền xử lý toàn bộ các tuyến đường và lưu trữ kết quả vào tệp tin. Nhờ đó, thời gian truy vấn tại thời điểm chạy chỉ cần O(1) để tìm bất kỳ đường đi nào.
Xét bản đồ dạng lưới với bán kính N, nếu chọn hai điểm bất kỳ làm điểm bắt đầu và kết thúc, số lượng đường đi tiềm năng sẽ ở cấp độ N^4. Rõ ràng là không thể lưu trữ toàn bộ các cặp điểm này theo kiểu “từ điểm A đến điểm B thì đi thế nào”.
Tuy nhiên, trong thực tế, trừ khi bản đồ là một mê cung phức tạp, phần lớn các đường đi đều có đoạn trùng lặp. Điều này rất giống với cách con người di chuyển hàng ngày. Ví dụ, khi bạn đi từ phòng ngủ đến chỗ làm việc trong văn phòng, hành trình sẽ gần như giống hệt khi bạn xuất phát từ phòng khách - chỉ khác đoạn đầu tiên ra khỏi nhà.
Trên máy chủ, bài toán tìm đường thường chỉ cần giải quyết việc di chuyển trong phạm vi nhỏ của NPC để tránh chướng ngại vật (như từ phòng ngủ ra cửa nhà). Còn các tuyến đường dài (từ nhà đến công ty) nên được xử lý ở một hệ thống cấp cao hơn.
Dù là dùng thuật toán A* dựa trên lưới hay thuật toán Dijkstra dựa trên đồ thị, việc tính toán đường đi đều rất đơn giản. Bài viết này không bàn đến thuật toán mà tập trung vào vấn đề lưu trữ kết quả.
Để giải quyết bài toán số lượng cặp điểm quá lớn (N^2 khả năng), chúng ta có thể chia bản đồ thành các khu vực nhỏ. Nếu mỗi khu vực là một đa giác lồi không có chướng ngại vật bên trong, thì khi cả điểm xuất phát và đích cùng nằm trong một khu vực, đường thẳng nối hai điểm chính là đường đi tối ưu.
Về cách chia khu vực, nếu chướng ngại vật chủ yếu song song với trục tọa độ, có thể dùng phương pháp chia đôi theo đường viền chướng ngại vật, tạo thành cấu trúc cây KD. Với chướng ngại vật không song song trục, có thể dùng cây BSP để chia không gian thành các tập hợp lồi.
Giả sử bản đồ đã được chia thành nhiều đa giác lồi hợp lý (tránh các khu vực quá hẹp và dài), chúng ta có thể xây dựng tuyến đường gần tối ưu theo phương pháp sau:
Khi điểm xuất phát và đích nằm ở khu vực khác nhau, trước tiên tìm đường ngắn nhất từ điểm xuất phát đến biên của khu vực đích, sau đó đi thẳng từ điểm biên đó đến đích. Nếu chia khu vực hợp lý, tuyến đường này gần như tối ưu - dù không phải là ngắn nhất tuyệt đối thì cũng cho kết quả rất tốt.
Để tìm đường ngắn nhất từ một điểm đến một khu vực (biên của khu vực), chúng ta có thể xây dựng “trường khoảng cách” như sau:
- Gán giá trị 0 cho tất cả ô lưới thuộc khu vực đích
- Lan truyền giá trị tăng dần ra các ô lân cận (mỗi bước tăng 1)
- Các ô không có giá trị sẽ là khu vực không thể tiếp cận
Trường này hoạt động như một bản đồ độ cao, nơi mỗi ô chứa khoảng cách ngắn nhất đến khu vực đích. Khi di chuyển, chỉ cần chọn ô lân cận có giá trị nhỏ nhất là sẽ tự động đi theo đường tối ưu.
Mỗi khu vực có thể lưu trữ thông tin hướng đi đến các khu vực lân cận trong phạm vi nhất định (không nhất thiết phải kề nhau về mặt không gian). Với lưới 4 hướng, chỉ cần 4 bit để biểu diễn 8 hướng di chuyển và trạng thái không thể đi (tổng cộng 9 trạng thái).
Cấu trúc dữ liệu tối ưu sẽ bao gồm:
- Bảng ghi khu vực của từng ô lưới
- Danh sách các khu vực lân cận cho mỗi khu vực
- Hướng đi tối ưu từ mỗi ô đến các khu vực lân cận
Tại thời điểm chạy, chỉ cần xác định khu vực của điểm đích, sau đó tra cứu hướng đi từ ô xuất phát. Nếu điểm đích cùng khu vực thì đi thẳng. Mỗi khi di chuyển đến ô mới, lại tra cứu hướng đi mới - toàn bộ quá trình chỉ cần O(1) và có thể dùng chung cho mọi đối tượng trên máy chủ. Phương pháp này đặc biệt phù hợp với môi trường có chướng ngại vật tĩnh nhưng điểm đích liên tục thay đổi (như khi truy đuổi mục tiêu di động).